FMS (Flag Management System)

一、题目概述

1.1 题目背景

题目描述:
Flag管理系统的开发者似乎给这个系统植入了一个后门，作为测试人员，你能找到后门并获得flag吗？

The developer of the Flag management system seems to have implanted a backdoor into this system. As a tester, can you find the backdoor and obtain the flag?

1.2 题目文件分析

题目提供了一个Python编写的Flag管理系统main.py，系统功能包括：

• [L]ogin: 用户登录

• [G]et Public Key: 获取公钥（实际是PRNG参数）

• [R]ead Flag: 读取加密的flag（需要admin权限）

• [E]xit: 退出系统

二、漏洞分析

2.1 系统架构分析

让我们先看看系统的核心组件：

2.1.1 PRNG（伪随机数生成器）

class PRNG:
    def __init__(self, a=None, b=None, p=None, seed=None):
        self.p = p if p else getPrime(128)      # 128位素数
        self.a = a if a else randrange(1, self.p)
        self.b = b if b else randrange(0, self.p)
        self.state = seed if seed else randrange(0, self.p)

    def next(self):
        self.state = (self.a * self.state + self.b) % self.p
        return self.state

关键点:

• 这是一个线性同余生成器（Linear Congruential Generator, LCG）

• 递推公式:state_{n+1} = (a × state_n + b) mod p

• 状态空间：128位素数p

2.1.2 密码生成机制

prng = PRNG()
Account = {
    "admin": sha256(("".join(prng.choices(ascii_letters + digits, 32))).encode()).hexdigest(),
    "guest": "84983c60f7daadc1cb8698621f802c0d9f9a3c3c295c810748fb048115c186ec"
}

重要发现:

1. admin密码由PRNG生成的32个随机字符组成

2. 如果能恢复PRNG的初始状态，就能重现admin密码

3. guest账户密码已知（hash值），但权限不够读取flag

2.1.3 验证码生成

vcode = prng.randbytes(4).hex().rjust(8, '0')

每次登录都会生成一个4字节的验证码，这是我们的信息泄露点！

2.2 后门分析

后门1: Get Public Key 功能

elif op == "G" or op == "GET PUBLIC KEY":
    print(prng)  # 泄露 a, b, p 参数！

漏洞: 直接泄露了LCG的全部参数（a, b, p），这是一个巨大的安全漏洞！

后门2: 验证码泄露低位

def randbytes(self, n):
    out = b''
    for _ in range(n):
        out += bytes([self.next() % 256])  # 只取低8位！
    return out

漏洞:

• 每次调用randbytes都会输出PRNG状态的低8位

• 登录失败不影响PRNG状态继续前进

• 可以通过多次尝试登录收集大量的低8位信息

三、攻击原理

3.1 LCG（线性同余生成器）基础知识

3.1.1 什么是LCG？

LCG是一种常见的伪随机数生成算法，其递推公式为：

X_{n+1} = (a × X_n + b) mod m

其中：

• X_n: 第n个状态

• a: 乘数（multiplier）

• b: 增量（increment）

• m: 模数（modulus）

示例:

初始种子: X_0 = 12345
参数: a = 7, b = 3, m = 100

X_1 = (7 × 12345 + 3) mod 100 = 86418 mod 100 = 18
X_2 = (7 × 18 + 3) mod 100 = 129 mod 100 = 29
X_3 = (7 × 29 + 3) mod 100 = 206 mod 100 = 6
...

3.1.2 LCG的安全性问题

LCG不适合用于密码学，原因：

1. 可预测性: 如果知道参数和当前状态，可以预测所有未来输出

2. 状态恢复: 通过连续的输出可以恢复内部状态

3. 低位相关性: 低位比高位更不随机

3.2 截断LCG攻击（Truncated LCG Attack）

3.2.1 问题定义

在本题中：

• 我们知道LCG参数：a, b, p

• 我们不知道初始种子（seed）

• 我们能观察到每个状态的低8位（即 state mod 256）

目标: 从这些低位信息恢复完整的初始种子

3.2.2 数学建模

设：

• s= 初始种子（未知）

• state_i= 第i个状态值（未知）

• T_i= 第i个观察到的低8位（已知）

• h_i= 第i个状态的高位部分（未知）

则有：

state_i = h_i × 256 + T_i

同时，根据LCG的递推关系：

