论文部分内容阅读
椭圆曲线密码学的许多形式有稍微的不同,但所有的形式都依赖于被广泛承认的解决椭圆曲线离散对数问题的困难性上,对应有限域上椭圆曲线的群。研究表明，椭圆曲线密码是目前唯一无法用亚指数算法破解的公钥密码。离散对数公钥加密算法是目前最为热门的公钥加密算法,其安全性要远远高于基于大数分解的RSA算法。通过几代密码学家几十年来的不懈努力,在求解椭圆曲线离散对数问题上取得了不少成绩,诞生了许多经典的求解算法,如Shanks的小步大步算法(BSGS)[1]、Pollard’sρ算法[2]、Pohlig-Hellman算法、Index Calculus算法等,以及针对特殊类型椭圆曲线的MOV算法[3]、SSAS算法等。本文将着重对Pollard’s ρ算法进行分析。Pollard’s ρ算法基于生日悖论,实为BSGS算法的一种变形。具体实施起来即在群元素中寻找匹配或者碰撞,并希望能从这种碰撞中恢复出关于起始点的一些信息。其运算时间与BSGS算法相同,但不需要存储空间。后来的密码学家在此基础上提出了各种对ρ算法的改进和优化的方法。其中韩国密码学家Jung Hee Cheon,Jin Homg和Minkyu Kim[4]提出了对求解有限域上的离散对数的ρ算法进行改进的方法。对G=<9>中的元素仍如原始ρ算法中一样运用迭代函数生成随机序列,并保证它们是指数可追踪的。事先选定某一性质作为对点进行筛选的条件,将满足这一性质的点定义为特征点。Jung Hee Cheon等人结合指标函数s：G→{0,1},其将G中1/r的元素映到0,其余映到1,选取一个小的正整数δ,将满足下式s(gi-δ+1)=…=s(gi-1)=s(gi)=0中的最后一点gi定义为他们所选取的特征点。由于照此方法定义的特征点有聚集出现的趋势,因此对连续的特征点组,只选取一点存储即可。通过计算,可求得连续的特征点组之间的平均距离(即平均迭代次数)为r/(r-1)(rδ-1),也就是平均作r/(r-1)(rδ-1)次迭代运算可以求得一个特征点。特征点定义好后,开始引入标记追踪法进行迭代运算。在迭代开始前,假定我们已有指标函数s：G→S={0,1….,r-1}和一个预计算表Ml,其中M={mi}i∈s。在迭代过程中,不需要如之前一样计算每一次gi+1=gimsi的值,通过引入一个辅助的指标函数s：G×Ml→S,便可很方便的求得gi+1。之后再结合特征点的定义,选取迭代过程中产生的特征点并存储,直至找到碰撞为止。由于相对于迭代计算过程,预计算表Ml的计算时间可以忽略,此方法比原始的ρ算法在求解时间上要快一些。下面我们所作的是,将上述ρ算法的改进方法应用到求解椭圆曲线离散对数问题上。椭圆曲线上离散对数的ρ算法与有限域上的ρ算法类似,但ECDLP比DLP要困难的多。结合前人的思想,我们可以考虑,将椭圆曲线上的离散对数问题转化到有限域上,再运用Jung Hee Cheon等人的改进方法来进行求解。本文所选取的方法是由Menezes、Okamoto和、anstone于1993年提出的MOV算法,定义双线性对Weil对利用双线性对的性质来完成MOV算法的转化。其核心思想便是将ECDLP转化为某个有限域的乘法群上的DLP,实质便是将Fq映到其扩域Fqk。而n|qk-1是利用MOV算法将DLP转化到Fqk上的必要条件。该方法在实际应用时,并不是对所有的椭圆曲线均有效,而是受有限域的扩张次数k的限制。若所取的k值太大时,并没有降低离散对数问题求解的困难度,该算法是无法有效进行运算的。因此我们要选取小一些的k值。目前通过运算已知k≤6时,MOV算法对一类特殊的椭圆曲线离散对数求解是十分有效的,即超奇异椭圆曲线,这个过程是亚指数时间算法的。应用MOV算法将ECDLP转化为DLP,就可以利用上述的ρ算法的改进方法来进行离散对数的求解。