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

• 作者: 关沛冬 罗玉琴 张方国 田海博
• 来源期刊: 密码学报
• 学科: 工学
• 关键词: Pollard rho算法 椭圆曲线 离散对数
• 年，卷（期）: 2022,（2）
• 页码范围: 322-340
• 页数: 19页
• 分类号: TP309.7
• 语种: 中文
• DOI: 10.13868/j.cnki.jcr.000522

摘要

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的效率.