Hellman算法可以在群的阶是光滑数的情况下使用，并且它的运算时间大约是O(pi)，其对椭圆曲线上ElGamal密码体制的攻击冯晓博，王明强山东大学密码技术与信息安全教育部重点实验室，济南250100摘要：本文提出了一种攻击椭圆曲线上ElGamal加密体制的算法。如果密码体制所在的群的阶满足一些条件，该攻击方法可以通过使用一次解密喻示恢复出密钥。使用本文的攻击算法可以以99.4%的概率恢复出密钥的部分信息。最后，本文给出了应对该攻击方法的措施。关键词：椭圆曲线；离散对数问题；Pohlig-Hellman算法；选择密文攻击中图分类号：TN918AttackontheECElGamalcryptosystemXiaoboFeng,MingqiangWangKeyLaboratoryofCryptologicTechnologyandInformationSecurity,MinistryofEducation,ShandongUniversity,Jinan250100Abstract:Inthispaper,weprovideamethodtoattackECElGamalcryptosystembasedonDLP.Byapplyingtheattackmethod,wecouldgetthepartialinformationoftheprivatekeywithhighprobability.IfthecyclicgroupGwhichthecryptosystemisbasedonsatisfiessomeconditions,wecangettheprivatekeybyapplyingone-timedecryptionoracle.Atlast,Wepresentthemeasurestoavoidthiskindofattack.Keywords:Discretelogarithmproblem;Silver-Pohlig-Hellmanalgorithm;Chosen-ciphertextattack;Ellipticcurve.0引言1976年，Diffie和Hellman[1]设计了基于离散对数问题(DLP)的密钥交换协议后，DLP就成为了密码学中的热点问题。基于离散对数问题的密码体制有很多，例如DSA，ElGamal密码体制，Schnorr签名体制等。假设T是一个群，g∈T，g是由g生成的循环子群，g的阶记作n，离散对数问题就是找到一个整数x使得gx=a，其中a∈g.√目前有很多计算离散对数问题的算法。Shanks[2]提出了大步小步法，该算法需要O(nlogn)的时间复杂度以及同样多的空间复杂度，因此它适用于群的阶n比较小的情况。Silver-Pohlig-√中pi是群g的阶的最大公因子。另外，还有很多其他的算法用来计算离散对数问题，例如Pollardρ算法，IndexCalculus算法等。基金项目：教育部博士点新教师基金(GrantNo.20090131120012)作者简介：冯晓博（1987-），男，硕士研究生，主要研究方向：信息安全。通信作者：王明强（1971-），男，副教授，主要研究方向：信息安全。Email:wangmingqiang@sdu.edu.cn-1-令G是密码算法所在的群且是一个椭圆曲线点群，如果G=g的阶除了一个大素数因子外还有一些其他因子，那么本文的攻击算法可以成功地得到密钥的部分信息，令ord(G)=j−1i=0peii，假设p0是ord(G)的最大素因子，如果p0/j−1i=1peii的大小在穷搜能力范围之内，该攻击算法可以穷搜出密钥的剩余信息，从而恢复出整个密钥。以80比特安全的ECElGamal密码体制为例，本文的攻击方法能以大约99.4%的概率获得密钥的部分信息，这个概率会随着群的阶的比特数的增加而提高。从具体攻击中可以知道与直接计算离散对数的方法相比，该攻击方法可以很明显地降低时间复杂度，本文的几个例子基本上都可以恢复出整个密钥。对于一般的ElGamal加密体制，本文的攻击方法会得到密钥的部分信息。本文也提供了一些抵抗这种攻击方法的措施。本文第一章回顾了椭圆曲线的基本知识以及ECElGamal加密体制，第二章给出对ECElGamal加密体制的攻击算法，分析了算法的攻击原理，并对一般的ElGamal加密算法在算法2攻击下的安全性做了分析，第三章给出了几个具体的实例，描述了攻击的具体过程，并分析了攻击的效率，第四章总结攻击的原理，然后提出抵抗本文攻击方法的措施。1背景知识定义在有限域Fq上的椭圆曲线可以写成下面Weierstrass方程的形式：E:y2+a1xy+a3y=x3+a2x2+a4x+a6,且满足ai∈Fq,i=1,2,3,4,6.定理1.令E是定义在有限域Fq上的椭圆曲线。那么E(Fq)Zn1×Zn2且满足n1|n2且n1|q−1.椭圆曲线离散对数问题：给定一个定义在有限域Fq上的椭圆曲线E，曲线上一个点Q和一个阶为p的点P，求一个整数d，0dp−1，使得Q=dP.ECElGamal[3]加密体制：参数选取：定义在有限域Fq上的椭圆曲线E，E的阶有一个大的素数因子p，选择阶为p的点P∈E(Fq)作为基点，选取整数d∈{1,...,p−1}作为密钥，另外，点...