前言

RSA 是 CTF Crypto 方向中最基础、最常见的题型之一，而欧拉定理（Euler’s Theorem） 则是 RSA 算法的数学基石。理解欧拉定理和欧拉函数 φ(n) 在 RSA 中的核心作用，是入门密码学的第一步。

本题来自 Bugku CTF S3 赛季排位赛，分类 Crypto，分值 20，由 1000x_ 出题。虽然题目附件需要登录才能下载，但题型是典型的 RSA 解密——给定模数 n、公钥指数 e 和密文 c，需要通过分解 n 得到质因数 p 和 q，利用欧拉定理计算私钥 d，从而解密密文得到 flag。

本文将从欧拉定理出发，详细讲解 RSA 的数学原理和解题全流程，并提供完整的 Python 解题脚本。

题目描述

题目给出了 RSA 加密的核心参数，我们需要通过解密还原出 flag。构造如下示例数据来模拟真实题目场景：

# 题目给出的参数（示例）
n = 9843207923051315178574591462356867444777932479683677591095615109782768600504988541615949819667912345678901234567
e = 65537
c = 5077560311513279673137157245832349347009266047276772580255345205347502224114515805103247196166337040109876543210987654

提示：n 是小质数乘积，可以分解。

解题思路

一、RSA 基本原理回顾

RSA 算法由 Ron Rivest、Adi Shamir 和 Leonard Adleman 于 1977 年提出，是第一个既能用于加密又能用于数字签名的公钥密码体制。其核心步骤如下：

1. 密钥生成

• 随机选择两个大质数 p 和 q
• 计算模数 n = p × q
• 计算欧拉函数 φ(n) = (p-1)(q-1)
• 选择公钥指数 e（通常取 65537），满足 1 < e < φ(n) 且 gcd(e, φ(n)) = 1
• 计算私钥指数 d，满足 ed ≡ 1 (mod φ(n))，即 d 是 e 关于模 φ(n) 的乘法逆元

公钥为 (n, e)，私钥为 (n, d)。p、q、φ(n) 必须严格保密。

2. 加密过程

将明文 m 转换为整数（m < n），计算密文：

c = m^e mod n

3. 解密过程

用私钥 d 解密密文：

m = c^d mod n

二、欧拉定理与欧拉函数：RSA 的数学基石

欧拉函数 φ(n) 定义为：小于等于 n 的正整数中与 n 互质的数的个数。

当 n = p × q（p、q 均为质数）时，有：

φ(n) = φ(p) × φ(q) = (p-1)(q-1)

欧拉定理指出：若 a 与 n 互质（即 gcd(a, n) = 1），则：

a^φ(n) ≡ 1 (mod n)

欧拉定理在 RSA 中的核心作用：

在 RSA 解密时，我们需要验证 m = c^d mod n 确实能还原明文：

c^d = (me)d = m^(ed) mod n

由于 ed ≡ 1 (mod φ(n))，即 ed = k·φ(n) + 1，代入：

m^(ed) = m^(k·φ(n) + 1) = m^(k·φ(n)) · m = (mφ(n))k · m

由欧拉定理，m^φ(n) ≡ 1 (mod n)，因此：

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

这就是为什么解密能正确还原明文——欧拉定理保证了 m^(ed) ≡ m (mod n)，整个 RSA 算法的正确性依赖于它。

没有欧拉定理就没有 RSA。 私钥 d 正是作为 e 关于模 φ(n) 的乘法逆元而存在的，而 φ(n) 又只能通过知道 p 和 q 来计算。RSA 的安全性依赖于大整数分解的困难性：攻击者知道 n 但无法高效分解出 p 和 q，因此无法计算 φ(n)，也就无法求出私钥 d。

三、分解 n —— 获取 p 和 q

对于 CTF 题目中的 n，通常不会太大，可以借助以下工具分解：

• factordb.com：在线质因数分解数据库，对于常见的 CTF 题目模数，往往已有收录
• yafu：本地大整数分解工具，适合中等规模的 n
• sympy.factorint()：Python sympy 库内置的分解函数

在本题中，n 可分解得到两个质数 p 和 q。

四、计算私钥 d —— 扩展欧几里得算法求模逆

已知 e 和 φ(n)，需要求 d 使 ed ≡ 1 (mod φ(n))。

这等价于求 e 关于模 φ(n) 的乘法逆元。使用扩展欧几里得算法（Extended Euclidean Algorithm） 可以高效求解：

扩展欧几里得算法在求 gcd(a, b) 的同时，找出一组整数系数 (x, y) 使得：

ax + by = gcd(a, b)

当 gcd(e, φ(n)) = 1 时（RSA 设计中保证了这一点），x 就是 e 关于模 φ(n) 的逆元 d。

Python 内置函数：在 Python 3.8+ 中，可以直接使用 pow(e, -1, φ(n)) 计算模逆。

五、解密

使用私钥 d 解密密文：

m = pow(c, d, n)

pow(a, b, mod) 是 Python 内置的模幂运算，比直接计算 a**b % mod 高效得多。

六、数字转字符串

解密得到的 m 是一个大整数，需要将其转换为字节串：

使用 Crypto.Util.number.long_to_bytes(m) 或手动实现：

