Lesson 55: RSA 公钥加密

练习任务

难度：中

实现一个玩具版 RSA 公钥加密系统，使用固定小素数参数完成"素性判定 → 密钥生成 → 加密 → 解密 → 验证"全流程。你需要实现 8 个核心组件：

1. gcd(a, b) — 欧几里得算法求最大公约数（★☆☆）
2. ext_gcd(a, b, &x, &y) — 扩展欧几里得算法，求模逆元 d（★★★）
3. fast_pow(base, exp, mod) — 快速模幂运算（★★☆）
4. is_prime(num) — Miller-Rabin 素性判定（★★★）
5. gen_keys(p, q, e, &n, &φ, &d) — 密钥生成，含 e 有效性验证（★★☆）
6. encrypt(msg, e, n) — RSA 加密（★☆☆）
7. decrypt(cipher, d, n) — RSA 解密（★☆☆）
8. main() — 串联全部步骤，按格式输出（★★☆）

固定参数：p=61, q=53, n=3233, φ=3120, e=17, m=42。

提示：RSA 的安全性依赖于大整数分解的困难性。本题使用 3233 只是玩具规模——思考如果 n 是 2048 位的数，哪些运算会成为瓶颈？素性判定、模逆元、快速幂各自承担什么角色？

---

核心知识点

• 模运算与同余 — a ≡ b (mod n) 表示 a 和 b 除以 n 的余数相同，模加法/乘法满足分配律
• 欧拉函数 φ(n) — [1, n] 中与 n 互质的整数个数，对素数乘积 φ(pq) = (p-1)(q-1)
• 欧拉定理 — 若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)，是 RSA 正确性的数学基石
• 欧几里得算法与扩展欧几里得 — 求最大公约数和 Bézout 系数，从 e 推导私钥 d
• 快速模幂运算 — 二分求幂将 O(exp) 降到 O(log exp)，每次乘法后取模防止溢出
• Miller-Rabin 素性测试 — 基于费马小定理的概率算法，选对见证人可在 uint64 范围给出确定性结果
• RSA 加密/解密正确性 — 由 e*d ≡ 1 (mod φ) 推出 m^(ed) ≡ m (mod n)
• uint64_t 玩具版限制 — n=3233 的规模远小于真实 RSA，但完整保留了算法的数学逻辑
• 防御式编程 — 密钥生成中验证 e 范围、gcd(e,φ)==1、e*d mod φ == 1 的多重保险

---

代码框架

55_rsa_crypto_demo.c

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

/* ─── RSA 固定参数 ─── */
static const uint64_t p = 61;
static const uint64_t q = 53;
static const uint64_t n = 3233;
static const uint64_t phi = 3120;
static const uint64_t e = 17;
static const uint64_t m = 42;

/* ─── TODO 1: 最大公约数 (欧几里得算法) ─── */
static uint64_t gcd(uint64_t a, uint64_t b) {
    // ① 当 b != 0 时，反复用 a % b 替换
    //    while (b != 0) { t = b; b = a % b; a = t; } return a;
}

/* ─── TODO 2: 扩展欧几里得算法 ─── */
static int64_t ext_gcd(int64_t a, int64_t b, int64_t *px, int64_t *py) {
    // ② 基准: if (b == 0) { *px = 1; *py = 0; return a; }
    //    递归: ext_gcd(b, a%b, &x1, &y1)
    //    回溯: *px = y1; *py = x1 - (a/b)*y1
}

/* ─── TODO 3: 快速模幂运算 ─── */
static uint64_t fast_pow(uint64_t base, uint64_t exp, uint64_t mod) {
    // ③ result = 1; base = base % mod
    //    while (exp > 0):
    //      if (exp & 1) result = (result * base) % mod
    //      exp >>= 1; base = (base * base) % mod
    //    return result
}

/* ─── TODO 4: Miller-Rabin 素性判定 ─── */
static int is_prime(uint64_t num) {
    // ④ 小情况: num<2→false; num==2||num==3→true; 偶数→false
    //    分解 num-1 = d*2^s: while ((d & 1) == 0) { d >>= 1; s++; }
    //    见证人 {2,3,5,7,11}: 对每个 a 做 Miller-Rabin 检测
}

/* ─── TODO 5: 密钥生成 ─── */
static int gen_keys(uint64_t prime_p, uint64_t prime_q, uint64_t pub_e,
                    uint64_t *out_n, uint64_t *out_phi, int64_t *out_d) {
    // ⑤ 计算 n=p*q, φ=(p-1)*(q-1)
    //    验证 1 < e < φ 且 gcd(e,φ)==1
    //    ext_gcd(e, φ, &x, &y)
    //    d = x mod φ (调整为正值)
    //    验证 e*d mod φ == 1
    //    *out_n=n; *out_phi=φ; *out_d=d; return 0
}

/*  ←── TODO 6: RSA 加密 ─── */
static uint64_t encrypt(uint64_t msg, uint64_t pub_exp, uint64_t modulus) {
    // ⑥ return fast_pow(msg, pub_exp, modulus)
}

/* ─── TODO 7: RSA 解密 ─── */
static uint64_t decrypt(uint64_t cipher, uint64_t priv_exp, uint64_t modulus) {
    // ⑦ return fast_pow(cipher, priv_exp, modulus)
}

/* ─── TODO 8: 主流程 ─── */
int main(void) {
    // ⑧ Step 1: 打印参数 + is_prime 验素数 p, q
    //    Step 2: gen_keys 生成密钥
    //    Step 3: c = encrypt(m, e, n)
    //    Step 4: m' = decrypt(c, d, n)
    //    Step 5: 验证 m' == m
}

阅读骨架后，尝试填充 // ① 到 // ⑧ 标记的部分。核心挑战在于：ext_gcd 的递归回溯如何从 Bézout 系数求得模逆元？Miller-Rabin 的见证人循环如何区分素数与合数？gen_keys 中防御式编程的多重验证分别防什么？

TIP

先不要往下翻看参考解答。用纸笔追踪一遍 ext_gcd(17, 3120) 的递归调用栈，理解 x=-367 如何调整成 d=2753。再用 fast_pow(42, 17, 3233) 验证二进制的 10001b 如何通过 5 次平方得到 2557。

---

