文：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??????1 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 的密文 143 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 = q2-εq

于是，

q = (ε + √ (ε2 + 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)??1r? ③

證明：

• 當 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)2?1r?

命題 成立。

• 歸納假設 小于等于 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)??1r? + (-1)??1?1r??? = (-1)??1(q??? r? - r???) = (-1)??1(-r???) = (-1)??1?1r???

命題 成立，于是 歸納得證！▌

• 當 u 是偶數時，根據 ③ 有，

c?ψ - d?e = (-1)??1r? = -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)??1?1r??? = -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

（關于，本文使用的定理的證明，見小石頭首頁中的相關文章。）