E_S_P - Writeup by AI

kang0x0

420人浏览 · 2026-05-08 11:06:07

kang0x0 · 2026-05-08 11:06:07 发布

E_S_P - Writeup by AI

一、题目信息

题目来源: BugKu CTF
题目名称: E_S_P (Extra Sensory Perception)
题目类别: Crypto / RSA
考点: RSA 小指数攻击、Coppersmith 方法、SageMath 在线应用

二、题目描述

2.1 加密代码 (esp.py)

from Crypto.Util.number import *
from secret import flag, yukko
import re

assert re.match(r"^KosenCTF{.+}$", flag)

Nbits = 1024
p = getPrime(Nbits)
q = getPrime(Nbits)
n = p * q
e = 5
c = pow(bytes_to_long((yukko + flag).encode()), e, n)

print("N = {}".format(n))
print("e = {}".format(e))

print("Wow Yukko the ESPer helps you!")
print(yukko + "the length of the flag = {}".format(len(flag)))
print("c = {}".format(c))

2.2 输出数据 (out.txt)

N = 11854673881335985163635072085250462726008700043680492953159905880499045049107244300920837378010293967634187346804588819510452454716310449345364124188546434429828696164683059829613371961906369413632824692460386596396440796094037982036847106649198539914928384344336740248673132551761630930934635177708846275801812766262866211038764067901005598991645254669383536667044207899696798812651232711727007656913524974796752223388636251060509176811628992340395409667867485276506854748446486284884567941298744325375140225629065871881284670017042580911891049944582878712176067643299536863795670582466013430445062571854275812914317
e = 5
Wow Yukko the ESPer helps you!
Yukko the ESPer: My amazing ESP can help you to get the flag! -----> the length of the flag = 39
c = 4463634440284027456262787412050107955746015405738173339169842084094411947848024686618605435207920428398544523395749856128886621999609050969517923590260498735658605434612437570340238503179473934990935761387562516430309061482070214173153260521746487974982738771243619694317033056927553253615957773428298050465636465111581387005937843088303377810901324355859871291148445415087062981636966504953157489531400811741347386262410364012023870718810153108997879632008454853198551879739602978644245278315624539189505388294856981934616914835545783613517326663771942178964492093094767168721842335827464550361019195804098479315147

三、考点分析

3.1 知识点权重

知识点	重要性	难度	说明
RSA 基础原理	⭐⭐⭐	简单	理解加密过程 c = m^e mod n
小指数攻击	⭐⭐⭐⭐⭐	中等	e=5 很小，但需要满足条件才能直接开方
Coppersmith 方法	⭐⭐⭐⭐⭐	困难	核心攻击手段，需要 SageMath
已知明文攻击	⭐⭐⭐⭐	中等	利用已知的 yukko 和 flag 前缀
多项式环理论	⭐⭐⭐⭐	困难	Z/NZ 上的多项式构造

四、解题思路

4.1 初步分析

步骤 1: 解析 yukko 字符串

从代码中可以看到：

print(yukko + "the length of the flag = {}".format(len(flag)))

对应输出：

Yukko the ESPer: My amazing ESP can help you to get the flag! -----> the length of the flag = 39

因此：

yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> "
yukko 长度 = 69 字节
flag 长度 = 39 字节
明文总长度 = 69 + 39 = 108 字节

步骤 2: 分析加密方式

c = pow(bytes_to_long((yukko + flag).encode()), e, n)

明文 P = yukko || flag（字符串拼接后转整数）
加密指数 e = 5（很小）
模数 N 为 1536 位（两个 1024 位素数的乘积）

步骤 3: 检查直接开方的可能性

如果 P^e < N，则可以直接对 c 开 5 次方根。

计算验证：

明文长度 ≈ 108 字节 = 864 位
P^5 ≈ 4320 位 >> N 的 1536 位

结论: 无法直接开方，需要更高级的攻击方法。

4.2 Coppersmith 攻击可行性分析

核心思想

将明文分为两部分：

