發展史
1976年以前，加密世界主要采用對稱加密算法（Symmetric-key algorithm）。
對稱加密存在讓人頭疼的問題：甲乙雙方通信，甲方必須把加密規則告訴乙方，否則無法解密。
儲存和傳遞密鑰無法確定安全？
1976年，兩位美國計算機學家Whitfield Diffie 和 Martin Hellman，"DH密鑰協定算法"。
如上所示，Alice和Bob同時擁有了共享密鑰K，私鑰a,b也未在網際網路上傳播，且公開的A\B\g\p在短時間内無法破解出a,b,K。是以DH算法便可以在不安全的網絡上協商出密鑰，基于此建構安全的加密通道。
這個算法啟發了其他科學家。人們認識到，加密和解密可以使用不同的規則，隻要這兩種規則之間存在某種對應關系即可，這樣就避免了直接傳遞密鑰。這種新的加密模式被稱為 **"非對稱加密算法"**。
如果公鑰加密的資訊隻有私鑰解得開，那麼隻要私鑰不洩漏，通信就是安全的。
1977年，三位數學家 Rivest、Shamir 和 Adleman 設計了一種算法，當時他們三人都在麻省理工學院工作。RSA 就是他們三人姓氏開頭字母拼在一起組成的，可以實作非對稱加密。從那時直到現在，RSA算法一直是最廣為使用的"非對稱加密算法"。毫不誇張地說，隻要有計算機網絡的地方，就有RSA算法。
在RSA算法中，加密密鑰（即公開密鑰）PK是公開資訊，而解密密鑰（即秘密密鑰）SK是需要保密的。加密算法E和解密算法D也都是公開的。
棱鏡門
據NSA前通訊員斯諾登所提供的機密檔案顯示，NSA跟RSA達成了一份價值1000萬美元的合同，前者通過在後者的加密軟體中植入一個缺陷公式，為自己留了一道“後門”。據悉，RSA存有缺陷公式的軟體叫做Bsafe，而該缺陷公式的名字為Dual Elliptic Curve，它由NSA開發而出。
BSafe是很多企業級使用者采購安全軟體，此舉将讓NSA通過随機數生成算法Bsafe的後門程式輕易破解各種加密資料。
RSA原理
根據數論，尋求兩個大素數比較簡單，而将它們的乘積進行因式分解卻極其困難，是以可以将乘積公開作為加密密鑰。
密鑰生成過程
步驟概述公式說明1随機p，qp,q選擇一對不相等且足夠大的質數2求nn = p*q計算質數p，q的乘積3求φ(n)φ(n) = (p-1)(q-1)計算n的歐拉函數4求e1 < e < φ(n)選一個和φ(n)互質的整數e5求ded = 1 (mod φ(n))計算出e對于φ(n)的模反元素d6公鑰e,nPK(e, n)7私鑰d,nSK(d, n)第一步：随機p，q
p，q為不相等且足夠大的質數。
質數（素數）：一個大于1的自然數，除了1和它自身外，不能被其他自然數整除的數叫做質數；否則稱為合數（規定1既不是質數也不是合數）。
代碼實作：
function isPrime(num) {
for (let i = 2; i < num; i++) {
if (num % i === 0) {
return false;
}
}
return true;
}
function getPrime(min, max) {
const rst = [];
for (let i = Math.max(2, min); i <= max; i++) {
if (isPrime(i)) {
rst.push(i);
}
}
return rst;
}
// 第一步，随機選擇兩個不相等的質數p和q
let primeList = getPrime(1, 100);
const pIndex = Math.floor(Math.random() * 1000) % primeList.length;
const p = primeList[pIndex];
primeList.splice(pIndex, 1);
const qIndex = Math.floor(Math.random() * 1000) % primeList.length;
const q = primeList[qIndex];
第二步：求n
n 的長度就是密鑰長度。
n = p * q = 11 * 3 = 33;
33寫成二進制是100001，一共有6位，是以這個密鑰就是6位。實際應用中，RSA密鑰一般是1024位，重要場合則為2048位。
代碼實作：
// 第二步 計算n 代表密鑰的長度
const n = p * q;
第三步：求n的歐拉函數φ(n)
互質關系 如果兩個正整數，除了1以外，沒有其他公因子，我們就稱這兩個數是互質關系（coprime）。比如，15和32沒有公因子，是以它們是互質關系。
公因子 是一個數學概念，指的是能同時整除幾個整數的整數，可以用輾轉相除法算出。
問題：任意兩個合數存在互質關系嗎？
例如15，44這說明，不是質數也可以構成互質關系。
互質關系結論
1. 任意兩個質數構成互質關系，比如13和61。
2. 一個數是質數，另一個數隻要不是前者的倍數，兩者就構成互質關系，比如3和10。
3. 如果兩個數之中，較大的那個數是質數，則兩者構成互質關系，比如97和57。
4. 1和任意一個自然數是都是互質關系，比如1和99。
5. p是大于1的整數，則p和p-1構成互質關系，比如57和56。
6. p是大于1的奇數，則p和p-2構成互質關系，比如17和15。
歐拉函數
任意給定正整數n，請問在小于等于n的正整數之中，有多少個與n構成互質關系？（比如φ(8)，表示在1到8之中，有多少個數與8構成互質關系？）
計算這個值的方法就叫做歐拉函數，以φ(n)表示。在1到8之中，與8形成互質關系的是1、3、5、7，是以 φ(n) = 4。
φ(n) 的計算方法并不複雜，但是為了得到最後那個公式，需要一步步讨論。
| 條件 | 公式 | 解釋 |
| 如果n=1 | φ(1) = 1 | 因為1與任何數（包括自身）都構成互質關系。 |
| 如果n是質數 | φ(n)=n-1 | 因為質數與小于它的每一個數，都構成互質關系。比如5與1、2、3、4都構成互質關系。 |
| 如果n是質數的某一個次方, n = p^k (p為質數，k為大于等于1的整數) | φ(p^k) = p^k - p^k-1 = p^k * (1 - 1/p) | 譬如 φ(8) = φ(2^3) =2^3 - 2^2 = 8 -4 = 4。這是因為隻有當一個數不包含質數p，才可能與n互質。而包含質數p的數一共有p^(k-1)個，即1×p、2×p、3×p、...、p^(k-1)×p，把它們去除，剩下的就是與n互質的數。當 k=1 時為第二種情況。 |
| 如果n可以分解成兩個互質的整數之積 | φ(n) = φ(q * p) = φ(q)φ(p) | 即積的歐拉函數等于各個因子的歐拉函數之積。比如，φ(56)=φ(8×7)=φ(8)×φ(7)=4×6=24。 |
| 因為任意一個大于1的正整數，都可以寫成一系列質數的積。 | n = p1^k1 * p2^k2... φ(n) = φ(p1^k1) * φ(p2^k2)... φ(n) = p1^k1 * p2^k2 * (1 - 1/p1)(1 - 1/p2) φ(n) = n(1 - 1/p1)(1 - 1/p2)... | φ(33) = φ(3 * 11) = 33 * (1-1/3) * (1-1/7) = 33*2/3*10/11 |
| 根據歐拉函數，求n的歐拉函數 φ(n) = φ(pq) = φ(p) φ(q) = (p-1)(q-1) |
代碼實作：
// 第三步 計算n的歐拉函數φ(n)
const oN = (p - 1) * (q - 1);
第四步：求e
随機選擇一個整數e，條件是1< e < φ(n)，且e與φ(n) 互質。
那麼是不是找出一個小于φ(n)且與φ(n)的最大公因子為1的數，這個數就是e？
歐幾裡德算法
求解最大公約數 Greatest Common Divisor(GCD)就叫歐幾裡得算法（又稱輾轉相除法），公式表示：gcd(a,b) = gcd(b,a mod b)
它的具體做法是：用較大數除以較小數，再用出現的餘數（第一餘數）去除除數，再用出現的餘數（第二餘數）去除第一餘數，如此反複，直到最後餘數是0為止。如果是求兩個數的最大公約數，那麼最後的除數就是這兩個數的最大公約數。
例如：68和3的最大公約數求解
68 % 3 = 2;
3 % 2 = 1;
2 % 1 = 0;
// 是以68和3的最大公約數是1
// 68和4的最大公約數求解
68 % 4 = 0;
// 68和4的最大公約數是4
代碼實作：
function gcd(a, b) {
// return b === 0 ? a : gcd(b, a%b)
let big = a;
let small = b;
if (a < b) {
big = b;
small = a;
}
return big % small === 0 ? small : gcd(big % small, small);
}
現在隻要滿足 gcd(x, φ(n))===1 則x就是我們要找的e，因為滿足 1< e < φ(n) 條件下和φ(n)互質的數不止一個，下面羅列所有的互質數然後随機選出一個就是e。
代碼實作：
const primeList = [];
for (let i = 1; i < oN; i++) {
if (gcd(i, oN) === 1) {
primeList.push(i);
}
}
const index = Math.floor(Math.random() * (primeList.length - 1)) + 1;
const e = primeList[index];
第五步：求d
求e對與φ(n)的模反元素d，根據歐拉定理得出以下公式：
ed ≡ 1 (mod φ(n))
歐拉定理
歐拉函數是根據歐拉定理計算的。
如果兩個正整數a和m互質，則m的歐拉函數 φ(m) 可以讓下面的等式成立：
也就是a的φ(m)次方被m除的餘數為1。或者說，a的φ(m)次方減去1，可以被m整除。
比如，3和7互質，而7的歐拉函數φ(7)等于6，是以3的6次方（729）減去1，可以被7整除（728/7=104）。
譬如求3和5互質，根據歐拉定理：
3^φ(5) = 1 (mod 5);
3^4 mod 5 = (3^4)%5 = 1;
歐拉定理有一個特殊情況。
假設正整數a與質數p互質，因為質數p的φ(p)等于p-1，則歐拉定理可以寫成:
這就是著名的費馬小定理。它是歐拉定理的特例。
歐拉定理是RSA算法的核心。了解了這個定理，就可以了解RSA。
模反元素
模反元素也稱為模倒數，或者模逆元。
一整數a對同餘n之模逆元是指滿足以下公式的整數 b：
公式為定理，如何推倒請看定理的推導過程。
也可以寫成以下的式子（定理）：
或者：
解釋：如果兩個正整數a和n互質，那麼一定可以找到整數b，使得 ab-1 被n整除，或者說ab被n除的餘數是1。
這時，b就叫做a的"模反元素"。
例如：3和11互質，那麼3的模反元素就是4，因為 (3 × 4)-1 可以被11整除。顯然，模反元素不止一個， 4加減11的整數倍都是3的模反元素 {...,-18,-7,4,15,26,...}，即如果b是a的模反元素，則 b+kn 都是a的模反元素。
可以用上述的歐拉定律來證明模範元素必然存在：
可以看到，a的 φ(n)-1 次方，就是a的模反元素。
換算以上公式：
ed ≡ 1 (mod φ(n))
ed - 1 = k\*φ(n)
**ed + φ(n)k = 1**
ax+by=1
因為e和φ(n)已知，實則求解而二進制一次方程d和k。
假設已知 e=17, φ(n)=3120，以上公式轉換為：
17x + 3120y = 1
那如何求解此二進制一次方程的解？
擴充歐幾裡德算法
利用擴充歐幾裡得算法計算乘法逆元。
擴充歐幾裡得算法（英語：Extended Euclidean algorithm）是歐幾裡得算法（又叫輾轉相除法）的擴充。已知整數a、b，擴充歐幾裡得算法可以在求得a、b的最大公約數的同時，能找到整數x、y（其中一個很可能是負數），使它們滿足貝祖等式：
如果a是負數，可以把問題轉化成為 ∣a∣(−x)+by=gcd(∣a∣,b)
|a|為a的絕對值，然後令:
x'=(-x)
歐幾裡德算法停止的狀态是：
a=gcd(a,b), b=0; x=1
由于歐幾裡德算法：
gcd(a, b) = gcd(b, amodb)
得出：
gcd(a，b) = ax+by
gcd(b, amodb) = bx1 + (amodb)y1
是以：
ax+by = bx1 + (amodb)y1
又因：
amodb=a−⌊a/b⌋b
例如：
11%3 = 11 - Math.floor(11 / 3)*3 = 11-9 = 2
是以：
ax+bx = bx1 + (a- ⌊a/b⌋b)y1
ax+bx = by1 + b(x1- ⌊a/b⌋y1)
推導出：x = y1
y=x1−⌊a/b⌋y1
采用遞歸先求解第一層x1、y1，再不斷疊代到上一層，不斷遞歸直到一組得到特解x=1,y=0停止。即：當b = 0時，ax+by = a故而x=1, y=0。
算法實作：
#include <bits/stdc++.h>
using namespace std;
int ext_euc(int a, int b, int &x, int &y)
{
if (b == 0)
{
x = 1, y = 0;
return a;
}
int x1, y1, d;
int d = ext_euc(b, a % b, x1, y1);
x = y1;
y = x1 - a/b * y1;
return d;
}
int main()
{
int a, b, x, y;
cin >> a >> b;
ext_euc(a, b, x, y);
cout << x << ' ' << y << endl;
return 0;
}
模拟執行：
假設 p=3, q=5, e=5，φ(n)=(3-1)*(5-1)=8
ext_euc(8,5,x,y) {d = ext_euc(5,1,x,y)}
ext_euc(5,1,x,y){d = ext_euc(1,0,x,y)}
ext_euc(1,0,x,y){x=1,y=0,return 1;}
ext_euc(5,1,x,y){d=1,x=0,y=1-5/1*0=1,return 1;}
ext_euc(8,5,x,y){d=1,x=1,y=0-8/5*1=-1,return 1;}
得出x = 1, y = -1;
js代碼實作：
const xyObj = { x: null, y: null };
function exGCD(a, b, xyObj) {
// 特解 ax + 0 * y = gcd(a, b); 當x=1,b=0時，a = gcd(a, 0);
if (b === 0) {
xyObj.x = 1;
xyObj.y = 0;
return a;
}
const ans = exGCD(b, a % b, xyObj);
const { x, y } = xyObj;
xyObj.y = x - Math.floor(a / b) * y;
xyObj.x = y;
return ans;
}
// e*x + oN*y = 1
exGCD(e, oN, xyObj);
while (xyObj.x < 0) {
xyObj.x += oN;
}
const d = xyObj.x;
第六步：公鑰和私鑰
公鑰：PK(n, e)
私鑰：SK(n, d)
加密
加密要用公鑰 (n,e)，所謂加密就是算出以下公式的c，等價于m的e次方除以n餘數為c，m為被加密對象，m必須是整數，且m必須小于n。
假設A的公鑰是(23, 3)，B的m假設是65，那麼算出以下等式：
公鑰(n,e) 隻能加密小于n的整數m，那麼如果要加密大于n的整數，該怎麼辦？
解密
解密要用私鑰(n,d)，所謂解密就是算出以下公式的m，等價于c的d次方除以n的餘數為m。
私鑰證明
根據加密公式
将 c 代入需要證明的那個密鑰規則：
等同于求證：
由于
ed ≡ 1 (mod φ(n))
ed = hφ(n) + 1
将ed代入：
φ
- 若m與n互質，根據歐拉定理: φ
得到：
φ
- m與n不是互質關系
參見：RSA加密算法【維基百科】
RSA算法的可靠性
那麼，有無可能在已知公鑰PK(n, e)的情況下，推導出d？
（1）ed≡1 (mod φ(n))。隻有知道e和φ(n)，才能算出d。
（2）φ(n)=(p-1)(q-1)。隻有知道p和q，才能算出φ(n)。
（3）n=pq。隻有将n因數分解，才能算出p和q。
結論：如果n可以被因數分解，d就可以算出，也就意味着私鑰被破解。
但至今為止還沒有人找到一個多項式時間的算法來分解一個大的整數的因子，同時也還沒有人能夠證明這種算法不存在，目前，除了暴力破解，還沒有發現别的有效方法。
對極大整數做因數分解的難度決定了RSA算法的可靠性。換言之，對一極大整數做因數分解愈困難，RSA算法愈可靠。
假如有人找到一種快速因數分解的算法，那麼RSA的可靠性就會極度下降。但找到這樣的算法的可能性是非常小的。今天隻有短的RSA密鑰才可能被暴力破解。到現在為止，世界上還沒有任何可靠的攻擊RSA算法的方式。
根據已經披露的文獻，目前被破解的最長RSA密鑰是768個二進制位。隻要密鑰長度足夠長，用RSA加密的資訊實際上是不能被解破的。
一般認為認為，1024位的RSA密鑰基本安全，2048位的密鑰極其安全。
參考來源
https://zh.wikipedia.org/zh-cn/RSA%E5%8A%A0%E5%AF%86%E6%BC%94%E7%AE%97%E6%B3%95
https://zh.wikipedia.org/wiki/%E6%A8%A1%E5%8F%8D%E5%85%83%E7%B4%A0
https://zh.wikipedia.org/wiki/擴充歐幾裡得算法
https://zh.wikipedia.org/wiki/%E8%BC%BE%E8%BD%89%E7%9B%B8%E9%99%A4%E6%B3%95
https://www.bilibili.com/video/BV1rD4y1C7qg/?zw
https://juejin.cn/post/7044863141062115341
https://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
https://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
https://www.aqniu.com/news-views/942.html
作者:闫俊啟
來源:微信公衆号:奇舞精選
出處:https://mp.weixin.qq.com/s/mXMey_uAAkt-W02KP78p_Q