RSA加密算法的特性及其破解方案

來源：超時代軟件     更新時間：2013年01月15日 18:53:06

作者：周緋菲 潘杰；整理：超時代軟件(主要產(chǎn)品視頻加密、共享文件夾加密、U盤防拷貝)

 

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

 

1.1 RSA算法描述

 

在該箅法中，公鑰和私鑰是兩個大素數(shù)的函數(shù)，從其中一個密鑰和密文恢復(fù)明文等價于將兩個素數(shù)的乘積因子分解．為生成這兩個密鑰，選擇兩個大素數(shù)P和q，計算其乘積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為私鑰，兩個素數(shù)P和q和不再用到，但不能泄露．加密報文時，首先將m分成若干以數(shù)字表示的塊，使得每塊都有一個模n表示，即如果P和q均為100位的十進(jìn)制素數(shù)，則n有近200位，并且每一報文塊m，也近似200位．密義c由類似報文塊大小的ci構(gòu)成．加密公式Ci=Mi的e次方(mod(n))，解密時取一塊Ci并計算：Mi=ci的d次方(mod(n))．

 

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

 

1.2.1 存在不動點

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

 

1.2.2 具有周期性

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

 

1.2.3 對明文的要求

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時，對應(yīng)的4個解是滿足m的e次方=mmodn與(m,n)=1的解．至少4個明文組同時滿足m的e次方=mmodn與(m,n)=1．所以，對于一些特殊明文，明文組會被加密成自己。

 

1.2.4 RSA算法的保密性

 

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

 

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

 

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

 

2.1 小指數(shù)攻擊法

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

 

2.2選擇密文攻擊

這是一種繞開RSA基本算法直接攻擊協(xié)議的方式．貿(mào)然簽名的一方容易被黑客進(jìn)行選擇密文攻擊．攻擊者E只需將某信息作一下偽裝(Blind)，讓擁有私鑰的實體A簽名，再經(jīng)計算就可得到E所想要的信息．例：E竊聽A的通訊，并設(shè)法收集用A的私鑰進(jìn)行RSA算法加密的密文c，E希望將c解密得到明文p(p=c的d次方modnn)。E首先選擇一個小于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，由此對Y解密，A發(fā)消息給E(利用u=y的d次方modn),通過以上公式，E可以計算出它本不應(yīng)該得到的P．

 

2.3公共模數(shù)攻擊

如果網(wǎng)絡(luò)中都使用同樣的n，容易被黑客進(jìn)行公共模數(shù)攻擊。例：p為明文，e1和e2為加密密鑰，公共模數(shù)為n,則兩個密文為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計時攻擊

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