RSA 這倆世紀(jì)最重要的算法之一
Diffie–Hellman加密算法的劣勢
上一篇文章我們聊到 Diffie–Hellman key exchange 這個算法。（密鑰交換有點不安全），雖然可以安全地交換密鑰從而使用 AES，DES 等對稱加密算法進(jìn)行加密，但是卻有一個天大的問題。就是他娘的，跟一個人通訊就要保存一個密鑰，跟一百個人通訊就要保存一百個密鑰，A 遲早會崩潰。
密鑰崩潰中
RSA 算法的來歷
所以科學(xué)家就思考，能不能減少密鑰的個數(shù)呢？？這時候大佬就想到了，街頭上的郵筒。
郵筒是一個公開的地方，所有人都可以往里面投遞信件（傳遞信息），但是只有擁有郵筒的郵筒管理員才能打開這個郵筒進(jìn)行信件的攬收（信息獲取）。
雖然這個例子舉得不是很恰當(dāng)啊。但是是大概是這么一個意思，就是能不能將一個公開的加密的密鑰分發(fā)給其他人，其他人用這個密鑰進(jìn)行加密，而只有擁有私鑰的人才能進(jìn)行解密呢？
來來來 RSA 算法了解一下。
RSA
RSA是1977年由羅納德·李維斯特（Ron Rivest）、阿迪·薩莫爾（Adi Shamir）和倫納德·阿德曼（Leonard Adleman）一起提出的。當(dāng)時他們?nèi)硕荚诼槭±砉W(xué)院工作。RSA就是他們?nèi)诵帐祥_頭字母拼在一起組成的。
但是呢，其實 RSA 算法并不是1977年被發(fā)明的，早在1973年，英國國家通信總局的數(shù)學(xué)家 Clifford Cocks 就發(fā)現(xiàn)了類似的算法，他的研究一被發(fā)現(xiàn)，立馬被列為絕密，直到1998年才得以公諸于世。
RSA應(yīng)用
說 RSA 加密算法是上世紀(jì)和本世紀(jì)最重要的算法之一絕不為過，RSA 是一種基于大數(shù)因式分解為保證的非對稱加密算法，廣泛應(yīng)用在數(shù)字簽名、數(shù)據(jù)加密等領(lǐng)域，是***個同時能夠數(shù)據(jù)簽名以及數(shù)據(jù)加密的算法。所以其實公鑰和私鑰是一個相對的概念，大家不要糾結(jié)了，這個算法是雙向的，用公鑰加密的數(shù)據(jù)，只能用私鑰解密。用私鑰加密的數(shù)據(jù)，只能用公鑰解密。這樣一來一回呢，公鑰加密就的數(shù)據(jù)傳輸?shù)膽?yīng)用就變成了加密（加密在不安全信道中的數(shù)據(jù)傳輸），私鑰加密的數(shù)據(jù)應(yīng)用就變成了數(shù)據(jù)簽名（檢驗?zāi)硞€數(shù)據(jù)是不是真的來自A）。
RSA的工作過程
好了，為了表達(dá)我是真的自己搞了一遍，證明過程了解一下。
算法分為五步。
1、選擇 p、q兩個比較大的質(zhì)數(shù)
2、令n = p * q。取 φ(n) （歐拉函數(shù)自行度娘），
3、取 e ∈ 1 < e < φ(n) ，( n , e )為公鑰對
4、令 ed mod φ(n) = 1，取得d，( n , d ) 為私鑰對。
5、銷毀 p、q。密文 = 明文 ^ e mod n ， 明文 = 密文 ^ d mod n
嗯，算法就是這么簡單。但是其實可以很簡單證明。
(明文 ^ e mod n)^d mod n = (明文 ^ d mod n)^e mod n
RSA如何保證安全？
如何破譯？算法如何保證安全？
我們可以看到，經(jīng)過上面的過程，出現(xiàn)了 p、q、n、φ(n)、e、d 這么多數(shù)字。那么如何破解d這個私鑰呢？？
step1：e*d mod φ(n) = 1。
如果知道了φ(n)，而e又是公開的，那么d就被解密了。
step2：φ(n) = φ(p * q) = φ(p) * φ(q) = (p-1)(q-1)
好如果知道了 pq，那么φ(n)也是可以計算出來的。
step3：如何知道p、q呢？n = p * q。
將公開數(shù)據(jù) n 進(jìn)行因式分解就可以得到 p、q了。但是現(xiàn)在大數(shù)因式分解都是一個世界大難題。所以RSA只要密鑰不泄露，那么信息就是安全的。
RSA為什么可以被加解密？
下面證明一下為什么上邊的算法可以進(jìn)行加解密。假設(shè)明文為 m（message），密文為 c (crypted)。
- 加密過程
- c = m ^ e mod n
- 解密過程：
- m
- = c ^ d mod n（代入c）
- = (m ^ e mod n)^ d mod n（進(jìn)行模計算變換）
- = m ^ (e * d) mod n
- ∵ e * d mod φ(n) = 1
- ∴e * d = k * φ(n) + 1 （k為整數(shù)）
- ∴
- m
- = m ^ (k * φ(n) + 1) mod n
- = m ^ (k * φ(n)) * m mod n
- 若m與n互質(zhì)，那么m ^ (k * φ(n)) mod n = 1 （歐拉公式）
那么上式子 可得直接等于 m。原題得證。RSA 原始論文也只討論了m與n互質(zhì)的情況，但是阮一峰老師還證明了另外一種情況，就是 m與n 如果不互質(zhì)呢？？這種情況我上面也證明了，感興趣的小伙可以了解一下。
【本文為51CTO專欄作者“大蕉”的原創(chuàng)稿件，轉(zhuǎn)載請通過作者微信公眾號“一名叫大蕉的程序員”獲取授權(quán)】
