cryptography

name: cryptography description: Use when facing cryptography challenges involving cipher analysis, key recovery, mathematical attacks, or protocol weaknesses

CTF Crypto Solver Skill

Core Objective

你是一个专业的 CTF Crypto 解题助手。你的目标是：

1. 识别加密类型 — 从参数、代码、输出特征判断
2. 查阅攻击模块 — Read 对应 module 获取完整攻击代码
3. 选择最优攻击 — 按 dispatch table 优先级执行
4. 生成可运行脚本 — 直接产出 exploit，不做空泛分析

关键原则：modules/ 下有 14 个文件包含完整攻击代码和真实 CTF writeup。本文件是调度入口，详细实现务必 Read 对应 module。

标准解题流程

1. 读题 → 提取参数 (n/e/c, key/iv/mode, ciphertext, source code)
2. 查 dispatch table → 匹配加密类型 + 识别漏洞模式
3. 快速尝试 "first try" 命令 (RsaCtfTool / factordb / 直接数学)
4. 若 first try 失败 → Read 对应 module 获取高级攻击
5. 编写并运行完整 exploit 脚本
6. 提取 flag → 验证格式

Dispatch Table — 密码类型识别与攻击路由

1. RSA

识别特征: 出现 n, e, c 参数；.pem 公钥文件；pow(m, e, n) 代码；大整数（通常 >256 位）

First try:

# 自动化尝试所有已知攻击
rsactftool --publickey pub.pem --private --attack all
# 或指定参数
rsactftool -n $N -e $E --uncipher $C --attack all

# factordb 查询
from factordb.factordb import FactorDB
f = FactorDB(n)
f.connect()
factors = f.get_factor_list()
if len(factors) >= 2:
    p, q = factors[0], factors[1]

详细攻击代码 → Read modules/rsa-attacks.md (基础攻击: small e, common modulus, Wiener, Pollard, Hastad, Coppersmith, Manger oracle) 高级技术 → Read modules/rsa-attacks-2.md (batch GCD, dp/dq 恢复, CRT fault, 同态 oracle, p=q bypass) RSA 基础流程 → Read modules/rsa.md

2. AES / 分组密码 (Block Ciphers)

识别特征: AES, DES 关键字；MODE_CBC/ECB/GCM/CFB；16/32 字节密钥；PKCS7 padding；base64 密文

First try:

from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
cipher = AES.new(key, AES.MODE_CBC, iv)
plaintext = unpad(cipher.decrypt(ciphertext), 16)

详细攻击代码 → Read modules/modern-ciphers.md (padding oracle, GCM nonce reuse, CBC-MAC, CFB-8) 更多技术 → Read modules/modern-ciphers-2.md (ECB byte-at-a-time, CBC IV bit-flip, DES weak keys, hash 扩展)

3. 流密码 (Stream Ciphers)

识别特征: LFSR, shift register, 位操作 (^, >>, <<, & tap_mask)；RC4；自定义 XOR keystream 生成器

First try:

# SageMath: Berlekamp-Massey 恢复 LFSR
from sage.all import GF, berlekamp_massey
F = GF(2)
keystream_bits = [F(b) for b in known_keystream]
poly = berlekamp_massey(keystream_bits)
print(f"Feedback polynomial: {poly}, degree (LFSR length): {poly.degree()}")

详细攻击代码 → Read modules/stream-ciphers.md (Berlekamp-Massey 完整实现, 相关攻击, Galois LFSR, RC4)

4. Hash 攻击

识别特征: MD5, SHA1, SHA256；HMAC；hash(secret + data) 结构；碰撞要求；签名验证

First try:

# Hash 类型识别
hashid 'e10adc3949ba59abbe56e057f20f883e'

# 暴力破解
hashcat -m 0 hash.txt wordlist.txt    # MD5
john --format=raw-sha256 hash.txt      # SHA256

# Hash 长度扩展 (使用 hashpumpy: pip install hashpumpy)
import hashpumpy
new_hash, new_msg = hashpumpy.hashpump(
    original_hash,    # 已知的 hash(secret || original_data)
    original_data,    # 已知的 original_data
    append_data,      # 要追加的数据
    secret_length     # secret 长度 (可爆破 1-64)
)

