對ElGamal密碼體制的攻擊.pdf

1、ElGamal算法[6]由TaherElGamal在1985年提出，ElGamal算法既可用于加密，也可用于數(shù)字簽名，DSA（數(shù)字簽名算法）亦是由ElGamal演變而來的，在相同的安全強度下，橢圓曲線密碼體制的密鑰尺寸比較小，又使得橢圓曲線ElGamal算法廣泛應(yīng)用在智能卡行業(yè)。ElGamal算法的安全性基于離散對數(shù)問題的困難性，目前有一些計算離散對數(shù)的算法，Shanks[16]提出了小步大步法，該算法需要O((√n)logn)的時間復(fù)

2、雜度以及同樣多的空間復(fù)雜度，Pohlig-Hellman算法則可以在群的階是光滑數(shù)的情況下使用，另外，還有Pollardρ算法[12]，IndexCalculus算法等，這些算法都極大地提高了計算的效率，但是目前還沒有計算離散對數(shù)問題的多項式時間算法。
　　 對于橢圓曲線離散對數(shù)問題，Agustin[5]等人提出了一種故障攻擊的方法。該方法通過對特征為2的橢圓曲線點乘算法進(jìn)行分析，得出點乘運算與曲線參數(shù)a無關(guān)，在對比了NIST推

3、薦的橢圓曲線E(a，b)和改變參數(shù)a后的曲線(E)（(a),b）后，其中Tr(a)=1-Tr((a))，又發(fā)現(xiàn)了改變參數(shù)a后的橢圓曲線點群在密碼學(xué)意義上以很大的概率是弱的，即群的階是比較小的素因子的乘積?；谝陨鲜聦?，Agustin等人在進(jìn)行橢圓曲線點乘運算時植入故障，從而使得輸入點（基點）P的x坐標(biāo)落到曲線(E)（(a),b）上，進(jìn)而通過點乘運算分別得到曲線上的點(P)和點(Q)=κ(P)，這樣就把強橢圓曲線上的困難的離散對數(shù)問題轉(zhuǎn)化

4、到弱橢圓曲線上的較容易的離散對數(shù)問題，然后通過Pohlig-Hellman算法求得離散對數(shù)κ或κ的部分信息。
　　 最近，Berzati等人在[18]中提出了一種針對DSA(DigitalSignatureAl-gorithm)的攻擊方法，這種攻擊方法通過使用格攻擊和故障攻擊兩種工具，有效地繞過了求解離散對數(shù)的困難問題。假設(shè)在進(jìn)行DSA簽名的第一部分模指數(shù)運算的最后t步之前，對公開參數(shù)p植入一個字節(jié)的故障，記改變后的p為(p),

5、通過猜測隨機數(shù)κ的最后t比特κt以及(p),并根據(jù)對簽名的分析得到的一些性質(zhì)來驗證猜測的結(jié)果從而求得κt，如果攻擊者能夠通過多次植入故障的方法得到多個故障簽名，那么可通過構(gòu)造格將求DSA私鑰的問題轉(zhuǎn)化為求格的最近向量問題，最后使用Babai的求格算法求出私鑰。
　　 本文提出了一種對ElGamal加密體制的攻擊方法。首先，對于橢圓曲線ElGamal加密算法，令G是密碼算法所在的橢圓曲線點群，如果G=〈g〉的階除了一個大素數(shù)因子外

6、還有一些其他因子，那么本文的攻擊算法可以成功地得到密鑰的部分信息。令ord(G)=∏j-1i=0peii，假設(shè)po是ord(G)的最大素因子，即在構(gòu)建ElGamal密碼體制時從G中選擇一個階為po的點作為基點P，Q=dP為公鑰，d為私鑰，則ElGamal加密體制最后生成的密文形如（H，m'）=（κP,x（κQ(○+)m）），其中κ是隨機數(shù)，m是待加密的信息。假設(shè)給定解密喻示，則可以偽造一個密文(pR，m")，其中R是階為∏j-1i=0p

7、eii的點，m"隨機選取且已知，解密喻示會計算dpR并返回x（dpR）(○+)m"，根據(jù)返回值可以求出dpR，然后利用Pholig-Hellman算法求出dmod∏j-1i=1peii，如果po/∏j-1i=1peii的大小在窮搜能力范圍之內(nèi)，該攻擊算法可以窮搜出密鑰的剩余信息，從而恢復(fù)出整個密鑰，第二章算法4給出了具體的攻擊步驟。
　　 以80比特安全的橢圓曲線ElGamal密碼體制為例，本文的攻擊方法能以大約99.4％的概率

8、獲得密鑰的部分信息，這個概率會隨著群的階的比特數(shù)的增加而提高。從具體攻擊中可以知道與直接計算離散對數(shù)的方法相比，該攻擊方法可以很明顯地降低時間復(fù)雜度，本文的幾個例子基本上都可以恢復(fù)出整個密鑰。
　　 對于有限域上ElGamal加密體制，和對橢圓曲線ElGamal加密體制的攻擊思路一致，但由于兩種密碼體制的構(gòu)造不同使得具體的攻擊過程也有相應(yīng)的不同。首先也需要把困難的離散對數(shù)問題轉(zhuǎn)化為一個較易解決的離散對數(shù)問題，假設(shè)α是有限域Zp的

9、本原元，且已知p-1的分解為p-1=p1p2e2…pses，若給定解密喻示，則構(gòu)造密文(γ，M)，其中γ=αp1，由解密喻示的返回值求出γa（a為私鑰），然后根據(jù)（γa，γ）使用Pohlig-Hellman算法計算:a1(≡)amodp2e2…pses，假如此時p1/p2e2…pses的大小也在計算能力之內(nèi)時，那么可以利用窮搜的方法搜索amodp1的剩余信息，即求得:a2(≡)amodp1，最后利用中國剩余定理求出完整的密鑰amodp-