对椭圆曲线上ElGamal密码体制的攻击
冯晓博，王明强
山东大学密码技术与信息安全教育部重点实验室，济南　250100
摘要：本文提出了一种攻击椭圆曲线上ElGamal加密体制的算法。如果密码体制所在的群的阶
满足一些条件，该攻击方法可以通过使用一次解密喻示恢复出密钥。使用本文的攻击算法可以
以99:4%的概率恢复出密钥的部分信息。最后，本文给出了应对该攻击方法的措施。
关键词：椭圆曲线；离散对数问题；Pohlig-Hellman算法；选择密文攻击
 0 引言
1976年，Die和Hellman[1]设计了基于离散对数问题(DLP)的密钥交换协议后，DLP就成
为了密码学中的热点问题。基于离散对数问题的密码体制有很多，例如DSA，ElGamal密码体
制，Schnorr 签名体制等。假设T是一个群，g 2 T，hgi是由g生成的循环子群，hgi的阶记作n，
离散对数问题就是找到一个整数x使得gx = a，其中a 2 hgi.
目前有很多计算离散对数问题的算法。Shanks[2]提出了大步小步法，该算法需要O(pn log n)的
时间复杂度以及同样多的空间复杂度，因此它适用于群的阶n比较小的情况。Silver-Pohlig-
Hellman 算法可以在群的阶是光滑数的情况下使用，并且它的运算时间大约是O(ppi)，其
中pi是群hgi的阶的最大公因子。另外，还有很多其他的算法用来计算离散对数问题，例
如Pollard 算法，Index Calculus算法等。
基金项目： 教育部博士点新教师基金(Grant No.20090131120012)
作者简介： 冯晓博（1987-），男，硕士研究生，主要研究方向：信息安全。通信作者：王明强（1971-），男，副教授，主要研
究方向：信息安全。Email: wangmingqiang@sdu.edu.cn
 令G是密码算法所在的群且是一个椭圆曲线点群，如果G = hgi的阶除了一个大素数因
子外还有一些其他因子，那么本文的攻击算法可以成功地得到密钥的部分信息，令ord(G) =
Qj
原创学术论文网Tag：代写论文 代写硕士论文 代写毕业论文 代写毕业设计