1. RSA算法原理及內(nèi)在特性

1.1 RSA算法描述

在該箅法中，公鑰和私鑰是兩個(gè)大素?cái)?shù)的函數(shù)，從其中一個(gè)密鑰和密文恢復(fù)明文等價(jià)于將兩個(gè)素?cái)?shù)的乘積因子分解．為生成這兩個(gè)密鑰，選擇兩個(gè)大素?cái)?shù)P和q，計(jì)算其乘積n=pq，再隨機(jī)選取加密密鑰e(一般e取3，17，65，537)，使得e與(p-1)(q-1)互素，*后用歐幾里德算解密密鑰d，使得d=e的-1次方mod((p—1)x(q—1))．在這種算法中e和d也是互素的，e和n為公鑰，d為私鑰，兩個(gè)素?cái)?shù)P和q和不再用到，但不能泄露．加密報(bào)文時(shí)，首先將m分成若干以數(shù)字表示的塊，使得每塊都有一個(gè)模n表示，即如果P和q均為100位的十進(jìn)制素?cái)?shù)，則n有近200位，并且每一報(bào)文塊m，也近似200位．密義c由類似報(bào)文塊大小的ci構(gòu)成．加密公式Ci=Mi的e次方(mod(n))，解密時(shí)取一塊Ci并計(jì)算：Mi=ci的d次方(mod(n))．

1.2 RSA算法的內(nèi)在特性

1.2.1 存在不動(dòng)點(diǎn)

當(dāng)n是不含平方因子的整數(shù)且為k個(gè)素?cái)?shù)因子之積時(shí)，對(duì)于任何奇數(shù)e，本算法的加密操作至少有3000個(gè)不動(dòng)點(diǎn)．所以密鑰對(duì)(e,n)的取值對(duì)于整個(gè)算法的安全性非常重要．

1.2.2 具有周期性

若x為整數(shù)，n為模數(shù)，并滿足X的a+b次方與X的a次方modn為同一個(gè)等價(jià)類，則b為X的a次方modn的周期，記為per(x，n)．根據(jù)周期判定充要條件可知，若n由若干素?cái)?shù)之積組成，則&(n)由一些小因子構(gòu)成．只需知道&(n)的所有因子，私鑰d馬上可以通過公式ed=1mod&(n)求出(e與&(n)互質(zhì))。

1.2.3 對(duì)明文的要求

1的e次方=1modP，1的e次方=1modq．而e為奇數(shù)，所以(p-1)的e次方=p的-1次方modP成立，(q—1)的e次方=q的-1次方modq也成立．根據(jù)孫子定理，x=amodp=bmodq成立．當(dāng)a與b分別取+1與-1時(shí)，對(duì)應(yīng)的4個(gè)解是滿足m的e次方=mmodn與(m,n)=1的解．至少4個(gè)明文組同時(shí)滿足m的e次方=mmodn與(m,n)=1．所以，對(duì)于一些特殊明文，明文組會(huì)被加密成自己。

1.2.4 RSA算法的保密性

RSA算法的保密性在于對(duì)大數(shù)進(jìn)行因數(shù)分解，這個(gè)時(shí)間比破譯DES算法耗時(shí)長(zhǎng)得多，但從長(zhǎng)遠(yuǎn)考慮，筆者認(rèn)為選擇大于1024位長(zhǎng)的模數(shù)n較為安全．

2. 常見的RSA算法破解方法

除因子分解法外，常見的黑客攻擊方法有以下4種．

2.1 小指數(shù)攻擊法

由DES與RSA的差異分析可知，RSA算法主要基于軟件與硬件的結(jié)合實(shí)現(xiàn)，其加密速度遠(yuǎn)不如DES快．所以一些使用RSA算法進(jìn)行加密的機(jī)構(gòu)采用一種提升RSA速度并且能使加密易于實(shí)現(xiàn)的解決方案——令公鑰e取較小的值．但這樣做會(huì)使該算法的強(qiáng)度降低．若解密指數(shù)d的值為n值的114并且e<n時(shí)，使用小指數(shù)攻擊法能解密d．

2.2選擇密文攻擊

這是一種繞開RSA基本算法直接攻擊協(xié)議的方式．貿(mào)然簽名的一方容易被黑客進(jìn)行選擇密文攻擊．攻擊者E只需將某信息作一下偽裝(Blind)，讓擁有私鑰的實(shí)體A簽名，再經(jīng)計(jì)算就可得到E所想要的信息．例：E竊聽A的通訊，并設(shè)法收集用A的私鑰進(jìn)行RSA算法加密的密文c，E希望將c解密得到明文p(p=c的d次方modnn)。

E首先選擇一個(gè)小于n的隨機(jī)數(shù)r，并根據(jù)x=r的e次方modn，y=x的e次方modn，t=r的-1次方modn得到A的公鑰e．由上式可推出t=x的d次方modn．E再設(shè)法讓A用其私鑰簽名y，由此對(duì)Y解密，A發(fā)消息給E(利用u=y的d次方modn),通過以上公式，E可以計(jì)算出它本不應(yīng)該得到的P．

2.3公共模數(shù)攻擊

如果網(wǎng)絡(luò)中都使用同樣的n，容易被黑客進(jìn)行公共模數(shù)攻擊。

例：p為明文，e1和e2為加密密鑰，公共模數(shù)為n,則兩個(gè)密文為C1=p的e1次方modn，C2=p的e2次方modn，由于e1，e2，c1，C2，n都已知，又e1和e2互索，由歐幾里德算法可以求得r和s，滿足rxel+s×e2=1．設(shè)r為負(fù)數(shù)，再用歐幾里德算法可算出(C一1)與c2的乘積等于Pmodn，可見無需解密密鑰即可還原出原始明文。

2.4計(jì)時(shí)攻擊

類似于通過觀察轉(zhuǎn)動(dòng)盤轉(zhuǎn)出每個(gè)數(shù)字所用時(shí)間的方法猜測(cè)出密碼數(shù)字組合。

若攻擊者監(jiān)視解密過程并精確計(jì)時(shí)，可以計(jì)算出d．例：攻擊者根據(jù)所得到的時(shí)間t估計(jì)某個(gè)臨時(shí)明文m1，計(jì)算ml加密的時(shí)間，與t進(jìn)行比較．如果比t大，則再取個(gè)較小的臨時(shí)明文m，將m作為m1，再計(jì)算加密時(shí)間井與t比較，算法的終止條件是直至比t?。O(shè)此時(shí)的明文為m，對(duì)ml與m：進(jìn)行取中運(yùn)算，計(jì)算新生成的m的加密時(shí)間．若比t大，則取中后的m作為m1；若比t小，取中后的m作為m2再進(jìn)行循環(huán)，直至越來越靠近的ml與m2*終收斂成真正的密文m．