1、RSA加密原理：

　　1. 數(shù)據(jù)。

　　數(shù)據(jù)在計算機中，其實就是字節(jié)串。

　　將被加密的數(shù)據(jù)，分割成一定長度的數(shù)據(jù)塊，每一塊就是一個bit串。

　　將這個比特串，看成一個二進制整數(shù)——以d表示

　　2. 密鑰

　　RSA算法是非對稱算法，因此使用兩個密鑰：

　　一個是公鑰，用于加密——以e表示，

　　一個是私鑰，用于解密——以p表示。

　　另外，還需要用到一個整數(shù)N，他是算法中進行模數(shù)運算時的底數(shù)。

　　一般來說，為了保證安全性，密鑰長度應在1024-bit以上。

　　總之，e、p、N，這三項數(shù)據(jù)，決定一次具體的加解密活動。

　　同被加密數(shù)據(jù)d一樣，e、p、N，這三個東東，也都是整數(shù)。

　　e、N，是對外公開的。而p則不對外公開。

　　3. 加解密

　　a）加密

　　c = d^e mod N /* d的e次方模上N，得到c，即加密后的數(shù)據(jù)*/

　　b）解密

　　d = c^p mod N /* c的p次方模上N，得到d，即原始數(shù)據(jù)*/

　　4. 安全性

　　RSA算法的安全在于，e、p、N，是隨機生成的。

　　知道e和N，想尋找p，在計算上是不可行的。

　　問題是，我們使用的軟件工具，生成這些隨機材料時，真的是“隨機”的嗎？

　　如果算法的提供者留下什么后門，或者提前做了什么準備工作，人家看到e和n，或許就能有辦法得到p呢。

　2、RSA加密算法的描述

　　RSA算法是一個基于初等數(shù)論定理的公鑰密碼體制加密算法，它的實現(xiàn)過程為：選取2個大素數(shù)p與q，然后算出n=pq，φ（n）=n－p－q＋1，再選取一個正整數(shù)e，使之滿足（e，φ（n））=1，1《E《Φ（N）；再求出正整數(shù)D，使之滿足1《D，而密鑰是。明文消息m滿足0≤m

　　例 取2個質(zhì)數(shù)p=11，q=13，p和q的乘積為n=p×q=143，算出φ（n）=n-p-q+1=120；再選取一個與φ（n）互質(zhì)的數(shù)，例如e=7，則公開密鑰=n，e=143，7.

　　對于這個e值，用歐幾里德擴展算法可以算出其逆：d=103.因為e×d=7×103=721，滿足e×d mod z =1；即721 mod 120=1成立。則秘密密鑰=n，d=143，103，

　　設發(fā)送方需要發(fā)送機密信息（明文）m=85，發(fā)送方已經(jīng)從公開媒體得到了接收方的公開密鑰n，e=143，7，于是發(fā)送方算出加密后的密文c= me mod n=857 mod 143=123并發(fā)送給接收方。

　　接收方在收到密文c=123后，利用只有他自己知道的秘密密鑰計算m= cd mod n =123103 mod 143=85，所以，接收方可以得到發(fā)送方發(fā)給他的真正信息m=85，實現(xiàn)了解密。

　　用RSA體制加密時，先將明文數(shù)字化再進行加密，在實際應用中m值的長度一般要遠大于n的長度，因此實際加密消息m時，首先將它分成比n小的數(shù)據(jù)分組（采用二進制數(shù)，選取小于n的2的最大次冪），再每組單獨加密和解密。比如說，選用的p和q為100位的素數(shù)，那么n將有200位，每個數(shù)據(jù)分組應小于200位長，但為保證安全性，每個數(shù)據(jù)的長度應盡量接近n的長度。

　　3、RSA算法的加密強度與因子分解強度

　　目前密碼的破譯主要有2種方法。方法之一是密鑰的窮盡搜索，其破譯方法是嘗試所有可能的密鑰組合。雖然大多數(shù)的密鑰嘗試都是失敗的，但最終有一個密鑰讓破譯者得到原文，這個過程稱為密鑰的窮盡搜索。方法之二是密碼分析。由于RSA算法在加密和解密過程都是用指數(shù)計算，其計算工作量巨大，用窮盡搜索法進行破譯是根本不可能的。因此要對RSA算法加密后的信息進行破譯只能采用密碼分析法，用密碼分析法攻擊RSA密碼系統(tǒng)，途徑之一是直接計算“n的e次方根”，但目前還沒有解決這一問題的算法，這個問題是現(xiàn)實不可計算的問題；途徑之二［4］是想辦法計算出d，欲得到d，可考慮從以下3個方面入手。

　?。?） 將數(shù)n分解因子