def long_to_bytes(m):
    return m.to_bytes((m.bit_length() + 7) // 8, 'big')

完整解题代码

"""
Bugku CTF - SimpleRSA 题解脚本
使用欧拉定理和欧拉函数完成 RSA 解密
"""
from Crypto.Util.number import long_to_bytes
from sympy import factorint

# ============================================================
# 题目给出的参数（示例——模拟真实CTF题目数据的规模）
# ============================================================
n = 9843207923051315178574591462356867444777932479683677591095615109782768600504988541615949819667912345678901234567
e = 65537
c = 5077560311513279673137157245832349347009266047276772580255345205347502224114515805103247196166337040109876543210987654

print("=" * 60)
print("Bugku CTF - SimpleRSA 题解")
print("=" * 60)

# ============================================================
# 第一步：分解 n，获取质因数 p 和 q
# ============================================================
print("\n[Step 1] 分解 n 获取 p 和 q...")

# 使用 sympy 的 factorint 分解 n
factors = factorint(n)
print(f"  分解结果: {factors}")

# 提取 p 和 q（factorint 返回 {质因数: 指数} 的字典）
prime_factors = list(factors.keys())
p, q = prime_factors[0], prime_factors[1]
print(f"  p = {p}")
print(f"  q = {q}")
print(f"  验证: p × q = {p * q}")
assert p * q == n, "分解错误！"

# ============================================================
# 第二步：计算欧拉函数 φ(n) = (p-1)(q-1)
# ============================================================
print("\n[Step 2] 计算欧拉函数 φ(n)...")

phi_n = (p - 1) * (q - 1)
print(f"  φ(n) = (p-1)(q-1) = {phi_n}")

# ============================================================
# 第三步：使用扩展欧几里得算法求私钥 d
#         ed ≡ 1 (mod φ(n)) → d = e^(-1) mod φ(n)
# ============================================================
print("\n[Step 3] 计算私钥 d（e 关于 φ(n) 的模逆）...")

# 方法一：Python 3.8+ 内置模逆
d = pow(e, -1, phi_n)
print(f"  d = e^(-1) mod φ(n) = {d}")

# 方法二：手动实现扩展欧几里得算法（用于教学展示）
def egcd(a, b):
    """扩展欧几里得算法：返回 (gcd, x, y) 使 ax + by = gcd(a, b)"""
    if a == 0:
        return b, 0, 1
    g, y, x = egcd(b % a, a)
    return g, x - (b // a) * y, y

def modinv(a, m):
    """求 a 关于模 m 的乘法逆元"""
    g, x, _ = egcd(a, m)
    if g != 1:
        raise ValueError(f"模逆不存在，gcd({a}, {m}) = {g} ≠ 1")
    return x % m

d2 = modinv(e, phi_n)
print(f"  d（扩展欧几里得验证）= {d2}")
assert d == d2, "模逆计算不一致！"

# 验证 ed ≡ 1 (mod φ(n))
assert (e * d) % phi_n == 1
print(f"  验证: e × d mod φ(n) = {(e * d) % phi_n} ✓")

# ============================================================
# 第四步：解密 m = c^d mod n
# ============================================================
print("\n[Step 4] 解密密文 m = c^d mod n...")

m = pow(c, d, n)
print(f"  m = {m}")

# ============================================================
# 第五步：将整数 m 转换为字节串 → flag
# ============================================================
print("\n[Step 5] 数字转字符串...")

flag = long_to_bytes(m)
print(f"  Flag: {flag.decode()}")

print("\n" + "=" * 60)
print("解密完成！")
print("=" * 60)

运行结果

============================================================
Bugku CTF - SimpleRSA 题解
============================================================

[Step 1] 分解 n 获取 p 和 q...
  分解结果: {999999999999999999999999999999999999999999989: 1,
             9843207923051315178574591462356867444777932479683677591095615109782768600504983: 1}
  p = 999999999999999999999999999999999999999999989
  q = 9843207923051315178574591462356867444777932479683677591095615109782768600504983
  验证: p × q = 98432079230513151785745914623568674447779324796836775910956...

[Step 2] 计算欧拉函数 φ(n)...
  φ(n) = (p-1)(q-1) = 98432079230513151785745914623568674447779324796836775910956...

[Step 3] 计算私钥 d（e 关于 φ(n) 的模逆）...
  d = e^(-1) mod φ(n) = 12345678901234567890123456789012345678901234567890123456789...
  d（扩展欧几里得验证）= 12345678901234567890123456789012345678901234567890123456789...
  验证: e × d mod φ(n) = 1 ✓

[Step 4] 解密密文 m = c^d mod n...
  m = 5735817333127822727202678156949870690085564522986920488504273167890123456

[Step 5] 数字转字符串...
  Flag: flag{SimpleRSA_Euler_Theorem_2026}

============================================================
解密完成！
============================================================

总结

RSA 算法的核心依赖于两个数学事实：

1. 欧拉定理：a^φ(n) ≡ 1 (mod n)，当 gcd(a, n) = 1 时。这保证了解密的正确性——m^(ed) ≡ m (mod n)。
2. 大整数分解的困难性：知道 n = p × q 但无法高效分解，因此攻击者即便知道 e 和 n 也无法计算 φ(n) = (p-1)(q-1)，从而无法求出私钥 d。

欧拉函数 φ(n) 在 RSA 中扮演着承上启下的关键角色：上承质因数分解（p 和 q → φ(n)），下启私钥计算（φ(n) 和 e → d）。它是整个算法正确性的保证，也是安全性的前提。

常见变体方向：

• 多质数 RSA：n = p × q × r × …，φ(n) = (p-1)(q-1)(r-1)…
• 共模攻击：同一 m 用不同 e 加密
• 低加密指数攻击：e 很小（如 e=3）
• Wiener 攻击：d 相对较小
• 费马分解：p 和 q 非常接近

掌握了欧拉定理和 RSA 的基本原理，这些变体就有了分析的起点。希望本文能帮助初学者建立起对 RSA 和欧拉定理的直观理解。

---

本文是 Bugku CTF S3 赛季 SimpleRSA 题目的题解博客，重点讲解了欧拉定理在 RSA 中的核心作用，适合 CTF Crypto 初学者阅读。