state_1 = (a × s + b) mod p
state_2 = (a × state_1 + b) mod p
state_3 = (a × state_2 + b) mod p
...

展开可得：

state_i = a^i × s + b × (a^(i-1) + a^(i-2) + ... + 1) mod p

3.2.3 构建方程组

将两个关系结合：

h_i × 256 + T_i = a^i × s + b × Σ(a^j) mod p

整理得：

h_i × 256 + T_i - a^i × s - b × Σ(a^j) ≡ 0 (mod p)

这是一个多变量多项式方程组，未知数为：s, h_1, h_2, ..., h_n

3.3 格基规约（Lattice-Based Attack）

3.3.1 什么是格（Lattice）？

格是向量空间中的一个离散子群。简单来说，就是由若干基向量通过整数线性组合生成的所有点的集合。

二维格示例:

基向量: v1 = (1, 0), v2 = (0, 1)
格点: 所有整数坐标点 (a, b)，其中 a, b ∈ ℤ

基向量: v1 = (2, 1), v2 = (1, 3)
格点: {a×(2,1) + b×(1,3) | a, b ∈ ℤ}

3.3.2 LLL算法

LLL（Lenstra-Lenstra-Lovász）算法是一种格基规约算法，用于找到格中较短的向量。

基本思想:

1. 给定一组格的基向量（可能很"长"很"歪斜"）

2. LLL算法输出一组"更好"的基向量（更短、更正交）

3. 规约后的短向量往往包含我们要找的解

3.3.3 将LCG问题转化为格问题

我们构建一个格，使得：

• 格中的短向量对应于方程组的解

• 未知数的界限对应于向量的长度约束

构造格矩阵:

每一行对应一个方程
每一列对应一个变量
矩阵元素是方程的系数

对于我们的问题：

变量: s, h_1, h_2, ..., h_n
界限:
  - s ∈ [0, 2^128]
  - h_i ∈ [0, 2^120]  (因为 state < p ≈ 2^128, state = h_i × 256 + T_i)

3.3.4 为什么格基规约能解决这个问题？

关键洞察：

1. 正确的解会产生一个短向量：因为所有方程都满足（结果为0或很小）

2. 错误的猜测会产生长向量：因为不满足模p的约束

3. LLL能找到短向量：从而找到正确解

3.4 解题流程图

[开始]
   ↓
[1. 连接服务器]
   ↓
[2. 获取LCG参数: a, b, p] ← Get Public Key
   ↓
[3. 收集验证码数据] ← 多次尝试登录（32次）
   |
   ├→ 每次登录生成4字节验证码
   ├→ 每字节是PRNG的一次输出 mod 256
   └→ 共收集 32×4 = 128 个低8位样本
   ↓
[4. 构建多项式方程组]
   |
   ├→ 定义变量: s (种子), h_0, h_1, ..., h_127 (高位)
   ├→ 约束: state_i = h_i × 256 + T_i
   └→ LCG递推: state_i = a^i × s + ... (mod p)
   ↓
[5. 格基规约求解]
   |
   ├→ 使用 find_small_roots() 或 LLL
   ├→ 设置变量界限
   └→ 求解得到种子 s
   ↓
[6. 回溯到初始种子]
   |
   └→ 逆向32次: s = (s - b) × a^(-1) mod p
   ↓
[7. 重现admin密码生成]
   |
   ├→ 使用恢复的种子初始化PRNG
   └→ 生成32字符的admin密码
   ↓
[8. 登录admin账户]
   |
   ├→ 获取当前验证码
   └→ 使用恢复的密码登录
   ↓
[9. 读取加密flag]
   |
   ├→ 继续推进PRNG状态（33次×4字节）
   ├→ 生成AES密钥和IV
   └→ 解密flag
   ↓
[获得flag!]

四、完整解题步骤

4.1 环境准备

# 安装依赖
pip install pycryptodome
pip install pwntools

# SageMath（用于格基规约）
# 下载地址: https://www.sagemath.org/

4.2 步骤1: 连接服务器并获取参数

from pwn import remote

# 连接到远程服务器
r = remote("pwn-xxx.challenge.xctf.org.cn", 9999, ssl=True)

# 获取LCG参数
r.sendlineafter(b'>>> ', b'G')
a = int(r.recvline().strip().split(b' = ')[1])
b = int(r.recvline().strip().split(b' = ')[1])
p = int(r.recvline().strip().split(b' = ')[1])

