LOADING

加载过慢请开启缓存 浏览器默认开启

Project Euler 182 中的 RSA 未加密消息

Cryptography 密码学 RSA Project Euler 阅读量 0

Project Euler 182 中的 RSA 未加密消息

Project Euler 182 讨论一个看起来有点反直觉的问题：RSA 加密以后，是否可能出现密文仍然等于明文？

也就是：

c = m^e mod n
c = m

满足这个条件的 m 被称为 unconcealed message，可以理解为“没有被隐藏的消息”。这不是 RSA 实现写错了，而是某些明文在特定指数 e 下天然满足这个同余关系。

本文使用平台给出的真实参数：

p = 1009
q = 3643

最终目标是找出所有合法 e 中，让 unconcealed messages 数量最少的那些 e，再求它们的和。

1. RSA 基本过程

RSA 先选两个素数：

p, q

然后计算：

n = p * q
phi = (p - 1) * (q - 1)

公钥指数 e 需要满足：

1 < e < phi
gcd(e, phi) = 1

加密为：

c = m^e mod n

解密指数 d 是 e 关于 phi 的模逆：

e * d = 1 mod phi

这里的 Euler 题不是让我们实现完整加解密，而是研究不同 e 会让多少个 m 满足：

m^e = m mod n

2. 为什么不能直接枚举所有 m

一个最直接的想法是：对每个合法 e，再枚举 m=0..n-1，检查 pow(m, e, n) == m。

但这样做没有必要。因为：

n = 1009 * 3643 = 3675787

合法 e 也很多。双重枚举会把问题做得很笨，而且容易超时。

更好的办法是先推导计数公式，只枚举 e，不枚举每一个 m。

3. 计数公式推导

题目条件是：

m^e ≡ m (mod n)

因为 n = p q，可以分别在模 p 和模 q 下考虑。

先看模 p：

m^e ≡ m (mod p)

移项：

m^e - m ≡ 0 (mod p)

提取 m：

m * (m^(e-1) - 1) ≡ 0 (mod p)

所以模 p 下有两类解：

m ≡ 0 (mod p)
m^(e-1) ≡ 1 (mod p)

在模 p 的非零乘法群里，群阶是 p-1。方程 x^(e-1)=1 的解数是：

gcd(e - 1, p - 1)

再加上 m=0 这个解，模 p 下解数就是：

gcd(e - 1, p - 1) + 1

同理，模 q 下解数是：

gcd(e - 1, q - 1) + 1

最后由中国剩余定理组合，模 n=pq 下总数量为：

(gcd(e - 1, p - 1) + 1) * (gcd(e - 1, q - 1) + 1)

这个公式就是整道题的关键。

4. 先写计数函数

代码很短：

import math


def unconcealed_count(e: int, p: int, q: int) -> int:
    return (math.gcd(e - 1, p - 1) + 1) * (math.gcd(e - 1, q - 1) + 1)

它只依赖 e、p、q，不需要枚举所有明文。

题目给了样例：

p = 19
q = 37
e = 181

样例结果应为：

703

所以正式扫描前先做这个检查。

5. 扫描所有合法 e

完整扫描逻辑如下：

def project_euler_182_details() -> dict[str, int | list[tuple[int, int]]]:
    p, q = 1009, 3643
    phi = (p - 1) * (q - 1)
    best = None
    total = 0
    count = 0
    valid_e = 0
    first_hits: list[tuple[int, int]] = []

    for e in range(2, phi):
        if math.gcd(e, phi) != 1:
            continue

        valid_e += 1
        value = unconcealed_count(e, p, q)

        if best is None or value < best:
            best = value
            total = e
            count = 1
            first_hits = [(e, value)]
        elif value == best:
            total += e
            count += 1
            if len(first_hits) < 8:
                first_hits.append((e, value))

    return {
        "p": p,
        "q": q,
        "n": p * q,
        "phi": phi,
        "valid_e": valid_e,
        "min_unconcealed": best or 0,
        "min_count": count,
        "sum": total,
        "first_hits": first_hits,
    }

这里保存了几个信息：

valid_e       合法 e 的数量
best          当前最小 unconcealed message 数量
count         达到最小值的 e 的数量
total         这些 e 的总和
first_hits    前几个达到最小值的 e，方便检查

6. 真实运行结果

运行脚本：

python work\experiment_03_rsa_math\02_solve_project_euler_182.py

真实 VSCode 运行截图如下：

Project Euler 182 运行截图

输出中的关键结果是：

p=1009, q=3643
n=3675787
phi=3671136
Valid e count: 1047167
Minimum unconcealed messages: 9
Number of e values at minimum: 217800
Final answer: 399788195976

最终答案：

399788195976

7. 和 RSA 实现放在一起验证

实验里还写了一个 RSA 基本实现，用来验证模逆、加密、解密流程。

def egcd(a: int, b: int) -> tuple[int, int, int]:
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - (a // b) * y1


def invmod(a: int, m: int) -> int:
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError("inverse does not exist")
    return x % m

演示用小素数只用于验证公式：

public key : e=3, n=11413
private key: d=7467, n=11413
message    : 42
ciphertext : 5610
decrypted  : 42

截图：

RSA roundtrip 运行截图

8. 常见错误

8.1 把 e 的范围写错

合法 e 必须满足：

1 < e < phi
gcd(e, phi) = 1

如果忘记 gcd(e, phi)=1，会把不能作为 RSA 公钥指数的值也算进去。

8.2 直接枚举每个 m

这道题重点是数论计数公式。枚举所有 m 不是不能做小样例，但对正式参数没有必要。

8.3 样例没验证就跑正式参数

先验证：

p=19, q=37, e=181 -> 703

样例正确后再跑平台参数，调试会稳很多。

8.4 只记录最小值，不记录所有 e 的和

题目要的是所有达到最小值的 e 的总和，不是其中一个 e。

9. 小结

Project Euler 182 的核心是把：

m^e = m mod n

转成可计数的同余方程。最后使用：

(gcd(e-1,p-1)+1)(gcd(e-1,q-1)+1)

避免枚举明文，只扫描合法 e。使用平台真实参数后，最终结果为：

399788195976

参考资料