LitCTF 2025 - Crypto - Basic 题解
LitCTF 2025 - Crypto - Basic 题解：RSA加密的致命缺陷前言在密码学竞赛中，RSA加密是最常见的考点之一。但你是否想过，如果RSA的模数n不是两个质数的乘积，而是直接使用一 2025-11-12 03:36:29 Author: www.freebuf.com(查看原文) 阅读量:16 收藏

LitCTF 2025 - Crypto - Basic 题解：RSA加密的致命缺陷

前言

在密码学竞赛中，RSA加密是最常见的考点之一。但你是否想过，如果RSA的模数n不是两个质数的乘积，而是直接使用一个大质数，会发生什么？本文将深入分析一道有趣的CTF题目，揭示这种错误实现带来的灾难性后果。

题目分析

题目源码

首先让我们看看题目提供的加密代码：

from Crypto.Util.number import *
from enc import flag

m = bytes_to_long(flag)
n = getPrime(1024)
e = 65537
c = pow(m,e,n)
print(f"n = {n}")
print(f"e = {e}")
print(f"c = {c}")

题目给出的加密参数：

n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893
e = 65537
c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505

初步观察

看到这段代码，有经验的CTF选手可能会立即注意到一个异常之处：

n = getPrime(1024)  #  直接生成一个质数！

这行代码直接生成了一个1024位的质数作为RSA的模数n。而标准的RSA实现应该是：

p = getPrime(512)
q = getPrime(512)
n = p * q  # n是两个质数的乘积

这个看似微小的差异，实际上完全破坏了RSA的安全性。要理解为什么，我们需要深入了解RSA的数学原理。

RSA加密原理详解

标准RSA加密流程

RSA加密算法的安全性建立在大整数分解的困难性上。标准流程如下：

1. 密钥生成

  • 选择两个大质数 p 和 q（通常各512位或更多）

  • 计算模数：n = p × q

  • 计算欧拉函数：φ(n) = (p-1) × (q-1)

  • 选择公钥指数 e（常用65537）

  • 计算私钥指数：d ≡ e⁻¹ (mod φ(n))

2. 加密过程

  • 将明文m转换为整数

  • 计算密文：c ≡ m^e (mod n)

3. 解密过程

  • 使用私钥解密：m ≡ c^d (mod n)

欧拉函数的关键作用

欧拉函数φ(n)在RSA中扮演着至关重要的角色。它定义为小于n且与n互质的正整数个数。

对于不同类型的n，欧拉函数的计算方式完全不同：

  1. 当n = p × q（p、q为不同质数）时：

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

    这是标准RSA的情况。攻击者要计算φ(n)，必须先分解n得到p和q，这在数学上极其困难。

  2. 当n本身就是质数时：

    φ(n) = n - 1

    这是本题的情况。根据欧拉函数的定义，质数n与所有小于n的正整数都互质，因此φ(n) = n-1。

为什么直接使用质数是致命的？

标准RSA的安全性依赖于：

  • 已知：n（公开）、e（公开）、c（密文）

  • 未知：p、q（保密）、φ(n)（无法直接计算）、d（私钥）

攻击者无法直接计算φ(n)，因为他们不知道p和q。而分解1024位的合数n在计算上不可行。

但如果n是质数：

  • 已知：n（公开）、e（公开）、c（密文）

  • 直接计算：φ(n) = n - 1（无需分解！）

  • 轻松计算：d ≡ e⁻¹ (mod φ(n))

安全屏障彻底崩溃！

漏洞验证

在开始攻击之前，我们需要验证题目给出的n确实是质数。虽然题目代码显示使用了getPrime()，但作为安全研究员，我们应该验证而非信任。

质数验证代码

from Crypto.Util.number import isPrime

n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893

print("正在验证 n 是否为质数...")
is_prime = isPrime(n)
print(f"n 是质数: {is_prime}")
print(f"n 的位数: {n.bit_length()} bits")

验证结果

正在验证 n 是否为质数...
n 是质数: True
n 的位数: 1024 bits

确认无疑！n确实是一个1024位的质数。这意味着我们可以直接计算私钥。

质数测试算法简介

PyCryptodome库的isPrime()函数使用Miller-Rabin素性测试，这是一种概率性算法：

  • 对于合数，该算法有极高概率（>99.99%）正确识别

  • 对于质数，永远返回True

  • 算法复杂度为O(k log³ n)，其中k是测试轮数

这个算法在密码学中广泛应用于大质数的生成和验证。

攻击实现

既然确认了n是质数，我们可以开始构建攻击。

数学推导

目标：从密文c恢复明文m

已知条件：

  • n = 1506243...（质数）

  • e = 65537

  • c = 2210024...

攻击步骤：

步骤1：计算欧拉函数

对于质数n，根据欧拉函数的性质：

φ(n) = n - 1

这一步只需要一次减法运算，计算复杂度为O(1)。

