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

鄧從政

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

0 引言

一般地，RSA密碼體制是利用Zn［1，2］的計(jì)算，設(shè)n=pq，其中，p，q為素?cái)?shù)，ab=1(mod＞ (n)).對(duì)此，定義如下的加密函數(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密碼體制就是攻擊者能夠拿到私鑰，也就是能夠計(jì)算出它的解密指數(shù)a.如果能做到這一點(diǎn)，那么就可以有效地破解對(duì)方發(fā)來的密文.事實(shí)上，目前有很多種計(jì)算私鑰a的方法［3，4］，在此基礎(chǔ)上，本文介紹一種利用有限簡(jiǎn)單連分?jǐn)?shù)最佳有理逼近原理計(jì)算解密指數(shù)的方法來實(shí)現(xiàn)對(duì)RSA密碼體制的有效攻擊.

1 有限簡(jiǎn)單連分?jǐn)?shù)最佳有理逼近原理

事實(shí)上，任何一個(gè)有理數(shù)都可以寫成一個(gè)有限連分?jǐn)?shù)的形式，

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

且，c0=1，d0=0.

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

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

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

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

從而，

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

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

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

通過計(jì)算，

并解如下方程，

則可以完全分解模n了.

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

2.1 威勒算法

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

2.2 應(yīng)用實(shí)例

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

解 ①將b/n展開為連分?jǐn)?shù)，

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

④解方程，

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

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

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

3 結(jié) 論

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

［1］Stinson D R.密碼學(xué)原理與實(shí)踐［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.