文档介绍：对椭圆曲线上ElGamal密码体制的攻击
冯晓博,王明强
山东大学密码技术与信息安全教育部重点实验室,济南 250100
摘要:本文提出了一种攻击椭圆曲线上ElGamal加密体制的算法。如果密码体制所在的群的阶
满足一些条件,该攻击方法可以通过使用一次解密喻示恢复出密钥。使用本文的攻击算法可以
%的概率恢复出密钥的部分信息。最后,本文给出了应对该攻击方法的措施。
关键词:椭圆曲线;离散对数问题;Pohlig-Hellman算法;选择密文攻击
中图分类号: TN918
Attack on the EC ElGamal cryptosystem
Xiaobo Feng, Mingqiang Wang
Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education,
Shandong University, Jinan 250100
Abstract: In this paper, we provide a method to attack EC ElGamal cryptosystem based
on DLP. By applying the attack method,we could get the partial information of the private
key with high probability. If the cyclic group G which the cryptosystem is based on satisfies
some conditions, we can get the private key by applying one-time decryption oracle. At last,
We present the measures to avoid this kind of attack.
Key words: Discrete logarithm problem; Silver-Pohlig-Hellman algorithm;
Chosen-ciphertext attack; Elliptic curve.
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( n log n)的
时间复杂度以及同样多的空间复杂度,因此它适用于群的阶n比较小的情况。 Silver-Pohlig-
√
中pi是群 g 的阶的最大公因子。另外,还有很多其他的算法用来计算离散对数问题,例
如Pollard ρ算法,Index Calculus算法等。
基金项目: 教育部博士点新教师基金(Grant