對橢圓曲線上ElGamal密碼體制的攻擊

1、對橢圓曲線上elgamal密碼體制的攻擊馮曉博，王明強山東大學(xué)密碼技術(shù)與信息安全教育部重點實驗室，濟南250100摘要：本文提出了一種攻擊橢圓曲線上elgamal加密體制的算法。如果密碼體制所在的群的階滿足一些條件，該攻擊方法可以通過使用一次解密喻示恢復(fù)出密鑰。使用本文的攻擊算法可以以99.4%的概率恢復(fù)出密鑰的部分信息。最后，本文給出了應(yīng)對該攻擊方法的措施。關(guān)鍵詞：橢圓曲線；離散對數(shù)問題；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設(shè)計了基于離散對數(shù)問題(dlp)的密鑰交換協(xié)議后，dlp就成為了密碼學(xué)中的熱點問題?；陔x散對數(shù)問題的密碼體制有很多，例如dsa，elgamal密碼體制，schnorr 簽名體制等。假設(shè)t 是一個群，g t ， g 是由g生成的循環(huán)子群， g 的階記作n，離散對數(shù)問題就是找到一個整數(shù)x使得gx = a，其中a g .目前有很多計算離散對數(shù)問題的算法。shanks2 提出了大步小步法，該算法需要o( n log n)的時間復(fù)雜度以及同樣多的空間復(fù)雜度，因此它適用于群的階n比較小

5、的情況。 silver-pohlig-中pi是群 g 的階的最大公因子。 另外，還有很多其他的算法用來計算離散對數(shù)問題，例如pollard 算法，index calculus算法等?；痦椖浚?教育部博士點新教師基金(grant no.20090131120012)作者簡介： 馮曉博（1987-），男，碩士研究生，主要研究方向：信息安全。通信作者：王明強（1971-），男，副教授，主要研究方向：信息安全。email: wangmingqiang-1-hellman 算法可以在群的階是光滑數(shù)的情況下使用，并且它的運算時間大約是o( pi)，其令g是密碼算法所在的群且是一個橢圓曲線點群，如果g =

6、 g 的階除了一個大素數(shù)因子外還有一些其他因子，那么本文的攻擊算法可以成功地得到密鑰的部分信息，令ord(g) =j1i=0pei i，假設(shè)p0是ord(g)的最大素因子，如果p0/j1i=1pei i 的大小在窮搜能力范圍之內(nèi)，該攻擊算法可以窮搜出密鑰的剩余信息，從而恢復(fù)出整個密鑰。以80比特安全的ec elgamal密碼體制為例，本文的攻擊方法能以大約99.4%的概率獲得密鑰的部分信息，這個概率會隨著群的階的比特數(shù)的增加而提高。從具體攻擊中可以知道與直接計算離散對數(shù)的方法相比，該攻擊方法可以很明顯地降低時間復(fù)雜度，本文的幾個例子基本上都可以恢復(fù)出整個密鑰。對于一般的elgamal加密體制，