已知部分 (m_known): yukko + flag 前缀 “KosenCTF{” + 第一个字符
未知部分 (x): flag 剩余的 29 个字符

构造多项式：

f(x) = (m_known + x)^e - c ≡ 0 (mod N)

Coppersmith 定理

对于上述多项式，如果 |x| < N^(1/e)，则可以在多项式时间内求出所有满足条件的小根。

数值验证

N^(1/5) ≈ 2^(1536/5) ≈ 2^307 ≈ 10^92
未知部分 x < 256^29 = 2^232 ≈ 10^70
232 位 < 307 位 ✅

结论: 完全满足 Coppersmith 攻击条件！

4.3 为什么需要枚举第一个字符？

由于 flag 格式为 KosenCTF{...}，我们知道：

前缀 yukko + "KosenCTF{" 是已知的
但剩余 29 个字符中，第一个字符不确定
通过枚举第一个可打印字符，可以将问题转化为：已知 30 字节中的高 1 字节，求解低 29 字节

这样构造的多项式为：

P = (known_prefix || c1 || 0x00*29 || '}') + x * 256

其中 x 就是我们要解的 29 字节未知部分。

五、详细解题步骤

5.1 准备工具

需要安装 SageMath（或使用在线环境）：

本地安装：https://www.sagemath.org/
在线环境：https://sagecell.sagemath.org/ 或 https://cocalc.com/

5.2 编写攻击脚本

import string

# ---------- 替代 Crypto 的函数 ----------
def bytes_to_long(b: bytes) -> int:
    return int.from_bytes(b, 'big')

def long_to_bytes(n: int, length: int = None) -> bytes:
    if length is None:
        length = (n.bit_length() + 7) // 8
    return n.to_bytes(length, 'big')
# --------------------------------------

# 硬编码参数（从 out.txt 提取）
N = 11854673881335985163635072085250462726008700043680492953159905880499045049107244300920837378010293967634187346804588819510452454716310449345364124188546434429828696164683059829613371961906369413632824692460386596396440796094037982036847106649198539914928384344336740248673132551761630930934635177708846275801812766262866211038764067901005598991645254669383536667044207899696798812651232711727007656913524974796752223388636251060509176811628992340395409667867485276506854748446486284884567941298744325375140225629065871881284670017042580911891049944582878712176067643299536863795670582466013430445062571854275812914317
e = 5
c = 4463634440284027456262787412050107955746015405738173339169842084094411947848024686618605435207920428398544523395749856128886621999609050969517923590260498735658605434612437570340238503179473934990935761387562516430309061482070214173153260521746487974982738771243619694317033056927553253615957773428298050465636465111581387005937843088303377810901324355859871291148445415087062981636966504953157489531400811741347386262410364012023870718810153108997879632008454853198551879739602978644245278315624539189505388294856981934616914835545783613517326663771942178964492093094767168721842335827464550361019195804098479315147
yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> "
flag_total_len = 39
flag_len = flag_total_len - len("KosenCTF{}") - 1   # 29

# 枚举第一个字符
for c1 in string.printable:
    # 构造已知部分的高位填充
    high_pad = bytes_to_long(
        yukko.encode() + b"KosenCTF{" + c1.encode() + b"\x00" * flag_len + b"}"
    )
    low_pad = 256  # x 的系数，表示未知部分左移 8 位

    # 在 Z/NZ 上构造多项式环
    PR.<x> = PolynomialRing(Zmod(N))
    
    # 构造多项式 f(x) = (high_pad + x * 256)^e - c
    f = (high_pad + x * low_pad)^e - c
    f = f.monic()
    
    # Coppersmith 求小根
    xs = f.small_roots(X=2^(flag_len * 8), beta=1)
    
    for x in xs:
        # 将 Sage 整数转换为 Python int
        x_int = int(x)
        flag = b"KosenCTF{" + c1.encode() + long_to_bytes(x_int) + b"}"
        print(flag)

5.3 执行攻击

运行上述脚本，SageMath 会自动：

构造格基（Lattice）
使用 LLL 算法进行规约
从规约后的基向量中提取小根
还原未知的明文字节

5.4 验证结果

将得到的 flag 代回原加密公式验证：

full_plain = yukko + full_flag
m = bytes_to_long(full_plain.encode())
assert pow(m, e, N) == c  # 应该通过

六、完整代码

6.1 优化版攻击脚本 (solve.py)

本脚本特点：

✅ 无需外部依赖：自实现 bytes_to_long 和 long_to_bytes
✅ 硬编码参数：直接从 out.txt 提取所有参数
✅ 在线兼容：可在 SageMath Cell 等在线环境运行
✅ 类型转换安全：正确处理 Sage 整数到 Python int 的转换

import string

# ---------- 替代 Crypto 的函数 ----------
def bytes_to_long(b: bytes) -> int:
    return int.from_bytes(b, 'big')

def long_to_bytes(n: int, length: int = None) -> bytes:
    if length is None:
        length = (n.bit_length() + 7) // 8
    return n.to_bytes(length, 'big')
# --------------------------------------

N = 11854673881335985163635072085250462726008700043680492953159905880499045049107244300920837378010293967634187346804588819510452454716310449345364124188546434429828696164683059829613371961906369413632824692460386596396440796094037982036847106649198539914928384344336740248673132551761630930934635177708846275801812766262866211038764067901005598991645254669383536667044207899696798812651232711727007656913524974796752223388636251060509176811628992340395409667867485276506854748446486284884567941298744325375140225629065871881284670017042580911891049944582878712176067643299536863795670582466013430445062571854275812914317
e = 5
c = 4463634440284027456262787412050107955746015405738173339169842084094411947848024686618605435207920428398544523395749856128886621999609050969517923590260498735658605434612437570340238503179473934990935761387562516430309061482070214173153260521746487974982738771243619694317033056927553253615957773428298050465636465111581387005937843088303377810901324355859871291148445415087062981636966504953157489531400811741347386262410364012023870718810153108997879632008454853198551879739602978644245278315624539189505388294856981934616914835545783613517326663771942178964492093094767168721842335827464550361019195804098479315147
yukko = "Yukko the ESPer: My amazing ESP can help you to get the flag! -----> "
flag_total_len = 39
flag_len = flag_total_len - len("KosenCTF{}") - 1   # 29

for c1 in string.printable:
    high_pad = bytes_to_long(
        yukko.encode() + b"KosenCTF{" + c1.encode() + b"\x00" * flag_len + b"}"
    )
    low_pad = pow(256, 1)   # 即 256

    PR.<x> = PolynomialRing(Zmod(N))
    f = (high_pad + x * low_pad)^e - c
    f = f.monic()
    xs = f.small_roots(X=2^(flag_len * 8), beta=1)
    for x in xs:
        # 关键：将 Sage 整数转换为 Python int
        x_int = int(x)
        flag = b"KosenCTF{" + c1.encode() + long_to_bytes(x_int) + b"}"
        print(flag)