Solving 94-bit ECDLP with 70 Computers in Parallel
Solving 94-bit ECDLP with 70 Computers in Parallel
复制标题
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Shunsuke Miyoshi;Y. Nogami;Takuya Kusaka;N. Yamai
中科院分区：
文献类型：
--
作者：
Shunsuke Miyoshi;Y. Nogami;Takuya Kusaka;N. Yamai
椭圆曲线离散对数问题（ECDLP）是基于配对密码学安全性的基础问题之一。本文采用Pollard的rho方法来评估基于Barreto-Naehrig（BN）曲线的ECDLP的安全性。提出了一些技术，使ρ方法的效率。特别是BN曲线上的群结构、特征点法和蒙哥马利技巧是众所周知的技术。本文应用这些技术，并显示其优化。根据实验结果，其中一个大规模的并行系统与MySQL的应用，94位ECDLP解决了约28小时并行71台计算机。关键词-波拉德法，BN曲线，蒙哥马利乘法。
Elliptic curve discrete logarithm problem(ECDLP) is one of problems on which the security of pairing-based cryptography is based. This paper considers Pollard’s rho method to evaluate the security of ECDLP on Barreto-Naehrig(BN) curve that is an efficient pairing-friendly curve. Some techniques are proposed to make the rho method efficient. Especially, the group structure on BN curve, distinguished point method, and Montgomery trick are well-known techniques. This paper applies these techniques and shows its optimization. According to the experimental results for which a large-scale parallel system with MySQL is applied, 94-bit ECDLP was solved about 28 hours by parallelizing 71 computers. Keywords—Pollard’s rho method, BN curve, Montgomery multiplication.