深度讲解

1. 模运算——RSA 的数学地基

1.1 同余的基本直觉

模运算（Modular Arithmetic）是 RSA 一切运算的"语言"。"a ≡ b (mod n)" 翻译成人话就是：a 和 b 除以 n 的余数相同。更严谨的表述是 n 整除 (a - b)。

同余的核心等价关系（a, b, n 都是整数，n > 0）：

  a ≡ b (mod n)  ⇔  a mod n = b mod n  ⇔  n | (a - b)

举例：
  17 ≡ 3 (mod 7)  因为 17 mod 7 = 3, 3 mod 7 = 3, 7 | (17-3)
"""

1.2 模运算的三条运算律

这三条规律是"每次乘法后立刻取模就不会溢出"的理论保证：

modular_rules.c

// 模加法分配律: (a + b) mod n = ((a mod n) + (b mod n)) mod n
// 模乘法分配律: (a * b) mod n = ((a mod n) * (b mod n)) mod n
// 模幂分配律:   a^e mod n = (a mod n)^e mod n

// 实际代码中的体现——每次乘法后都取模：
uint64_t result = 1;
base = base % mod;                    // 利用模幂分配律，先将底数取模
while (exp > 0) {
    if (exp & 1)
        result = (result * base) % mod;  // 乘法后立即取模
    exp >>= 1;
    base = (base * base) % mod;          // 平方后立即取模
}

IMPORTANT

这三个分配律意味着：每次乘法取模后，结果一定在 [0, n-1] 范围内。只要 n*n 不溢出 uint64_t，就不会有中间溢出问题。本题 n=3233，而 uint64_t 可容纳 ~1.8×10^19，安全裕度巨大。

1.3 在 RSA 中的角色

RSA 运算全在模 n 的意义下进行：

  加密: c ≡ m^e (mod n)
  解密: m ≡ c^d (mod n)

加密方向是"正向"的模幂，解密方向只有知道 d 才能高效计算。
从公钥 (e, n) 推导 d 的困难性 = 从 n 分解出 p, q 的困难性。

---

2. 欧拉函数与欧拉定理——RSA 正确性的证明

2.1 欧拉函数 φ(n)

欧拉函数 φ(n) = [1, n] 中与 n 互质的整数个数。

φ(1)  = 1     // {1}
φ(2)  = 1     // {1}            (2 不是，因为 gcd(2,2)=2)
φ(3)  = 2     // {1, 2}
φ(6)  = 2     // {1, 5}
φ(9)  = 6     // {1, 2, 4, 5, 7, 8}

对于素数 p：φ(p) = p - 1，因为 [1, p-1] 全都与 p 互质。

对于两个不同素数 p 和 q：
  φ(p*q) = (p-1) * (q-1)     ← 这是本课最重要的公式！

  本题：φ(61×53) = φ(61) × φ(53) = 60 × 52 = 3120

为什么 φ(pq) = (p-1)(q-1)？

从 [1, pq] 中剔除与 pq 不互质的数。不互质 = 包含因子 p 或因子 q：

• p 的倍数：p, 2p, 3p, ..., qp → 共 q 个
• q 的倍数：q, 2q, 3q, ..., pq → 共 p 个
• pq 被重复计算了一次

所以 φ(pq) = pq - q - p + 1 = pq - p - q + 1 = (p-1)(q-1)。

2.2 欧拉定理

若 gcd(a, n) = 1，则 a^φ(n) ≡ 1 (mod n)。

这是 RSA 正确性的基石。对于本课（n = pq），如果明文 m 与 n 互质（实践中以极高概率成立），有：

m^φ(n) ≡ 1 (mod n)
m^(k·φ(n)) ≡ 1^k ≡ 1 (mod n)
m^(k·φ(n)+1) ≡ m (mod n)

2.3 RSA 正确性的完整推导

设 e·d = k·φ(n) + 1（即 e·d ≡ 1 mod φ(n)），则：

加密后的密文:  c = m^e mod n
解密恢复:      c^d ≡ (m^e)^d ≡ m^(e·d) ≡ m^(k·φ(n)+1)
                 ≡ (m^φ(n))^k · m ≡ 1^k · m ≡ m (mod n)

即：解密得到的就是原始明文 m。加密和解密互为逆运算。

NOTE

这个推导假设 gcd(m, n) = 1。当 m 恰好是 p 或 q 的倍数时，可以通过中国剩余定理证明解密仍然正确。实践中明文通常远小于 n，并且现代 RSA 使用随机填充（OAEP），不会直接加密原始消息。

---

3. 欧几里得算法与模逆元——从 e 到 d

3.1 基本欧几里得算法 (gcd) — TODO 1

gcd_algorithm.c

// 核心递归式: gcd(a, b) = gcd(b, a % b)，当 b = 0 时返回 a
uint64_t gcd(uint64_t a, uint64_t b) {
    while (b != 0) {
        uint64_t t = b;
        b = a % b;
        a = t;
    }
    return a;
}

手动追踪 gcd(17, 3120)：

步骤 │  a   │  b   │ a % b │ 说明
─────┼──────┼──────┼───────┼─────────────────────
  1  │ 17   │ 3120 │  17   │ 交换：实际计算 gcd(3120, 17)
  2  │ 3120 │  17  │   9   │ 3120 = 183 × 17 + 9
  3  │  17  │   9  │   8   │ 17 = 1 × 9 + 8
  4  │   9  │   8  │   1   │ 9 = 1 × 8 + 1
  5  │   8  │   1  │   0   │ 8 = 8 × 1 + 0
  6  │   1  │   0  │   —   │ b==0，返回 a=1 ✓

结论：gcd(17, 3120) = 1 → e 和 φ 互质，可以继续密钥生成

3.2 扩展欧几里得算法 (ext_gcd) — TODO 2

扩展不仅求 gcd，还要求 Bézout 系数 x, y，使得 a*x + b*y = gcd(a, b)。当 gcd = 1 时，x 就是 a 模 b 的乘法逆元。

ext_gcd_algorithm.c

// 递归实现：基准 b==0 返回 a, x=1, y=0
// 递归后回溯：x = y1, y = x1 - (a/b)*y1
int64_t ext_gcd(int64_t a, int64_t b, int64_t *px, int64_t *py) {
    if (b == 0) {
        *px = 1;
        *py = 0;
        return a;
    }
    int64_t x1, y1;
    int64_t g = ext_gcd(b, a % b, &x1, &y1);
    *px = y1;
    *py = x1 - (a / b) * y1;
    return g;
}

递归调用栈追踪 ext_gcd(17, 3120)：

调用 ext_gcd(17, 3120)
  → ext_gcd(3120, 17)
    → ext_gcd(17, 9)
      → ext_gcd(9, 8)
        → ext_gcd(8, 1)
          → ext_gcd(1, 0) = 1, x1=1, y1=0  ← 触底
        回：x = 0, y = 1 - (8/1)*0 = 1        → (x=0, y=1)
      回：x = 1, y = 0 - (9/8)*1 = -1         → (x=1, y=-1)
    回：x = -1, y = 1 - (17/9)*(-1) = 2        → (x=-1, y=2)
  回：x = 2, y = -1 - (3120/17)*2 = -367      → (x=2, y=-367)
回：x = -367, y = 2 - (17/3120)*(-367) = 2    → (x=-367, y=2)

验证：17 × (-367) + 3120 × 2 = -6239 + 6240 = 1 ✓

从 x = -367 计算私钥 d：

key_from_ext_gcd.c

// 模逆元取最小非负剩余
int64_t d = x % phi;
if (d < 0) d += phi;   // d = -367 + 3120 = 2753

// 或者直接用：d = (x % phi + phi) % phi;

// 验证：17 * 2753 = 46801,  46801 mod 3120 = 1 ✓

WARNING

不要直接使用负的 x 作为私钥。虽然 x 也是合法的模逆元（因为 17×(-367) mod 3120 = 1），但后面的 encrypt/decrypt 调用的 fast_pow 期望无符号指数。务必在 gen_keys 中将 d 调整为正值。

---

4. 快速模幂——让 (42^2753 mod 3233) 成为可能

4.1 二分求幂（Binary Exponentiation）

计算 base^exp mod mod。朴素连乘需要 exp 次乘法——当 exp=2753 时需 2753 次，当 exp 有 2048 位时计算彻底不可行。

快速幂的核心思想：将指数按二进制展开，利用反复平方法。

exp 的二进制表示：exp = b₀·2⁰ + b₁·2¹ + b₂·2² + ... + bₖ·2ᵏ

则 base^exp = base^(b₀·2⁰) × base^(b₁·2¹) × ... × base^(bₖ·2ᵏ)

只需要计算 base^(2ⁱ)（每次平方可得），再乘上 bᵢ=1 的那些项。

fast_pow_algorithm.c

uint64_t fast_pow(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t result = 1;
    base = base % mod;                  // 预取模

    while (exp > 0) {
        if (exp & 1)                     // 最低位为 1？
            result = (result * base) % mod;
        exp >>= 1;                       // 右移一位
        base = (base * base) % mod;      // 平方
    }
    return result;
}

4.2 完整追踪 fast_pow(42, 17, 3233)

17 的二进制：10001b (bit₀=1, bit₄=1)

    exp    bit   result                     base
─────────────────────────────────────────────────────────
初始  17(10001)             1             42 % 3233 = 42
─────────────────────────────────────────────────────────
步1   17     bit₀=1  1×42 % 3233 = 42    42² % 3233 = 1764
步2    8     bit₁=0  (不变) 42           1764² % 3233 = 2998
步3    4     bit₂=0  (不变) 42           2998² % 3233 = 1652
步4    2     bit₃=0  (不变) 42           1652² % 3233 = 2444
步5    1     bit₄=1  42×2444 % 3233=2557 (不再需要)
─────────────────────────────────────────────────────────

结果：c = 2557 ← 42^17 mod 3233

只用了 5 次平方 + 2 次乘法 = 共 7 次乘法，而非 16 次！

IMPORTANT

快速幂将 O(exp) 降为 O(log exp)。17 的二进制只有 5 位，所以 5 次平方。对于真实的 2048 位 RSA，解密指数 d 约有 2048 位——朴素法需 2^2048 次乘（宇宙年龄都不够），快速幂只需约 3072 次乘。这是"算法让不可能变为可能"的经典示范。

4.3 为什么每次乘法后必须取模？

why_mod_every_mul.c

// 危险做法——结果会在某次平方后溢出 uint64_t
result = (result * base);   // ❌ 不做取模！

// 安全做法
result = (result * base) % mod;  // ✓ 结果总在 [0, mod-1]

// 原理：模运算分配律保证
// ((a % m) * (b % m)) % m = (a * b) % m
// 所以分步取模的结果与先乘再取模完全一致，但绝不会溢出

本题 n=3233，任何中间值平方 ≤ 3232² = 10,445,824 < uint64_t 的 ~1.8×10^19，非常安全。但当 n 达到 2^32 时，n² ≈ 2^64 就接近 uint64_t 上限——这就是为何真实 RSA 必须用大数库（GMP、OpenSSL BIGNUM）。

---

5. Miller-Rabin 素性测试——确定什么是素数

5.1 为什么需要素性测试？

RSA 的安全性依赖两个大素数的乘积难以分解。但首先必须确认 p 和 q 确实是素数。对于 2048 位的数，试除法不可行（O(√n) = O(2^1024)）。Miller-Rabin 是工业标准解决方案。

5.2 从费马小定理到 Miller-Rabin

费马小定理：若 n 是素数且 gcd(a, n) = 1，则 a^(n-1) ≡ 1 (mod n)。

其"逆否"命题：如果存在 a 使 a^(n-1) ≢ 1 (mod n)，则 n 一定是合数。但反过来不一定对——Carmichael 数（如 561）对所有 a 都满足 a^(n-1) ≡ 1，却不是素数。

Miller-Rabin 填补了这个漏洞：

若 n 是奇素数，n-1 = d·2^s（d 为奇数），则对任意 1 < a < n-1： 要么 a^d ≡ 1 (mod n) 要么存在 r ∈ [0, s-1] 使得 a^(d·2^r) ≡ -1 (mod n)

如果某个 a 让这两个条件都不成立，n 一定是合数。这样的 a 称为"合数见证人"。

miller_rabin_algorithm.c

static int is_prime(uint64_t num) {
    // 1. 小情况快速决策
    if (num < 2)  return 0;             // 0 和 1 不是素数
    if (num == 2 || num == 3) return 1; // 2 和 3 是素数
    if ((num & 1) == 0) return 0;       // 偶数是合数

    // 2. 分解 num-1 = d * 2^s
    uint64_t d = num - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    // 3. 见证人集合：{2, 3, 5, 7, 11} 对所有 < 2^64 的数确定
    static const uint64_t witnesses[] = {2, 3, 5, 7, 11};

    for (int i = 0; i < 5; i++) {
        uint64_t a = witnesses[i];
        if (a >= num) continue;          // 见证人比 num 大则跳过

        uint64_t x = fast_pow(a, d, num);

        if (x == 1 || x == num - 1)      // 条件 1 或条件 2(r=0)
            continue;                     // 此见证人通过

        int composite = 1;
        for (int r = 0; r < s - 1; r++) {
            x = (x * x) % num;
            if (x == num - 1) {          // 条件 2(r>0)
                composite = 0;
                break;
            }
        }
        if (composite) return 0;          // 合数！
    }

    return 1;  // 所有见证人通过 → 素数
}

5.3 见证人集合的数学证明

见证人集合	确定性范围	证明来源
	n < 2,047	基础费马测试
	n < 1,373,653	—
	n < 25,326,001	—
{2, 3, 5, 7, 11}	n < 2,152,302,898,747	Jaeschke (1993)
	n < 341,550,071,728,321	—

本题使用 {2, 3, 5, 7, 11}，确定性范围 n < 2.15×10^12。Jim Sinclair (2011) 进一步验证这个集合对 所有 n < 2^64 有效，完全覆盖 uint64_t 范围。

NOTE

本课是"玩具版"RSA（n=3233），但这个素性测试本身是工业级实现。同样是这 5 个见证人，可以用来验证真实场景中 uint64_t 范围内的任意素数候选。

5.4 示例：验证 61 是素数

num = 61
num-1 = 60 = 15 × 2^2  →  d = 15, s = 2

见证人 a=2:
  x = 2^15 mod 61 = fast_pow(2, 15, 61)

  15 = 1111b → 逐次平方：
  2^1=2, 2^2=4, 2^4=16, 2^8=256%61=11
  x = 2×4×16×11 % 61 = ...

  ... 计算得 x = 11
  x ≠ 1, x ≠ 60 → 进入平方循环

  r=0: x = 11^2 % 61 = 121 % 61 = 60 = num-1 ✓ 通过！

见证人 a=3, 5, 7, 11: 类似过程，全部通过。

→ 61 是素数 ✓

---

6. 密钥生成与加解密——组装完整流程

6.1 gen_keys — TODO 5

gen_keys 是整个 RSA 系统的"组装流水线"。它不仅要计算数值，还必须进行多重验证：

gen_keys_algorithm.c

static int gen_keys(uint64_t prime_p, uint64_t prime_q, uint64_t pub_e,
                    uint64_t *out_n, uint64_t *out_phi, int64_t *out_d) {
    // 1. 计算公钥模数和欧拉函数
    uint64_t my_n = prime_p * prime_q;
    uint64_t my_phi = (prime_p - 1) * (prime_q - 1);

    printf("  n = p*q = %" PRIu64 "*%" PRIu64 " = %" PRIu64 "\n",
           prime_p, prime_q, my_n);
    printf("  φ(n) = (p-1)*(q-1) = %" PRIu64 "*%" PRIu64 " = %" PRIu64 "\n",
           prime_p - 1, prime_q - 1, my_phi);
    printf("  Select e = %" PRIu64 " (public exponent)\n", pub_e);

    // 2. 防御检查：e 必须在 (1, φ) 范围内
    if (pub_e <= 1 || pub_e >= my_phi) {
        printf("  [ERROR] e must satisfy 1 < e < φ(n)\n");
        return 1;
    }

    // 3. 验证 e 与 φ 互质（否则不存在模逆元）
    uint64_t g = gcd(pub_e, my_phi);
    printf("  Verify gcd(e, φ) = gcd(%" PRIu64 ", %" PRIu64 ") = %" PRIu64 "\n",
           pub_e, my_phi, g);
    if (g != 1) {
        printf("  [ERROR] e and φ are not coprime!\n");
        return 1;
    }
    printf("  [OK — e and φ are coprime]\n");

    // 4. 扩展欧几里得求模逆元
    int64_t x, y;
    int64_t g2 = ext_gcd((int64_t)pub_e, (int64_t)my_phi, &x, &y);
    printf("  ext_gcd(e=%" PRId64 ", φ=%" PRId64 ") → gcd=%" PRId64
           ", x=%" PRId64 ", y=%" PRId64 "\n",
           (int64_t)pub_e, (int64_t)my_phi, g2, x, y);
    printf("  Equation: e*x + φ*y = gcd  →  %" PRId64 "*%" PRId64
           " + %" PRId64 "*%" PRId64 " = %" PRId64 "\n",
           (int64_t)pub_e, x, (int64_t)my_phi, y, g2);

    // 5. 调整 d 为非负数
    int64_t d = x % (int64_t)my_phi;
    if (d < 0) d += (int64_t)my_phi;
    printf("  Private key d = x mod φ = %" PRId64 "\n", d);

    // 6. 最终验证
    uint64_t verify = (uint64_t)(((uint64_t)pub_e * (uint64_t)d) % my_phi);
    printf("  Verify: e*d mod φ = %" PRIu64 " %s\n",
           verify, verify == 1 ? "[OK]" : "[FAIL]");

    *out_n = my_n;
    *out_phi = my_phi;
    *out_d = d;
    return 0;
}

防御层次分析：

防御层 1: 检查 1 < e < φ
          → 防止 e=0 或 e=1（加密退化）或 e≥φ（冗余）

防御层 2: 检查 gcd(e, φ) == 1
          → 确保存在模逆元（密钥生成的前提）

防御层 3: 检查 e*d mod φ == 1
          → 最终验证——确认加密和解密互为逆运算

密码学代码中，验证永远不嫌多。一个错误可能让整个系统不安全。

6.2 加密与解密 — TODO 6, 7

加密和解密都只是一行 fast_pow 调用，因为 RSA 的数学已经封装在指数中：

encrypt_decrypt.c

// 加密：c = m^e mod n
//    c = 42^17 mod 3233 = 2557
static uint64_t encrypt(uint64_t msg, uint64_t pub_exp, uint64_t modulus) {
    return fast_pow(msg, pub_exp, modulus);
}

// 解密：m' = c^d mod n
//    m' = 2557^2753 mod 3233 = 42
static uint64_t decrypt(uint64_t cipher, uint64_t priv_exp, uint64_t modulus) {
    return fast_pow(cipher, priv_exp, modulus);
}

---

7. uint64_t 玩具版的限制与实战差异

7.1 本课实现 vs 真 — RSA 的差距

┌─────────────────────┬──────────────────┬────────────────────────────┐
│      特性           │   本课玩具版       │   真实 RSA（工业级）        │
├─────────────────────┼──────────────────┼────────────────────────────┤
│ n 的规模            │ 3233 (~12 位)    │ ≥ 2048 位 (≥617 位十进RSA)  │
│ p, q 的规模         │ 61, 53 (~6 位)    │ ~1024 位素数               │
│ 素性测试目标        │ 小整数验证方法     │ 数百位大整数               │
│ 算术实现            │ uint64_t 内置乘法 │ 大数库 (GMP, BIGNUM)       │
│ 模乘                │ 直接 % 运算       │ 蒙哥马利模乘               │
│ 填充方案            │ 无（原始加密）     │ OAEP / PKCS#1 v1.5         │
│ 侧信道防护           │ 无               │ 恒定时间实现               │
│ 安全性              │ 可被秒破           │ 计算上不可行               │
└─────────────────────┴──────────────────┴────────────────────────────┘

7.2 容易破解的原因

攻击者截获：密文 c=2557，公钥 (e=17, n=3233)

攻击步骤：
  1. 分解 n=3233 → 试除法，几毫秒：发现 3233 = 61 × 53
  2. 计算 φ = (61-1)×(53-1) = 3120
  3. 计算 d ≡ 17⁻¹ mod 3120 = 2753
  4. 解密：m = 2557^2753 mod 3233 = 42

为什么真实 RSA 不行？因为 2048 位的 n，即使用最先进的数域筛法
（GNFS）和超级计算机，分解需要数十亿年。

7.3 教科书式 RSA 的安全缺陷

1. 确定性加密：相同的明文 → 相同密文，泄露模式
2. 选择密文攻击（CCA）不安全：攻击者可构造特殊密文解密后获取信息
3. 短消息可穷举：如果空间小，可预计算所有可能消息的密文
4. 无随机性：语义不安全

实际应用必须使用 OAEP (Optimal Asymmetric Encryption Padding) 等填充方案，为每条消息注入随机性。

---

参考解答

练习 1-3: gcd, ext_gcd, fast_pow — 数学基础三件套

solution_rsa_math_basics.c

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

/* TODO 1: 欧几里得算法 —— 最大公约数 */
uint64_t gcd(uint64_t a, uint64_t b) {
    while (b != 0) {
        uint64_t t = b;
        b = a % b;
        a = t;
    }
    return a;
}

/* TODO 2: 扩展欧几里得算法 —— 求模逆元 */
int64_t ext_gcd(int64_t a, int64_t b, int64_t *px, int64_t *py) {
    if (b == 0) {
        *px = 1;
        *py = 0;
        return a;
    }
    int64_t x1, y1;
    int64_t g = ext_gcd(b, a % b, &x1, &y1);
    *px = y1;
    *py = x1 - (a / b) * y1;
    return g;
}

/* TODO 3: 快速模幂运算 —— 二分求幂 */
uint64_t fast_pow(uint64_t base, uint64_t exp, uint64_t mod) {
    uint64_t result = 1;
    base = base % mod;
    while (exp > 0) {
        if (exp & 1)
            result = (result * base) % mod;
        exp >>= 1;
        base = (base * base) % mod;
    }
    return result;
}

/* 快速测试 */
int main(void) {
    printf("gcd(17, 3120) = %" PRIu64 "\n", gcd(17, 3120));

    int64_t x, y;
    ext_gcd(17, 3120, &x, &y);
    printf("ext_gcd(17, 3120) → x=%" PRId64 ", y=%" PRId64 "\n", x, y);
    printf("17*%" PRId64 " + 3120*%" PRId64 " = %" PRId64 "\n",
           x, y, 17 * x + 3120 * y);

    printf("fast_pow(42, 17, 3233) = %" PRIu64 "\n",
           fast_pow(42, 17, 3233));
    return 0;
}

要点：ext_gcd 递归基准是 b==0，回溯时正确计算 x 和 y。fast_pow 中每次乘法后必须 % mod。

练习 4: is_prime — Miller-Rabin 素性判定

solution_miller_rabin.c

#include <inttypes.h>
#include <stdint.h>

static int is_prime(uint64_t num) {
    if (num < 2)  return 0;
    if (num == 2 || num == 3) return 1;
    if ((num & 1) == 0) return 0;

    // 分解 num-1 = d * 2^s
    uint64_t d = num - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    // 见证人集合：{2, 3, 5, 7, 11}
    static const uint64_t witnesses[] = {2, 3, 5, 7, 11};

    for (int i = 0; i < 5; i++) {
        uint64_t a = witnesses[i];
        if (a >= num) continue;

        uint64_t x = fast_pow(a, d, num);
        if (x == 1 || x == num - 1) continue;

        int composite = 1;
        for (int r = 0; r < s - 1; r++) {
            x = (x * x) % num;
            if (x == num - 1) {
                composite = 0;
                break;
            }
        }
        if (composite) return 0;
    }
    return 1;
}

要点：s 循环条件是 r < s-1 而非 r < s，因为最后一步由循环后的 if (composite) 判断覆盖。见证人 a >= num 时必须跳过（判断 3 时跳过 3 本身）。

练习 5: gen_keys — 密钥生成

solution_gen_keys.c

static int gen_keys(uint64_t prime_p, uint64_t prime_q, uint64_t pub_e,
                    uint64_t *out_n, uint64_t *out_phi, int64_t *out_d) {
    uint64_t my_n = prime_p * prime_q;
    uint64_t my_phi = (prime_p - 1) * (prime_q - 1);

    printf("  n = p*q = %" PRIu64 "*%" PRIu64 " = %" PRIu64 "\n",
           prime_p, prime_q, my_n);
    printf("  φ(n) = (p-1)*(q-1) = %" PRIu64 "*%" PRIu64 " = %" PRIu64 "\n",
           prime_p - 1, prime_q - 1, my_phi);
    printf("  Select e = %" PRIu64 " (public exponent)\n", pub_e);

    if (pub_e <= 1 || pub_e >= my_phi) {
        printf("  [ERROR] e must satisfy 1 < e < φ(n)\n");
        return 1;
    }

    uint64_t g = gcd(pub_e, my_phi);
    printf("  Verify gcd(e, φ) = gcd(%" PRIu64 ", %" PRIu64 ") = %" PRIu64 "\n",
           pub_e, my_phi, g);
    if (g != 1) {
        printf("  [ERROR] e and φ are not coprime!\n");
        return 1;
    }
    printf("  [OK — e and φ are coprime]\n");

    int64_t x, y;
    int64_t g2 = ext_gcd((int64_t)pub_e, (int64_t)my_phi, &x, &y);
    printf("  ext_gcd(e=%" PRId64 ", φ=%" PRId64 ") → gcd=%" PRId64
           ", x=%" PRId64 ", y=%" PRId64 "\n",
           (int64_t)pub_e, (int64_t)my_phi, g2, x, y);
    printf("  Equation: e*x + φ*y = gcd  →  %" PRId64 "*%" PRId64
           " + %" PRId64 "*%" PRId64 " = %" PRId64 "\n",
           (int64_t)pub_e, x, (int64_t)my_phi, y, g2);

    int64_t d = x % (int64_t)my_phi;
    if (d < 0) d += (int64_t)my_phi;
    printf("  Private key d = x mod φ = %" PRId64 "\n", d);

    uint64_t verify = (uint64_t)(((uint64_t)pub_e * (uint64_t)d) % my_phi);
    printf("  Verify: e*d mod φ = %" PRIu64 " %s\n",
           verify, verify == 1 ? "[OK]" : "[FAIL]");

    *out_n   = my_n;
    *out_phi = my_phi;
    *out_d   = d;
    return 0;
}

要点：d 必须从负的 x 调整为正数。最后一层验证 e*d mod φ == 1 是"验证之验证"——确保前面的所有计算都正确。

练习 6-8: encrypt, decrypt, main — 加解密与主流程

solution_rsa_full.c

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>

/* TODO 6: RSA 加密 */
static uint64_t encrypt(uint64_t msg, uint64_t pub_exp, uint64_t modulus) {
    return fast_pow(msg, pub_exp, modulus);
}

/* TODO 7: RSA 解密 */
static uint64_t decrypt(uint64_t cipher, uint64_t priv_exp, uint64_t modulus) {
    return fast_pow(cipher, priv_exp, modulus);
}

/* TODO 8: 主流程 */
int main(void) {
    printf("=== RSA Public-Key Crypto Demo (uint64 toy version) ===\n\n");

    /* Step 1: 参数与素性验证 */
    printf("Step 1 — RSA Parameter Setup & Primality Verification:\n");
    printf("  Prime p = %" PRIu64 " — Miller-Rabin: %s\n",
           p, is_prime(p) ? "prime ✓" : "composite ✗");
    printf("  Prime q = %" PRIu64 " — Miller-Rabin: %s\n",
           q, is_prime(q) ? "prime ✓" : "composite ✗");
    printf("  Modulus n = p*q = %" PRIu64 "\n", n);
    printf("  Euler φ(n) = (p-1)*(q-1) = %" PRIu64 "\n", phi);
    printf("  Public exponent e = %" PRIu64 "\n", e);
    printf("  Plaintext message m = %" PRIu64 "\n\n", m);

    /* Step 2: 密钥生成 */
    printf("Step 2 — Key Generation:\n");
    uint64_t gen_n, gen_phi;
    int64_t d;
    if (gen_keys(p, q, e, &gen_n, &gen_phi, &d) != 0) {
        printf("[FATAL] Key generation failed!\n");
        return 1;
    }
    printf("\n");

    /* Step 3: 加密 */
    uint64_t c = encrypt(m, e, n);
    printf("Step 3 — Encryption (c = m^e mod n):\n");
    printf("  c = %" PRIu64 "^%" PRIu64 " mod %" PRIu64 "\n", m, e, n);
    printf("    = fast_pow(%" PRIu64 ", %" PRIu64 ", %" PRIu64 ")\n",
           m, e, n);
    printf("    = %" PRIu64 "\n\n", c);

    /* Step 4: 解密 */
    uint64_t mp = decrypt(c, (uint64_t)d, n);
    printf("Step 4 — Decryption (m' = c^d mod n):\n");
    printf("  m' = %" PRIu64 "^%" PRId64 " mod %" PRIu64 "\n", c, d, n);
    printf("     = fast_pow(%" PRIu64 ", %" PRId64 ", %" PRIu64 ")\n",
           c, d, n);
    printf("     = %" PRIu64 "\n\n", mp);

    /* Step 5: 验证 */
    printf("Step 5 — Verification:\n");
    printf("  Original message  m  = %" PRIu64 "\n", m);
    printf("  Decrypted message m' = %" PRIu64 "\n", mp);
    printf("  m' == m  →  RSA works! ✓\n");

    return 0;
}

要点：PRIu64 和 PRId64 是来自 <inttypes.h> 的宏，必须写成 "%" PRIu64（引号的断开位置很关键——PRIu64 本身不在引号内）。Step 5 最后以 Unicode ✓ (U+2713) 结尾。

对照检查：ext_gcd 的递归基准是 b==0 吗？Miller-Rabin 的 s 循环条件是 r < s-1 吗？gen_keys 中将 d 从负值转为正值了吗？fast_pow 的每次乘法后都 % mod 了吗？printf 中 PRIu64 写成 "%" PRIu64（而非 "PRIu64"）了吗？

---

课堂讨论

1. 为什么公钥指数 e 必须与 φ(n) 互质？如果 gcd(e, φ) ≠ 1，系统还能工作吗？
2. Miller-Rabin 是概率素性测试，为什么本课使用 {2, 3, 5, 7, 11} 可以给出确定性结果？这个确定性维持到什么范围？
3. 如果有人截获密文 c=2557 和公钥 (e=17, n=3233)，能恢复明文 m=42 吗？为什么真实 RSA 不行？
4. 快速幂中每次乘法后 % mod 的作用是什么？？如果 n 大到 n² 超出 uint64_t 范围，fast_pow 还安全吗？
5. gen_keys 中为什么需要"验证 e 的范围"和"验)，即 e*d mod φ == 1"两重检查？它们各防什么错误？
6. 教科书式 RSA 与真实 HTTPS/TLS 中的 RSA 有什么关键区别？为什么不能直接用本课实现加密网络通信？

讨论答案

Q1: e 为什么必须与 φ 互质？

解密依赖 e 模 φ(n) 的乘法逆元 d（即 e*d ≡ 1 mod φ(n)）。整数 a 模 m 存在乘法逆元当且仅当 gcd(a, m) = 1。

如果 gcd(e, φ) ≠ 1：

• 不存在 d 使 e*d ≡ 1 mod φ
• 无法解密：不存在合法的私钥
• 即使尝试用 ext_gcd(e, φ)，得到的 g > 1，方程 e*x + φ*y = g 中的 x 不是模逆元

这就是 gen_keys 中必须检查 gcd 的原因。实际应用中，常用固定 e=65537（费马素数 2^16+1）因为它二进制只有两个 1，加密运算极快，几乎总是和 φ 互质。

Q2: Miller-Rabin 的确定性从何而来？

Miller-Rabin 本身是概率算法——对 k 个随机见证人，错误概率 < 4^(-k)。但 Arnault、Jaeschke、Sinclair 等人的研究证明了：如果使用特定的固定见证人集合，可以对一定范围内的所有 n 给出正确判定。

关键转折：

1. Jaeschke (1993) 证明了 {2, 3, 5, 7, 11} 对 n < 2,152,302,898,747 确定
2. Jim Sinclair 在 2011 年用大量计算验证了该集合对 n < 2^64 有效
3. 因为 2^64 ≈ 1.8×10^19 > uint64_t 最大值，所以在 C 语言 uint64_t 范围内是确定性的

但注意：这不意味着你可以随便选 5 个见证人都行——必须是经过严格数学证明的具体集合。对 64 位整数，{2, 325, 9375, 28178, 450775, 9780504, 1795265022} 是另一个已知的确定性见证人集合。

Q3: 为什么本题可被破解而真实 RSA 不行？

本题的破解思路：

已知：c=2557, e=17, n=3233

1. 分解 n=3233 → 找出 p=61, q=53（很简单——n 只有 12 位）
2. φ = (61-1)×(53-1) = 3120
3. d = 17⁻¹ mod 3120 = 2753  
4. m = 2557^2753 mod 3233 = 42 ✓

真实 RSA n 有 2048 位（617 个十进制位）。分解这样的 n：

• 试除法：约 10^308 步，宇宙年龄都不够
• 最先进算法（数域筛法 GNFS）：子指数时间，但 2048 位仍需数十亿年
• 量子计算（Shor 算法）：理论可行，但规模化量子计算机尚不存在

安全性建立在"大整数分解"这个假设的计算困难性上——不是绝对安全，而是"计算上不可行"。当量子计算机实用化，基于因子分解的 RSA 将被淘汰，这也是后量子密码学（PQC）的研究方向。

Q4: 取模运算与 uint64_t 的限制

每次乘法后取模有两层作用：

1. 防止溢出：结果始终在 [0, mod-1] 范围内。本题 mod=3233，最大中间值 ≈ 10^7，安全。但如果 mod 达到 2^32，mod² ≈ 2^64 就逼近 uint64_t 上限——再大就要溢出。

2. 数学正确性：模运算分配律保证 ((a%m)*(b%m))%m = (a*b)%m，分步取模不改变结果。

当 n 超出 uint64_t 安全范围时，需要使用任意精度算术库（GMP、OpenSSL BIGNUM），核心操作是蒙哥马利模乘（Montgomery Multiplication）——专为大数据模乘优化的算法，避免除法运算。

本课的 fast_pow 在 n < 2^32 时完全安全，n 在 2^32 到 ~2^32 之间需要额外注意。这是"玩具版"RSA 的核心限制之一。

Q5: gen_keys 多重检查的设计哲学

检查 1: 1 < e < φ
  防什么？防 e=0（无加密）、e=1（恒等加密，c=m）、e=φ（无效）

检查 2: gcd(e, φ) == 1
  防什么？防不存在模逆元——这是数学前提，没有 d 就不能解密

检查 3: e*d mod φ == 1
  防什么？防 ext_gcd 计算错误、类型转换错误、或任何实现 bug

第 3 层是"自我验证"的典型实践：用结果反推前提是否成立。这是密码学代码的标准做法——"信任但要验证"（trust but verify）。

printf 的格式严格匹配 expected_output.txt 也是类似的防御思维：多一个空格、少一个换行都会导致 make test 失败。

Q6: 教科书 RSA vs 真实 TLS RSA

区别	教科书 RSA（本课）	TLS RSA（工业级）
填充	无	OAEP（加密）/ PSS（签名）
安全性	确定性（同输入→同输出）	概率性（随机填充）
CCA 安全	不安全	安全（IND-CCA2）
模数大小	12 位 (3233)	2048-4096 位
速度	即时	依赖蒙哥马利模乘加速
侧信道防护	无	恒定时间实现
密钥验证	无	验证 p≠q, n=pq, de≡1, 等

核心区别在于填充。不加填充的 RSA 是确定性加密，攻击者可以：

• 预计算常见消息的密文（字典攻击）
• 利用数学性质伪造签名
• 通过"选择密文"攻击解密任意消息

这就是为什么你不能直接用本课实现加密网络通信——不是说算法不对，而是缺少了填充方案、侧信道防护、密钥管理等整套安全基础设施。

---

课后练习

1. 大顶堆版素性测试验证。将 is_prime 中见证人集合扩展到 {2,3,5,7,11,13}，验证 10000 以内的所有素数是否都能被正确判定。研究 Carmichael 数 561、1105、1729 是否被正确发现为合数。

   知识点提示：Carmichael 数能通过费马小定理测试（对所有 a，a^(n-1)≡1 mod n），但 Miller-Rabin 能检测出来——因为它的平方根检测拒绝了 Carmichae l数。

   参考解答

   ex1_carmichael_test.c

   #include <inttypes.h>
   #include <stdint.h>
   #include <stdio.h>
   
   // 复用前面的 is_prime, fast_pow...
   
   int main(void) {
       uint64_t carmichaels[] = {561, 1105, 1729, 2465, 2821, 6601};
       int n = sizeof(carmichaels) / sizeof(carmichaels[0]);
   
       printf("Carmichael 数 Miller-Rabin 测试:\n");
       for (int i = 0; i < n; i++) {
           printf("  %" PRIu64 ": Miller-Rabin → %s\n",
                  carmichaels[i],
                  is_prime(carmichaels[i]) ? "prime (mistake!)" : "composite ✓");
       }
       return 0;
   }
   
   /* 预期输出: 所有 Carmichael 数都判定为 composite */

   要点：561 = 3×11×17，费马测试漏检（对所有 a 满足 a^560≡1），但 Miller-Rabin 的平方根检测会在某个步骤发现非平凡平方根。

2. RSA 签名实现。实现 sign(msg, d, n) 和 verify(msg, sig, e, n) 两个函数，展示 RSA 如何用于数字签名。签名 = 用私钥"加密"消息，验证 = 用公钥"解密"签名再比较。

   知识点提示：RSA 签名是加解密的逆操作——私钥签名（计算 s = m^d mod n），公钥验证（检查 m == s^e mod n）。这使得只有私钥持有者能签名，但任何人都能验证。

   参考解答

   ex2_rsa_signature.c

   #include <inttypes.h>
   #include <stdint.h>
   #include <stdio.h>
   
   /* 签名：s = m^d mod n（与解密公式相同，但没有"机密性"，只有认证性）*/
   uint64_t sign(uint64_t msg, uint64_t priv_key, uint64_t modulus) {
       return fast_pow(msg, priv_key, modulus);
   }
   
   /* 验证：m' = s^e mod n，检查 m' == m */
   int verify(uint64_t msg, uint64_t signature,
              uint64_t pub_key, uint64_t modulus) {
       uint64_t recovered = fast_pow(signature, pub_key, modulus);
       return recovered == msg;
   }
   
   int main(void) {
       uint64_t msg = 42;
       uint64_t d = 2753, e = 17, n = 3233;
   
       uint64_t sig = sign(msg, d, n);
       printf("Message: %" PRIu64 "\n", msg);
       printf("Signature: %" PRIu64 "\n", sig);
       printf("Verification: %s\n", verify(msg, sig, e, n) ? "PASS" : "FAIL");
       printf("Verify tampered: %s\n", verify(43, sig, e, n) ? "PASS" : "FAIL");
       return 0;
   }
   
   /* 预期输出:
      Message: 42
      Signature: 2557
      Verification: PASS
      Verify tampered: FAIL
   */

   关键观察：签名值 2557 恰好与加密密文相同（因为 m=42, e=17 的加密和 m=42, d=2753 的签名在这个特定组合下巧合相等——一般情况下不同）。真正应用中消息先做哈希再签名。

3. 模拟暴力破解。编写一个程序，给定公钥 (e, n)，尝试分解 n 并计算私钥 d。用它破解 (e=17, n=3233)，体会玩具 RSA 的脆弱性。

   知识点提示：对 n=3233 使用从 2 到 √n 的试除法。思考如果 n 是 2048 位的数，试除法需要多少步？理解"计算上不可行"的含义。

   参考解答

   ex3_factor_attack.c

   #include <inttypes.h>
   #include <stdint.h>
   #include <stdio.h>
   #include <math.h>
   
   int main(void) {
       uint64_t n = 3233;
       uint64_t e = 17;
   
       uint64_t p = 0, q = 0;
       uint64_t limit = (uint64_t)sqrt((double)n);
   
       for (uint64_t i = 2; i <= limit; i++) {
           if (n % i == 0) {
               p = i; q = n / i; break;
           }
       }
   
       if (p == 0) {
           printf("Failed to factor n\n"); return 1;
       }
   
       printf("Factored: %" PRIu64 " = %" PRIu64 " × %" PRIu64 "\n", n, p, q);
   
       uint64_t phi = (p - 1) * (q - 1);
       int64_t x, y;
       ext_gcd((int64_t)e, (int64_t)phi, &x, &y);
       int64_t d = x % (int64_t)phi;
       if (d < 0) d += (int64_t)phi;
   
       printf("Computed d = %" PRId64 "\n", d);
       printf("e*d mod φ = %" PRIu64 "\n", (e * (uint64_t)d) % phi);
   
       // 演示解密
       uint64_t cipher = 2557;
       uint64_t plain = fast_pow(cipher, (uint64_t)d, n);
       printf("Decrypted: %" PRIu64 " → %" PRIu64 "\n", cipher, plain);
       return 0;
   }
   
   /* 预期: 成功分解 3233 = 61 × 53，计算 d = 2753，解密 2557 → 42 */

   试除法对 n=3233 运行 √3233 ≈ 57 步，瞬时完成。对 2048 位的 n，需 √(2^2048) = 2^1024 步，在可观测宇宙中不可能完成——这就是 RSA 安全性的数学基础。

---

参考资料

• Rivest, Shamir & Adleman (1978). A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM.
• Miller, G. L. (1976). Riemann's Hypothesis and Tests for Primality. JCSS.
• Jaeschke, G. (1993). On Strong Pseudoprimes to Several Bases. Mathematics of Computation.
• Wikipedia: RSA (cryptosystem) — 加解密原理、填充方案、安全分析
• Wikipedia: Miller–Rabin primality test — 素性测试的完整数学证明与见证人表
• RFC 8017 — PKCS #1 v2.2: RSA Cryptography Standard（OAEP 填充方案的工业标准）
• Ferguson, Schneier & Kohno (2010). Cryptography Engineering. Wiley.

"The security of RSA is based on the difficulty of factoring large integers." — Ron Rivest