RSA是在Diffe-Hellman算法問(wèn)世兩年之后，由Rivest、Shamir和Adelman在MIT研究出的，并于1978年公布。

---

RSA系統(tǒng)利用這樣的事實(shí)：模運(yùn)算中冥的自乘數(shù)是容易解的。RSA的加密方程為：

這里，密文C是信息m自乘指數(shù)冪e并除以模數(shù)n后的余數(shù)。這可以由任何一個(gè)知道信息m、模數(shù)n和加密指數(shù)e的計(jì)算機(jī)迅速完成。另一方面，將這一個(gè)過(guò)程反過(guò)來(lái)，根據(jù)em$e^m$ 根求膜n。對(duì)任何一個(gè)不知道n因子的人來(lái)說(shuō)，這是很困難的。
RSA系統(tǒng)非常適合用于制作用于制作數(shù)學(xué)特征和某些加密應(yīng)用。但是，常常要求制作保密密鑰，以便直接用于保存密鑰保密系統(tǒng)，這需要使用另外一個(gè)單向函數(shù)。

（在g自乘冪x后，然后除以p，x為余數(shù)）

RSA特點(diǎn)

1. 密鑰配發(fā)十分方便，用戶的公用密鑰可以像電話號(hào)碼一樣公開(kāi)，使用方便。這對(duì)網(wǎng)絡(luò)環(huán)境眾多用戶的系統(tǒng)，密鑰管理更加便捷。每個(gè)用戶只需要只有一對(duì)密鑰即可實(shí)現(xiàn)與網(wǎng)路中任何一個(gè)用戶的保密通信。
2. RSA加密原理基于單向函數(shù)，非法接受者利用公用密鑰不可能在有限的時(shí)間內(nèi)推算出秘密密鑰，這種算法的保密性好。
3. RSA在用戶確認(rèn)和實(shí)現(xiàn)數(shù)組簽名方面優(yōu)于現(xiàn)有的其他加密機(jī)制。
4. RSA的加密速度是一個(gè)缺陷。由于進(jìn)行的都是大數(shù)運(yùn)算，使得RSA最快的情況也比DES慢上好幾倍。由于這些限制，RSA目前主要用于網(wǎng)絡(luò)環(huán)境中少量的數(shù)據(jù)加密。
5. RSA數(shù)字簽名是一種強(qiáng)有力的認(rèn)證鑒別方式，他可以確保接收方能夠判斷發(fā)送方的真實(shí)身份。

是不是有點(diǎn)一頭霧水？別急，前面的都不重要，到這里我們只需要腦子里有一點(diǎn)概念，RSA實(shí)現(xiàn)原理是于一個(gè)單向函數(shù)就OK了。下面我們將以例子的形式來(lái)進(jìn)行分析說(shuō)明。

RSA公開(kāi)密鑰密碼系統(tǒng)

首先我們先梳理RSA的使用機(jī)制。

RSA要求每一個(gè)用戶擁有自己的一種密鑰。
* 公開(kāi)的加密密鑰，用來(lái)加密明文
* 保密的解密密鑰，用來(lái)解密密文
這是一對(duì)非對(duì)稱密鑰，又稱為公用密鑰體制(Public Key Cryptosystem )。

在RSA密鑰體制運(yùn)行中，當(dāng)A用戶發(fā)送文件給B用戶時(shí)，A用戶用B用戶公開(kāi)的密鑰加密明文，B用戶則用解密密鑰解讀密文。

下面將用一個(gè)簡(jiǎn)單的例子來(lái)說(shuō)明RSA公開(kāi)密鑰密碼系統(tǒng)的工作原理。

1. 隨機(jī)取兩個(gè)質(zhì)數(shù)。
   例如p=11,q=13.（實(shí)際應(yīng)用中，著兩個(gè)質(zhì)數(shù)越大，越難破解）
2. 計(jì)算p和q的乘積n。
   n = p*q = 11*13 = 143
   (此時(shí)n的長(zhǎng)度就是密鑰的長(zhǎng)度，此時(shí)n=143，轉(zhuǎn)化成二進(jìn)制為1000 1111 ，一共是8位，實(shí)際應(yīng)用中一般用1024-2048位)
3. 計(jì)算n的歐拉函數(shù)φ(n)。
   　　由公式φ(n) = (p-1)(q-1)
   　　可得出此時(shí)φ(n) = 120。
4. 隨機(jī)選擇一個(gè)與φ(n)互質(zhì)的數(shù),取值范圍為1~φ(n)。
   例如這里我們隨機(jī)選擇 e = 7。（稱為“公開(kāi)指數(shù)”）