7、本文的攻擊方法會得到密鑰的部分信息。本文也提供了一些抵抗這種攻擊方法的措施。本文第一章回顧了橢圓曲線的基本知識以及ec elgamal加密體制，第二章給出對ecelgamal加密體制的攻擊算法，分析了算法的攻擊原理，并對一般的elgamal加密算法在算法2攻擊下的安全性做了分析，第三章給出了幾個具體的實例，描述了攻擊的具體過程，并分析了攻擊的效率，第四章總結(jié)攻擊的原理，然后提出抵抗本文攻擊方法的措施。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.橢圓曲線離散對數(shù)問題： 給定一個定義在有限域fq上的橢圓曲線e，曲線上一個點q和一個階為p的點p ，求一個整數(shù)d，0dp 1，使得q = dp .ec elgamal3加密體制：參數(shù)選?。憾x在有限域fq上的橢圓曲線e，e的階有一個大的素數(shù)因子p，選擇階為p的點p e(fq)作為基點，選取整數(shù)d 1, . . . , p1作為密鑰，另外，點q e(fq)，且q = dp .公開p 和q，保密d.加密算法：1. 選取一個隨機數(shù)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 的階是一個光滑數(shù)，可以使用silver-pohlig-hellman算法（算法1）計算橢圓曲線離散對數(shù)，這個算法把dlp歸約到階為素數(shù)的子群上。在1.3.2中，可以使用pollards rho算法計算橢圓曲線離散對數(shù)，因為計算是在一個階為小素數(shù)的子群上進行的。算法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(luò) 1執(zhí)行：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是素數(shù)時，該算法實際上是調(diào)用了一次pollards rho方法，其時間復(fù)雜度也就 為o( n l

11、og n)，否則，該算法的時間復(fù)雜度為o( pj log pj)，其中pj是n的最大素因子。2攻擊算法本章給出對ec elgamal加密體制的攻擊算法，假設(shè)給定解密喻示。假 設(shè) 橢 圓 曲 線 點 群 的 階 不 是 素 數(shù)， 那 么 可 以 從 橢 圓 曲 線 上 選 取 一 個 點r, 它 的 階是n2 = n p, 從而pr的階為ord(pr) = n . 將pr和隨機選取的數(shù)m 作為密文發(fā)給解密喻示，通過解密喻示返回的明文m0 = x(dpr) m 求得dpr，然后利用(pr, dpr) 計算出密鑰的部分信息d mod n ，最后通過窮搜得到私鑰d 的剩余信息從而恢復(fù)出整個的密鑰，攻擊

12、的具體過程如算法2所示。算法2 對ec elgamal 加密體制的攻擊算法輸入: 定義在有限域fq上的橢圓曲線e，p e(fq)，ord(p ) = p, q p輸出: d mod p.-3-1. 選擇一個密文并把它發(fā)送給解密喻示1.1 選取一個數(shù)m fq.1.2 選取一個階為n2 = n p的點r, 并計算pr.1.3 發(fā)送(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)時執(zhí)行如下操作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假定了橢圓曲線點群的階除了大素數(shù)因子外還有其他因子，然后選取了階為n2 = n p的點r用來構(gòu)造密文，從而通過解密喻示恢復(fù)出密鑰的部分信息。 事實上，假設(shè)n2是隨機的且p大約是160比特，那么n2是個素數(shù)的概率大約是1/ ln n2 1/160，因此n2一般情況下不是素數(shù)，即算法2假定的條件是基本成立的。假如n 是素數(shù)，算法2中(4)的計算時間復(fù) 雜度大約是

14、o( n )，否則，假設(shè)s是n 的最大素因子，時間復(fù)雜度為o( s)，在下文將它們統(tǒng)一記作o(t )，在具體計算時加以區(qū)分。事實上，以256比特的橢圓曲線點群來說，在達到80比特的安全性后，n 的長度至多為96比特，此時算法2中(4)的時間復(fù)雜度為o(248).注2：算法2中的(6)窮搜了剩余的比特信息。 為了完全恢復(fù)密鑰信息，窮搜的時間復(fù)雜度o(p/n )應(yīng)該在可窮搜能力范圍內(nèi)，然后利用已知的密鑰d的部分信息窮搜剩余的信息。 綜上，算法2的時間復(fù)雜度為o(t ) + o(p/n )，在分析攻擊實例時會具體計算算法2的時間復(fù)雜度。注3：算法2也可以攻擊一般的elgamal加密體制。構(gòu)造一般的e

15、lgamal加密算法需要一個大素數(shù)p，并且p 1有一個大的素因子。如果知道p 1的分解p 1 = p1p2 . . . ps，并且p1是唯一的大素因子，如算法2所述，假設(shè)d是私鑰，選擇一個階為p2p3 . . . ps的元素，然后隨機選取一個數(shù)m ，并把(, m )發(fā)送給解密喻示，由解密喻示返回的信息計算出d，從而由(, d)計算出d mod p2p3 . . . ps，當p1/p2p3 . . . ps的大小在計算能力之內(nèi)時，可以計算出d mod p1. 最后，利用中國剩余定理恢復(fù)出整個密鑰d.-4-3攻擊實例本章給出了利用算法2攻擊的橢圓曲線的實例。 這些橢圓曲線是定義在素域gf (q)上

