话题：#科学# #数学# #密码学# #算法#
小石头/编
RSA（Rivest-Shamir-Adleman）是一种非对称加密算法，密钥 分为 公钥 PK=(e, n) 和 私钥 SK=(d, n) ，其中 e, d, n 都是 正整数。
PK是公开的，任何人都可以通过下面的加密公式，用 PK 对 明文 M （为整数），进行加密 ，得到 密文 C （为整数），并发送给 接收者。
Mᵉ mod n = C
SK不公开，只有接收者知道，收到C后，可以通过下面的解密公式，得到M。
Cᵈ mod n = M
这里的 mod 称为 模运算，对于 任意整数 a，b(≠0)，做带余除法，有，
a = qb + r，0 ≤ r < |b|
定义，
a mod b = r (a ≥ 0) 或 -r (a < 0)
RSA 密钥 的构造 如下：
1 任意选取 两个 奇素数 p 和 q，令 n = pq；
2 计算 ψ(n)=(p-1)(q-1)；
ψ(n) 称为 欧拉函数， 表示：小于 n 并且 与 n 互素 的 正整数 个数。若 整数 a 和 b 的更大公约数 (a, b) = 1，则称 a 与 b 互素。
对于 素数 p 而言，任何 小于 p的 正整数 显然 和 p 互素，小于p 的正整数 个数 是 p-1，因此 ψ(p) = p-1，同理 ψ(q) = q-1。
又显然 (p,q) = 1，根据，
定理1： 若(a, b) = 1 则 ψ(ab)=ψ(a)ψ(b)；立即得到：
ψ(n)=(p-1)(q-1)
3 选取 正整数 1 < e < ψ(n) ，使得 (e, ψ(n)) = 1 ①；
由于，ψ(n)=(p-1)(q-1) > 1，故 一定存在 小于 ψ(n) 与 ψ(n) 互素 的 非1 正整数 e。
4 求 e 的 模 ψ(n) 逆 d，即，求 正整数 1 < d < ψ(n)，使得 ed mod ψ(n) = 1 ②；
根据，
贝祖定理：对于任意整数 a, b(≠0)，都存在 整数 c 和 d，使得 (a, b) = ca + db；由①有，
1 = (e, ψ(n)) = (ψ(n), e) = cψ(n) + de
再利用 模运算法则：
法则1：(a + b) mod m = (a mod m + b) mod m于是有，
1 = 1 mod ψ(n) = (cψ(n) + de) mod ψ(n) = (cψ(n) mod ψ(n) + de) mod ψ(n) = (0 + de) mod ψ(n) = de mod ψ(n)
这样我们就证明了 d 的存在性。
5 销毁 p，q，ψ(n)，只保留 e, d, n 分别组成 PK=(e, n) 和 SK=(d, n)。
我们需要证明，用上面 构造的 PK 和 SK，对于 加密公式 和 解密公式 有效，为此我们仅需要验证，
(Mᵉ mod n)ᵈ mod n = M
即可。
根据 模运算 法则：
法则2： (a mod m)ᵇ mod m = aᵇ mod m上面等式，
左边 = (Mᵉ)ᵈ mod n = Mᵉᵈ mod n
而由 ② 有，
ed = kψ(n) +1， k 是某个正整数
于是，
左边 = Mᵏᵠ⁽ⁿ⁾⁺¹ mod n = (Mᵏ)ᵠ⁽ⁿ⁾M mod n
再根据 模运算 法则：
法则3： ab mod m = (a mod m)b mod m有，
左边 = ((Mᵏ)ᵠ⁽ⁿ⁾ mod n)M mod n
又有，
费马小定理：若 (a, m) = 1，则 aᵠ⁽ᵐ⁾ ≡ 1 (mod m)这里恒等式的意义是：若 a mod m = b mod m，则称 a 和 b 模 m 同余，记为 a ≡ b (mod m)。
因为 n = pq，p和q都是素数，所以 我们只要保证，
☆ M ≠ p,q
则一定有 (Mᵏ, n) = 1，这样利用 费马小定理，有，
左边 = 1M mod n = M mod n
如果再保证，
★ |M| < n
则，
左边 = M = 右边
这样就证明了前面的等式。
类似地，我们还能证明：(Mᵈ mod n)ᵉ mod n = M，这说明：用SK加密，用PK解密，也行。
一个栗子：
小明 和 贝贝 的交往，遭到双方家人的反对，这天 小明 想要 贝贝告诉他 约会地点，但又不想监控他们通信的家人知道，于是 小明 选取 p = 3， q = 11 两个 奇素数，得到，
n = 3×11 = 33
并计算出，
ψ(n) = (3-1)×(11-1) = 20
由 (3, 20) = 1, 选 e = 3，又，
3×7 = 21 = 20 + 1 ⇒ 3×7 mod 20 = 1
故 d = 7，然后，小明 构造 PK=(3, 33), SK=(7, 33)，并将 PK 以明文的方式发送个 给贝贝。
贝贝选择的约会地点是：漠河舞厅，写成拼音就是 mo he wu ting。
贝贝和小明约定：
用 0 表示空格；用 1-2, 4-10, 12-27 这26个数字 依此 表示 26个英文字母；这使得 ☆ 和 ★ 得到保证。
于是 m = 14 是m的明文，根据加密公式，得到 m 的密文 14³ mod 33 = 5，然后发送个小明，小明受到 5 后，使用解密公式，得到明文 5⁷ mod 33 = 14，再根据约定，就知道 14 = m。
对于 后续的 o he wu ting，依此重复以上的操作，最终，小明就知道了 约会地点。
当然，手动算毕竟很麻烦，于是小明 写了一个 简单的 JavaScript 代码如下：
function is_prime(n) { for(let k = 2; k <= Math.sqrt(n); k++) if (!(n % k)) return false; return true; } function gen_key(p, q) { let n = p*q, y = (p-1)*(q-1); let e = 3; while (is_prime(e) && !(y % e)) e += 2; let d = 2; while (!(d*e % y === 1)) d++; return [e, d, n] } let encrypt = (M, e, n) => Math.pow(M, e) % n; let decrypt = (C, d, n) => Math.pow(C, d) % n;
RSA 在实际应用时，会选取 很大的 两个 奇素数 p, q，这样不仅使得 n非常大，监听者 很难 通过因子分解 n 得到 p 和 q，而且可以让 任何 M < p，q，于是 ☆ 和 ★ 也就得到了保证。
另外，还需要注意：
p 和 q 不能离得太近，一般要保证 |p-q| ≥ √n；不妨设 p ≤ q，令 ε=q-p 则有，
n = pq = (q-ε)q = q²-εq
于是，
q = (ε + √ (ε² + 4n)) / 2
若 p 和 q 离得很近，则 ε 就很小，于是我们可以从 0 开始 通过不断 尝试 得到 q。
e 和 d 都不能太小；这同样容易被破解。由于，e 和 ψ(n) 都很大，我们很难通过 尝试的 求的 d，这时就需要 使用 秦九韶的 大衍求一术，具体 如下：
对 ψ=ψ(n) 和 e 进行辗转相除（带余除法），有，
ψ = q₁e + r₁
e = q₂r₁ + r₂
r₁ = q₃r₂ + r₃
...
rᵤ₋₂ = qᵤrᵤ₋₁ + rᵤ，（rᵤ=1）
构造两个数列，
c₀=0,c₁=1, cᵢ=qᵢcᵢ₋₁+cᵢ₋₂
d₀=1,d₁=q₁, dᵢ=qᵢdᵢ₋₁+dᵢ₋₂
我们断定有，
命题：cᵢψ - dᵢe = (-1)ⁱ⁻¹rᵢ ③
证明：
当 i=2 时，有，c₂ψ - d₂e = (q₂c₁+c₀)ψ - (q₂d₁+d₀)e = q₂ψ - (q₂q₁+1)e = q₂(q₁e + r₁) - (q₂q₁+1)e = q₂r₁ - e = -r₂ = (-1)²⁻¹r₂
命题 成立。
归纳假设 小于等于 i 时 ③ 成立，考虑 i+1 的情况，有，cᵢ₊₁ψ - dᵢ₊₁e = (qᵢ₊₁cᵢ+cᵢ₋₁)ψ - (qᵢ₊₁dᵢ+dᵢ₋₁)e = qᵢ₊₁cᵢψ + cᵢ₋₁ψ - qᵢ₊₁dᵢe - dᵢ₋₁e = qᵢ₊₁(cᵢψ - dᵢe) + (cᵢ₋₁ψ - dᵢ₋₁e) = qᵢ₊₁ (-1)ⁱ⁻¹rᵢ + (-1)ⁱ⁻¹⁻¹rᵢ₋₁ = (-1)ⁱ⁻¹(qᵢ₊₁ rᵢ - rᵢ₋₁) = (-1)ⁱ⁻¹(-rᵢ₊₁) = (-1)ⁱ⁺¹⁻¹rᵢ₊₁
命题 成立，于是 归纳得证！▌
当 u 是偶数时，根据 ③ 有，cᵤψ - dᵤe = (-1)ᵘ⁻¹rᵤ = -1
于是，
dᵤe mod ψ = (cᵤψ + 1) mod ψ = 1
故 dᵤ 就是所求的 d。
当 u 是奇数时，我们可以将辗转相除法再进行一步：rᵤ₋₁ = qᵤ₊₁rᵤ + rᵤ₊₁, (qᵤ₊₁ = rᵤ₋₁ - 1, rᵤ₊₁ = 1)
u+1就是偶数，于是这样根据③ 有，
cᵤ₊₁ψ - dᵤ₊₁e = (-1)ᵘ⁺¹⁻¹rᵤ₊₁ = -1
于是，
dᵤ₊₁e mod ψ = (cᵤ₊₁ψ + 1) mod ψ = 1
故 dᵤ₊₁ 就是所求的 d。
大衍求一术 写成 JavaScript代码 如下：
function dyqysh(y, e) { let d, d1 = 0, d2 = 1 let r1 = y, r2 = e; let isodd = false; do { isodd = !isodd; let r = r1 % r2, q = (r1 - r) / r2; // console.log(`${r1} = ${q}*${r2}+${r}`); d = q*d2 + d1; d1 = d2, d2 = d; r1 = r2, r2 = r; } while(!(r2 === 1)) if (isodd) d = (r1-1)*d2 + d1; return d; }
好了，关于 RSA，小石头目前能想到的就这么多内容了，希望对大家有所帮助。
附录： 推导模运算法则。
法则1：有带余除法 a = km + r，于是有，
a + b = km + r + b
于是，
(a + b) mod m = (r + b) mod m
而根据模运算定义有，
a mod m = r
带入前式，立即得证。
法则2：令 a mod m = k，于是有， a ≡ k (mod m) ，根据同余性质，有，
aᵇ ≡ kᵇ (mod m)
也就是说，
aᵇ mod m = kᵇ mod m = (a mod m)ᵇ mod m
法则3：与法则1推导类似，由带余除法 a = km + r，有，
ab = bkm + rb
于是，
ab mod m = rb mod m = (a mod m)b mod m
（关于，本文使用的定理的证明，见小石头首页中的相关文章。）
