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