《对椭圆曲线上ElGamal密码体制的攻击.doc》由会员分享，可在线阅读，更多相关《对椭圆曲线上ElGamal密码体制的攻击.doc（7页珍藏版）》请在三一办公上搜索。
1、对椭圆曲线上ElGamal密码体制的攻击冯晓博，王明强山东大学密码技术与信息安全教育部重点实验室，济南250100摘要：本文提出了一种攻击椭圆曲线上ElGamal加密体制的算法。如果密码体制所在的群的阶满足一些条件，该攻击方法可以通过使用一次解密喻示恢复出密钥。使用本文的攻击算法可以以99.4%的概率恢复出密钥的部分信息。最后，本文给出了应对该攻击方法的措施。关键词：椭圆曲线；离散对数问题；Pohlig-Hellman算法；选择密文攻击中图分类号： TN918Attack on the EC ElGamal cryptosystemXiaobo Feng, Mingqiang WangKey
2、Laboratory of Cryptologic Technology and Information Security, Ministry of Education,Shandong University, Jinan 250100Abstract: In this paper, we provide a method to attack EC ElGamal cryptosystem basedon DLP. By applying the attack method,we could get the partial information of the privatekey with
3、high probability. If the cyclic group G which the cryptosystem is based on satisessome 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;Ch
4、osen-ciphertext attack; Elliptic curve.0引言1976年，Die和Hellman1设计了基于离散对数问题(DLP)的密钥交换协议后，DLP就成为了密码学中的热点问题。基于离散对数问题的密码体制有很多，例如DSA，ElGamal密码体制，Schnorr 签名体制等。假设T 是一个群，g T ， g 是由g生成的循环子群， g 的阶记作n，离散对数问题就是找到一个整数x使得gx = a，其中a g .目前有很多计算离散对数问题的算法。Shanks2 提出了大步小步法，该算法需要O( n log n)的时间复杂度以及同样多的空间复杂度，因此它适用于群的阶n比较小
5、的情况。 Silver-Pohlig-中pi是群 g 的阶的最大公因子。 另外，还有很多其他的算法用来计算离散对数问题，例如Pollard 算法，Index Calculus算法等。基金项目： 教育部博士点新教师基金(Grant No.20090131120012)作者简介： 冯晓博（1987-），男，硕士研究生，主要研究方向：信息安全。通信作者：王明强（1971-），男，副教授，主要研究方向：信息安全。Email: wangmingqiang-1-Hellman 算法可以在群的阶是光滑数的情况下使用，并且它的运算时间大约是O( pi)，其令G是密码算法所在的群且是一个椭圆曲线点群，如果G =
6、 g 的阶除了一个大素数因子外还有一些其他因子，那么本文的攻击算法可以成功地得到密钥的部分信息，令ord(G) =j1i=0pei i，假设p0是ord(G)的最大素因子，如果p0/j1i=1pei i 的大小在穷搜能力范围之内，该攻击算法可以穷搜出密钥的剩余信息，从而恢复出整个密钥。以80比特安全的EC ElGamal密码体制为例，本文的攻击方法能以大约99.4%的概率获得密钥的部分信息，这个概率会随着群的阶的比特数的增加而提高。从具体攻击中可以知道与直接计算离散对数的方法相比，该攻击方法可以很明显地降低时间复杂度，本文的几个例子基本上都可以恢复出整个密钥。对于一般的ElGamal加密体制，
7、本文的攻击方法会得到密钥的部分信息。本文也提供了一些抵抗这种攻击方法的措施。本文第一章回顾了椭圆曲线的基本知识以及EC ElGamal加密体制，第二章给出对ECElGamal加密体制的攻击算法，分析了算法的攻击原理，并对一般的ElGamal加密算法在算法2攻击下的安全性做了分析，第三章给出了几个具体的实例，描述了攻击的具体过程，并分析了攻击的效率，第四章总结攻击的原理，然后提出抵抗本文攻击方法的措施。1背景知识定义在有限域Fq上的椭圆曲线可以写成下面Weierstrass方程的形式：E : y2 + a1xy + a3y = x3 + a2x2 + a4x + a6,且满足ai Fq, i =
8、 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 .EC ElGamal3加密体制：参数选取：定义在有限域Fq上的椭圆曲线E，E的阶有一个大的素数因子p，选择阶为p的点P E(Fq)作为基点，选取整数d 1, . . . , p1作为密钥，另外，点Q E(Fq)，且Q = dP .公开P 和Q，保密d.加密算法：1. 选取一个随机数k，1 k p，并计算kP
9、 ；2. 计算kQ，记x(kQ)为kQ的x坐标；3. 计算x(kQ) m (m是待加密的信息)；4. 输出密文(H, m ) = (kP, x(kQ) m).-2-解密算法：1. 计算dH；2. 返回m x(dH).如果基点P 的阶是一个光滑数，可以使用Silver-Pohlig-Hellman算法（算法1）计算椭圆曲线离散对数，这个算法把DLP归约到阶为素数的子群上。在1.3.2中，可以使用Pollards rho算法计算椭圆曲线离散对数，因为计算是在一个阶为小素数的子群上进行的。算法1 Silver-Pohlig-Hellman 算法输入: P E(Fq)，Q P ，n = ord(P )
10、 =j1i=0pei i，其中pi pi+1.输出: d mod n.1. i从0到j 1执行：1.1 Q O, ki 0.1.2 Pi (n/pi)P.1.3 For t = 0 to (ei 1) do1.3.1 Qt,i (n/pti+1)(Q + Q ).1.3.2 Wt,i logPi Qt,i.1.3.3 Q Q Wt,iptiP.1.3.4 ki ki + ptiWt,i.2. 使用中国剩余定理计算k ki mod pei i，从而可以得到k mod n.3. 返回(k).当P 的阶n是素数时，该算法实际上是调用了一次Pollards rho方法，其时间复杂度也就 为O( n l
11、og n)，否则，该算法的时间复杂度为O( pj log pj)，其中pj是n的最大素因子。2攻击算法本章给出对EC ElGamal加密体制的攻击算法，假设给定解密喻示。假 设 椭 圆 曲 线 点 群 的 阶 不 是 素 数， 那 么 可 以 从 椭 圆 曲 线 上 选 取 一 个 点R, 它 的 阶是n2 = n p, 从而pR的阶为ord(pR) = n . 将pR和随机选取的数m 作为密文发给解密喻示，通过解密喻示返回的明文m0 = x(dpR) m 求得dpR，然后利用(pR, dpR) 计算出密钥的部分信息d mod n ，最后通过穷搜得到私钥d 的剩余信息从而恢复出整个的密钥，攻击
12、的具体过程如算法2所示。算法2 对EC ElGamal 加密体制的攻击算法输入: 定义在有限域Fq上的椭圆曲线E，P E(Fq)，ord(P ) = p, Q P输出: d mod p.-3-1. 选择一个密文并把它发送给解密喻示1.1 选取一个数m Fq.1.2 选取一个阶为n2 = n p的点R, 并计算pR.1.3 发送(pR, m )给解密喻示。2. 解密喻示计算dP R 并返回m0 = x(dpR) m .3. 计算x(dpR) = m0 m .4. 利用(dpR, pR)，使用算法1计算出d mod n .5. 寻找满足lcm(n , r)n的最小的r.6. 穷搜密钥的剩余信息6.
13、1 d 0.6.2 当(d r)时执行如下操作6.2.1 搜索d 使得满足d d mod r和d d mod n .6.2.2 计算R = d P .6.2.3 如果满足(R = R)，返回d .6.2.4 否则d d + 1.注1：算法2假定了椭圆曲线点群的阶除了大素数因子外还有其他因子，然后选取了阶为n2 = n p的点R用来构造密文，从而通过解密喻示恢复出密钥的部分信息。 事实上，假设n2是随机的且p大约是160比特，那么n2是个素数的概率大约是1/ ln n2 1/160，因此n2一般情况下不是素数，即算法2假定的条件是基本成立的。假如n 是素数，算法2中(4)的计算时间复 杂度大约是
14、O( n )，否则，假设s是n 的最大素因子，时间复杂度为O( s)，在下文将它们统一记作O(T )，在具体计算时加以区分。事实上，以256比特的椭圆曲线点群来说，在达到80比特的安全性后，n 的长度至多为96比特，此时算法2中(4)的时间复杂度为O(248).注2：算法2中的(6)穷搜了剩余的比特信息。 为了完全恢复密钥信息，穷搜的时间复杂度O(p/n )应该在可穷搜能力范围内，然后利用已知的密钥d的部分信息穷搜剩余的信息。 综上，算法2的时间复杂度为O(T ) + O(p/n )，在分析攻击实例时会具体计算算法2的时间复杂度。注3：算法2也可以攻击一般的ElGamal加密体制。构造一般的E
15、lGamal加密算法需要一个大素数p，并且p 1有一个大的素因子。如果知道p 1的分解p 1 = p1p2 . . . ps，并且p1是唯一的大素因子，如算法2所述，假设d是私钥，选择一个阶为p2p3 . . . ps的元素，然后随机选取一个数M ，并把(, M )发送给解密喻示，由解密喻示返回的信息计算出d，从而由(, d)计算出d mod p2p3 . . . ps，当p1/p2p3 . . . ps的大小在计算能力之内时，可以计算出d mod p1. 最后，利用中国剩余定理恢复出整个密钥d.-4-3攻击实例本章给出了利用算法2攻击的椭圆曲线的实例。 这些椭圆曲线是定义在素域GF (q)上
16、的，其中q = 2256 2224 + 2192 + 296 1，椭圆曲线的系数用十六进制表示。下面先给出一个实例并进行具体分析。例1E1(Fq) : y2 = x3 + 3x + 2797.E1(Fq) = (2)(5)(23)(5370637)(790894181)(46759853569199) (28277533277870611404339941741614907344645402643) =: t2 t1在构造EC ElGamal加密体制时，选择阶为t1的点作为基点P，私钥d 1, . . . , t1 1. 该例中的椭圆曲线点群是个循环群，在攻击时，可选取一个生成元作为R，则t1
17、R的阶为t2，再随机选取一个数m，把(t1R, m)作为密文发给解密喻示，根据解密喻示返回的信息计算出dt1R，然后如算法2所述，根据(t1R, dt1R)计算d mod t2，由于t2不是素数，且它的最大素因子为46比特，因此算法2中(4)的时间复杂度为O(223). 接下来穷搜私钥d的剩余信息，由于t1/t2大约是51比特，因此穷搜的时间复杂度大约是O(251). 这样，算法2攻击由例1中椭圆曲线构建的ECElGamal加密体制大约需要O(251)的时间复杂度，这可以由一台3.0GHZ CPU计算出来，因此算法2可以有效地攻击这个实例。现在给出更多的实例，具体攻击过程与例1相同，在此略去，
18、仅列出算法2的攻击效率：例2例3例4E2(Fq): y2 = x3 + 3x + 2856.E2(Fq) = (3)2(37)(83)(173)(5818209373)(123501592004059) (33701447871816624823180418737838204532603728567).安全比特: 78-bit，算法2攻击的时间复杂度: O(256).E3: y2 = x3 + 3x + 2827.E3(Fq) = (2)(167)(31801451173371723465286035451) (10901480562550603272739848422221870051364
19、268019).安全比特: 78-bit，算法2攻击的时间复杂度: O(250).E4: y2 = x3 + 3x + 2849.E4(Fq) = (3)(43)(103)(1326887)(31252950941137087429) (210148834385369687849650143310155097634428976543).安全比特: 80-bit，算法2攻击的时间复杂度: O(259).4抵抗算法2攻击的措施本文在第二章描述了攻击EC ElGamal加密体制的算法，根据攻击算法的原理以及在攻击中所使用的方法可以总结出抵抗算法2攻击的措施。-5-首先，在构造ElGmal或EC El
20、Gamal加密算法时应该更严格地考虑一般的或椭圆曲线的群结构，仅满足群的阶有一个大素数因子是不安全的，群的其他因子也应该尽量的小，最好群的阶几乎是素数(p)，例如ord(G) = hp，其中h与p相比足够小。其次，算法2使用了选择密文攻击和伪造密文，因此为抵抗攻击应保证密文没有被篡改。算法2攻击时发送给解密喻示的密文第一部分是属于群 pQ 的，阶为n ，而不属于群 P ，因此为防止伪造密文，可以检查密文的第一部分是否属于群 P ，即可以用群 P 的阶乘以密文第一部分，验证其是否为无穷远点O.5结论本文描述了一种攻击基于ECDLP的EC ElGamal加密体制的算法，该攻击算法说明为了保证加密体
21、制的安全性，椭圆曲线群的阶只有一个大素因子是不够的，如果群的阶满足特定的条件，基于大素因子的离散对数问题可能被转化为另外一个群上的离散对数问题，从而导致密钥被攻破。另外，本文的攻击实例证明了算法2的攻击不仅有理论意义，如果攻击算法所要求的条件实现，密码体制在实际应用中也能被攻破。参考文献（References）1 W. Die and M. Hellman, New Directions in Cryptography, IEEE Transactions on Infor-mation Theory. IT-22(1976), 472-492.2 D. Shanks, Class numbe
22、r, a theory of factorization, and genera, in Proceedings of theSymposium in Pure Mathematics, vol. 20 (American Mathematical Society, Providence,1971), pp. 415-440.3 T. ElGamal, A public key cryptosystem and a signature scheme based on discrete loga-rithms. IEEE Transactions on Information Theory, 1
23、985, 31(4), 469-472.4 Ingrid Biehl, Bernd Meyer and Volker Muller, Dierential Fault Attacks on ELliptic CurvesCryptosystems (Extend Abstract), lecture Notes in Computer Science, 2000, Vol.1880,131-146.5 B. J. Birch, How the number of points of an elliptic curve over a xed prime eld varies,J. London
24、Math. Soc. 43 (1968), 57-60.6 D. BOneh, R.A. DeMillo, R.J. Lipto, On the Importance of Checking Cryptographic Pro-tocols for Faults. Advances in Cryptology-EUROCRYPT97, LNCS 1233, Springer-Verlag,1997, 37-51.7 A. Dominguez-Oviedo, M. A. Hasan and B. Ansari, Fault-Based Attack on MontgomerysLadder Al
25、gorithm, Journal of Cryptology, 24 (2010), 346-374.-6-8 D. Hankerson, A. Menezes, S.A. Vanstone, Guide to Elliptic Curve Cryptography(Springer, Berlin, 2003).9 N.Koblitz, Elliptic curve cryptosystems. Math. Comp., Vol.48, No.177(1987), 203-209.10 A. Menezes, T. Okamoto and S. Vanstone, Reducing elli
26、ptic curve logarithms to logarithmsin a nite eld, IEEE Transactions on Information Theory, 39 (1993), 1639-1646.11 V. Miller, Use of elliptic curves in cryptography. In CRYPTO 86, Lecture Notes in Comput.Sci. 263, (1987), 417-426.12 P.L. Montgomery, Speeding the Pollard and elliptic curve methods of
27、 factorization. Math.Comput. 48, (1987), pp.243-264.13 J.M. Pollard, Monte Carlo methods for index computation (mod p). Math. Comput. 32,(1978), 918-924.14 S. Pohlig, M. Hellman, An improved algorithm for computing logarithms over GF (p) andits cryptographic signicance. IEEE Trans. Inf. Theory 24, (
28、1978), 106-110.15 H-G. Ruck, A note on elliptic curves over nite elds. Mathematics of Computation, 1987,49(179):301-304.16 R. J. Schoof, Elliptic curves over nite elds and the computation of square roots mod p,Math. Comp. Vol 44(1985), 483-494.17 J. H. Silverman, The arithmetic of elliptic curves, G
29、raduate Texts in Mathematics,Springer-Verlag, New York.1994, 45-70.18 N. Smart, The discrete logarithm problem on elliptic curves of trace one, Journal of Cryp-tology, 12 (1999), 193-196.19 M. Wang, X. Wang, T. Zhan, Y. Zheng, Skew-Frobenius map on twisted Edwards curve,ICIC Express letters, 5(6) 2011, 2009-2094.20 M.Wang, T.Zhan, Analysis of the Fault attack ECDLP over Prime Field, Journal of Ap-plied Mathematics, volume 2011, doi:10.1155/2011/580749, to appear.-7-