print(f"LCG参数获取成功:")
print(f"a = {a}")
print(f"b = {b}")
print(f"p = {p} ({p.bit_length()} bits)")

为什么这样做？

• Get Public Key功能是后门，直接泄露了完整的LCG参数

• 有了a, b, p，我们就知道了PRNG的所有公开信息

4.3 步骤2: 收集验证码（低8位信息）

T = []  # 存储所有收集到的低8位

def collect_verification_code():
    """收集一次登录的验证码（4字节）"""
    global T
    r.sendlineafter(b'>>> ', b'L')

    # 接收验证码
    vcode_hex = r.recvline().strip().split(b': ')[1].decode()

    # 转换为字节列表
    vcode_bytes = [int(vcode_hex[2*i:2*i+2], 16) for i in range(len(vcode_hex)//2)]
    T.extend(vcode_bytes)

    # 随便输入用户名密码（登录失败，但PRNG状态已前进）
    r.sendlineafter(b'Username: ', b'guest')
    r.sendlineafter(b'Password: ', b'wrong')
    r.sendlineafter(b'Verification code: ', b'wrong')

# 收集32次，共128个字节
for i in range(32):
    collect_verification_code()
    print(f"已收集 {len(T)} 个字节...")

print(f"\\n总共收集到 {len(T)} 个PRNG输出的低8位")

为什么收集32次（128字节）？

1. 信息理论: 初始种子约128位，需要足够的约束才能唯一确定

2. 格基规约要求: 更多的方程意味着更强的约束，更容易找到短向量

3. 实践经验: 128个样本足以可靠地恢复128位的种子

4.4 步骤3: 构建多项式方程组

from sage.all import *

# 定义多项式环
# 变量: s (种子) + h0, h1, ..., h127 (每个输出的高位)
var_names = ['s'] + [f'h{i}' for i in range(len(T))]
R = PolynomialRing(GF(p), var_names)

# 提取变量
s = R.gen(0)  # 种子
hs = [R.gen(i+1) for i in range(len(T))]  # 高位

# 构建方程
F = []  # 方程列表
state = s  # 当前状态从种子开始

for i in range(len(T)):
    # LCG 递推
    state = a * state + b

    # 约束方程: h_i × 256 + T_i - state = 0
    equation = hs[i] * 256 + T[i] - state
    F.append(equation)

print(f"构建了 {len(F)} 个多项式方程")

数学解释:

对于第i个输出：

state_i = (a × state_{i-1} + b) mod p
state_i = h_i × 256 + T_i

因此:
h_i × 256 + T_i ≡ a × state_{i-1} + b (mod p)

展开后，state_i 都是关于初始种子s和各个h_i的多项式。

4.5 步骤4: 使用格基规约求解

from cuso import find_small_roots

# 定义变量的界限
bounds = {s: (0, 2**128)}  # 种子范围
for h in hs:
    bounds[h] = (0, 2**120)  # 高位范围

# 求解小根
print("开始格基规约求解...")
solutions = find_small_roots(F, bounds)

# 提取种子
recovered_seed = solutions[0][s]
print(f"恢复的种子 (after 32 vcodes): {recovered_seed}")
print(f"种子位长: {recovered_seed.bit_length()} bits")

关键技术 - find_small_roots:

这个函数实现了基于格基规约的多变量多项式小根查找算法：

1. 输入:

   • 多项式方程组

   • 每个变量的取值范围

2. 内部流程:

   a) 将多项式方程组转换为格基矩阵
   b) 每个方程对应矩阵的一行
   c) 每个变量对应一列
   d) 使用变量界限调整矩阵尺度
   e) 执行LLL格基规约
   f) 从短向量中提取变量的值
   

3. 输出:

   • 满足所有方程且在界限内的解

4.6 步骤5: 回溯到真正的初始种子

# 关键理解：格求解器返回的seed是"开始收集验证码之前"的状态
# 这个状态正好是"生成admin密码之后"的状态
# 只需要回溯生成admin密码时的32次next()调用

# LCG 逆向公式:
# 如果 state_{n+1} = (a × state_n + b) mod p
# 则 state_n = (state_{n+1} - b) × a^(-1) mod p

a_inv = inverse_mod(a, p)  # 计算a的模逆

original_seed = recovered_seed
for _ in range(32):  # 逆向32次（不是128次！）
    original_seed = (original_seed - b) * a_inv % p

