欧拉函数与欧拉定理#

对于正整数 n，欧拉函数 φ(n) 表示小于 n 且与 n 互素的正整数个数。当 n = pq（p、q 为不同素数）时，φ(n) = (p-1)(q-1)。

欧拉定理指出：若 gcd(a, n) = 1，则 $a^{\varphi(n)} \equiv 1 \pmod{n}$。RSA 解密正确性的核心保证来源于此：由于 $ed \equiv 1 \pmod{\varphi(n)}$，存在整数 k 使得 $ed = 1 + k\varphi(n)$，于是

$m^{ed} \equiv m^{1 + k\varphi(n)} \equiv m \cdot (m^{\varphi(n)})^k \equiv m \pmod{n}$

扩展欧几里得算法#

RSA 的私钥 d 是公钥 e 在模 φ(n) 下的乘法逆元，即满足 $ed \equiv 1 \pmod{\varphi(n)}$。求模逆需要扩展欧几里得算法（Extended GCD），它不仅计算两个整数的最大公约数，还找到满足 $ax + by = \gcd(a, b)$ 的整数系数 x 和 y。

1
def extended_gcd(a: int, b: int) -> tuple[int, int, int]:
2
    if b == 0:
3
        return a, 1, 0
4
    g, x1, y1 = extended_gcd(b, a % b)
