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

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

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

 

1. RSA算法原理及內在特性

 

1.1 RSA算法描述

 

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

 

1.2 RSA算法的內在特性

 

1.2.1 存在不動點

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

 

1.2.2 具有周期性

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

 

1.2.3 對明文的要求

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

 

1.2.4 RSA算法的保密性

 

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

 

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

 

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

 

2.1 小指數攻擊法

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

 

2.2選擇密文攻擊

這是一種繞開RSA基本算法直接攻擊協議的方式．貿然簽名的一方容易被黑客進行選擇密文攻擊．攻擊者E只需將某信息作一下偽裝(Blind)，讓擁有私鑰的實體A簽名，再經計算就可得到E所想要的信息．例：E竊聽A的通訊，并設法收集用A的私鑰進行RSA算法加密的密文c，E希望將c解密得到明文p(p=c的d次方modnn)。E首先選擇一個小于n的隨機數r，并根據x=r的e次方modn，y=x的e次方modn，t=r的-1次方modn得到A的公鑰e．由上式可推出t=x的d次方modn．E再設法讓A用其私鑰簽名y，由此對Y解密，A發消息給E(利用u=y的d次方modn),通過以上公式，E可以計算出它本不應該得到的P．

 

2.3公共模數攻擊

如果網絡中都使用同樣的n，容易被黑客進行公共模數攻擊。例：p為明文，e1和e2為加密密鑰，公共模數為n,則兩個密文為C1=p的e1次方modn，C2=p的e2次方modn，由于e1，e2，c1，C2，n都已知，又e1和e2互索，由歐幾里德算法可以求得r和s，滿足rxel+s×e2=1．設r為負數，再用歐幾里德算法可算出(C一1)與c2的乘積等于Pmodn，可見無需解密密鑰即可還原出原始明文。

 

2.4計時攻擊

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