利用有限簡單連分數的最佳逼近原理破譯公鑰密碼RSA及其實現

鄧從政

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

0 引言

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

由于，

有，

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

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

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

1 有限簡單連分數最佳有理逼近原理

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

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

且，c0=1，d0=0.

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

2 利用逼近原理對RSA密碼體制進行有效低解密指數的攻擊與實現

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

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

從而，

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

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

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

通過計算，

并解如下方程，

則可以完全分解模n了.

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

2.1 威勒算法

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

2.2 應用實例

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

解 ①將b/n展開為連分數，

②驗證漸近分數EK.發現，E1、E2、E3、E4、E5不是最佳漸近分數，不能產生n的分解和計算出解密指數a.

④解方程，

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

⑤據此可以把n成功的地分解為，

故所求的解密指數a為，

3 結 論

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

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

［2］潘承洞，潘承彪.初等數論［M］.北京:北京大學出版社，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.