步骤2：计算私钥d

私钥d需要满足：

e × d ≡ 1 (mod φ(n))

即d是e关于φ(n)的模逆元。使用扩展欧几里得算法可以高效计算：

d = inverse(e, φ(n))

扩展欧几里得算法的时间复杂度为O(log min(e, φ(n)))。

步骤3：解密密文

使用计算得到的私钥d进行解密：

m ≡ c^d (mod n)

这一步使用快速幂模运算，时间复杂度为O(log d)。

步骤4：转换为明文

将整数形式的明文m转换回字节串：

flag = long_to_bytes(m)

完整攻击脚本

from Crypto.Util.number import *

# 题目给出的参数
n = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181893
e = 65537
c = 22100249806368901850308057097325161014161983862106732664802709096245890583327581696071722502983688651296445646479399181285406901089342035005663657920475988887735917901540796773387868189853248394801754486142362158369380296905537947192318600838652772655597241004568815762683630267295160272813021037399506007505

print("=" * 60)
print("攻击开始")
print("=" * 60)

# 步骤1: 计算欧拉函数
print("\n[步骤1] 计算欧拉函数")
print("因为n是质数，φ(n) = n - 1")
phi_n = n - 1
print(f"φ(n) = {phi_n}")

# 步骤2: 计算私钥d
print("\n[步骤2] 计算私钥")
print("求解: d ≡ e^(-1) (mod φ(n))")
d = inverse(e, phi_n)
print(f"私钥 d 已计算完成")
print(f"d = {d}")

# 步骤3: 解密
print("\n[步骤3] 解密密文")
print("计算: m ≡ c^d (mod n)")
m = pow(c, d, n)
print(f"明文 m (整数形式) = {m}")

# 步骤4: 转换为flag
print("\n[步骤4] 转换为可读字符串")
flag = long_to_bytes(m)
print(f"Flag: {flag.decode()}")

print("\n" + "=" * 60)
print("攻击成功！")
print("=" * 60)

执行结果

============================================================
攻击开始
============================================================

[步骤1] 计算欧拉函数
因为n是质数，φ(n) = n - 1
φ(n) = 150624321883406825203208223877379141248303098639178939246561016555984711088281599451642401036059677788491845392145185508483430243280649179231349888108649766320961095732400297052274003269230704890949682836396267905946735114062399402918261536249386889450952744142006299684134049634061774475077472062182860181892

[步骤2] 计算私钥
求解: d ≡ e^(-1) (mod φ(n))
私钥 d 已计算完成
d = 91606027459737693805781060886286796952482794536832539794153363716502717770980178997262047705803845725219463412120219173858012460696707432226118739646834038573948568803912462271839376570563154180744807642905266432629277632120773233463784859115126762588096410821552513737434044132542444833111645047141072083401

[步骤3] 解密密文
计算: m ≡ c^d (mod n)
明文 m (整数形式) = 637558173724466425090042285461917437773779880317000622001200157462593547255728881535305989120893

[步骤4] 转换为可读字符串
Flag: LitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}

============================================================
攻击成功！
============================================================

成功获取Flag：LitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}

技术深度剖析

为什么inverse()函数能工作？

inverse(a, m)函数计算a关于m的模逆元，即找到x使得：

a × x ≡ 1 (mod m)

这个函数的实现基于扩展欧几里得算法（Extended Euclidean Algorithm）：

算法原理：

  1. 欧几里得算法可以计算gcd(a, m)

  2. 扩展版本不仅计算最大公约数，还能找到贝祖系数x和y，使得：

    a × x + m × y = gcd(a, m)

  3. 当gcd(a, m) = 1时（即a和m互质），上式变为：

    a × x + m × y = 1

  4. 两边对m取模：

    a × x ≡ 1 (mod m)

  5. 因此x就是a的模逆元

在本题中：

  • e = 65537是质数

  • φ(n) = n - 1是偶数（因为n是奇质数）

  • e和φ(n)互质（65537不整除n-1）

  • 因此模逆元一定存在

快速幂模运算的优化

计算c^d mod n时，如果直接计算c^d再取模，中间结果会是天文数字。Python的pow(c, d, n)使用了快速幂算法（Binary Exponentiation）：

算法思想：

# 计算 c^d mod n
# 将指数d表示为二进制
# 例如：d = 13 = 1101₂ = 2³ + 2² + 2⁰

result = 1
base = c
# 遍历d的每一位
while d > 0:
    if d & 1:  # 如果当前位是1
        result = (result * base) % n
    base = (base * base) % n  # base = c^(2^i)
    d >>= 1  # 右移一位

时间复杂度：O(log d)次乘法，而不是O(d)次

这使得即使d是300多位的大数，计算也能在毫秒级完成。

安全性对比

让我们量化一下这个漏洞的严重性：

