2026-SparkCTF-crypto-writeup

Crypto 方向

初赛部分

题目1：寻找戒指的旅途

让AI帮我静态分析了一下，发现是PyInstaller 打包的 Python 程序，让他帮我解一下PyInstaller包并反编译出pyc，看到了加密原理：

$$c \equiv (m * iv) \mod s$$

接下来很简单，由output.json里的两组m，iv，c做一个gcd先恢复出模数s，然后根据最后一组的iv，c计算m
exp：

import json
import math
from Crypto.Util.number import long_to_bytes

with open("output.json", "r", encoding="utf-8") as f:
    obj = json.load(f)

# 通过已知样本恢复模数 s
t = []
for row in obj["data"]:
    m = row["m"]
    iv = row["iv"]
    c = row["c"]
    t.append(m * iv - c)

s = math.gcd(*t)
print("[+] s =", s)

# 解密目标密文
target = obj["C"][0]
iv = target["iv"]
c = target["c"]

m = c * pow(iv, -1, s) % s
flag = long_to_bytes(m)

print("[+] flag =", flag.decode())

flag：flag{I_got_the_Real_R1ng_I_Am_The_LOrd_0F_the_R1ng5_in_SparkCTF}

题目2：lattice 1

翻译一下题目给出的式子：

$$c \equiv a_0 \cdot m_0^2 + a_1 \cdot m_1 + a_2 \pmod p$$

其中，$a_0,a_1,a_2$都是512位的，m0是flag的uuid转成大整数之后，大约336位，m1是100位
结合题目描述和位数的信息，要求的未知的都比较小，所以可以想到构造格子打copper
我们用x，y表示m0和m1，得到：

$$a_0 x^2 + a_1 y + (a_2 - c) \equiv 0 \pmod p$$

为了成功打copper，得变成首一多项式，同乘a0模p的逆元，得到：

$$x^2 + \frac{a_1}{a_0} y + \frac{a_2 - c}{a_0} \equiv 0 \pmod p$$

令 $k_1 \equiv a_1 \cdot a_0^{-1} \pmod p$，$k_0 \equiv (a_2 - c) \cdot a_0^{-1} \pmod p$，得到最终的二元多项式：

$$f(x, y) = x^2 + k_1 y + k_0 \equiv 0 \pmod p$$

接下来的攻击目标是：将模p的方程转化为整数方程。也就是说要找到一个多项式h(x,y),满足两个条件：
1.和原方程有同样的根(x0,y0)
2.带入根之后，多项式的计算结果的绝对值小于p
这样就可以去掉模p的影响，之后计算结式就能求出整数解
那么如何用LLL算法找到这样的多项式呢？

第一步，构造多项式族
构造一系列多项式，它们都共享同样的根 $(x_0, y_0)$ 模 $p^m$。
通常形式如下：

$$g_{i,j,k}(x, y) = x^i \cdot y^j \cdot f(x, y)^k \cdot p^{m-k}$$

这些多项式的组合构成了我们的解空间。
第二步，构造格基矩阵
将这些多项式的系数提取出来，构建一个巨大的矩阵。矩阵的每一行代表一个多项式。
第三步，LLL 算法
作用是在这个格空间中寻找“最短向量”。在代数意义上，向量的“长度”对应多项式系数的大小。LLL 找到的最短向量，对应着一个系数极小的多项式 $h(x, y)$。
第四步，Howgrave-Graham定理
该定理保证了：只要未知数 $x, y$ 的范围足够小，且 LLL 找到的多项式系数足够小，那么就一定满足 $|h(x_0, y_0)| < p^m$。

在本题中，我们已知flag格式是flag{}，可以对未知数部分进行优化：

$$m_0 = \text{prefix} \cdot 2^{296} + x \cdot 2^8 + \text{suffix}$$

其中，$\text{prefix} = \text{flag\{}$，$\text{suffix} = \text{\}}$，现在UUID部分的大小被限制在 $X < 2^{288}$，而 $y$ 的界限是 $Y < 2^{100}$。
在真正打脚本的时候遇到了几个问题：
1.构造格子的办法和参数选择经常出现矛盾，例如参数太大计算量大就容易卡死，但是减小参数就导致界限不足跑不出来。因此一定要根据一切可利用的信息来减小未知量，优化格子
2.sagemath内置的small_roots函数只支持单变量，因此需要我们手动构造格子，不能用自带的函数
3.多项式内的系数必须在同一个环上
最后的脚本是：

from Crypto.Util.number import long_to_bytes,bytes_to_long
import itertools
import time


# --- 核心攻击算法 (Defund/Coron 风格) ---
def small_roots(f, bounds, m=1, d=None):
    if not d: d = f.degree()
    
    # 切换到整数环
    f = f.change_ring(ZZ)
    R = f.base_ring()
    vars = f.variables()
    N = R.cardinality() # 对于模p多项式，这里其实不起作用，我们手动处理
    
    # 获取正确的模数 (题目中是 p)
    # 注意：传入的 f 是 Zmod(p) 上的，change_ring(ZZ) 后丢失了模数信息
    # 我们需要在构造格子时手动乘 p
    
    print(f"[*] 初始化 Lattice (m={m}, d={d})...")
    
    # 生成移位多项式 (Shift Polynomials)
    # 核心公式: g_{i,j,k} = x^i * y^j * f^k * p^(m-k)
    shifts = []
    # 我们需要显式传递模数 p，因为 f 在 ZZ 上没有模数
    # 从外部传入 p 会更方便，但这里我们可以从原始环推断
    # 为了通用性，我们在外部构造好 shift 可能会更清晰，但为了封装：
    # 假设 f 的原始环是 Zmod(p)
    
    # 重新获取 p
    # 这里通过一个小技巧获取 p: 
    # 如果 f 是 ZZ 多项式，我们假设外部逻辑保证了同余关系
    # 但标准的 coppersmith 需要 p。
    # 我们让函数接受 modulus 参数，或者简化逻辑：
    # 直接在主流程里写 Lattice 构造 (如下所示)。
    return []