print(f"\\n原始初始种子: {original_seed}")
print(f"位长: {original_seed.bit_length()} bits")

为什么只回溯32次而不是128次？

关键理解：

1. 虽然我们收集了128个字节（128次next调用）

2. 但格求解器求解的变量s定义为"第一次观测之前"的状态

3. 这个s正好是"生成admin密码之后"的时间点

时间线：

[程序启动] seed_0
    ↓
    ↓ choices(seq, 32) → 32次next()调用
    ↓
[生成admin后] ← 格求解器返回的就是这里！
    ↓
    ↓ 32次randbytes(4) → 128次next()调用
    ↓
[收集完成]

所以只需要回溯32次（生成admin密码的调用）就能回到seed_0。

4.7 步骤6: 重现PRNG并生成admin密码

from string import ascii_letters, digits

class PRNG:
    # ... (与题目相同的实现)

# 使用恢复的初始种子重新初始化
prng = PRNG(a, b, p, original_seed)

# 生成admin密码（与题目代码完全一致）
admin_password = "".join(prng.choices(ascii_letters + digits, 32))

print(f"\\nAdmin密码: {admin_password}")

为什么这样有效？

• 伪随机数生成器是确定性的

• 相同的种子 + 相同的算法 = 相同的输出序列

• 我们完美复刻了题目的密码生成过程

4.8 步骤7: 登录admin并获取flag

# 登录admin
r.sendlineafter(b'>>> ', b'L')
current_vcode = r.recvline().strip().split(b': ')[1]
r.sendlineafter(b'Username: ', b'admin')
r.sendlineafter(b'Password: ', admin_password.encode())
r.sendlineafter(b'Verification code: ', current_vcode)

print(r.recvline())  # 应该显示 "Welcome, admin!"

# 此时PRNG又前进了4次（验证码），需要同步
prng.randbytes(4)

4.9 步骤8: 解密flag

from Crypto.Cipher import AES

# 再前进33次（4字节），到达生成密钥的位置
# 这个次数需要根据实际程序流程调整
for _ in range(33):
    prng.randbytes(4)

# 生成AES密钥和IV（与题目代码一致）
key = prng.randbytes(16)
iv = prng.randbytes(16)

print(f"AES Key: {key.hex()}")
print(f"AES IV:  {iv.hex()}")

# 读取加密的flag
r.sendlineafter(b'>>> ', b'R')
enc_flag = bytes.fromhex(r.recvline().decode().strip())

# 解密
aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(enc_flag)

print(f"\\n Flag: {flag.decode()}")

PRNG状态同步的重要性:

时间线:
[初始种子]
  → 生成admin密码 (32次choices)
  → [我们的交互开始]
  → 32次登录验证码 (128次next)
  → 最后一次登录验证码 (4次next)
  → ??? 次未知操作
  → 生成AES key (16次next)
  → 生成AES iv (16次next)
  → 加密flag

我们需要精确追踪每一次PRNG的调用，确保在正确的时间点生成密钥。

五、完整EXP脚本

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

from sage.all import *
from Crypto.Util.number import *
from Crypto.Cipher import AES
from string import ascii_letters, digits
from pwn import process, remote
from cuso import find_small_roots

# ============== 配置 ==============
REMOTE = True
if REMOTE:
    r = remote("pwn-xxx.challenge.xctf.org.cn", 9999, ssl=True)
else:
    r = process(['python3', 'main.py'])

# ============== 第1步: 获取LCG参数 ==============
print("[*] 步骤1: 获取LCG参数...")
r.sendlineafter(b'>>> ', b'G')
a = int(r.recvline().strip().split(b' = ')[1])
b = int(r.recvline().strip().split(b' = ')[1])
p = int(r.recvline().strip().split(b' = ')[1])

print(f"[+] a = {a}")
print(f"[+] b = {b}")
print(f"[+] p = {p} ({p.bit_length()} bits)")

# ============== 第2步: 收集验证码 ==============
print("\\n[*] 步骤2: 收集验证码...")
T = []

