利用有限簡單連分數(shù)的最佳逼近原理破譯公鑰密碼RSA及其實現(xiàn)

鄧從政

(凱里學(xué)院理學(xué)院，貴州凱里 556000)

0 引言

一般地，RSA密碼體制是利用Zn［1，2］的計算，設(shè)n=pq，其中，p，q為素數(shù)，ab=1(mod＞ (n)).對此，定義如下的加密函數(shù)，ek(x)=xbmodn，和解密函數(shù)，dk(y)=yamodn，其中，x，y∈Zn.這樣n，b組成了公鑰，p，q，a組成了私鑰，x是要加密的明文，y =ek(x)是密文，b是加密指數(shù)，a是解密指數(shù).假如知道了解密密鑰a，那么可以按照以下流程來破譯出被加密的明文x.

由于，

有，

假定，x∈Z*N，則有，

式(3)正是我們所期望的解密出來的明文［1］.

從以上的解密流程可以看出，攻擊RSA密碼體制就是攻擊者能夠拿到私鑰，也就是能夠計算出它的解密指數(shù)a.如果能做到這一點，那么就可以有效地破解對方發(fā)來的密文.事實上，目前有很多種計算私鑰a的方法［3，4］，在此基礎(chǔ)上，本文介紹一種利用有限簡單連分數(shù)最佳有理逼近原理計算解密指數(shù)的方法來實現(xiàn)對RSA密碼體制的有效攻擊.

1 有限簡單連分數(shù)最佳有理逼近原理

事實上，任何一個有理數(shù)都可以寫成一個有限連分數(shù)的形式，

式中，a，b，q1，q2，q3，…，qm，都是非負整數(shù).把［q1，q2，…，qk］，1≤k≤m，稱為a/b的第k個漸近分數(shù)或者收斂子，容易看出，a/b=［q1，q2，…，qk］，稱［q1，q2，…，qk］為連分數(shù)a/b的展式.若記，Ek為［q1，q2，…，qk］的第k個收斂子，則每一個Ek可以寫成有理數(shù)ck/dk的形式，而其中的ck和dk滿足如下的遞推關(guān)系［2］，

且，c0=1，d0=0.

通常，一個有理數(shù)的連分數(shù)展式有很多有用的性質(zhì)，基于本研究的目的，最重要的是如下有理數(shù)的最佳逼近原理，限于篇幅，這里不作證明.

2 利用逼近原理對RSA密碼體制進行有效低解密指數(shù)的攻擊與實現(xiàn)

假定 n = pq，p和 q為素數(shù)，ab≡1(mod＞ (n))，3a＜n1/4，且q＜p＜2q.也就是說，如果n的二進制表示長為x比特，那么當a的二進制表示的位數(shù)小于x/4-1比特，且p和q相距很近時就可以進行有效攻擊.在此條件下，解密指數(shù)a的計算方法如下:

由于，ab≡1(mod＞ (n))，可知存在一個整數(shù)t使得，

從而，

由于，t＜a，有，3t＜3a＜n1/4，因此，

由于，3a＜n1/4，可得，

根據(jù)有理數(shù)的最佳逼近原理，分數(shù)t/a是分數(shù)b/n的一個最佳漸近分數(shù).n和b是公鑰，很容易計算出它的收斂子來.

通過計算，

并解如下方程，

則可以完全分解模n了.

下面給出依據(jù)上述逼近原理計算最佳漸近分數(shù)的一種算法和一個具體實例.

2.1 威勒算法

威勒算法(Wiener Algorithm)［3］的具體步驟如下:

2.2 應(yīng)用實例

例 設(shè)n=160 523 347，b=60 728 973，計算其解密指數(shù)a，并且將n分解.

解 ①將b/n展開為連分數(shù)，

②驗證漸近分數(shù)EK.發(fā)現(xiàn)，E1、E2、E3、E4、E5不是最佳漸近分數(shù)，不能產(chǎn)生n的分解和計算出解密指數(shù)a.

④解方程，

得到，x1=12 347，x2=13 001

⑤據(jù)此可以把n成功的地分解為，

故所求的解密指數(shù)a為，

3 結(jié) 論

事實上，攻擊RSA密碼體制最常用的一種方式就是攻擊者試圖分解模數(shù)n，獲得密鑰p和q，如果這一點得以實現(xiàn)，那么就可以很簡單地計算出，＞(n) =(p-1)(q-1)，然后從b精確地計算出解密指數(shù)a，從而破解密文.從本文的分析可以看出，當RSA密碼體制所選模數(shù)n滿足一定的條件時，可以利用連分數(shù)的最佳有理逼近原理很快地將模數(shù)完全分解并計算出它的解密指數(shù)，本文方法不失為攻擊RSA密碼體制的一種有效方法.因此，一個RSA密碼體制要成為安全的，必須要求n=pq充分大，并使之超出現(xiàn)有的分解因子算法的能力，進而使得分解它在計算上是不可行的.

［1］Stinson D R.密碼學(xué)原理與實踐［M］.馮登國譯.北京:電子工業(yè)出版社，2003.

［2］潘承洞，潘承彪.初等數(shù)論［M］.北京:北京大學(xué)出版社，2003.

［3］Rivest R L.Shamir A，Adleman L.A Method for Obtaining Digital Signatures and Public Key Cryptosystems［J］.Communications of the ACM，1978，21(2):120-126.

［4］Rosen K H.Elementary Number Theory and Its Applications［M］.New Jersey:Addison-Wesley Publishing Company，1999.