F2^m上并行Pollard rho算法的优化实现

并行Pollard rho算法是目前攻击椭圆曲线密码体制(E lliptic Curve Cryptosystem,简称ECC)的最好算法,国内外的研究十分活跃。本文首先介绍了攻击F2m上ECC的并行Pollard rho算法及我们的实现流程,然后给出了核心基本运算(包括求逆、一般乘法、平方、求模等)的优化算法。实验数据表明,根据本文优化算法编制的MPI并行程序在多机上加速比良好,运算速度优于互联网上公开的程序。

ECDLP问题中的点乘优化算法和Pollard-rho算法仿真研究

对多方认证密钥协商协议中求解一般椭圆曲线上ECDLP问题的点乘优化算法和Pollardrho协议攻击算法进行仿真,验证了点乘优化算法可降低运算复杂度,提升了有效性。随阶数的增大,Pollard-rho算法计算量增大。不同阶数的椭圆曲线密钥大小对Pollard-rho算法迭代次数影响具有一定的相似性,于是提出了一个针对协议的不安全密钥舍弃原则。根据Pollard-rho算法复杂度,估算不同密钥长度下的破解时间,验证了椭圆曲线密码体制的安全性,证明了协议的可靠性,给出了协议应采用160 bit长度密钥的依据。

MD5(0,δb,δc,δc)-消息对Pollard's rho搜索算法设计

MD5选择前缀碰撞攻击可应用于伪造CA证书等实际攻击中,构造MD5选择前缀碰撞对是攻击MD5的一个重要研究课题。构造MD5选择前缀碰撞消息对时,需要利用高性能计算设备搜索(0,δb,δc,δc,)-消息对,文章用概率方法描述了生日攻击的原理,阐述了利用生日攻击思想搜索(0,δb,δc,δc,)-消息对的Pollard's rho算法和并行Pollard's rho算法,分析了算法的复杂度,最后给出了一组实验数据。

基于SIMD指令的ECC攻击算法研究

ECC是目前比特安全强度最高的公钥密码体制,对它的攻击需要大量的计算资源.基于SIMD指令和bitslice数据结构设计了GF(2m)上的ECC攻击算法,并对核心模块进行了优化.利用比特交换的方法提出了一个bitslice数据结构和非bitslice数据结构的快速转换算法,计算复杂度为O(nlogn),对算法简单调整后可适用于二元矩阵的快速转置;利用Karatsuba-Ofman算法和Montgomery并行求逆对椭圆曲线底层运算进行了优化,分析了计算复杂度.对ECC挑战中的ECC2-109和ECC2-131进行了测试,在单核Pentium 4 3.0GHz平台上的迭代速度分别为1 330 000次/s和980 000次/s,攻击效率比Chris Monico的公开程序提高了1倍.

基于ECDLP的工作量证明方案设计

椭圆曲线离散对数问题(EDCLP)的求解是现代密码学体系中一个重要的研究方向.目前,求解ECDLP最有效的算法是Pollard rho算法.区块链技术作为一门新兴技术,受到各行各业的广泛关注.本文引入ECDLP作为工作量证明的困难问题计算,使得工作量证明在区块链的能源消耗变得有意义,同时借助区块链的激励机制,让更多的人参与到ECDLP求解计算中去,进而促进在密码学中对困难问题求解的研究.特别地,本文通过Pollard rho算法提出了一个新的思路,有效解决了一个区块中从初始点到满足挑战难度的可区分点的有效验证问题.

Solving the Multi-discrete Logarithm Problems over a Group of Elliptic Curves with Prime Order

In this paper, we discuss the expected number of steps in solving multi-discrete logarithm problems over a group of elliptic curves with prime order by using Pollard＇s rho method and parallel collision search algorithm. We prove that when using these algorithms to compute discrete logarithms, the knowledge gained through computing many logarithms does not make it easier for finding other logarithms. Hence in an elliptic cryptosystem, it is safe for many users to share the same curve, with different private keys.