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