圖解|什么是RSA算法
本文轉載自微信公眾號「后端技術指南針」，作者指南針氪金入口。轉載本文請聯系后端技術指南針公眾號。
1. 數學之美和密碼學
前陣子閑來無事看了會兒《數學之美》，其中第17章講述了由電視劇《暗算》展開的密碼學背后的一些數學原理。
書中從凱撒密碼到二戰盟軍和日軍，講到密碼學中均勻分布&統計獨立的基礎理論，看得我津津有味，但是其中一些細節沒有整明白，于是決定搞篇文章。
2. 加密算法的一點歷史
我們知道常見的加密算法有：對稱加密和非對稱加密，非對稱加密是我們今天的主角。
非對稱加密不是一蹴而就的，它是1976年之后才出現的，可以說非對稱加密是對稱加密的優化。
2.1 對稱加密的缺點
所謂對稱加密是指：發送方使用一種規則對信息進行處理，接收方需要使用相同的規則對信息進行逆向處理。
對稱加密要求通信雙方使用相同的規則和密鑰進行加解密，這樣如何妥善保管密鑰和規則就非常重要了。
如果密鑰泄露那么再強大的對稱加密算法也是徒勞的，所以如何安全地交換對稱加密的規則和密鑰是短板。
如何安全地交換密鑰呢?讓人頭疼。
2.2 密鑰交換算法
1976年兩位美國計算機學家 Whitfield Diffie 和 Martin Hellman，提出了一種嶄新構思，可以在不傳遞密鑰的情況下，完成解密，聽著很厲害的樣子，這難道就是江湖上傳說的隔空打牛?
其實這是被稱為 Diffie-Hellman 迪菲-赫爾曼密鑰交換算法，來看看維基百科上兩位大神的簡介：
這兩位大神是密碼學的先驅，為非對稱加密算法指出了明路：雙方不一定要直接交換密鑰。
迪菲-赫爾曼密鑰交換算法中通信雙方并沒有真正交換密鑰，而是通過計算生成出一個相同的共享密鑰，具體的過程還是比較復雜，在此不展開了。
非對稱加密算法RSA借鑒了這種思想，使用公鑰和私鑰來完成加解密，但是又避免了密鑰傳輸，RSA算法的公鑰是公開的，使用公鑰加密的信息，必須使用對應的私鑰才能解密。
3. RSA算法
RSA算法可以說是地球上最重要的算法之一，是數據通信和網絡安全的基石。
3.1 算法作者
RSA是1977年由羅納德·李維斯特(Ron Rivest)、阿迪·薩莫爾(Adi Shamir)和倫納德·阿德曼(Leonard Adleman)一起提出的。
當時他們三人都在麻省理工學院工作，RSA就是他們三人姓氏開頭字母拼在一起組成的。
RSA算法密鑰越長越難破解，根據相關文獻，目前被破解的最長RSA密鑰是768個二進制位。一般認為，1024位的RSA密鑰基本安全，2048位的密鑰極其安全，RSA算法目前支持4096位長度。
密鑰長度和加解密的時間是成正比的，因此我們需要根據自己的場景來選擇密鑰長度，不必追求一味長密鑰。
3.2 算法過程
RSA算法的本質就是數學，公鑰和私鑰是數學上關聯的，無須直接傳遞。
算法過程包括：密鑰生成、密鑰加解密。
3.2.1 密鑰生成
RSA算法的密鑰是成對的，公鑰加密私鑰解密，來看下這對密鑰是如何被計算出來的。
- 1.隨機選擇兩個質數P和Q
我們選擇P=61，Q=53，計算PQ的乘積N=PQ=61*53=3233，將N轉換為二進制:110010100001，N的二進制長度是12，也就是密鑰長度為12。
本文只是闡述算法原理，在實際中密鑰長度在1024位以上才安全，12位基本上就是個演示。
- 2.求N的歐拉函數值M
歐拉函數的定義：任意給定正整數n，請問在小于等于n的正整數之中，有多少個與n構成互質關系?
歐拉函數有個通用的計算公式：
要證明歐拉函數需要分為很多種情況，特別地，當n是質數時會出現一些特殊的情況。
直接來個結論:
a. 如果k是質數，則φ(k) = k-1;
b.如果 n = P * Q，P 與 Q 均為質數，則 φ(n) = φ(P * Q)= φ(P)φ(Q) = (P - 1)(Q - 1) 。
P=61、Q=53 則N=3233，那么N的歐拉函數記為M=(P-1)*(N-1) = 60*52=3120
- 3.找一個與M互素的整數E
M和E之間除了1以外沒有公約數(互質)且E
- 4.找一個整數D，滿足如下關系：
(E*D) mod M = 1，換句話說E和D的乘積除以M的余數為1，這里有一個術語-模逆元，也就是指有一個整數d，可以使得ed被φ(n)除的余數為1。
等價于 如下計算過程：
當E=17，M=3120，K=1，2，3...時，
17*D - K*M = 1，求解這個方程找到一組滿足關系的D和K即可，可證其中一組為(D,K)=(2753,15)。
綜上所述，我們找到了通過隨機選擇的互質的P和Q計算得到N、M、E、D，我們把這些數字分為兩組：(E,N)和(D,N)分別為公鑰組和私鑰組，E是公鑰、D是私鑰。
在本例中公鑰組為(E,N)=(17,3233)，私鑰組(D,N)=(2753,3233)，接下來我們將使用這對密鑰進行加解密。
3.2.1 加密過程
由于RSA算法本質是數字的運算，因此我們在對字符串進行加密時需要先將字符串數值化，可以借助ascii碼、unicode編碼、utf-8編碼等將字符串轉換為數字。
需要特別注意轉換后的數字X需要小于密鑰組中的N，如果字符串轉換后的數字大于N則需要進行拆分，這可能也是在數據量大時我們使用對稱加密算法來加密內容，用非對稱加密算法來加密密鑰的原因吧。
加密過程滿足：
X^E mod N = Y
其中X為明文，E為公鑰，N為大整數，Y為密文，mod取余運算。
3.2.3 解密過程
我們獲得密文Y后，開始解密，過程滿足：
Y^D mod N = X
其中Y為密文，D為私鑰，N為大整數，X為明文，mod取余運算。
上述的加密和解密過程涉及到了費爾馬小定理。
3.2.4 歐拉定理和費爾馬小定理
這塊有點晦澀，但是確實RSA算法的核心部分，簡單看下吧：
費爾馬小定理給出了素數檢測性質，歐拉對其進行了證明，也就是費馬-歐拉定理。
3.3 RSA算法可靠性分析
經過上面的密鑰生成、加解密過程，我們難免要問：RSA算法可靠嗎?通過公鑰組(E,N)能否推導出私鑰D呢?
來梳理一下：
- 由于ed≡1 (mod φ(N))，只有知道e和φ(N)，才能算出d，e是公鑰匙，所以需要知道φ(N)就可以。
- 根據歐拉函數 φ(N)=(P-1)(Q-1)，只有知道P和Q，才能算出φ(N)。
- N=pq，只有將N進行因數分解，才能算出P和Q。
所以，如果大數N可以被因數分解，私鑰D就可以算出，從而破解密文。
3.5 大整數因數分解
大整數的因數分解是極其困難的，屬于NPC問題，除了暴力破解沒有很好的解決方案，目前人類分解的最大長度的二進制數為768位，1024位的長度目前尚未破解，因此1024長度的二進制密鑰是安全的。
所以RSA算法的安全性取決于大整數分解的難度，目前RSA算法可以支持4096位密鑰長度，分解難度超乎想象，即使借助于量子計算機難度和時間都是非常非常大的。
4. 總結
本文從對稱加密算法傳遞密鑰安全性為起點，說到迪菲-赫爾曼算法進行密鑰交換協商，該算法為RSA算法的公鑰和私鑰提供了靈感。
麻省理工的三位數學家在歐拉定理&費爾馬定理等等一些數學定理的基礎上創造了偉大的RSA非對稱加密算法。
RSA算法的安全性取決于大數質因數分解的難度，目前而言1024位二進制長度的密鑰人類都沒有破解，為了安全性考慮可使用2048位長度的RSA密鑰進行加密。
確實是燒腦的硬核內容啊，不由得感嘆素數真是個神奇的東西，段位有限只能拋磚引玉，到此為止啦!