16、的，其中q = 2256 2224 + 2192 + 296 1，橢圓曲線的系數(shù)用十六進制表示。下面先給出一個實例并進行具體分析。例1e1(fq) : y2 = x3 + 3x + 2797.e1(fq) = (2)(5)(23)(5370637)(790894181)(46759853569199) (28277533277870611404339941741614907344645402643) =: t2 t1在構(gòu)造ec elgamal加密體制時，選擇階為t1的點作為基點p，私鑰d 1, . . . , t1 1. 該例中的橢圓曲線點群是個循環(huán)群，在攻擊時，可選取一個生成元作為r，則t1

17、r的階為t2，再隨機選取一個數(shù)m，把(t1r, m)作為密文發(fā)給解密喻示，根據(jù)解密喻示返回的信息計算出dt1r，然后如算法2所述，根據(jù)(t1r, dt1r)計算d mod t2，由于t2不是素數(shù)，且它的最大素因子為46比特，因此算法2中(4)的時間復(fù)雜度為o(223). 接下來窮搜私鑰d的剩余信息，由于t1/t2大約是51比特，因此窮搜的時間復(fù)雜度大約是o(251). 這樣，算法2攻擊由例1中橢圓曲線構(gòu)建的ecelgamal加密體制大約需要o(251)的時間復(fù)雜度，這可以由一臺3.0ghz cpu計算出來，因此算法2可以有效地攻擊這個實例?，F(xiàn)在給出更多的實例，具體攻擊過程與例1相同，在此略去，

18、僅列出算法2的攻擊效率：例2例3例4e2(fq): y2 = x3 + 3x + 2856.e2(fq) = (3)2(37)(83)(173)(5818209373)(123501592004059) (33701447871816624823180418737838204532603728567).安全比特: 78-bit，算法2攻擊的時間復(fù)雜度: o(256).e3: y2 = x3 + 3x + 2827.e3(fq) = (2)(167)(31801451173371723465286035451) (10901480562550603272739848422221870051364

19、268019).安全比特: 78-bit，算法2攻擊的時間復(fù)雜度: o(250).e4: y2 = x3 + 3x + 2849.e4(fq) = (3)(43)(103)(1326887)(31252950941137087429) (210148834385369687849650143310155097634428976543).安全比特: 80-bit，算法2攻擊的時間復(fù)雜度: o(259).4抵抗算法2攻擊的措施本文在第二章描述了攻擊ec elgamal加密體制的算法，根據(jù)攻擊算法的原理以及在攻擊中所使用的方法可以總結(jié)出抵抗算法2攻擊的措施。-5-首先，在構(gòu)造elgmal或ec el

20、gamal加密算法時應(yīng)該更嚴格地考慮一般的或橢圓曲線的群結(jié)構(gòu)，僅滿足群的階有一個大素數(shù)因子是不安全的，群的其他因子也應(yīng)該盡量的小，最好群的階幾乎是素數(shù)(p)，例如ord(g) = hp，其中h與p相比足夠小。其次，算法2使用了選擇密文攻擊和偽造密文，因此為抵抗攻擊應(yīng)保證密文沒有被篡改。算法2攻擊時發(fā)送給解密喻示的密文第一部分是屬于群 pq 的，階為n ，而不屬于群 p ，因此為防止偽造密文，可以檢查密文的第一部分是否屬于群 p ，即可以用群 p 的階乘以密文第一部分，驗證其是否為無窮遠點o.5結(jié)論本文描述了一種攻擊基于ecdlp的ec elgamal加密體制的算法，該攻擊算法說明為了保證加密體

21、制的安全性，橢圓曲線群的階只有一個大素因子是不夠的，如果群的階滿足特定的條件，基于大素因子的離散對數(shù)問題可能被轉(zhuǎn)化為另外一個群上的離散對數(shù)問題，從而導(dǎo)致密鑰被攻破。另外，本文的攻擊實例證明了算法2的攻擊不僅有理論意義，如果攻擊算法所要求的條件實現(xiàn)，密碼體制在實際應(yīng)用中也能被攻破。參考文獻（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 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 i