题目来源：CryptoHack - Public-Key Cryptography 公钥密码学模块 难度：20 分 · 15714 次解题 · 26 个解决方案 知识标签：RSA、模乘法逆元、欧拉函数、扩展欧几里得算法

一、题目背景

题目给出了 RSA 中的两个素数和公钥指数：

p = 857504083339712752489993810777 q = 1029224947942998075080348647219 e = 65537

要求计算对应的私钥：

d≡e−1(modφ(N))

其中 φ(N) 是欧拉函数（Euler's totient function），N=pq。

二、RSA 加密原理简述

在进入计算之前，先理一下 RSA 的整体框架，理解「为什么私钥是 e−1modφ(N)」。

1. 密钥生成

• 随机选取两个大素数 p,q，计算 N=pq。N 是模数，会公开。
• 计算欧拉函数 φ(N)=(p−1)(q−1)。这是秘密，因为分解 N 困难。
• 选取公钥指数 e，要求 gcd(e,φ(N))=1。常用值是 65537=216+1。
• 计算私钥 d≡e−1(modφ(N))，即 e⋅d≡1(modφ(N))。

最终：

• 公钥：(N,e)
• 私钥：(N,d)

2. 加密与解密

加密：加密：c=memodN

解密：解密：m=cdmodN

3. 为什么 d=e−1modφ(N) 能解密？

由欧拉定理，当 gcd(m,N)=1 时：

mφ(N)≡1(modN)

若 e⋅d≡1(modφ(N))，即 ed=kφ(N)+1，则：

cd=(me)d=med=mkφ(N)+1=(mφ(N))k⋅m≡1k⋅m≡m(modN)

这就是 RSA 能正确解密的数学基础。私钥 d 之所以被称为「陷阱门（trapdoor）」，正是因为它让我们能快速反转 m↦memodN 这个函数，而没有 d（也就是没有 φ(N)）的攻击者只能去分解 N。

三、解题步骤

Step 1：计算 N 和 φ(N)

N=p⋅q

φ(N)=(p−1)(q−1)

由于 p,q 都是素数，φ(N) 直接由公式给出（这是关键：只有在已知 p,q 的情况下才能快速算出 φ(N)，否则需要先分解 N）。

Step 2：求 e 模 φ(N) 的乘法逆元

我们需要找到 d 使得：

e⋅d≡1(modφ(N))

这是一个模乘法逆元问题，标准解法有两种：

1. 扩展欧几里得算法（Extended Euclidean Algorithm）：在求 gcd(e,φ(N)) 的同时得到一组系数 (x,y) 满足 ex+φ(N)y=gcd=1，于是 d≡x(modφ(N))。
2. 费马小定理 / 欧拉定理：当模数为素数时可用 a−1≡ap−2(modp)，但这里 φ(N) 不是素数，不能用此法。

本题用扩展欧几里得即可。

四、代码实现

方法一：Python 内置（Python 3.8+）

Python 3.8 起的 pow(a, -1, m) 直接支持模乘法逆元，背后用的就是扩展欧几里得：

p = 857504083339712752489993810777
q = 1029224947942998075080348647219
e = 65537

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

# 模乘法逆元：d = e^(-1) mod phi(N)
d = pow(e, -1, phi)

print("N   =", N)
print("phi =", phi)
print("d   =", d)

# 验证
assert (e * d) % phi == 1
print("验证 (e*d) mod phi =", (e * d) % phi, "=> OK")

方法二：手写扩展欧几里得算法

为了更直观地理解原理，可以手写一遍 EEA：

def egcd(a, b):
    """返回 (g, x, y) 使得 a*x + b*y = g = gcd(a, b)"""
    if b == 0:
        return a, 1, 0
    g, x1, y1 = egcd(b, a % b)
    return g, y1, x1 - (a // b) * y1

def modinv(a, m):
    g, x, _ = egcd(a, m)
    if g != 1:
        raise Exception(f"{a} 在模 {m} 下无逆元 (gcd={g})")
    return x % m

d = modinv(e, phi)
print("d   =", d)
```

两种方法得到的结果完全一致。

运行结果

N   = 882564595536224140639625987659416029426239230804614613279163
phi = 882564595536224140639625987657529300394956519977044270821168
d   = 121832886702415731577073962957377780195510499965398469843281
验证 (e*d) mod phi = 1 => OK

五、结果验证

为确保正确性，做两个检查：

检查 1：e⋅d≡1(modφ(N))

e * d = 65537 * 121832886702415731577073962957377780195510499965398469843281
      = 7986803722695006743881348245664854549172812954392417215712469148697
(e * d) mod phi(N) = 1  ✓

检查 2：用 (N,e) 加密一个测试明文，再用 d 解密，能还原

```python
m = 20260704                       # 任取一个测试明文
c = pow(m, e, N)                   # 加密
m2 = pow(c, d, N)                  # 解密
assert m == m2
print("解密还原 m =", m2, "=> OK")

运行后 m2 == 20260704，验证通过，说明 d 确实是正确的私钥。

六、Flag

121832886702415731577073962957377780195510499965398469843281

七、一点拓展

1. 为什么 e 通常取 65537？

65537=216+1 是一个费马素数。选择它的原因：

• 是素数，能提高与 φ(N) 互素的概率；
• 二进制表示为 1 0000 0000 0000 0001，只有两个 1，模平方算法只需 17 次乘法，加密速度快；
• 比早期的 e=3 更安全（e=3 时若消息过小或相同消息发给多个接收者，容易遭受 Coppersmith / Håstad 攻击）。

2. 实际 RSA 的安全性依赖

本题直接给出了 p,q，所以计算 φ(N) 是 O(1) 的。但在真实 RSA 中，攻击者只能拿到公开的 (N,e)，必须先分解 N 才能算出 φ(N) 和 d。当 N 足够大（目前推荐 2048 位以上）时，大整数分解是公认的困难问题，这就是 RSA 安全性的基石。

3. Python 3.8 以下怎么办？

老版本 Python 没有 pow(e, -1, m)，可以用 gmpy2.invert(e, phi) 或者直接调用上面手写的 modinv。竞赛/CTF 中 gmpy2 几乎是标配。

八、小结

这道题的核心知识点：

1. 私钥的本质：d 是 e 在模 φ(N) 下的乘法逆元，由 ed≡1(modφ(N)) 定义。
2. 欧拉函数：当 N=pq 且 p,q 为素数时，φ(N)=(p−1)(q−1)，这是 RSA 的「陷阱门」信息。
3. 求解方法：扩展欧几里得算法，Python 中即 pow(e, -1, phi)。
4. 安全前提：所有这些计算都依赖于已知 p,q；若只知道 N，则需先分解，这正是 RSA 安全性的来源。