ECC2-131的并行Pollardrho算法实现分析  

Analysis of Implementation of Parallel Pollard rho Algorithm for ECC2-131

作　　者：关沛冬 罗玉琴 张方国[1,2] 田海博[1,2] GUAN Pei-Dong;LUO Yu-Qin;ZHANG Fang-Guo;TIAN Hai-Bo(School of Computer Science and Engineering,Sun Yat-sen University,Guangzhou 510006,China;Guangdong Key Laboratory of Information Security Technology,Guangzhou 510006,China)

机构地区：[1]中山大学计算机学院,广州510006 [2]广东省信息安全技术重点实验室,广州510006

出　　处：《密码学报》2022年第2期322-340,共19页Journal of Cryptologic Research

基　　金：广东省基础与应用基础研究重大项目(2019B030302008);国家自然科学基金(61972429)。

摘　　要：Pollard rho算法与其分布式版本算法是目前求解有限域上椭圆曲线群的离散对数问题被公认的最优算法.自该算法提出以来,许多密码学家提出了多种分布式Pollard rho算法的改进算法.本文对基于不同迭代函数的三种的分布式Pollard rho算法的效率进行分析,并针对ECC2-131在通用CPU上对算法进行软件程序的实现.本文发现基于r-加游走的算法在理论分析和程序实现上都有着最优的效率,说明基于r-加游走的分布式Pollard rho算法在求解ECDLP上仍占有很大优势.本文给出在计算机工作站和天河二号超级计算机上测量得出的Pollard rho算法的效率,发现在当前求解离散对数问题的算法和计算机的计算能力上求解ECC2-131仍然是困难的,在时间和金钱上的开销不符合实际.本文还找出有限域F2131上运算性能最优的不可约多项式.通过域的同构诱导出椭圆曲线的同构,ECDLP能在同构后得到的椭圆曲线上进行求解.若算法的软件实现使用同构后得到的椭圆曲线,则有限域模运算有11:29%的效率提升,乘法运算有11:23%的效率提升.通过有限域运算效率的提升可以进一步提高求解ECDLP的效率.Pollard rho algorithm and its distributed variants are currently known as the best algorithms for solving the discrete logarithm problem of elliptic curve groups over finite fields.Since the Pollard rho algorithm was proposed,many cryptographers proposed a variety of improved algorithms for the distributed Pollard rho algorithm.This paper analyzes the efficiency of three distributed Pollard rho algorithms which are based on a different iteration function,and implements the algorithm as a software program for ECC2-131 on a general CPU.This paper finds that,the algorithm based on the r-adding walk achieves the optimal efficiency in theoretical analysis and in program implementation,which means that distributed Pollard rho algorithm based on the r-adding walk plays an important role on for solving ECDLP.This paper tested the efficiency of the Pollard rho algorithm on computer workstation and the Tianhe-2 supercomputer,and found that it is still difficult to solve the ECC2-131 based on the current algorithm for solving the discrete logarithm problem and the available computing power,and the cost of time and money is unrealistic.This paper also presents the irreducible polynomial with the best computational performance for the finite field F2131.By inducing the isomorphism of elliptic curve from the isomorphism of finite field,the ECDLP can be solved on the elliptic curve obtained after isomorphism.If the software implementation of the algorithm uses the new elliptic curve,the efficiency of the modular operation can be improved by 11.29%,and the efficiency of multiplication operation can be improved by 11.23%,which makes a further improvement on the efficiency of solving ECDLP.

关 键 词：Pollardrho算法 椭圆曲线 离散对数 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]