def collect_vcode():
    global T
    r.sendlineafter(b'>>> ', b'L')
    vcode_hex = r.recvline().strip().split(b': ')[1].decode()
    vcode_bytes = [int(vcode_hex[2*i:2*i+2], 16) for i in range(len(vcode_hex)//2)]
    T.extend(vcode_bytes)
    r.sendlineafter(b'Username: ', b'guest')
    r.sendlineafter(b'Password: ', b'wrong')
    r.sendlineafter(b'Verification code: ', b'wrong')

for i in range(32):
    collect_vcode()
    print(f"  进度: {i+1}/32", end='\\r')

print(f"\\n[+] 收集完成! 共 {len(T)} 个字节")

# ============== 第3步: 构建方程组 ==============
print("\\n[*] 步骤3: 构建多项式方程组...")
l = len(T)
R = PolynomialRing(GF(p), names=['s'] + [f'h{i}' for i in range(l)])
s, *hs = R.gens()

F = []
state = s
for i in range(l):
    state = a * state + b
    F.append(hs[i] * 256 + T[i] - state)

print(f"[+] 已构建 {len(F)} 个方程")

# ============== 第4步: 格基规约求解 ==============
print("\\n[*] 步骤4: 格基规约求解...")
bounds = {s: (0, 2**128)}
for h in hs:
    bounds[h] = (0, 2**120)

seed_after_collection = find_small_roots(F, bounds)[0][s]
print(f"[+] 恢复种子: {seed_after_collection}")

# ============== 第5步: 回溯初始种子 ==============
print("\\n[*] 步骤5: 回溯到初始种子...")
a_inv = inverse_mod(a, p)
original_seed = seed_after_collection

# 只需回溯32次（生成admin密码时的32次choices调用）
for _ in range(32):
    original_seed = (original_seed - b) * a_inv % p

print(f"[+] 初始种子: {original_seed}")
print(f"[+] 位长: {original_seed.bit_length()} bits")

# ============== 第6步: 生成admin密码 ==============
print("\\n[*] 步骤6: 生成admin密码...")

class PRNG:
    def __init__(self, a, b, p, seed):
        self.p = p
        self.a = a
        self.b = b
        self.state = seed

    def next(self):
        self.state = (self.a * self.state + self.b) % self.p
        return self.state

    def randbytes(self, n):
        out = b''
        for _ in range(n):
            out += bytes([self.next() % 256])
        return out

    def choices(self, seq, k):
        return [seq[self.next() % len(seq)] for _ in range(k)]

prng = PRNG(a, b, p, original_seed)
admin_password = "".join(prng.choices(ascii_letters + digits, 32))

print(f"[+] Admin密码: {admin_password}")

# ============== 第7步: 登录admin ==============
print("\\n[*] 步骤7: 登录admin账户...")
r.sendlineafter(b'>>> ', b'L')
vcode = r.recvline().strip().split(b': ')[1]
r.sendlineafter(b'Username: ', b'admin')
r.sendlineafter(b'Password: ', admin_password.encode())
r.sendlineafter(b'Verification code: ', vcode)

response = r.recvline()
print(f"[+] {response.decode()}")

# 同步PRNG状态（刚才用了4字节的验证码）
prng.randbytes(4)

# ============== 第8步: 解密flag ==============
print("\\n[*] 步骤8: 读取并解密flag...")

# 根据实际情况调整这个次数
for _ in range(33):
    prng.randbytes(4)

key = prng.randbytes(16)
iv = prng.randbytes(16)

r.sendlineafter(b'>>> ', b'R')
enc = bytes.fromhex(r.recvline().decode().strip())

aes = AES.new(key, AES.MODE_CBC, iv)
flag = aes.decrypt(enc)

print(f"\\n{'='*50}")
print(f" Flag: {flag.decode()}")
print(f"{'='*50}\\n")

r.close()

六、关键技术详解

6.1 为什么LCG不安全？

6.1.1 完全可预测

# 已知参数和一个状态，可以预测所有未来
state_1 = ...  # 观察到的某个状态
state_2 = (a * state_1 + b) % p  # 可以计算
state_3 = (a * state_2 + b) % p  # 可以计算
# ... 所有未来状态都能计算

6.1.2 状态恢复

即使只观察到部分信息（如低位），通过数学方法也能恢复完整状态：

• 线性方程组求解

• 格基规约

• 中国剩余定理

• 截断LCG攻击

6.1.3 统计缺陷

• 低位的周期比高位短

• 连续输出之间存在线性相关

• 不满足密码学安全的"不可区分性"

6.2 格基规约为何有效？

6.2.1 核心思想

格基规约将"求解模方程组"转化为"在格中找短向量"：

原问题: 找 x_1, x_2, ..., x_n 使得
  f_1(x_1, ..., x_n) ≡ 0 (mod p)
  f_2(x_1, ..., x_n) ≡ 0 (mod p)
  ...
  且 x_i ∈ [L_i, U_i]

格问题: 找向量 v = (x_1, x_2, ..., x_n) 使得
  ||v|| 很小（短向量）
  v 在由方程定义的格中

6.2.2 几何直观

想象在高维空间中：

• 所有可能的猜测构成一个格

• 正确的解对应一个特别短的向量

• LLL算法能高效找到这样的短向量

6.2.3 为什么短向量就是解？

因为我们构造格时：

1. 如果x_i满足约束，对应的向量分量很小

2. 如果不满足，分量会很大（接近模数p）

3. 所以满足所有约束的解 = 最短的向量

6.3 cuso.find_small_roots 源码解析

这个函数的核心实现（伪代码）：

def find_small_roots(polynomials, bounds):
    # 1. 提取变量和参数
    vars = extract_variables(polynomials)
    n = len(vars)

    # 2. 构建格基矩阵
    M = build_lattice_matrix(polynomials, bounds)
    # M 的每一行对应一个多项式
    # M 的每一列对应一个变量

    # 3. 缩放（根据变量界限）
    for i, var in enumerate(vars):
        lower, upper = bounds[var]
        scale_factor = upper - lower
        M[:, i] *= scale_factor

    # 4. LLL 规约
    B = M.LLL()  # 调用 SageMath 的 LLL 实现

    # 5. 从短向量提取解
    shortest_vector = B[0]  # 通常第一行是最短的

    solution = {}
    for i, var in enumerate(vars):
        # 逆缩放
        lower, upper = bounds[var]
        value = shortest_vector[i] // scale_factor + lower
        solution[var] = value

    # 6. 验证解
    if verify_solution(polynomials, solution):
        return [solution]
    else:
        # 尝试其他短向量
        return try_other_vectors(B, bounds)

6.4 模逆运算详解

在步骤5中，我们需要计算a^(-1) mod p：

a_inv = inverse_mod(a, p)

什么是模逆？

a × a_inv ≡ 1 (mod p)

为什么能求逆？

• 因为p是素数，且 gcd(a, p) = 1

• 根据费马小定理: a^(p-1) ≡ 1 (mod p)

• 所以: a^(-1) ≡ a^(p-2) (mod p)

用途：逆向LCG

正向: state_{n+1} = (a × state_n + b) mod p
逆向: state_n = (state_{n+1} - b) × a^(-1) mod p

验证：

(a × state_n + b - b) × a^(-1)
= a × state_n × a^(-1)
= state_n × (a × a^(-1))
= state_n × 1
= state_n  ✓

6.5 PRNG状态同步的技巧

这是解题的一个难点：必须精确追踪PRNG的每次调用。

调试技巧：

1. 在本地运行题目，添加日志

def next(self):
    self.state = (self.a * self.state + self.b) % self.p
    print(f"[DEBUG] PRNG.next() called, state = {self.state}")  # 添加
    return self.state

2. 对比本地和远程

# 本地
local_prng = PRNG(a, b, p, seed)
local_key = local_prng.randbytes(16)

# 远程
r.sendlineafter(b'>>> ', b'R')
remote_enc = r.recvline()

# 如果解密失败，说明PRNG状态不同步

3. 二分查找同步点

# 尝试不同的前进次数
for skip in range(0, 100):
    test_prng = PRNG(a, b, p, seed)
    # ... 生成admin密码等
    for _ in range(skip):
        test_prng.randbytes(4)

    test_key = test_prng.randbytes(16)
    test_iv = test_prng.randbytes(16)

    if try_decrypt(enc, test_key, test_iv):
        print(f"找到正确的skip次数: {skip}")
        break

七、总结

7.1 知识点总结

本题涉及的密码学和数学知识：

1. 伪随机数生成器 (PRNG)

   • 线性同余生成器 (LCG)

   • LCG的数学性质

   • 密码学安全的PRNG

2. 数论

   • 模运算

   • 模逆 (Modular Inverse)

   • 费马小定理

3. 格理论 (Lattice Theory)

   • 格的定义

   • 格基规约

   • LLL算法

   • 短向量问题 (SVP)

4. 密码分析

   • 截断输出攻击

   • 隐藏数问题 (HNP)

   • 格攻击在密码学中的应用

5. 编程技巧

   • Socket编程 (pwntools)

   • SageMath使用

   • 状态同步

7.2 解题关键点

1. 发现后门：Get Public Key 泄露LCG参数

2. 信息收集：通过多次登录收集低位信息

3. 数学建模：将问题转化为多变量多项式方程组

4. 格基规约：使用LLL算法求解

5. 状态回溯：逆向LCG到初始种子

6. 精确同步：追踪PRNG的每次调用

7.3 参考资料

论文:

• Frieze, A. et al. "Reconstructing Truncated Integer Variables Satisfying Linear Congruences" (1988)

• Nguyen, P. Q. "The LLL Algorithm" (2010)

工具:

• SageMath: https://www.sagemath.org/

• crypto-attacks: https://github.com/jvdsn/crypto-attacks

• pwntools: https://github.com/Gallopsled/pwntools

教程:

• "Lattice-based Attacks in Cryptography" - Tutorial

• "The Hidden Number Problem" - Survey Paper

八、练习

8.1 基础练习

1. 手动计算LCG

   给定: a=7, b=3, m=100, seed=12
   计算前10个输出
   

2. 模逆计算

   计算 7^(-1) mod 100
   验证: 7 × 7^(-1) ≡ 1 (mod 100)
   

3. LCG逆向

   给定: state_10 = 45, a=7, b=3, m=100
   求: state_9
   

8.2 编程练习

1. 实现简单的LCG破解

   # 已知a, b, p 和连续的两个输出
   # 恢复种子
   def break_lcg(a, b, p, output1, output2):
       # your code here
       pass
   

2. 实现验证码收集器

   # 自动化收集多次登录的验证码
   def auto_collect(num_attempts):
       # your code here
       pass
   

九、附录

10.1 完整的cuso模块实现

由于原题使用的cuso模块可能来自特定的CTF工具库，这里提供一个基于SageMath的替代实现：

# cuso.py - 格基规约求解多变量多项式小根

from sage.all import *

def find_small_roots(polynomials, bounds, m=1, t=None, debug=False):
    \"""
    使用格基规约寻找多变量多项式的小根

    参数:
        polynomials: 多项式列表 (在 GF(p) 上定义)
        bounds: 字典 {variable: (lower, upper)}
        m: 格参数
        t: 格参数
        debug: 是否输出调试信息

    返回:
        解的列表，每个解是一个字典 {variable: value}
    \"""
    if not polynomials:
        return []

    R = polynomials[0].parent()
    vars_list = R.gens()
    p = R.characteristic()

    if debug:
        print(f"Variables: {vars_list}")
        print(f"Modulus p: {p} ({p.bit_length()} bits)")
        print(f"Number of polynomials: {len(polynomials)}")

    # 构建格
    # ... (实现细节)

    # 这里可以根据具体需求实现
    # 或者使用 SageMath 的内置函数

    pass  # 完整实现略，参考相关文献

# 使用示例
# solutions = find_small_roots(F, bounds, debug=True)

9.2 常用SageMath命令

# 多项式环
R = PolynomialRing(GF(p), ['x', 'y', 'z'])
x, y, z = R.gens()

# 矩阵
M = Matrix(ZZ, [[1, 2], [3, 4]])
B = M.LLL()  # LLL 规约

# 模逆
a_inv = inverse_mod(a, p)

# 求幂
result = power_mod(a, b, p)  # a^b mod p

# 解方程
solve([x + y == 5, x - y == 1], [x, y])

9.3 调试技巧

# 1. 打印中间状态
print(f"[DEBUG] Current state: {state}")

# 2. 保存和加载PRNG状态
def save_prng_state(prng):
    return {
        'a': prng.a,
        'b': prng.b,
        'p': prng.p,
        'state': prng.state
    }

def load_prng_state(saved):
    return PRNG(saved['a'], saved['b'], saved['p'], saved['state'])

# 3. 单元测试
def test_lcg_inverse():
    prng = PRNG(seed=12345)
    state0 = prng.state
    state1 = prng.next()

    # 逆向
    a_inv = inverse_mod(prng.a, prng.p)
    recovered = (state1 - prng.b) * a_inv % prng.p

    assert recovered == state0, "LCG inverse failed"
    print("✓ LCG inverse test passed")

test_lcg_inverse()

声明: 本文档仅用于CTF竞赛学习和安全研究目的，请勿用于非法用途。