5. 計(jì)算e對(duì)于φ(n)的摸反元素d。
   d的值需要滿足e×d=1mod(φ(n))$e\times d=1mod(\phi (n))$這個(gè)等式相當(dāng)于(e×d)mod(φ(n))=1$(e\times d)mod(\phi (n))=1$，可得出d = 103。其實(shí)7*103 = 721除以120確實(shí)余1。
   到此，我們的公開(kāi)密鑰和私有密鑰都已經(jīng)計(jì)算完畢。此時(shí)最開(kāi)始取的兩個(gè)質(zhì)數(shù)已經(jīng)沒(méi)有作用了，但是不能泄露。
6. 分裝密鑰
   其實(shí)（n,e）就是公開(kāi)密鑰（n，d）就是私密密鑰
   那么此時(shí)的公開(kāi)密鑰是(143,7),私密密鑰是(143,103)
7. 利用公開(kāi)密鑰加密明文
   設(shè)想需要發(fā)送機(jī)密信息（明文，即未加密的報(bào)文）s = 85 ，已經(jīng)獲得了上面的公鑰(n,e) = (143,7)。于是算出加密值：
   
   c=Semodn=857mod143=123$$c=S^{e}modn={85}^{7}mod143=123$$
8. 利用解密密鑰解密密文
   在收到上面加密后的密文c = 123 后，在利用上面的私密密鑰(n,d) = (143,103)來(lái)還原本來(lái)的信息。
   
   s=cdmodn=123103mod143=85$$s=c^{d}modn={123}^{1}03mod143=85$$
   
   通過(guò)上面的私密密鑰的解密，我們就得到了真正的信息s=85。
9. 私鑰解密的證明
   有沒(méi)有好奇，為什么我們通過(guò)私密密鑰還原密文就可以得到原來(lái)的信息。下面來(lái)我們來(lái)進(jìn)行證明：
   就本例而言：其實(shí)也就是證明：
   
   cd=s(mod(n))$$c^d=s(mod(n))$$
   
   根據(jù)加密規(guī)則： se=c（mod(n)）$s^e=c（mod(n)）$,可以得到：
   
   c=Se?k×n$$c=S^e?k\times n$$
   
   將c代入解密規(guī)則，得：
   
   (se?k×n)d=s(mod(n))$$(s^e?k\times n{)}^d=s(mod(n))$$
   
   化簡(jiǎn)，得：
   
   Sed=S(mod(n))$$S^{ed}=S(mod(n))$$
   
   由于e×d=1(mod(φ(n)))$e\times d=1(mod(\phi (n)))$,有
   
   e×d=hφ(n)+1$$e\times d=h\phi (n)+1$$
   
   將ed代入，得：
   
   Shφ(n)+1=s(mod(n))$$S^{h\phi (n)+1}=s(mod(n))$$
   
   接下來(lái)，分成兩種情況證明上面的式子：
   (1) s與n互質(zhì)。
   根據(jù)歐拉定理，此時(shí)：
   
   sφ(n)=1(mod(n))$$s^{\phi (n)}=1(mod(n))$$
   
   得到：
   
   (sφ(n))h=s(mod(n))$$(s^{\phi (n)}{)}^h=s(mod(n))$$
   
   得證。
   (1) s與n不互質(zhì)。
   比較復(fù)雜，就不做詳細(xì)證明。具體請(qǐng)參考博客
   關(guān)鍵一點(diǎn)，設(shè)s = kp;然后運(yùn)行歐拉定理。

---

在上面的例子中，n= 143只是示意的，用來(lái)說(shuō)明RSA的計(jì)算過(guò)程。從143找出他的質(zhì)數(shù)因子11和13不困難。但對(duì)于巨大的指數(shù)q和p，計(jì)算乘積n=p×q$n=p\times q$ 非常簡(jiǎn)單，但是逆運(yùn)算卻是非常難的。這是一種“單向性”的預(yù)算。相應(yīng)的函數(shù)稱為“單向函數(shù)”。任何單向函數(shù)都可以作為某一種公開(kāi)密鑰密碼系統(tǒng)的基礎(chǔ)，而單向函數(shù)的安全性也就是這種公開(kāi)密鑰密碼系統(tǒng)的安全性。

還是不是很理解？沒(méi)關(guān)系，可以參考源碼：

待添加

或者，下載加密演示exe。

–資源預(yù)計(jì)明天上傳，正在編寫(xiě)中。