算法：RSA

大家好，欢迎来到IT知识分享网。

话题：#科学# #数学# #密码学# #算法#

小石头/编

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

（关于，本文使用的定理的证明，见小石头首页中的相关文章。）