标准RSA（n = p × q）：

  • 攻击者需要分解1024位合数

  • 最优算法（GNFS）复杂度：≈ 2^80运算

  • 使用当前最强超级计算机：数百年时间

错误实现（n为质数）：

  • 直接计算φ(n) = n - 1

  • 计算模逆元：毫秒级

  • 快速幂解密：毫秒级

  • 总时间：不到1秒

安全性差距：10^15倍以上！

为什么RSA必须使用合数？

这个题目引出了一个深刻的问题：为什么RSA的设计者选择n = p × q，而不是简单地使用质数n？

安全性需求

RSA的安全性依赖于单向函数的特性：

  • 正向计算容易：给定p和q，计算n = p × q很简单

  • 反向计算困难：给定n，分解出p和q极其困难

这种不对称性正是公钥密码学的基石。

陷门函数

更准确地说，RSA基于陷门单向函数（Trapdoor Function）：

  • 有陷门（知道p和q）：加密和解密都容易

  • 无陷门（只知道n）：解密极其困难

合数n = p × q的设计巧妙之处在于：

  1. 公开n不会泄露p和q（分解困难）

  2. 知道p和q可以高效计算φ(n) = (p-1)(q-1)

  3. 不知道p和q无法计算φ(n)（这是关键！）

  4. 无法计算φ(n)就无法计算私钥d

如果n是质数：

  • φ(n) = n - 1可以直接从公开信息计算

  • 陷门失效！

  • 任何人都能计算私钥

数学美学

从数学角度看，RSA的设计体现了优雅的对称性：

公钥：(n, e) - n是复合的秘密(p×q)的公开表示
私钥：(n, d) - d依赖于隐藏的结构(p和q)

这种设计让公钥可以安全公开，同时确保只有拥有私钥的人才能解密。

实战经验总结

代码审计要点

在CTF或安全审计中遇到RSA实现时，应检查：

  1. 模数n的生成方式

    # ❌ 错误：直接使用质数
n = getPrime(1024)

# ✓ 正确：使用两个质数的乘积
p = getPrime(512)
q = getPrime(512)
n = p * q

  2. 质数的位长

    # ❌ 弱：质数太小
p = getPrime(256)
q = getPrime(256)

# ✓ 强：足够的位长
p = getPrime(1024)
q = getPrime(1024)

  3. 公钥指数e的选择

    # ❌ 危险：e太小（如e=3）且无padding
e = 3

# ✓ 安全：标准选择
e = 65537

  4. p和q的关系

    # ❌ 弱：p和q太接近
p = getPrime(512)
q = next_prime(p)

# ✓ 强：p和q充分独立
p = getPrime(512)
q = getPrime(512)

常见RSA攻击类型

除了本题的"质数模数"漏洞，CTF中常见的RSA攻击还包括：

  1. 小指数攻击：e过小且明文小，可直接开方

  2. 共模攻击：相同n加密不同消息，可恢复明文

  3. Wiener攻击：d太小时可通过连分数攻击

  4. 因式分解：n太小或p、q选择不当

  5. 填充攻击：PKCS#1 v1.5等填充方案的漏洞

防御建议

对于开发者：

  1. 使用经过验证的库：OpenSSL、PyCryptodome等

  2. 遵循标准：PKCS#1、OAEP等

  3. 密钥长度：至少2048位，推荐3072或4096位

  4. 定期更新：密码学算法会老化

对于安全研究员：

  1. 质疑假设：不要假设n一定是合数

  2. 验证参数：检查所有加密参数的合理性

  3. 理解原理：深入理解密码学算法的数学基础

总结

本题通过一个简单的实现错误，展示了密码学中细节决定一切的铁律。使用质数作为RSA模数，将本应需要数百年才能破解的加密系统，降级为不到1秒就能攻破的"纸老虎"。

关键要点回顾

  1. RSA安全性的基础：大整数分解的困难性

  2. 欧拉函数的关键作用：连接公钥和私钥的桥梁

  3. 质数vs合数：φ(质数) = n-1可直接计算，φ(合数)需要分解

  4. 陷门函数设计：知道p和q是解密的"陷门"

  5. 理论与实践：数学原理必须正确实现

更广泛的启示

这道题目提醒我们：

  • 密码学不是魔法，而是精确的数学

  • 实现细节至关重要，小错误导致大灾难

  • 安全审计需要深入理解底层原理

  • "永远不要自己实现密码学算法"这句话的价值

在密码学的世界里，信任必须建立在数学证明和严格实现的基础上。任何偏离标准的"创新"，都可能打开潘多拉的魔盒。

Flag:LitCTF{ee2c30dfe684f13a6e6c07b9ec90cc2c}

希望这篇文章能帮助你深入理解RSA的数学原理和安全性基础。在CTF的旅程中，理解"为什么"比记住"怎么做"更重要。继续探索，保持好奇！


文章来源: https://www.freebuf.com/articles/others-articles/456718.html
如有侵权请联系:admin#unsafe.sh