　　密碼分析員一旦分解出n的因子p和q，就可以先后求出φ（n）和d，從而攻破RSA公開鑰密碼系統(tǒng)．由此得出如下結論：破譯RSA密碼不可能比分解因子的問題更困難。

　?。?） 不分解n的因子計算φ（n）

　　顯然，如果密碼分析員能夠求出φ（n），由于e是公開的，就可以通過de≡1 （modφ（n））算出d，從而攻破RSA密碼系統(tǒng)。但是，一旦密碼分析員知道了φ（n），他就可以很容易地分解出n的因子。究其原因為

　　φ（n）＝n-（p+q）+l，

　　所以，由n及φ（n）可以計算出（p+q）．有了（p+q），就可以通過p-q=（p+q）2-4n求出（p-q），因而最終解出p和q.計算φ（n）的方法并不比分解n的因子容易，換言之，通過計算φ（n）破譯RSA密碼的方法不會比通過分解n的因子破譯RSA密碼的方法更容易。

　?。?） 不分解n的因子或計算φ（n）確定d

　　如果能夠知道d，分解n的因子問題也同樣會變得容易起來。因為φ（n）＝（ed-1）×k，其中k為任意整數(shù)，已知d （e 是公開的）時，可求出φ（n），根據(jù)φ（n）＝n-（p+q）+l，由于n是已知的（公開的），在求出φ（n）時可求出p+q，設求出的p+q=r，又由于n=p×q，從而可得p×p-p×r+n=0，這是一個一元二次方程，自然可非常簡單求出p，同理可求出q，分解n完成．

　　G. L. Miller在1975年指出，利用φ（n）的任何倍數(shù)都可以容易地分解出n的因子。因此，用Miller算法就可以由（ed-1）分解出n的因子，也就是說計算d并不比分解n的因子更容易。密碼分析員還可能希望找到某個與d等價的d′，從而攻破RSA密碼。但是，所有這樣的d′只相差（p-1）和（q-1）的最小公倍數(shù)的整數(shù)倍，因此，找到一個這樣的d′就可以使分解n的因子問題變得容易起來，也即找到這樣的d′并不比分解n的因子更容易。

　　綜上所述，破譯RSA密碼系統(tǒng)和分解因子問題同樣困難，盡管目前還不能完全證實它，即在目前狀況下，如果參數(shù)p，q和e選取恰當?shù)脑?，RSA的加密強度，就取決于的抗因子分解強度。

　　4、 大數(shù)因子分解的難度

　　著名數(shù)學家費馬（1601—1665）和勒讓德（（1752—1833）都研究過分解因子的算法，現(xiàn)代某些更好的算法是勒讓德方法的擴展．其中，R. Schroeppel算法是好算法中的一類，用此法分解因子仍然需要大約eln nlnln n次運算，其中l(wèi)n表示自然對數(shù)，可見分解n 所需的運算次數(shù)與密鑰的長度有關，隨著密鑰長度的增加，分解所需的時間會成指數(shù)倍增加。對于不同長度的十進制數(shù)n，Schroeppel算法分解n的因子時所需的運算次數(shù)如表1所示。

　　若用1臺1 s能進行1億次因子分解的高速計算機來計算，分解十進制長度為200位的n，其所需時間為3 800 000年。由此可見，對于RSA系統(tǒng)，如果用一個長度為200位（十進制）的n，認為它是比較安全的，如果n的長度更長，因子分解越困難，一般來說，每增加10位二進制數(shù)，分解的時間就要加長1倍。密碼就越難以破譯，加密強度就越高。

　　不過隨著計算機運算速度的提高和并行計算的發(fā)展，破解的速度也會同步提高，這時可能要求使用更長的密鑰。

　　RSA的安全性依賴于大數(shù)的因子分解，這樣攻擊RSA系統(tǒng)的難度就是大整數(shù)因子分解的難度，一般認為這是一個NPC問題，盡管尚未在理論上證明分解因子的問題一定困難，但千百年來經(jīng)過眾多學者的研究，迄今沒有找到一種有效算法，絕大多數(shù)數(shù)論學家傾向于認為不存在大整數(shù)因子分解的多項式算法，因此目前這一破譯只能依賴于現(xiàn)代的計算機技術，用程序進行嘗試分解，從而對大數(shù)的因子分解。不過隨著計算機運算速度的提高和并行計算的發(fā)展，加上因子分解方法的改進，低位數(shù)的密鑰的破解已成為可能。因子分解需的時間隨密鑰長度的增加而成指數(shù)指增加，只要n的長度達到一定要求，并且參數(shù)p，q和e選取恰當?shù)脑?，RSA系統(tǒng)是相當安全的.