5
    return g, y1, x1 - (a // b) * y1
6

7
def mod_inverse(a: int, m: int) -> int:
8
    g, x, _ = extended_gcd(a, m)
9
    if g != 1:
10
        raise ValueError(f"modular inverse does not exist: gcd({a}, {m}) = {g}")
11
    return x % m

扩展欧几里得算法的递归实现优雅但容易出错。关键在于理解递归返回时的系数如何变换：如果已知 b * x1 + (a % b) * y1 = g，代入 a % b = a - (a // b) * b，重组后得到 a * y1 + b * (x1 - (a // b) * y1) = g，因此新的系数为 (y1, x1 - (a // b) * y1)。

密钥生成#

RSA 密钥生成需要两个大素数 p 和 q。在真实应用中，p 和 q 通常为 1024 位或 2048 位，但挑战中使用较小的位数（64 位）以便于调试。

生成素数使用了 Miller-Rabin 概率素性检验：

1
def is_prime(n: int, k: int = 40) -> bool:
2
    if n < 2:
3
        return False
4
    if n == 2 or n == 3:
5
        return True
6
    if n % 2 == 0:
7
        return False
8

9
    r, d = 0, n - 1
10
    while d % 2 == 0:
11
        r += 1
12
        d //= 2
13

14
    for _ in range(k):
15
        a = random.randrange(2, n - 1)
16
        x = pow(a, d, n)
17
        if x == 1 or x == n - 1:
18
            continue
19
        for _ in range(r - 1):
20
            x = pow(x, 2, n)
21
            if x == n - 1:
22
                break
23
        else:
24
            return False
25
    return True

Miller-Rabin 算法的核心思想是把 n - 1 写成 $2^r \cdot d$（d 为奇数），然后检查 $a^d, a^{2d}, a^{4d}, \ldots, a^{2^r d}$ 这个序列。如果 n 是素数，这个序列要么全部是 1，要么在某处出现 -1。如果两个条件都不满足，n 一定是合数。进行 k 轮测试后，错误概率最多为 $1/4^k$，这里 k=40 已经足够安全。

有了素性检验后，随机生成指定位数的奇数并测试，直到找到素数：

1
def generate_prime(bits: int = 64) -> int:
2
    while True:
3
        candidate = random.getrandbits(bits)
4
        candidate |= 1  # 确保奇数
5
        if is_prime(candidate):
6
            return candidate

完整的密钥生成函数如下：

1
def generate_rsa_keys(bits: int = 64) -> tuple[tuple[int, int], tuple[int, int]]:
2
    p = generate_prime(bits)
3
    q = generate_prime(bits)
4
    while p == q:
5
        q = generate_prime(bits)
6

7
    n = p * q
8
    phi = (p - 1) * (q - 1)
9

10
    e = 3
11
    while gcd(e, phi) != 1:
12
        e += 2
13

14
    d = mod_inverse(e, phi)
15
    return (e, n), (d, n)

这里选择 e = 3 作为公钥指数是一个有争议的做法——虽然 e = 3 在特定条件下（小消息、广播攻击）存在安全隐患，但对于教科书 RSA 实现来说非常简洁。实际应用中更常用 e = 65537（即 $2^{16}+1$），它是一个费马素数，既保证计算效率又避免了小 e 带来的问题。

加密与解密#

加密和解密的核心就是模幂运算。Python 内置的 pow(base, exp, mod) 使用了快速幂取模算法，时间复杂度为 $O(\log \text{exp})$：

1
def rsa_encrypt(plaintext: int, pubkey: tuple[int, int]) -> int:
2
    e, n = pubkey
3
    return pow(plaintext, e, n)
4

5
def rsa_decrypt(ciphertext: int, privkey: tuple[int, int]) -> int:
6
    d, n = privkey
7
    return pow(ciphertext, d, n)

测试用一个简单的数字消息验证加解密正确性：

1
Original:  42
2
Encrypted: 8241602486128260 (示例，每次运行 n 不同)
3
Decrypted: 42
4
Match: True

对于文本消息，可以使用 int.from_bytes 将字节串转换为整数：

1
text = b"Hello, RSA!"
2
m = int.from_bytes(text, "big")
3
# ... 加密解密后 ...
4
recovered = dec.to_bytes((dec.bit_length() + 7) // 8, "big")

这里需要注意：消息转换为整数后必须小于 n，否则无法正确解密。因此需要根据消息大小选择合适的密钥长度。

实现中的关键细节#

RSA 实现中有几个容易出错的地方：

• p 和 q 必须不同。如果 p = q，则 φ(n) = p(p-1) 而非 (p-1)(q-1)，解密会失效。
• e 必须与 φ(n) 互素，否则模逆不存在。这里如果 e=3 不满足条件就 +2 推进（跳到下一个奇数），直到 gcd(e, phi) = 1。
• Miller-Rabin 中要处理 n=2 和 n=3 的边界情况，以及排除偶数。
• 模逆计算后需要取模：扩展欧几里得算法返回的 x 可能是负数，需要用 x % m 得到正的模逆值。

未遮掩消息的数学定义#

在 RSA 中，“未遮掩消息”（unconcealed message）是指那些加密后等于自身的消息，即满足：

$m^e \equiv m \pmod{n}$

对任何 RSA 系统，总是存在一些平凡的未遮掩消息（m = 0 一定满足，m = 1 也满足）。但当 e 选择不当时，可能会有更多的 m 满足这个条件，这就削弱了加密的隐蔽性。

一个问题自然地浮现：给定了 n = pq，有多少个 m 满足这个条件？

利用中国剩余定理分解#

由于 n = pq 且 p、q 互素，中国剩余定理（CRT）告诉我们：$m^e \equiv m \pmod{n}$ 等价于下面两个同余式同时成立：

$m^e \equiv m \pmod{p}$ $m^e \equiv m \pmod{q}$

在模素数 p 下，$m^e \equiv m$ 等价于 $m(m^{e-1} - 1) \equiv 0$，即要么 $m \equiv 0 \pmod{p}$，要么 $m^{e-1} \equiv 1 \pmod{p}$。

由费马小定理，$m^{p-1} \equiv 1 \pmod{p}$（对 m 不被 p 整除的情况）。方程 $m^{e-1} \equiv 1 \pmod{p}$ 在模 p 的乘法群（阶为 p-1）中解的数量等于 $\gcd(e-1, p-1)$。加上 m = 0，模 p 下的解共有 $1 + \gcd(e-1, p-1)$ 个。

同理模 q 下有 $1 + \gcd(e-1, q-1)$ 个解。根据中国剩余定理的乘法原理，模 n 下的解的总数为两者的乘积：

$U(e) = (1 + \gcd(e-1, p-1)) \times (1 + \gcd(e-1, q-1))$

这就是 Project Euler 182 的核心公式。

求解过程#

有了公式，问题变成了一个搜索优化问题。p-1 = 1008，q-1 = 3642，φ = 3671136。

第一步：遍历所有有效的 e（1 < e < φ，gcd(e, φ) = 1），计算 U(e)，找出最小值。

第二步：遍历所有有效的 e，找出达到该最小值的那些，求和。

1
from math import gcd
2

3
p = 1009
4
q = 3643
5
phi = (p - 1) * (q - 1)
6
p1 = p - 1  # 1008
7
q1 = q - 1  # 3642
8

9
def unconcealed_count(e: int) -> int:
10
    return (1 + gcd(e - 1, p1)) * (1 + gcd(e - 1, q1))
11

12
# 第一步：找最小值
13
min_count = float("inf")
14
for e in range(2, phi):
15
    if gcd(e, phi) == 1:
16
        u = unconcealed_count(e)
17
        if u < min_count:
18
            min_count = u
19

20
# 第二步：求和
21
total = 0
22
for e in range(2, phi):
23
    if gcd(e, phi) == 1 and unconcealed_count(e) == min_count:
24
        total += e

这个算法的核心洞察在于：U(e) 的值完全由 $\gcd(e-1, p-1)$ 和 $\gcd(e-1, q-1)$ 决定。要使 U(e) 最小，需要让这两个 gcd 尽可能小——但 e-1 是偶数（因为 e 必须是奇数才能与 φ 互素），所以与 1008（有很多 2 因子）的 gcd 至少为 2。

每个 e 的 U(e) 值只需计算一次，且 φ 范围约为 3.67 × 10⁶，直接遍历完全可行。

为什么未遮掩消息是一个安全问题#

如果存在大量的 m 使得 $m^e \equiv m \pmod{n}$，这意味着：

• 攻击者如果碰巧选择了这样一个 m，加密并没有改变它——密文就是明文本身
• 在极端情况下（U(e) 很大），有相当比例的消息在 RSA 加密下是”透明的”
• 这不是 RSA 算法的 bug，而是公钥指数 e 选择不当导致的后果

事实上，如果 e = 1（虽然通常在要求范围之外），则 U(1) = (1 + gcd(0, p-1)) × (1 + gcd(0, q-1)) = (1 + p-1) × (1 + q-1) = pq = n，即所有消息都是未遮掩的——因为”加密”退化为恒等变换。

这就是为什么实际应用中通常选择 e = 65537（$2^{16}+1$）：它是一个素数，gcd(e-1, p-1) = gcd(65536, p-1) 只有 p-1 与 65536 共享的少数 2 因子，通常非常小，从而保持 U(e) 接近最小值。