文：RSA算法是一种非对称加密算法，用于加密、解密和数字签名等场景。本文将介绍如何在JavaScript中使用RSA算法，并提供一个实际的案例，同时也会说明如何生成公钥和私钥。

首先，确保您已经引入了jsencrypt库。以下是一个使用RSA算法进行加密和解密的示例，同时也包含了公钥和私钥的生成方法：

// 引入jsencrypt库
const JSEncrypt = require("jsencrypt");

// 生成RSA密钥对
const rsa = new JSEncrypt();
const keypair = rsa.getKey();

// 获取公钥和私钥
const publicKey = keypair.getPublicKey();
const privateKey = keypair.getPrivateKey();

console.log("公钥：", publicKey);
console.log("私钥：", privateKey);

// 实例化一个RSA对象
const rsaInstance = new JSEncrypt();

// 设置公钥和私钥
rsaInstance.setPublicKey(publicKey);
rsaInstance.setPrivateKey(privateKey);

// 定义待加密的字符串
const plaintext = "Hello, World!";

// 加密字符串
const encrypted = rsaInstance.encrypt(plaintext);

console.log("加密后的密文：", encrypted);

// 解密密文
const decrypted = rsaInstance.decrypt(encrypted);

console.log("解密后的明文：", decrypted);

在上述代码中，我们首先引入了jsencrypt库，并实例化了一个JSEncrypt对象。通过调用getKey()方法，我们生成了一个RSA密钥对。然后，我们使用getPublicKey()和getPrivateKey()方法获取公钥和私钥。生成的公钥和私钥可以用于后续的加密和解密操作。

接下来，我们实例化另一个JSEncrypt对象，并使用setPublicKey()和setPrivateKey()方法设置公钥和私钥。之后，我们定义了待加密的字符串，并使用encrypt()方法对字符串进行加密。最后，通过调用decrypt()方法对密文进行解密，并将解密后的明文输出。

通过以上示例，您可以在JavaScript中使用RSA算法进行加密和解密操作，并自动生成公钥和私钥。需要注意的是，生成的公钥和私钥应妥善保管，确保其安全性和保密性，以防止数据泄露和非法使用。

总结：通过jsencrypt库，我们可以在JavaScript中轻松实现RSA算法的加密和解密功能。本文提供了一个实际的案例，并详细说明了如何生成公钥和私钥。通过生成的密钥对，我们可以进行数据加密和解密操作，确保数据的安全性和保密性。在实际应用中，请妥善保存生成的公钥和私钥，以保证数据的安全。

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

小石头/编

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

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