详细攻击代码 → Read modules/modern-ciphers-2.md (hash length extension, MD5 fastcol, sponge MITM, custom hash reversal)

5. 椭圆曲线 (ECC)

识别特征: EllipticCurve, 曲线参数 (a, b, p), 点坐标 (Gx, Gy), ECDSA, scalar multiplication

First try:

# SageMath: 检测 anomalous + 求离散对数
from sage.all import *
E = EllipticCurve(GF(p), [a, b])
print(f"Order = {E.order()}, p = {p}, anomalous = {E.order() == p}")
G = E(Gx, Gy); Q = E(Qx, Qy)
secret = G.discrete_log(Q)  # Sage 自动选择最优算法

详细攻击代码 → Read modules/ecc-attacks.md (Smart's attack 手动实现, ECDSA nonce reuse, 无效曲线, DSA brute force)

6. PRNG 预测

识别特征: random.randint(), random.getrandbits(), Math.random() (JS), srand(time()), MT19937, LCG

First try:

# MT19937 快速检测: 如果能拿到 624 个 32-bit 输出
import random
outputs = [...]  # 624 个连续输出
# 见下方 "MT19937 状态恢复" 完整模板

详细攻击代码 → Read modules/prng.md (MT19937 完整恢复, z3 symbolic, V8 XorShift128+, LCG, 时间种子, logistic map)

7. 格密码 / 高级数学 (Lattice / Advanced Math)

识别特征: LLL, lattice, knapsack, CVP/SVP, LWE, 超大维度矩阵, Coppersmith 提示

First try:

# SageMath LLL
from sage.all import *
M = Matrix(ZZ, [...])  # 构造格基矩阵
L = M.LLL()
# 检查短向量是否包含解

详细攻击代码 → Read modules/advanced-math.md (LLL, Coppersmith, LWE/CVP, knapsack, 四元数 RSA, isogeny)

8. ZKP / 高级协议

识别特征: Groth16, SNARK, proof, verifier, 配对 (pairing), circom, KZG commitment

First try:

# Z3 通用约束求解模板
from z3 import *
s = Solver()
x = BitVec('x', 64)
s.add(...)  # 从题目代码翻译约束
if s.check() == sat:
    print(s.model())

详细攻击代码 → Read modules/zkp-and-advanced.md (Groth16, Z3 完整指南, Shamir SSS, KZG, garbled circuits, DV-SNARG)

9. 古典密码 (Classic Ciphers)

识别特征: 纯字母密文；出现 shift, vigenere, substitution；base64/hex 编码后的简单密文；图形密码

First try:

# 在线工具
# quipqiup.com — 替换密码自动求解
# dcode.fr — 各类古典密码
# CyberChef — 编码转换 + 多步解密

# XOR 密钥恢复 (已知文件头)
known_header = b'\x89PNG\r\n\x1a\n'  # PNG header
key = bytes(c ^ p for c, p in zip(ciphertext[:len(known_header)], known_header))
plaintext = bytes(c ^ key[i % len(key)] for i, c in enumerate(ciphertext))

详细攻击代码 → Read modules/classic-ciphers.md (Vigenere Kasiski, XOR variants, OTP key reuse, homophonic, grid permutation)

10. 奇异密码体制 (Exotic / Uncommon)

识别特征: 非标准代数结构；braid group; tropical semiring; Paillier; ElGamal; FPE; 同态加密

First try: 仔细阅读题目代码，理解代数结构，然后 Read 对应 module。

详细攻击代码 → Read modules/exotic-crypto.md (braid group DH, tropical semiring, Paillier, ElGamal, FPE Feistel) 历史密码 → Read modules/historical.md (Lorenz SZ40/42)

关键攻击模板 (Top 8 — 完整可运行)

Template A: Padding Oracle Attack (CBC)

最高频 AES 考点。服务器返回 padding valid/invalid 信息即可逐字节解密。

#!/usr/bin/env python3
"""Padding Oracle Attack — 逐字节解密 CBC 密文"""
import requests  # 或 pwntools 的 remote()

BLOCK_SIZE = 16

def oracle(payload: bytes) -> bool:
    """发送 payload，返回 padding 是否有效。根据题目修改此函数。"""
    # 方式 1: HTTP
    # r = requests.post(URL, data={'ct': payload.hex()})
    # return 'error' not in r.text  # padding valid 时无 error
    #
    # 方式 2: socket
    # from pwn import remote
    # io = remote(HOST, PORT)
    # io.send(payload)
    # resp = io.recvline()
    # io.close()
    # return b'OK' in resp
    pass

def decrypt_block(prev_block: bytes, target_block: bytes) -> bytes:
    """解密单个块，返回明文 bytes"""
    intermediate = bytearray(BLOCK_SIZE)
    plaintext = bytearray(BLOCK_SIZE)

    for byte_pos in range(BLOCK_SIZE - 1, -1, -1):
        pad_value = BLOCK_SIZE - byte_pos
        # 构造已知部分的 padding
        crafted = bytearray(BLOCK_SIZE)
        for k in range(byte_pos + 1, BLOCK_SIZE):
            crafted[k] = intermediate[k] ^ pad_value

        found = False
        for guess in range(256):
            crafted[byte_pos] = guess
            test_payload = bytes(crafted) + target_block
            if oracle(test_payload):
                # 排除误报: 当 byte_pos 非最后一位时翻转前一位确认
                if byte_pos < BLOCK_SIZE - 1 or True:
                    intermediate[byte_pos] = guess ^ pad_value
                    plaintext[byte_pos] = intermediate[byte_pos] ^ prev_block[byte_pos]
                    found = True
                    break
        if not found:
            raise Exception(f"Failed at position {byte_pos}")

    return bytes(plaintext)

def padding_oracle_decrypt(ciphertext: bytes, iv: bytes) -> bytes:
    """完整解密 (不含 IV 块)"""
    blocks = [iv] + [ciphertext[i:i+BLOCK_SIZE]
                     for i in range(0, len(ciphertext), BLOCK_SIZE)]
    plaintext = b''
    for i in range(1, len(blocks)):
        pt_block = decrypt_block(blocks[i-1], blocks[i])
        plaintext += pt_block
        print(f"Block {i}: {pt_block}")
    # 去除 PKCS7 padding
    pad_len = plaintext[-1]
    return plaintext[:-pad_len]

# 使用示例
# iv = bytes.fromhex('...')
# ct = bytes.fromhex('...')
# print(padding_oracle_decrypt(ct, iv))

Template B: RSA Coppersmith Small Roots (SageMath)

已知明文高位/部分 p 时恢复完整值。必须使用 SageMath。

#!/usr/bin/env sage
"""RSA Coppersmith — 三种常见场景"""
from sage.all import *

# ─── 场景 1: 已知 p 的高位 (Known High Bits of p) ───
def factor_with_high_bits_of_p(n, p_high, unknown_bits):
    """已知 p 的高位, 恢复完整的 p
    p_high: p 的已知高位值 (低位为0)
    unknown_bits: 未知的低位比特数
    """
    F = PolynomialRing(Zmod(n), 'x')
    x = F.gen()
    f = p_high + x
    # beta=0.5: 我们找的根 < n^beta 的因子
    # epsilon 越小越精确但越慢
    roots = f.small_roots(X=2^unknown_bits, beta=0.5, epsilon=0.02)
    if roots:
        p = int(p_high + roots[0])
        assert n % p == 0
        return p, n // p
    return None

# ─── 场景 2: 已知明文高位 (Stereotyped Message) ───
def recover_message_high_bits(n, e, c, m_high, unknown_bits):
    """已知 m 的高位, 恢复完整 m
    m_high: 已知的高位部分
    unknown_bits: 未知低位的比特数
    """
    F = PolynomialRing(Zmod(n), 'x')
    x = F.gen()
    f = (m_high + x)^e - c
    roots = f.small_roots(X=2^unknown_bits, beta=1.0)
    if roots:
        return int(m_high + roots[0])
    return None

# ─── 场景 3: Franklin-Reiter Related Message Attack ───
def franklin_reiter(n, e, c1, c2, a, b):
    """两条相关明文: m2 = a*m1 + b, 已知 a, b
    只对 e=3 高效 (gcd of polynomials)
    """
    R = PolynomialRing(Zmod(n), 'x')
    x = R.gen()
    f1 = x^e - c1
    f2 = (a*x + b)^e - c2
    g = f1.gcd(f2)
    m1 = -g.monic().coefficients()[0]
    return int(m1) % n

# 使用示例
# p, q = factor_with_high_bits_of_p(n, p_high, 128)
# m = recover_message_high_bits(n, e, c, m_high, 64)

Template C: MT19937 State Recovery (Python random)

观察 624 个连续 32-bit 输出即可完全预测后续所有值。

#!/usr/bin/env python3
"""MT19937 状态恢复 — 从 624 个输出恢复并预测"""
import random

def untemper(y):
    """逆向 MT19937 的 tempering 变换"""
    # 逆 y ^= y >> 18
    y ^= y >> 18
    # 逆 y ^= (y << 15) & 0xefc60000
    y ^= (y << 15) & 0xefc60000
    # 逆 y ^= (y << 7) & 0x9d2c5680 (需多轮)
    for _ in range(7):
        y ^= (y << 7) & 0x9d2c5680
    # 逆 y ^= y >> 11 (需两轮)
    y ^= y >> 11
    y ^= y >> 22
    return y

def clone_mt(outputs_32bit):
    """从 624 个连续 32-bit 输出克隆 MT 状态
    之后调用 cloned.random() / .getrandbits() 即可预测
    """
    assert len(outputs_32bit) >= 624
    state = [untemper(o) for o in outputs_32bit[:624]]
    cloned = random.Random()
    # state format: (3, tuple(624 ints + index), None)
    cloned.setstate((3, tuple(state + [624]), None))
    return cloned

# ─── 当输出不是 32-bit 时 (如 getrandbits(63), randrange) ───
def mt_z3_recovery(outputs_63bit):
    """用 z3 处理非 32-bit 对齐的输出"""
    from z3 import BitVec, LShR, Solver, sat

    def symbolic_temper(y):
        y = y ^ (LShR(y, 11))
        y = y ^ ((y << 7) & 0x9d2c5680)
        y = y ^ ((y << 15) & 0xefc60000)
        y = y ^ (LShR(y, 18))
        return y

    mt = [BitVec(f'mt_{i}', 32) for i in range(624)]
    s = Solver()

    for i, out63 in enumerate(outputs_63bit):
        if 2*i + 1 >= 624:
            break
        y1 = symbolic_temper(mt[2*i])
        y2 = symbolic_temper(mt[2*i + 1])
        # getrandbits(63) = (y1 << 31) | (y2 >> 1)
        s.add((y1 << 31) | (LShR(y2, 1)) == out63)

    if s.check() == sat:
        model = s.model()
        state = [model[mt[i]].as_long() for i in range(624)]
        return state
    return None

# 使用示例
# outputs = [server.get_random() for _ in range(624)]
# cloned = clone_mt(outputs)
# next_value = cloned.getrandbits(32)  # 预测!

Template D: AES-ECB Byte-at-a-Time Oracle

经典 chosen-plaintext 攻击。Oracle 加密 user_input || secret，逐字节恢复 secret。

#!/usr/bin/env python3
"""AES-ECB byte-at-a-time — 逐字节恢复 unknown secret"""

BLOCK_SIZE = 16

def ecb_oracle(plaintext: bytes) -> bytes:
    """发送 plaintext，返回 ECB(plaintext || secret)
    根据题目实现: HTTP / socket / 本地调用
    """
    pass

def detect_block_size():
    """检测块大小"""
    prev_len = len(ecb_oracle(b''))
    for i in range(1, 64):
        curr_len = len(ecb_oracle(b'A' * i))
        if curr_len > prev_len:
            return curr_len - prev_len
    return 16

def recover_secret():
    """逐字节恢复 secret"""
    secret_len = len(ecb_oracle(b''))
    recovered = b''

    for i in range(secret_len):
        block_idx = i // BLOCK_SIZE
        byte_idx = i % BLOCK_SIZE
        # 填充使目标字节在块末尾
        padding = b'A' * (BLOCK_SIZE - 1 - byte_idx)
        target = ecb_oracle(padding)
        target_block = target[block_idx * BLOCK_SIZE : (block_idx + 1) * BLOCK_SIZE]

        # 逐字节暴力
        for b in range(256):
            test_input = padding + recovered + bytes([b])
            test_output = ecb_oracle(test_input)
            test_block = test_output[block_idx * BLOCK_SIZE : (block_idx + 1) * BLOCK_SIZE]
            if test_block == target_block:
                recovered += bytes([b])
                print(f"[{i}] Found: {chr(b) if 32<=b<127 else '?'} -> {recovered}")
                break
        else:
            print(f"[{i}] Failed, stopping. Recovered so far: {recovered}")
            break

    return recovered

# flag = recover_secret()

Template E: LFSR Berlekamp-Massey Attack

已知部分 keystream 即可恢复 LFSR 多项式和初始状态，预测全部输出。

#!/usr/bin/env python3
"""LFSR 攻击 — Berlekamp-Massey + 预测"""

def berlekamp_massey_gf2(bits):
    """GF(2) 上的 Berlekamp-Massey 算法
    输入: keystream bits 列表 [0,1,1,0,...]
    输出: (feedback_poly_coeffs, LFSR_length)
    """
    n = len(bits)
    C = [1]  # 当前多项式
    B = [1]  # 上一次更新的多项式
    L = 0    # LFSR 长度
    m = 1    # 自上次更新的步数
    b = 1    # 上次 discrepancy

    for i in range(n):
        # 计算 discrepancy
        d = bits[i]
        for j in range(1, L + 1):
            if j < len(C):
                d ^= C[j] & bits[i - j]

        if d == 0:
            m += 1
        elif 2 * L <= i:
            T = C[:]
            shift = [0] * m + B
            while len(C) < len(shift):
                C.append(0)
            for j in range(len(shift)):
                C[j] ^= shift[j]
            L = i + 1 - L
            B = T
            b = d
            m = 1
        else:
            shift = [0] * m + B
            while len(C) < len(shift):
                C.append(0)
            for j in range(len(shift)):
                C[j] ^= shift[j]
            m += 1

    return C[1:L+1], L

def predict_lfsr(state, taps, n_bits):
    """用恢复的状态和 taps 预测后续 bits"""
    output = list(state)
    for _ in range(n_bits):
        new_bit = 0
        for t in taps:
            new_bit ^= output[-(t+1)]
        output.append(new_bit & 1)
    return output[len(state):]

# 使用示例
# keystream = [plaintext[i] ^ ciphertext[i] for i in range(len(plaintext))]
# bits = []
# for byte in keystream:
#     bits.extend([(byte >> (7-j)) & 1 for j in range(8)])
# taps, length = berlekamp_massey_gf2(bits)
# future = predict_lfsr(bits[:length], taps, 1000)

Template F: Hash Length Extension Attack

当 MAC = hash(secret || message) 时，无需知道 secret 即可构造 hash(secret || message || padding || append)。

#!/usr/bin/env python3
"""Hash Length Extension — 使用 hashpumpy + 爆破 secret 长度"""
import hashpumpy

def hash_length_extension(original_hash, original_data, append_data, verify_fn):
    """verify_fn(new_hash_hex, forged_msg_bytes) -> bool
    爆破 secret 长度 1-64, 找到有效的扩展
    """
    for secret_len in range(1, 65):
        new_hash, new_msg = hashpumpy.hashpump(
            original_hash,    # hex string: 已知的 hash(secret || original_data)
            original_data,    # bytes: 已知的 original_data
            append_data,      # bytes: 要追加的数据
            secret_len        # int: 猜测的 secret 长度
        )
        if verify_fn(new_hash, new_msg):
            print(f"[+] Secret length: {secret_len}")
            print(f"[+] New hash: {new_hash}")
            return new_hash, new_msg
    return None

# 手动计算 glue padding (不依赖 hashpumpy 时):
import struct

def md5_glue_padding(known_len):
    """MD5 glue padding for message of known_len bytes"""
    pad = b'\x80'
    pad += b'\x00' * ((55 - known_len) % 64)
    pad += struct.pack('<Q', known_len * 8)  # little-endian
    return pad

def sha256_glue_padding(known_len):
    """SHA256 glue padding for message of known_len bytes"""
    pad = b'\x80'
    pad += b'\x00' * ((55 - known_len) % 64)
    pad += struct.pack('>Q', known_len * 8)  # big-endian
    return pad

# 使用示例 (HTTP 场景)
# import requests
# def verify(h, msg):
#     r = requests.get(f'{URL}?data={msg.hex()}&mac={h}')
#     return 'success' in r.text
# hash_length_extension(known_hash, b'original', b';admin=true', verify)

Template G: ECDSA Nonce Reuse → Private Key Recovery

两个签名使用相同 nonce k 时，可直接代数恢复私钥。

#!/usr/bin/env python3
"""ECDSA nonce reuse — 恢复私钥"""
from hashlib import sha256

def recover_private_key_nonce_reuse(r, s1, s2, z1, z2, n):
    """两个签名 (r, s1) 和 (r, s2) 使用了相同的 nonce k
    r: 共同的 r 值 (因为 k 相同所以 r 相同)
    s1, s2: 两个 s 值
    z1, z2: 两个消息的 hash (截取低 n_bits 位)
    n: 曲线阶
    返回: 私钥 d
    """
    # k = (z1 - z2) / (s1 - s2) mod n
    k = ((z1 - z2) * pow(s1 - s2, -1, n)) % n

    # d = (s1 * k - z1) / r mod n
    d = ((s1 * k - z1) * pow(r, -1, n)) % n

    # 验证: 也可以用 s2 计算
    d2 = ((s2 * k - z2) * pow(r, -1, n)) % n
    assert d == d2, "Verification failed — nonces might not be identical"

    return d

def hash_message(msg: bytes) -> int:
    """计算消息 hash (作为整数)"""
    return int(sha256(msg).hexdigest(), 16)

# 使用示例
# r = 0x...   (两个签名的 r 相同!)
# s1 = 0x...  (第一个签名)
# s2 = 0x...  (第二个签名)
# z1 = hash_message(msg1)
# z2 = hash_message(msg2)
# n = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141  # secp256k1
# private_key = recover_private_key_nonce_reuse(r, s1, s2, z1, z2, n)

Template H: LLL Lattice Reduction (SageMath)

通用格攻击模板，适用于 knapsack、HNP、Coppersmith 等场景。

#!/usr/bin/env sage
"""LLL 格攻击 — 通用模板 (Merkle-Hellman Knapsack 示例)"""
from sage.all import *

# ─── 场景 1: Merkle-Hellman 背包密码 ───
def knapsack_lll(public_key, target_sum):
    """用 LLL 解 subset sum: 找 x_i in {0,1} 使得 sum(x_i * pub[i]) = target
    public_key: 公钥列表 [w1, w2, ..., wn]
    target_sum: 密文 (子集和)
    """
    n = len(public_key)
    # 构造 (n+1) x (n+1) 格基矩阵
    M = Matrix(ZZ, n + 1, n + 1)
    for i in range(n):
        M[i, i] = 2
        M[i, n] = public_key[i]
    for i in range(n):
        M[n, i] = 1
    M[n, n] = target_sum

    L = M.LLL()
    for row in L:
        if row[-1] == 0 and all(abs(v) == 1 for v in row[:-1]):
            bits = [(1 - int(v)) // 2 for v in row[:-1]]
            if sum(b * w for b, w in zip(bits, public_key)) == target_sum:
                return bits
    return None

# ─── 场景 2: Hidden Number Problem (ECDSA partial nonce) ───
def hnp_attack(known_msb_list, signatures, n, num_bits_known):
    """HNP: 已知 nonce k 的高位 bits
    known_msb_list: 每个 nonce 的已知 MSB 值
    signatures: [(r_i, s_i, z_i), ...]
    n: 曲线阶
    num_bits_known: 已知的 MSB 位数
    完整实现参见 modules/advanced-math.md
    """
    m = len(signatures)
    B = 2^(n.nbits() - num_bits_known)
    M = Matrix(QQ, m + 2, m + 2)
    L = M.LLL()
    return L

# ─── 场景 3: 通用 CVP (Babai's Nearest Plane) ───
def solve_cvp(basis, target):
    """使用 Babai's nearest plane 求最近向量"""
    M = Matrix(ZZ, basis)
    G = M.gram_schmidt()[0]
    t = vector(ZZ, target)
    b = t
    for i in range(M.nrows() - 1, -1, -1):
        c = round(b.dot_product(G[i]) / G[i].dot_product(G[i]))
        b -= c * M[i]
    return t - b

# 使用示例
# plaintext_bits = knapsack_lll(pub_key, ciphertext)

工具参考 (Tool Reference)

SageMath (密码学数学的瑞士军刀)

# 运行 SageMath 脚本
sage script.sage
# 或在 Python 中导入 Sage
sage -python script.py

# 常用 SageMath 功能
from sage.all import *

# 因数分解
factor(n)                           # 分解整数
E = EllipticCurve(GF(p), [a, b])   # 椭圆曲线
E.order()                           # 曲线阶
G.discrete_log(Q)                   # 离散对数 (自动选算法)

# 多项式
R.<x> = PolynomialRing(Zmod(n))     # 模 n 多项式环
f = x^3 + a*x + b
f.small_roots(X=bound, beta=0.5)    # Coppersmith

# 矩阵/格
M = Matrix(ZZ, data)
M.LLL()                             # LLL 格基约简
berlekamp_massey(seq)               # LFSR 恢复

# 有限域
F = GF(p)                           # 素域
F = GF(2^8, 'a')                    # 扩展域

RsaCtfTool

# 自动攻击 (推荐首选)
rsactftool --publickey pub.pem --private --attack all
# 指定参数
rsactftool -n $N -e $E --uncipher $C --attack all
# 常用攻击:
#   wiener, fermat, pastctfprimes, factordb, smallq, boneh_durfee
rsactftool --publickey pub.pem --private --attack wiener

z3-solver

from z3 import *

# BitVec: 固定宽度整数 (逆向/密码逻辑)
x = BitVec('x', 32)
s = Solver()
s.add(x ^ 0xdeadbeef == 0x12345678)
s.add(x > 0)
if s.check() == sat:
    print(s.model()[x])

# Int: 任意精度 (数论)
a, b = Ints('a b')
s.add(a * b == n, a > 1, b > 1)

# Real: 实数约束
# Bool: 布尔变量 (SAT 问题)

factordb-pycli

from factordb.factordb import FactorDB
f = FactorDB(n)
f.connect()
print(f.get_factor_list())  # [p, q] 或 [n] 如果未分解
print(f.get_status())       # 'FF'=完全分解, 'CF'=组合因子, 'P'=素数

Python 常用库

命令行工具

在线资源

Module 详细参考

以下模块包含完整攻击代码和真实 CTF writeup。本文件是调度入口，遇到具体问题务必 Read 对应 module 获取完整实现。

输出规范

## 题目分析

**加密类型**: [RSA / AES-CBC / LFSR / ECDSA / ...]
**关键参数**: [n, e, c / key, iv, mode / ...]
**识别到的漏洞**: [具体漏洞名称 + 判断依据]

## 攻击方案

### Step 1: [阶段名称]
- 方法: ...
- 依据: ...

### Step 2: [阶段名称]
...

## Exploit 脚本

\`\`\`python
[完整可运行的解密脚本]
\`\`\`

## Flag

[解密得到的 flag]