# 为了确保无误，我们直接在主脚本中实现特定的 Lattice 构造逻辑
# 这样可以避免任何环境或传参导致的错误。

def solve_problem():
    # 1. 题目数据
    a_list = [7741319537308958501673945651303135989370388830734734613244416411870009515202597589426755861700658282411334090461856172066647825919965025780441733193707631, 12708340876096551823276094712154414605837041085217978402889133607179618520600229244521374546834126064757709025940472587603468976924003081466800964792013013, 9030711413715281616029109754098399408890501652813598936414313002302683150175563423273614447665545285792056876395737350904586524679558542610755539162370587]
    p = 94690982578140825601653787176952155164024939144212543950179743880762139204220427235536177869621577569149451317757150677696875463702458773015732097441809269178006694893934645510620728280094314782174427788383842690678353897827910292552841901283381647961750223031946826141032247802658949788038880100911120792699
    c = 60290713494234755291199980313218149618616938762129052976161786328128580668563788306218103869210206471067575629316788623403982658483270173487078950519913786502247521966103352915555189439284683709867886369283376517212062313536340599285181669868490307467284768160302733028625254340933632547167284245344104667790

    # 2. 环与多项式定义
    PR.<x, y> = PolynomialRing(Zmod(p))
    a0, a1, a2 = a_list
    inv_a0 = inverse_mod(a0, p)

    # 3. 构造 m0 的已知结构
    # flag = "flag{" + UUID + "}"
    # 总长 42 字节。
    # 前缀: "flag{" (5字节)
    # 后缀: "}" (1字节)
    # 未知部分 x: UUID (36字节) -> 288 bits
    
    prefix = b"flag{"
    suffix = b"}"
    
    prefix_val = bytes_to_long(prefix)
    suffix_val = bytes_to_long(suffix)
    
    # m0 = (prefix << 296) + (x << 8) + suffix
    # 解释: 
    # suffix 占 8 bits (0-7)
    # x 占 288 bits (8-295)
    # prefix 占 40 bits (296-335)
    m0_known = (prefix_val << 296) + suffix_val
    
    # 代入方程: a0 * m0^2 + a1 * m1 + a2 = c
    # 变为: (m0_known + x*2^8)^2 + (a1/a0)*y + (a2-c)/a0 = 0
    k1 = (inv_a0 * a1) % p
    k0 = (inv_a0 * (a2 - c)) % p
    
    # f(x, y)
    f = (m0_known + x * 2**8)**2 + k1 * y + k0
    
    # 4. 参数设置
    # X_bound: 2^288 (36字节)
    # Y_bound: 2^100
    X_bound = 2**288
    Y_bound = 2**100
    bounds = {x: X_bound, y: Y_bound}
    
    # m=3, d=4 是一个比较稳健的组合
    m = 3
    d = 4
    
    print(f"[*] Bounds: X=2^{log(X_bound, 2):.1f}, Y=2^{log(Y_bound, 2):.1f}")
    
    # 5. 构造 Lattice
    f_zz = f.change_ring(ZZ)
    vars_zz = f_zz.parent().gens() # x, y in ZZ
    x_z, y_z = vars_zz
    
    shifts = []
    # 只有当 i+j 总体次数不高时才加入，保持 Lattice 稀疏度
    for k in range(m + 1):
        for i in range(d - k + 1):
            for j in range(d - k + 1):
                 # 剪枝: 保持总次数限制 (可选，但推荐)
                 if i + j + k * f.degree() <= max(d, m*f.degree()): 
                     # 构造 shift: x^i * y^j * f^k * p^(m-k)
                     shift = (x_z**i) * (y_z**j) * (f_zz**k) * (p**(m-k))
                     shifts.append(shift)
    
    # 提取单项式并排序
    monomials = set()
    for s in shifts:
        monomials.update(s.monomials())
    monomials = sorted(list(monomials))
    
    print(f"[*] 格子维度: {len(shifts)} x {len(monomials)}")
    
    # 填充矩阵
    L = Matrix(ZZ, len(shifts), len(monomials))
    for r, poly in enumerate(shifts):
        for c, mono in enumerate(monomials):
            # 系数 * 变量Scale
            coeff = poly.monomial_coefficient(mono)
            scale = 1
            if mono.degree(x_z) > 0: scale *= X_bound ** mono.degree(x_z)
            if mono.degree(y_z) > 0: scale *= Y_bound ** mono.degree(y_z)
            L[r, c] = coeff * scale
            
    # 6. LLL
    print("[*] 正在执行 LLL...")
    B = L.LLL()
    print("[*] LLL 完成。")
    
    # 7. 提取短多项式并求解
    # 我们收集所有满足该界限的向量，不仅仅是第一个
    pols = []
    for i in range(B.nrows()):
        vec = B[i]
        poly = 0
        for j, mono in enumerate(monomials):
            scale = 1
            if mono.degree(x_z) > 0: scale *= X_bound ** mono.degree(x_z)
            if mono.degree(y_z) > 0: scale *= Y_bound ** mono.degree(y_z)
            poly += (vec[j] // scale) * mono
            
        if poly.is_constant(): continue
        
        # 检查是否为0多项式（有些实现会产生0行）
        if poly == 0: continue
        pols.append(poly)
        
    print(f"[*] 找到 {len(pols)} 个候选多项式。")
    
    # 使用 Groebner Basis / Variety 求解
    # 这是比 resultant 更稳健的方法
    if pols:
        print("[*] 正在计算 Variety (求根)...")
        # 我们可以只取前几个最短的，通常 2-3 个就够了
        ideal_polys = pols[:min(len(pols), 3)]
        I = Sequence(ideal_polys, f_zz.parent().change_ring(QQ)).ideal()
        
        try:
            # variety(ring=ZZ) 会自动寻找整数解
            roots = I.variety(ring=ZZ)
            for r in roots:
                # r 是字典 {x: val, y: val}
                val_x = int(r[x_z])
                print(f"[+] 发现根 x: {val_x}")
                
                # 恢复 m0
                m0_rec = m0_known + (val_x << 8)
                flag_bytes = long_to_bytes(m0_rec)
                print(f"[+] 解码结果: {flag_bytes}")
                
                if b"flag{" in flag_bytes:
                    print("\nSUCCESS!!!")
                    return
        except Exception as e:
            print(f"[-] Variety求解出错: {e}")
            # 备选：如果 variety 失败，尝试暴力验证 LLL 结果中最短向量的根
            # 对于本题，y 很小，也可以尝试对最短多项式进行 y 的穷举（如果它不含 x）
            pass
            
    print("[-] 未能找到 Flag，请尝试微调 m 或 d。")

solve_problem()

运行结果：[] Bounds: X=2^288.0, Y=2^100.0
[] 格子维度: 42 x 25
[] 正在执行 LLL…
[] LLL 完成。
[] 找到 25 个候选多项式。
[] 正在计算 Variety (求根)…
[+] 发现根 x: 103714300444054387887339203139930231726487903284461116240497528576823017989460585571429
[+] 解码结果: b’flag{5c5d5d52-1a7e-4233-aba7-1655070d2cde}’

题目3：lattice 2

题目意思很简单明了，但是搜索深度是2^101，太大了，不能直接爆破，一开始不知道该怎么和格联系上，后来刷博客刷到了类似的题型和解法
大概意思是将flag用ASCII和数学式子表达出来，然后转化为子集和问题
已知 g 的 ASCII 码是 103，o 的 ASCII 码是 111，两者相差 8。设 $x_i \in \{0, 1\}$ 表示第 $i$ 个字符是否为 o（其中 $0 \le i \le 100$）。
此时整个 flag 对应的整数 $F$ 可以表示为：

$$F = B + \sum_{i=0}^{100} x_i \cdot 8 \cdot 256^{101-i}$$

其中，$B$ 是假设 101 位字符全为 g 时的基础数值。
根据题目给出的加密逻辑 $F \equiv c \pmod p$，代入上面的公式可得：

$$\sum_{i=0}^{100} x_i \cdot \left(8 \cdot 256^{101-i}\right) \equiv c - B \pmod p$$

令系数 $A_i = (8 \cdot 256^{101-i}) \pmod p$，目标值 $T = (c - B) \pmod p$。
问题即可转化为标准的子集和问题，即寻找一组 $x_i \in \{0, 1\}$ 和一个整数 $k$，使得：

$$\sum_{i=0}^{100} x_i A_i - k \cdot p = T$$

然后可以构造格基规约矩阵。
为了让 LLL 算法更容易命中短向量，构造一个 $(N+2) \times (N+2)$ 的格矩阵 $M$（此处 $N = 101$），将变量转化为 $\{-1, 1\}$ 的形式。
构建的格矩阵 $M$ 如下：

$$M = \begin{pmatrix} 2 & 0 & \dots & 0 & 0 & A_0 \cdot W \\ 0 & 2 & \dots & 0 & 0 & A_1 \cdot W \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \dots & 2 & 0 & A_{100} \cdot W \\ 0 & 0 & \dots & 0 & 0 & p \cdot W \\ -1 & -1 & \dots & -1 & 1 & -T \cdot W \\ \end{pmatrix}$$

矩阵原理解析：矩阵左上角 $101 \times 101$ 的对角线元素为 $2$，最后一行前 101 列对应全为 $-1$。
在格规约过程中，如果对应系数为 $x_i$，前 101 列的计算结果将是 $2x_i - 1$。因为 $x_i \in \{0, 1\}$，所以这部分结果必定为 $\pm 1$，这极大地缩短了目标向量的长度。
第 $N+1$ 列（倒数第二列）是用于固定常数 $1$ 的权重列。第 $N+2$ 列（最后一列）是等式校验列。我们引入一个极大的权重常数 $W$（例如 $2^{1024}$），强制 LLL 算法在寻找最短向量时，必须让这一列的线性组合结果精确为 $0$。
exp：

# 已知参数
p = 2157911408903816440001478305817039407175476474018384087827264804670444904936946922895956667319579115769204739052099777659
c = 1174991717228130578398439743141866600386053936270000296953662636741858928760200802613536886618630745247582903538089645287

# 计算基础偏置
base_flag = b"flag{" + b"g"*101 + b"}"
base_val = int.from_bytes(base_flag, 'big')

# 计算目标值 T
T = (c - base_val) % p

N = 101
A = []
for i in range(N):
    # 位权计算：每个字符的增量为 8 ('o' - 'g' = 8)
    weight = (8 * pow(256, 101 - i, p)) % p
    A.append(weight)

# 构造 (N+2) * (N+2) 维度的格矩阵
dim = N + 2
M = Matrix(ZZ, dim, dim)

W = 2^1024 # 给等式列设置极大的权重
W2 = 1     # 常数1列的权重

# 填充矩阵
for i in range(N):
    M[i, i] = 2
    M[i, dim - 1] = A[i] * W

M[N, dim - 1] = p * W

for i in range(N):
    M[N+1, i] = -1

M[N+1, N] = W2
M[N+1, dim - 1] = -T * W

print("开始运行 LLL 算法...")
M_red = M.LLL()
print("LLL 规约完成，正在提取 flag...")

# 在规约后的格基中寻找符合条件的最短向量
for row in M_red:
    # 最后一列必须为0，且常数列必须为 1 或 -1
    if row[dim-1] == 0 and abs(row[N]) == W2:
        ans = ""
        valid = True
        
        # 为了处理可能的符号反转，根据 row[N] 决定正负
        sign = 1 if row[N] == W2 else -1
        
        for i in range(N):
            val = row[i] * sign
            if val == 1:       # 2*1 - 1 = 1 => 选 'o'
                ans += "o"
            elif val == -1:    # 2*0 - 1 = -1 => 选 'g'
                ans += "g"
            else:
                valid = False
                break
                
        if valid:
            print(f"\n找到 Flag: flag{{{ans}}}")
            break

flag：flag{ogggoogoooggggggoooogoggogoogoggogoogogoggoogooogggogggggggooogogogogggogogggogggggggggggggogogooggog}

题目4：随机数之旅

题目意思很明确，key是通过random调用的16字节，我们需要从给出的hint来恢复这个random状态
经典的破解MT19937 PRNG伪随机数问题
学习一下师傅们的经典文章：https://xenny.wiki/posts/crypto/PRNG/MT19937.html
本题中，hint给出了同一个状态后续2506x8=20048位的泄露，但是每次都是泄露的32位中的高8位，不是完整输出，不能直接untemper，所以得写成在GF(2)域上的线性方程组
然后把624x32个状态bit当未知数，把hint的20048个bit变成20048个方程组去做高斯消元
但是这里会有一个问题，CPython中，twist是in-place更新，就会导致原始状态state[0]的低31位不会线性传播到可见的hint中，我们写脚本去恢复初始state也会发现仍然剩下了31位的自由度，这31位是“藏”在了key调用的第一个32bit里，后面需要爆破一下2^31中可能性，不过可以加上已知flag头的flag{做一下DFS

第一阶段：

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import ast
import sys
import random

N = 624
M = 397

UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff
MATRIX_A = 0x9908b0df

B = 0x9d2c5680
C = 0xefc60000

SKIP_OUTPUTS = 4  # randbytes(16) 先消耗 4 个 32-bit 输出


def xor_word(a, b):
    return [x ^ y for x, y in zip(a, b)]


def shift_right(a, k):
    r = [0] * 32
    for i in range(32 - k):
        r[i] = a[i + k]
    return r


def shift_left(a, k):
    r = [0] * 32
    for i in range(k, 32):
        r[i] = a[i - k]
    return r


def and_mask(a, mask):
    r = [0] * 32
    for i in range(32):
        if (mask >> i) & 1:
            r[i] = a[i]
    return r


def const_mul(bitcoeff, const):
    r = [0] * 32
    for i in range(32):
        if (const >> i) & 1:
            r[i] = bitcoeff
    return r


def or_disjoint(u, l):
    return [x ^ y for x, y in zip(u, l)]


def temper_bits(x):
    y = x
    y = xor_word(y, shift_right(y, 11))
    y = xor_word(y, and_mask(shift_left(y, 7), B))
    y = xor_word(y, and_mask(shift_left(y, 15), C))
    y = xor_word(y, shift_right(y, 18))
    return y


def twist_sym_inplace(mt):
    mt = mt[:]

    for kk in range(N - M):
        y = or_disjoint(
            and_mask(mt[kk], UPPER_MASK),
            and_mask(mt[kk + 1], LOWER_MASK),
        )
        mt[kk] = xor_word(
            xor_word(mt[kk + M], shift_right(y, 1)),
            const_mul(y[0], MATRIX_A),
        )

    for kk in range(N - M, N - 1):
        y = or_disjoint(
            and_mask(mt[kk], UPPER_MASK),
            and_mask(mt[kk + 1], LOWER_MASK),
        )
        mt[kk] = xor_word(
            xor_word(mt[kk + (M - N)], shift_right(y, 1)),
            const_mul(y[0], MATRIX_A),
        )

    y = or_disjoint(
        and_mask(mt[N - 1], UPPER_MASK),
        and_mask(mt[0], LOWER_MASK),
    )
    mt[N - 1] = xor_word(
        xor_word(mt[M - 1], shift_right(y, 1)),
        const_mul(y[0], MATRIX_A),
    )

    return mt


def add_row_to_basis(row, basis):
    while row:
        p = row.bit_length() - 1
        if p == 0:
            return (row & 1) == 0
        if p in basis:
            row ^= basis[p]
        else:
            basis[p] = row
            return True
    return True


def build_basis(hint_bytes, start_idx=SKIP_OUTPUTS):
    # bit0 存 RHS；bit1.. 对应变量
    mt = [[(1 << (1 + i * 32 + b)) for b in range(32)] for i in range(N)]
    idx = start_idx
    basis = {}

    for byte in hint_bytes:
        if idx >= N:
            mt = twist_sym_inplace(mt)
            idx = 0

        y = temper_bits(mt[idx])
        idx += 1

        # getrandbits(8) 对应 tempered 输出的高 8 位
        for bpos in range(8):
            rhs = (byte >> bpos) & 1
            row = rhs ^ y[24 + bpos]
            if not add_row_to_basis(row, basis):
                raise RuntimeError("UNSAT: 线性系统不一致")

    return basis


def solve_from_basis(basis, nvars):
    pivots = sorted(basis.keys())
    pivot_vars = set(p - 1 for p in pivots)
    free_vars = [i for i in range(nvars) if i not in pivot_vars]

    sol = 0
    for p in pivots:
        row = basis[p]
        var = p - 1
        rhs = row & 1
        row_vars = (row >> 1) & ~(1 << var)
        parity = (sol & row_vars).bit_count() & 1
        if rhs ^ parity:
            sol |= 1 << var

    return sol, free_vars


def state_from_solution(sol_bits):
    mt = []
    for i in range(N):
        w = 0
        base = i * 32
        for b in range(32):
            if (sol_bits >> (base + b)) & 1:
                w |= 1 << b
        mt.append(w & 0xFFFFFFFF)
    return mt


def main():
    path = sys.argv[1] if len(sys.argv) > 1 else "data.txt"

    with open(path, "r", encoding="utf-8") as f:
        lines = [ln.strip() for ln in f if ln.strip()]

    if len(lines) < 2:
        print("data.txt 需要两行：第一行 cipher，第二行 hint")
        sys.exit(1)

    cipher = bytes(ast.literal_eval(lines[0]))
    hint = bytes(ast.literal_eval(lines[1]))

    basis = build_basis(hint, SKIP_OUTPUTS)
    sol, free_vars = solve_from_basis(basis, N * 32)
    mt = state_from_solution(sol)

    x0_msb = (mt[0] >> 31) & 1

    # 关键：把恢复出的状态直接塞回 CPython random
    r = random.Random()
    r.setstate((3, tuple(mt) + (0,), None))

    key = r.randbytes(16)
    suffix = key[4:]

    # 回放验证
    replay = bytes(r.getrandbits(8) for _ in range(len(hint)))
    ok = (replay == hint)

    with open("params.h", "w", encoding="utf-8") as f:
        f.write("#pragma once\n")
        f.write(f"#define X0_MSB {x0_msb}\n")
        f.write("static const unsigned char KEY_SUFFIX[12] = {")
        f.write(",".join(f"0x{b:02x}" for b in suffix))
        f.write("};\n")
        f.write(f"static const unsigned char CIPHER[{len(cipher)}] = {{")
        f.write(",".join(f"0x{b:02x}" for b in cipher))
        f.write("};\n")
        f.write(f"#define CIPHER_LEN {len(cipher)}\n")

    print(f"[+] rank={len(basis)} free={len(free_vars)} x0_msb={x0_msb} suffix={suffix.hex()}")
    print(f"[+] replay ok = {ok}")
    print("[+] wrote params.h")

    if not ok:
        print("[!] replay mismatch，说明 stage1 仍然不对")
        sys.exit(1)


if __name__ == "__main__":
    main()

能得到一个params.h文件，然后再让AI写一个C程序去爆破（速度比python快一点）

#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>
#include <pthread.h>
#include <openssl/aes.h>

#include "params.h"

static volatile int FOUND = 0;
static uint32_t FOUND_X0 = 0;
static unsigned char FOUND_PT[CIPHER_LEN];

static inline uint32_t temper(uint32_t x) {
    uint32_t y = x;
    y ^= (y >> 11);
    y ^= (y << 7)  & 0x9d2c5680u;
    y ^= (y << 15) & 0xefc60000u;
    y ^= (y >> 18);
    return y;
}

static inline int is_printable(unsigned char c) {
    return (c >= 0x20 && c <= 0x7e) || c == '\n' || c == '\r' || c == '\t';
}

typedef struct {
    int tid;
    int nthreads;
} arg_t;

static void *worker(void *vp) {
    arg_t *a = (arg_t *)vp;
    int tid = a->tid;
    int nthreads = a->nthreads;

    unsigned char key[16];
    memcpy(key + 4, KEY_SUFFIX, 12);

    AES_KEY dk;
    unsigned char block0[16];
    unsigned char pt[CIPHER_LEN];

    const uint64_t LIMIT = (1ULL << 31);

    for (uint64_t low = (uint64_t)tid; low < LIMIT && !FOUND; low += (uint64_t)nthreads) {
        uint32_t x0 = ((uint32_t)X0_MSB << 31) | (uint32_t)low;
        uint32_t y0 = temper(x0);

        key[0] = (unsigned char)(y0 & 0xff);
        key[1] = (unsigned char)((y0 >> 8) & 0xff);
        key[2] = (unsigned char)((y0 >> 16) & 0xff);
        key[3] = (unsigned char)((y0 >> 24) & 0xff);

        AES_set_decrypt_key(key, 128, &dk);
        AES_decrypt(CIPHER, block0, &dk);

        if (block0[0] != 'f' || block0[1] != 'l' || block0[2] != 'a' || block0[3] != 'g' || block0[4] != '{') {
            goto progress;
        }

        for (int i = 0; i < 16; i++) {
            if (!is_printable(block0[i])) {
                goto progress;
            }
        }

        for (int off = 0; off < CIPHER_LEN; off += 16) {
            AES_decrypt(CIPHER + off, pt + off, &dk);
        }

        int has_brace = 0;
        for (int i = 0; i < CIPHER_LEN; i++) {
            if (pt[i] == '}') {
                has_brace = 1;
                break;
            }
        }
        if (!has_brace) {
            goto progress;
        }

        unsigned char pad = pt[CIPHER_LEN - 1];
        if (pad < 1 || pad > 16) {
            goto progress;
        }
        for (int i = 0; i < pad; i++) {
            if (pt[CIPHER_LEN - 1 - i] != pad) {
                goto progress;
            }
        }

        FOUND = 1;
        FOUND_X0 = x0;
        memcpy(FOUND_PT, pt, CIPHER_LEN);
        break;

progress:
        if (tid == 0 && (low % (1ULL << 26) == 0)) {
            fprintf(stderr, "\r[*] low=%llu / %llu",
                    (unsigned long long)low,
                    (unsigned long long)LIMIT);
            fflush(stderr);
        }
    }

    return NULL;
}

int main(int argc, char **argv) {
    int nthreads = 8;
    if (argc > 1) {
        nthreads = atoi(argv[1]);
    }
    if (nthreads <= 0) {
        nthreads = 1;
    }

    printf("[+] threads=%d\n", nthreads);

    pthread_t *th = (pthread_t *)calloc((size_t)nthreads, sizeof(pthread_t));
    arg_t *args = (arg_t *)calloc((size_t)nthreads, sizeof(arg_t));
    if (!th || !args) {
        fprintf(stderr, "[!] calloc failed\n");
        return 1;
    }

    for (int i = 0; i < nthreads; i++) {
        args[i].tid = i;
        args[i].nthreads = nthreads;
        pthread_create(&th[i], NULL, worker, &args[i]);
    }

    for (int i = 0; i < nthreads; i++) {
        pthread_join(th[i], NULL);
    }

    if (!FOUND) {
        printf("\n[!] not found\n");
        free(th);
        free(args);
        return 1;
    }

    unsigned char pad = FOUND_PT[CIPHER_LEN - 1];
    int msg_len = (int)CIPHER_LEN - (int)pad;

    printf("\n[!!!] FOUND x0 = 0x%08x\n", FOUND_X0);
    printf("[+] plaintext = ");
    fwrite(FOUND_PT, 1, msg_len, stdout);
    putchar('\n');

    free(th);
    free(args);
    return 0;
}

在cmd里运行的结果是：

题目5：RSA? O! RCA！

这题是CVE-2017-15361，ROCA漏洞，网上有很多现成的分析和脚本，也出过很多类似的题目
主要参考：https://bitsdeep.com/posts/analysis-of-the-roca-vulnerability/
exp：

#!/usr/bin/env sage
# -*- coding: utf-8 -*-

from sage.all import *
import sys

# =======================
# Instance from rsa_o!rca!.py
# =======================
N = Integer(17853573899076341181096267567874616214556285809566419320975211748455658403574952424384450961122059841394637349769390646220566170958316752370568080811)
ENC = Integer(14134528243637339528516880595615017358007046031917320457849840313575913728415212293709028402353118219198627787035921516021202481286846551245272653155)
E = Integer(65537)

# =======================
# M' : a special divisor of primorial(39) used in ROCA-512 setting
# (This M' is exactly product of many primes <= 167 whose 65537-order divides 1201200)
# =======================
M_PRIME = Integer(0x1b3e6c9433a7735fa5fc479ffe4027e13bea)  # = 2373273553037774377596381010280540868262890
MM = 5
TT = MM + 1

# =======================
# Howgrave-Graham Coppersmith (univariate, self-contained)
# =======================
def coppersmith_howgrave_univariate(pol, modulus, beta, mm, tt, XX):
    dd = pol.degree()
    nn = dd * mm + tt

    if not (0 < beta <= 1):
        raise ValueError("beta must be in (0,1].")
    if not pol.is_monic():
        raise ArithmeticError("Polynomial must be monic.")

    polZ = pol.change_ring(ZZ)
    x = polZ.parent().gen()

    gg = []
    for ii in range(mm):
        for jj in range(dd):
            gg.append((x * XX) ** jj * modulus ** (mm - ii) * polZ(x * XX) ** ii)
    for ii in range(tt):
        gg.append((x * XX) ** ii * polZ(x * XX) ** mm)

    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        for jj in range(ii + 1):
            BB[ii, jj] = gg[ii][jj]

    BB = BB.LLL()

    new_pol = 0
    for ii in range(nn):
        new_pol += x ** ii * BB[0, ii] // (XX ** ii)

    roots = []
    for r, mult in new_pol.roots():
        if r in ZZ:
            r = ZZ(r)
            val = polZ(r)
            if gcd(modulus, val) >= modulus ** beta:
                roots.append(r)
    return roots

# =======================
# Try a candidate exponent a (mod ord) and recover p via Coppersmith
# =======================
def try_a(N, Mp, a, mm, xx_bound):
    # r = 65537^a mod Mp   -> p ≡ r (mod Mp)
    r = Integer(pow(E, a, Mp))

    # known = r * Mp^{-1} (mod N)
    known = Integer((r * inverse_mod(Mp, N)) % N)

    # polynomial f(x) = x + known (mod N), small root x = k where p = k*Mp + r
    F = PolynomialRing(Zmod(N), names=('x',), implementation='NTL')
    x = F.gen()
    pol = x + known

    beta = 0.10
    roots = coppersmith_howgrave_univariate(pol, N, beta, mm, mm + 1, xx_bound)

    for k in roots:
        k = Integer(k)
        if k < 0:
            k = -k
        p = Integer(k * Mp + r)
        if p > 1 and N % p == 0:
            return p, Integer(N // p)
    return None

# =======================
# ROCA-style factorization for this challenge
# =======================
def factor_orca(N):
    Mp = M_PRIME
    g = Zmod(Mp)(E)

    # discrete log: N ≡ 65537^(a_p + a_q) (mod Mp)
    try:
        a_sum = Integer(Zmod(Mp)(N).log(E))
    except Exception:
        a_sum = Integer(discrete_log(Mod(N, Mp), Mod(E, Mp)))

    order = Integer(g.multiplicative_order())

    inf = a_sum // 2
    sup = (a_sum + order) // 2

    print("[+] N bits =", int(N.nbits()))
    print("[+] Using M' =", int(Mp))
    print("[+] ord_g  =", int(order))
    print("[+] a_sum  =", int(a_sum))
    print("[+] search a in [", int(inf), ",", int(sup), ") size =", int(sup - inf))

    # bound for k: k ≈ p / Mp ≤ 2*sqrt(N)/Mp
    XX = Integer(floor(2 * sqrt(N) / Mp))

    # --- Notebook-safe: disable multiprocessing in ipykernel ---
    in_notebook = ("ipykernel" in sys.modules)

    if in_notebook:
        print("[+] Detected notebook/ipykernel -> run single-process (no multiprocessing).")
        for i, a in enumerate(range(int(inf), int(sup))):
            if (i + 1) % 10000 == 0:
                print(f"[+] checked {i+1} / {int(sup-inf)} a-values ...")
            val = try_a(N, Mp, a, MM, XX)
            if val is not None:
                return val
        return None

    # --- CLI: use sage parallel multiprocessing ---
    from sage.parallel.multiprocessing_sage import parallel_iter
    from multiprocessing import cpu_count

    workers = cpu_count()
    chunk_size = 10000
    checked = 0

    for start in range(int(inf), int(sup), chunk_size):
        end = min(start + chunk_size, int(sup))
        inputs = [((N, Mp, a, MM, XX), {}) for a in range(start, end)]

        for _, val in parallel_iter(workers, try_a, inputs):
            if val is not None:
                return val

        checked += (end - start)
        print(f"[+] checked {checked} / {int(sup-inf)} a-values ...")

    return None

# =======================
# decrypt
# =======================
def long_to_bytes(x):
    x = int(x)
    if x == 0:
        return b"\x00"
    l = (x.bit_length() + 7) // 8
    return x.to_bytes(l, "big")

def main():
    print("[+] Starting factorization...")
    fac = factor_orca(N)
    if fac is None:
        raise RuntimeError("[-] Factorization failed (unexpected for this instance).")

    p, q = fac
    print("[+] Found factors:")
    print("[+] p =", int(p))
    print("[+] q =", int(q))

    phi = (p - 1) * (q - 1)
    d = inverse_mod(E, phi)
    m = power_mod(ENC, d, N)
    pt = long_to_bytes(m)

    print("[+] Decrypted plaintext bytes:")
    print(pt)

if __name__ == "__main__":
    main()

运行结果：

复赛部分

题目1：rsa_final

一个rsa问题，给了u和v，分别是e模p-1和q-1的逆元，然后泄露了U=u mod 2^199和V=v mod 2^199，也就是u和v的低位
存在正整数 $k_1, k_2$ 满足：

$$e \cdot u = k_1(p-1) + 1$$

$$e \cdot v = k_2(q-1) + 1$$

由于 $u < p-1$，显然有 $k_1 < e$。题目限制了 $e$ 为 72 bit，因此 未知数 $k_1, k_2$ 被严格界定在 $2^{72}$ 的小范围内，可以打二元copper先解出k1和k2
将第一个等式变形，隔离出未知的素数 $p$：

$$k_1 \cdot p = e \cdot u - 1 + k_1$$

已知我们只掌握了低位 $U$，可设高位部分为未知的 $x_u$，即 $u = U + x_u \cdot Q$。代入展开得到：

$$k_1 \cdot p = e(U + x_u \cdot Q) - 1 + k_1 = (e \cdot U - 1) + k_1 + x_u \cdot e \cdot Q$$

为了彻底消灭含有未知数 $x_u$ 的项，我们在等式两边同时对 $M = e \cdot Q$ 取模。
令常量 $A = e \cdot U - 1$ 和 $B = e \cdot V - 1$，我们得到了纯净的模同余方程：

$$k_1 \cdot p \equiv A + k_1 \pmod M$$

$$k_2 \cdot q \equiv B + k_2 \pmod M \quad \text{(同理可得)}$$

将上述两个同余方程相乘，并代入已知量 $n = p \cdot q$：

$$k_1 \cdot k_2 \cdot n \equiv (A + k_1)(B + k_2) \pmod M$$

展开后，将 $k_1, k_2$ 视作代数变量 $x, y$，得到标准的二元多项式同余方程：

$$(n - 1)xy - Bx - Ay - AB \equiv 0 \pmod M$$

目标是求解该方程在 $X, Y \le 2^{72}$ 范围内的小根。然而，在实际构造格基规约时，有几个小问题：
1.非首一多项式
标准的 Coppersmith 往往要求 $xy$ 的系数为 1。若强行除以公因数 $g = \gcd(n-1, M)$，由于剩余项 $A, B$ 不一定能被 $g$ 整除，会导致方程产生浮点数，破坏整数环特性。
因此，使用扩展欧几里得算法（XGCD）求出乘法逆元，提取真正的等价同余系数，将问题转化为非首一多项式的格基映射，并在格矩阵对角线填充 $M^2$。

2.格维度问题
如果仅使用单次展开的 8x8 基础格（$m=1$），理论求解上界为 $XY < M^{0.3} \approx 2^{81}$。但实际 $XY = 2^{144}$，根完全超出搜索范围。
引入多项式平方向（$m=2$），构建 9x9 高维格，将上界提升至 $XY < M^{0.55} \approx 2^{150}$，完美覆盖目标根。

在构造好 9x9 格矩阵并进行 LLL 规约后，算法会输出系数极小的代数独立多项式 $h_1(x,y)$ 和 $h_2(x,y)$。
通过计算这两个多项式关于 $y$ 的 结式（Resultant）（底层是通过计算西尔维斯特矩阵的行列式），可以彻底消去变量 $y$，得到一个只含 $x$ 的一元多项式 $R(x) = 0$。求其整数根即可得到 $k_1$。

求出 $k_1$ 后，可以推导出 $p$ 的低位 $p_0$。但需注意，$k_1$ 可能与 $M$ 存在公约数（如偶数），直接求逆元会触发 ZeroDivisionError。必须先通过 $\gcd(k_1, M)$ 进行约分。
由于 RSA 方程对称，利用已知的 $k_1$，可通过线性同余 $C \cdot k_2 \equiv D \pmod M$ 直接解出 $k_2$，进而求出 $q_0$。

最后阶段利用 SageMath 的 small_roots 函数恢复完整的素数。
由于 $p, q$ 中必然一个大于 $\sqrt{n}$，一个小于 $\sqrt{n}$，而 beta=0.5 默认只能寻找大于 $\sqrt{n}$ 的因子。因此，必须分别将 $p_0$ 和 $q_0$ 喂给 small_roots，并下调 epsilon=0.01 强制算法扩展搜索格维度，只要其中一个命中，即可抓出来

exp：

from Crypto.Util.number import long_to_bytes
import sys

# ================= 题目给定的已知参数 =================
e = 3269834770218481694809
n = 116751448703484355366840201775025865284279195145208042014752560554254636974525900445094434252393126306176328832097159472476466590293588331993005014071275598655101202121619626318044504094075467859952644155183869979160232841481376700194232735947985899320628279507496457026945044297152394600116703106832211346061
U = 555611581159257311716055656452890010637201822068729404411499
V = 520010580954705400377356820181443490009781402173307624774437
c = 99187346948849420907019215990061100332115122516855278156650894560306436495360198420769656203171806023514280892533005165646154539175562103367269192004403942772970427349736360945900801496540291398189377832235682243639988397146507656194107585761666153861534184005851946717219982375709146955987443467659229839064

# ================= 1. 数据预处理与非首一多项式构造 =================
Q = 2^199
M = e * Q
A_prime = e * U - 1
B_prime = e * V - 1

# 原始方程: C3*xy + C1*x + C2*y + C0 ≡ 0 (mod M)
C3 = (n - 1) % M
C1 = (-B_prime) % M
C2 = (-A_prime) % M
C0 = (-A_prime * B_prime) % M

# 使用 XGCD 将 C3 转换为真正的公约数 g，避免假性整除问题
g, u, v = xgcd(C3, M)

# 构建等价的新系数方程 F'(x,y) = g*xy + C1'*x + C2'*y + C0' ≡ 0 (mod M)
C1_prime = (u * C1) % M
C2_prime = (u * C2) % M
C0_prime = (u * C0) % M

# ================= 2. 构造严格映射的 9x9 格 =================
print("[+] Constructing mathematically sound 9x9 Lattice...")
X_bound = 2^72
Y_bound = 2^72

B_mat = Matrix(QQ, 9, 9)

# 对角线填充模数平方 M^2 (对应单项式 1, x, y, x^2, y^2)
for i in range(5):
    B_mat[i, i] = M^2

# Row 5: M * F'(x,y)
B_mat[5, 0] = M * C0_prime; B_mat[5, 1] = M * C1_prime; B_mat[5, 2] = M * C2_prime; B_mat[5, 5] = M * g

# Row 6: x * M * F'(x,y)
B_mat[6, 1] = M * C0_prime; B_mat[6, 3] = M * C1_prime; B_mat[6, 5] = M * C2_prime; B_mat[6, 6] = M * g

# Row 7: y * M * F'(x,y)
B_mat[7, 2] = M * C0_prime; B_mat[7, 5] = M * C1_prime; B_mat[7, 4] = M * C2_prime; B_mat[7, 7] = M * g

# Row 8: F'(x,y)^2 (展开所有项)
B_mat[8, 0] = C0_prime^2
B_mat[8, 1] = 2 * C1_prime * C0_prime
B_mat[8, 2] = 2 * C2_prime * C0_prime
B_mat[8, 3] = C1_prime^2
B_mat[8, 4] = C2_prime^2
B_mat[8, 5] = 2 * g * C0_prime + 2 * C1_prime * C2_prime
B_mat[8, 6] = 2 * g * C1_prime
B_mat[8, 7] = 2 * g * C2_prime
B_mat[8, 8] = g^2

# 应用界限权重
W = [1, X_bound, Y_bound, X_bound^2, Y_bound^2, X_bound*Y_bound, (X_bound^2)*Y_bound, X_bound*(Y_bound^2), (X_bound^2)*(Y_bound^2)]

for i in range(9):
    for j in range(9):
        B_mat[i, j] *= W[j]

# ================= 3. LLL 规约与多项式结式求根 =================
print("[+] Running LLL reduction...")
B_mat = B_mat.LLL()

PR.<x,y> = PolynomialRing(ZZ)
monomials = [1, x, y, x^2, y^2, x*y, x^2*y, x*y^2, x^2*y^2]

def get_poly(row):
    return sum(ZZ(B_mat[row, j] / W[j]) * monomials[j] for j in range(9))

polys = [get_poly(i) for i in range(9)]
k1_val = None

print("[+] Computing resultants to solve for x (k1)...")
for i in range(9):
    for j in range(i + 1, 9):
        res = polys[i].resultant(polys[j], y)
        if not res.is_zero() and not res.is_constant():
            pol_x = res.univariate_polynomial()
            roots_x = pol_x.roots()
            for root, mult in roots_x:
                if root > 0 and root.is_integer():
                    k1_val = ZZ(root)
                    print(f"[+] Successfully found k1 = {k1_val}")
                    break
            if k1_val: break
    if k1_val: break

if not k1_val:
    raise Exception("[-] ERROR: Mathematics failed to yield a root. Check matrix construction bounds.")

# ================= 4. 代数求 k2 与双重 Coppersmith 恢复 =================
print("[+] Recovering p0 using k1...")
# 消除 k1 与 M 可能存在的公约数
g_k1 = GCD(k1_val, M)
M_p = M // g_k1
p0 = (((A_prime + k1_val) // g_k1) * inverse_mod(k1_val // g_k1, M_p)) % M_p
print(f"[+] p0 = {p0}")

print("\n[+] Analytically extracting k2 using symmetry...")
C = (n - 1) * k1_val - A_prime
D = B_prime * k1_val + A_prime * B_prime
g_C = GCD(C, M)

k2_val = (ZZ(D // g_C) * inverse_mod(ZZ(C // g_C), ZZ(M // g_C))) % (M // g_C)
print(f"[+] Exact k2 found: {k2_val}")

print("[+] Recovering q0 using k2...")
# 【修复核心】：消除 k2 与 M 存在的公约数 (处理 ZeroDivisionError)
g_k2 = GCD(k2_val, M)
M_q = M // g_k2
q0 = (((B_prime + k2_val) // g_k2) * inverse_mod(k2_val // g_k2, M_q)) % M_q
print(f"[+] q0 = {q0}")

print("\n[+] Running Univariate Coppersmith (Dual Strike)...")
P.<k> = PolynomialRing(Zmod(n))

X_bound = 2^245 
p = None

# 第一击：攻击 p
print("  -> Strike 1: Attacking p0...")
f_p = (p0 + k * M_p).monic()
roots_p = f_p.small_roots(X=X_bound, beta=0.499, epsilon=0.01)
if roots_p:
    p = p0 + ZZ(roots_p[0]) * M_p
    print("  [+] Hit! Success on p0.")

# 第二击：攻击 q
if not p:
    print("  -> Missed p0. Strike 2: Attacking q0...")
    # 注意这里要使用对应的 M_q
    f_q = (q0 + k * M_q).monic()
    roots_q = f_q.small_roots(X=X_bound, beta=0.499, epsilon=0.01)
    if roots_q:
        p = q0 + ZZ(roots_q[0]) * M_q 
        print("  [+] Hit! Success on q0.")

if p:
    q = n // p
    assert p * q == n
    print(f"\n[+] Successfully factored n!")
    print(f"p = {p}")
    print(f"q = {q}")
    
    # ================= 5. 解密密文 =================
    phi = (p - 1) * (q - 1)
    d = inverse_mod(e, phi)
    m = pow(c, d, n)
    # 使用 uuid 格式的 flag 提取
    import re
    flag_bytes = long_to_bytes(m)
    print("\n[★] Raw Decrypted Bytes: ", flag_bytes)
    
    try:
        flag_str = flag_bytes.decode('utf-8', errors='ignore')
        match = re.search(r'flag\{[a-f0-9\-]+\}', flag_str)
        if match:
            print("[★] Formatted Flag: ", match.group(0))
    except Exception as e:
        pass
else:
    raise Exception("[-] Ultimate fail. Both strikes missed.")

flag:flag{ad9633bf-6300-450f-a21c-a2b72b6a6d86}