ctf-crypto

Compare original and translation side by side

🇺🇸

Original

English

🇨🇳

Translation

Chinese

CTF Cryptography

CTF密码学

Quick reference for crypto challenges. For detailed techniques, see supporting files.

密码学挑战快速参考手册。如需详细技术细节，请参阅配套文件。

Additional Resources

额外资源

prng.md - PRNG attacks (Mersenne Twister, LCG, time-based seeds, password cracking)
historical.md - Historical ciphers (Lorenz SZ40/42)
advanced-math.md - Advanced mathematical attacks (isogenies, Pohlig-Hellman, LLL, Coppersmith)

prng.md - PRNG攻击（包括Mersenne Twister、线性同余生成器LCG、基于时间的种子、密码破解）
historical.md - 历史密码（如Lorenz SZ40/42）
advanced-math.md - 高级数学攻击（如同源攻击、Pohlig-Hellman算法、LLL算法、Coppersmith方法）

ZKP Attacks

ZKP攻击

Look for information leakage in proofs
If proving IMPOSSIBLE problem (e.g., 3-coloring K4), you must cheat
Find hash collisions to commit to one value but reveal another
PRNG state recovery: salts generated from seeded PRNG can be predicted
Small domain brute force: if you know
```
commit(i) = sha256(salt(i), color(i))
```
and have salt, brute all colors

寻找证明过程中的信息泄露点
若需证明不可能问题（例如K4图的3着色），必须采用作弊手段
寻找哈希碰撞，实现承诺一个值但披露另一个值
PRNG状态恢复：由带种子PRNG生成的盐值可被预测
小范围暴力破解：若已知
```
commit(i) = sha256(salt(i), color(i))
```
且掌握盐值，可暴力枚举所有颜色

Graph 3-Coloring

图3着色

python

import networkx as nx
nx.coloring.greedy_color(G, strategy='saturation_largest_first')

python

import networkx as nx
nx.coloring.greedy_color(G, strategy='saturation_largest_first')

CBC-MAC vs OFB-MAC Vulnerability

CBC-MAC与OFB-MAC的漏洞

OFB mode creates a keystream that can be XORed for signature forgery
If you have signature for known plaintext P1, forge for P2:
```
new_sig = known_sig XOR block2_of_P1 XOR block2_of_P2
```
Don't forget PKCS#7 padding in calculations!
Small bruteforce space? Just try all combinations (e.g., 100 for 2 unknown digits)

OFB模式生成的密钥流可通过异或操作实现签名伪造
若掌握已知明文P1的签名，可伪造P2的签名：
```
new_sig = known_sig XOR block2_of_P1 XOR block2_of_P2
```
计算时不要忘记PKCS#7填充！
暴力破解空间小？直接尝试所有组合（例如2个未知数字的情况下尝试100种可能）

Weak Hash Functions

弱哈希函数

Linear permutations (only XOR, rotations) are algebraically attackable
Build transformation matrix and solve over GF(2)

仅包含异或、旋转操作的线性置换可通过代数方法攻击
构建变换矩阵并在GF(2)域上求解

GF(2) Gaussian Elimination

GF(2)高斯消元法

python

import numpy as np

def solve_gf2(A, b):
    """Solve Ax = b over GF(2)."""
    m, n = A.shape
    Aug = np.hstack([A, b.reshape(-1, 1)]) % 2
    pivot_cols, row = [], 0
    for col in range(n):
        pivot = next((r for r in range(row, m) if Aug[r, col]), None)
        if pivot is None: continue
        Aug[[row, pivot]] = Aug[[pivot, row]]
        for r in range(m):
            if r != row and Aug[r, col]: Aug[r] = (Aug[r] + Aug[row]) % 2
        pivot_cols.append((row, col)); row += 1
    if any(Aug[r, -1] for r in range(row, m)): return None
    x = np.zeros(n, dtype=np.uint8)
    for r, c in reversed(pivot_cols):
        x[c] = Aug[r, -1] ^ sum(Aug[r, c2] * x[c2] for c2 in range(c+1, n)) % 2
    return x

python

import numpy as np

def solve_gf2(A, b):
    """Solve Ax = b over GF(2)."""
    m, n = A.shape
    Aug = np.hstack([A, b.reshape(-1, 1)]) % 2
    pivot_cols, row = [], 0
    for col in range(n):
        pivot = next((r for r in range(row, m) if Aug[r, col]), None)
        if pivot is None: continue
        Aug[[row, pivot]] = Aug[[pivot, row]]
        for r in range(m):
            if r != row and Aug[r, col]: Aug[r] = (Aug[r] + Aug[row]) % 2
        pivot_cols.append((row, col)); row += 1
    if any(Aug[r, -1] for r in range(row, m)): return None
    x = np.zeros(n, dtype=np.uint8)
    for r, c in reversed(pivot_cols):
        x[c] = Aug[r, -1] ^ sum(Aug[r, c2] * x[c2] for c2 in range(c+1, n)) % 2
    return x

RSA Attacks

RSA攻击

Small e with small message: take eth root
Common modulus: extended GCD attack
Wiener's attack: small d
Fermat factorization: p and q close together
Pollard's p-1: smooth p-1
Hastad's broadcast attack: same message, multiple e=3 encryptions

小e值搭配小明文：直接开e次方根
公模攻击：扩展欧几里得算法攻击
Wiener攻击：针对小d值
费马因式分解：当p和q数值接近时
Pollard's p-1算法：适用于p-1为光滑数的情况
Hastad广播攻击：同一明文使用多个e=3的加密

RSA with Consecutive Primes

连续素数RSA

Pattern (Loopy Primes): q = next_prime(p), making p ≈ q ≈ sqrt(N).

Factorization: Find first prime below sqrt(N):

python

from sympy import nextprime, prevprime, isqrt

root = isqrt(n)
p = prevprime(root + 1)
while n % p != 0:
    p = prevprime(p)
q = n // p

Multi-layer variant: 1024 nested RSA encryptions, each with consecutive primes of increasing bit size. Decrypt in reverse order.

模式（循环素数）： q = next_prime(p)，即p ≈ q ≈ sqrt(N)。

因式分解方法： 寻找sqrt(N)下方的第一个素数：

python

from sympy import nextprime, prevprime, isqrt

root = isqrt(n)
p = prevprime(root + 1)
while n % p != 0:
    p = prevprime(p)
q = n // p

多层变体： 1024层嵌套RSA加密，每层使用比特长度递增的连续素数。需按逆序解密。

Multi-Prime RSA

多素数RSA

When N is product of many small primes (not just p*q):

python

undefined

当N是多个小素数的乘积（而非仅p*q）：

python

undefined

Factor N (easier when many primes)

分解N（素数数量多时更简单）

from sympy import factorint factors = factorint(n) # Returns {p1: e1, p2: e2, ...}

from sympy import factorint factors = factorint(n) # 返回 {p1: e1, p2: e2, ...}

Compute phi using all factors

利用所有因子计算phi

phi = 1 for p, e in factors.items(): phi *= (p - 1) * (p ** (e - 1))

d = pow(e, -1, phi) plaintext = pow(ciphertext, d, n)

undefined

phi = 1 for p, e in factors.items(): phi *= (p - 1) * (p ** (e - 1))

d = pow(e, -1, phi) plaintext = pow(ciphertext, d, n)

undefined

AES Attacks

AES攻击

ECB mode: block shuffling, byte-at-a-time oracle
CBC bit flipping: modify ciphertext to change plaintext
Padding oracle: decrypt without key

ECB模式：块置换、逐字节 oracle 攻击
CBC位翻转：修改密文以改变明文
Padding Oracle：无需密钥即可解密

AES-CFB-8 Static IV State Forging

AES-CFB-8静态IV状态伪造

Pattern (Cleverly Forging Breaks): AES-CFB with 8-bit feedback and reused IV allows state reconstruction.

Key insight: After encrypting 16 known bytes, the AES internal shift register state is fully determined by those ciphertext bytes. Forge new ciphertexts by continuing encryption from known state.

模式（巧妙伪造突破）： 采用8位反馈且重复使用IV的AES-CFB模式可实现状态重构。

核心思路： 加密16个已知字节后，AES内部移位寄存器的状态可完全由这些密文字段确定。通过已知状态继续加密，即可伪造新的密文。

Classic Ciphers

经典密码

Caesar: frequency analysis or brute force 26 keys
Vigenere: Kasiski examination, index of coincidence
Substitution: frequency analysis, known plaintext

凯撒密码：频率分析或暴力破解26个密钥
维吉尼亚密码：Kasiski检验、重合指数法
替换密码：频率分析、已知明文攻击

Vigenère Cipher

维吉尼亚密码

Known Plaintext Attack (most common in CTFs):

python

def vigenere_decrypt(ciphertext, key):
    result = []
    key_index = 0
    for c in ciphertext:
        if c.isalpha():
            shift = ord(key[key_index % len(key)].upper()) - ord('A')
            base = ord('A') if c.isupper() else ord('a')
            result.append(chr((ord(c) - base - shift) % 26 + base))
            key_index += 1
        else:
            result.append(c)
    return ''.join(result)

def derive_key(ciphertext, plaintext):
    """Derive key from known plaintext (e.g., flag format CCOI26{)"""
    key = []
    for c, p in zip(ciphertext, plaintext):
        if c.isalpha() and p.isalpha():
            c_val = ord(c.upper()) - ord('A')
            p_val = ord(p.upper()) - ord('A')
            key.append(chr((c_val - p_val) % 26 + ord('A')))
    return ''.join(key)

When standard keys don't work:

Key may not repeat - could be as long as message
Key derived from challenge theme (character names, phrases)
Key may have "padding" - repeated letters (IICCHHAA instead of ICHA)
Try guessing plaintext words from theme, derive full key

已知明文攻击（CTF中最常见）：

python

def vigenere_decrypt(ciphertext, key):
    result = []
    key_index = 0
    for c in ciphertext:
        if c.isalpha():
            shift = ord(key[key_index % len(key)].upper()) - ord('A')
            base = ord('A') if c.isupper() else ord('a')
            result.append(chr((ord(c) - base - shift) % 26 + base))
            key_index += 1
        else:
            result.append(c)
    return ''.join(result)

def derive_key(ciphertext, plaintext):
    """从已知明文推导密钥（例如flag格式CCOI26{）"""
    key = []
    for c, p in zip(ciphertext, plaintext):
        if c.isalpha() and p.isalpha():
            c_val = ord(c.upper()) - ord('A')
            p_val = ord(p.upper()) - ord('A')
            key.append(chr((c_val - p_val) % 26 + ord('A')))
    return ''.join(key)

当标准密钥无效时：

密钥可能不重复——长度与消息相同
密钥源自挑战主题（角色名、短语等）
密钥可能包含“填充”——重复字母（如IICCHHAA而非ICHA）
尝试猜测主题相关的明文字词，推导完整密钥

Elliptic Curve Attacks (General)

椭圆曲线攻击（通用方法）

Small subgroup attacks:

Check curve order for small factors
Pohlig-Hellman: solve DLP in small subgroups, combine with CRT

Invalid curve attacks:

If point validation missing, send points on weaker curves
Craft points with small-order subgroups

Singular curves:

If discriminant Δ = 0, curve is singular
DLP becomes easy (maps to additive/multiplicative group)

Smart's attack:

For anomalous curves (order = field size p)
Lifts to p-adics, solves DLP in O(1)

python

undefined

小子群攻击：

检查曲线阶是否存在小因子
Pohlig-Hellman算法：在小子群中求解离散对数问题（DLP），结合中国剩余定理（CRT）合并结果

无效曲线攻击：

若缺少点验证步骤，可发送弱曲线上的点
构造具有小子群的点

奇异曲线：

若判别式Δ = 0，曲线为奇异曲线
DLP问题将变得简单（映射到加法/乘法群）

Smart攻击：

针对异常曲线（阶等于域大小p）
提升到p-adic域，以O(1)复杂度求解DLP

python

undefined

SageMath ECC basics

SageMath椭圆曲线基础操作

E = EllipticCurve(GF(p), [a, b]) G = E.gens()[0] # generator order = E.order()

undefined

E = EllipticCurve(GF(p), [a, b]) G = E.gens()[0] # 生成元 order = E.order()

undefined

ECC Fault Injection

ECC故障注入攻击

Pattern (Faulty Curves): Bit flip during ECC computation reveals private key bits.

Attack: Compare correct vs faulty ciphertext, recover key bit-by-bit:

python

undefined

模式（故障曲线）： ECC计算过程中的位翻转会泄露私钥比特。

攻击方法： 对比正确与故障密文，逐位恢复密钥：

python

undefined

For each key bit position:

针对每个密钥比特位：

If fault at bit i changes output → key bit i affects computation

若比特i处的故障改变输出 → 密钥比特i影响计算

Binary distinguisher: faulty_output == correct_output → bit is 0

二进制判别：故障输出 == 正确输出 → 比特为0

undefined

undefined

Useful Tools

实用工具

bash

undefined

bash

undefined

Python setup

Python环境配置

pip install pycryptodome z3-solver sympy gmpy2

SageMath for advanced math (required for ECC)

高级数学计算需使用SageMath

sage -python script.py

undefined

sage -python script.py

undefined

Common Patterns

常见代码模板

python

from Crypto.Util.number import *

python

from Crypto.Util.number import *

RSA basics

RSA基础操作

n = p * q phi = (p-1) * (q-1) d = inverse(e, phi) m = pow(c, d, n)

XOR

XOR操作

from pwn import xor xor(ct, key)

undefined

from pwn import xor xor(ct, key)

undefined

Z3 SMT Solver

Z3 SMT求解器

Z3 solves constraint satisfaction - useful when crypto reduces to finding values satisfying conditions.

Basic usage:

python

from z3 import *

Z3用于求解约束满足问题——当密码学问题可转化为寻找满足条件的值时非常实用。

基础用法：

python

from z3 import *

Boolean variables (for bit-level problems)

布尔变量（适用于比特级问题）

bits = [Bool(f'b{i}') for i in range(64)]

Integer/bitvector variables

整数/比特向量变量

x = BitVec('x', 32) # 32-bit bitvector y = Int('y') # arbitrary precision int

solver = Solver() solver.add(x ^ 0xdeadbeef == 0x12345678) solver.add(y > 100, y < 200)

if solver.check() == sat: model = solver.model() print(model.eval(x))


**BPF/SECCOMP filter solving:**

When challenges use BPF bytecode for flag validation (e.g., custom syscall handlers):

```python
from z3 import *

x = BitVec('x', 32) # 32位比特向量 y = Int('y') # 任意精度整数

solver = Solver() solver.add(x ^ 0xdeadbeef == 0x12345678) solver.add(y > 100, y < 200)

if solver.check() == sat: model = solver.model() print(model.eval(x))


**BPF/SECCOMP过滤器求解：**

当挑战使用BPF字节码进行flag验证时（例如自定义系统调用处理程序）：

```python
from z3 import *

Model flag as array of 4-byte chunks (how BPF sees it)

将flag建模为4字节块数组（BPF的处理方式）

flag = [BitVec(f'f{i}', 32) for i in range(14)] s = Solver()

Constraint: printable ASCII

约束：可打印ASCII字符

for f in flag: for byte in range(4): b = (f >> (byte * 8)) & 0xff s.add(b >= 0x20, b < 0x7f)

Extract constraints from BPF dump (seccomp-tools dump ./binary)

从BPF转储中提取约束（使用seccomp-tools dump ./binary）

mem = [BitVec(f'm{i}', 32) for i in range(16)]

Example BPF constraint reconstruction

BPF约束重构示例

s.add(mem[0] == flag[0]) s.add(mem[1] == mem[0] ^ flag[1]) s.add(mem[4] == mem[0] + mem[1] + mem[2] + mem[3]) s.add(mem[8] == 4127179254) # From BPF if statement

if s.check() == sat: m = s.model() flag_bytes = b'' for f in flag: val = m[f].as_long() flag_bytes += val.to_bytes(4, 'little') print(flag_bytes.decode())


**Converting bits to flag:**
```python
from Crypto.Util.number import long_to_bytes

if solver.check() == sat:
    model = solver.model()
    flag_bits = ''.join('1' if model.eval(b) else '0' for b in bits)
    print(long_to_bytes(int(flag_bits, 2)))

When to use Z3:

Type system constraints (OCaml GADTs, Haskell types)
Custom hash/cipher with algebraic structure
Equation systems over finite fields
Boolean satisfiability encoded in challenge
Constraint propagation puzzles

s.add(mem[0] == flag[0]) s.add(mem[1] == mem[0] ^ flag[1]) s.add(mem[4] == mem[0] + mem[1] + mem[2] + mem[3]) s.add(mem[8] == 4127179254) # 来自BPF条件语句

if s.check() == sat: m = s.model() flag_bytes = b'' for f in flag: val = m[f].as_long() flag_bytes += val.to_bytes(4, 'little') print(flag_bytes.decode())


**比特转flag：**
```python
from Crypto.Util.number import long_to_bytes

if solver.check() == sat:
    model = solver.model()
    flag_bits = ''.join('1' if model.eval(b) else '0' for b in bits)
    print(long_to_bytes(int(flag_bits, 2)))

Z3适用场景：

类型系统约束（OCaml GADTs、Haskell类型）
带代数结构的自定义哈希/密码算法
有限域上的方程组
挑战中编码的布尔可满足性问题
约束传播谜题

Cascade XOR (First-Byte Brute Force)

级联XOR（首字节暴力破解）

Pattern (Shifty XOR): Each byte XORed with previous ciphertext byte.

python

undefined

模式（移位XOR）： 每个字节与前一个密文字节异或。

python

undefined

c[i] = p[i] ^ c[i-1] (or similar cascade)

c[i] = p[i] ^ c[i-1]（或类似级联结构）

Brute force first byte, rest follows deterministically

暴力破解首字节，其余字节可确定性推导

for first_byte in range(256): flag = [first_byte] for i in range(1, len(ct)): flag.append(ct[i] ^ flag[i-1]) if all(32 <= b < 127 for b in flag): print(bytes(flag))

undefined

for first_byte in range(256): flag = [first_byte] for i in range(1, len(ct)): flag.append(ct[i] ^ flag[i-1]) if all(32 <= b < 127 for b in flag): print(bytes(flag))

undefined

ECB Pattern Leakage on Images

ECB模式图像泄露

Pattern (Electronic Christmas Book): AES-ECB on BMP/image data preserves visual patterns.

Exploitation: Identical plaintext blocks produce identical ciphertext blocks, revealing image structure even when encrypted. Rearrange or identify patterns visually.

模式（电子圣诞书）： 对BMP/图像数据使用AES-ECB模式会保留视觉模式。

利用方法： 相同明文块会生成相同密文块，即使加密后也能泄露图像结构。可通过视觉方式识别或重新排列模式。

Padding Oracle Attack

Padding Oracle攻击

Pattern (The Seer): Server reveals whether decrypted padding is valid.

Byte-by-byte decryption:

python

def decrypt_byte(block, prev_block, position, oracle):
    for guess in range(256):
        modified = bytearray(prev_block)
        # Set known bytes to produce valid padding
        pad_value = 16 - position
        for j in range(position + 1, 16):
            modified[j] = known[j] ^ pad_value
        modified[position] = guess
        if oracle(bytes(modified) + block):
            return guess ^ pad_value

模式（预言者）： 服务器会泄露解密后的填充是否有效。

逐字节解密：

python

def decrypt_byte(block, prev_block, position, oracle):
    for guess in range(256):
        modified = bytearray(prev_block)
        # 设置已知字节以生成有效填充
        pad_value = 16 - position
        for j in range(position + 1, 16):
            modified[j] = known[j] ^ pad_value
        modified[position] = guess
        if oracle(bytes(modified) + block):
            return guess ^ pad_value

Atbash Cipher

Atbash密码

Simple substitution: A↔Z, B↔Y, C↔X, etc.

python

def atbash(text):
    return ''.join(
        chr(ord('Z') - (ord(c.upper()) - ord('A'))) if c.isalpha() else c
        for c in text
    )

Identification: Challenge name hints ("Abashed" ≈ Atbash), preserves spaces/punctuation, 1-to-1 substitution.

简单替换密码：A↔Z, B↔Y, C↔X等。

python

def atbash(text):
    return ''.join(
        chr(ord('Z') - (ord(c.upper()) - ord('A'))) if c.isalpha() else c
        for c in text
    )

识别方法： 挑战名称提示（如"Abashed"近似Atbash）、保留空格/标点符号、一对一替换。

Substitution Cipher with Rotating Wheel

转轮替换密码

Pattern (Wheel of Mystery): Physical cipher wheel with inner/outer alphabets.

Brute force all rotations:

python

outer = "ABCDEFGHIJKLMNOPQRSTUVWXYZ{}"
inner = "QNFUVWLEZYXPTKMR}ABJICOSDHG{"  # Given

for rotation in range(len(outer)):
    rotated = inner[rotation:] + inner[:rotation]
    mapping = {outer[i]: rotated[i] for i in range(len(outer))}
    decrypted = ''.join(mapping.get(c, c) for c in ciphertext)
    if decrypted.startswith("METACTF{"):
        print(decrypted)

模式（神秘转轮）： 带内外层字母表的物理密码转轮。

暴力破解所有旋转位置：

python

outer = "ABCDEFGHIJKLMNOPQRSTUVWXYZ{}"
inner = "QNFUVWLEZYXPTKMR}ABJICOSDHG{"  # 给定的内层字母表

for rotation in range(len(outer)):
    rotated = inner[rotation:] + inner[:rotation]
    mapping = {outer[i]: rotated[i] for i in range(len(outer))}
    decrypted = ''.join(mapping.get(c, c) for c in ciphertext)
    if decrypted.startswith("METACTF{"):
        print(decrypted)

Non-Permutation S-box Collision Attack

非置换S盒碰撞攻击

Pattern (Tetraes, Nullcon 2026): Custom AES-like cipher with S-box collisions.

Detection:

len(set(sbox)) < 256

means collisions exist. Find collision pairs and their XOR delta.

Attack: For each key byte, try 256 plaintexts differing by delta. When

ct1 == ct2

, S-box input was in collision set. 2-way ambiguity per byte, 2^16 brute-force. Total: 4,097 oracle queries.

See advanced-math.md for full S-box collision analysis code.

模式（Tetraes, Nullcon 2026）： 自定义类AES密码算法存在S盒碰撞。

检测方法：

len(set(sbox)) < 256

说明存在碰撞。寻找碰撞对及其XOR差值。

攻击方法： 针对每个密钥字节，尝试256个差值为delta的明文。当

ct1 == ct2

时，S盒输入属于碰撞集合。每个字节存在2种歧义，总暴力破解量为2^16。共需约4097次oracle查询。

完整S盒碰撞分析代码请参阅advanced-math.md。

Polynomial CRT in GF(2)[x]

GF(2)[x]中的多项式CRT

Pattern (Going in Circles, Nullcon 2026):

r = flag mod f

where f is random GF(2) polynomial. Collect ~20 pairs, filter coprime, CRT combine.

See advanced-math.md for GF(2)[x] polynomial arithmetic and CRT implementation.

模式（Going in Circles, Nullcon 2026）：

r = flag mod f

，其中f是随机GF(2)多项式。收集约20对数据，筛选互质多项式，通过CRT合并结果。

GF(2)[x]多项式运算及CRT实现请参阅advanced-math.md。

Manger's RSA Padding Oracle Attack

Manger RSA Padding Oracle攻击

Pattern (TLS, Nullcon 2026): RSA-encrypted key with threshold oracle. Phase 1: double f until

k*f >= threshold

. Phase 2: binary search. ~128 total queries for 64-bit key.

See advanced-math.md for full implementation.

模式（TLS, Nullcon 2026）： 带阈值oracle的RSA加密密钥。阶段1：将f翻倍直到

k*f >= threshold

。阶段2：二分查找。64位密钥约需128次查询。

完整实现请参阅advanced-math.md。

Book Cipher Brute Force

书籍密码暴力破解

Pattern (Booking Key, Nullcon 2026): Book cipher with "steps forward" encoding. Brute-force starting position with charset filtering reduces ~56k candidates to 3-4.

See historical.md for implementation.

模式（Booking Key, Nullcon 2026）： 采用“向前步进”编码的书籍密码。通过字符集过滤暴力破解起始位置，可将约56k候选值缩减至3-4个。

实现请参阅historical.md。

Affine Cipher over Non-Prime Modulus

非素数模下的仿射密码

Pattern (Matrixfun, Nullcon 2026):

c = A @ p + b (mod m)

with composite m. Chosen-plaintext difference attack. For composite modulus, solve via CRT in each prime factor field separately.

See advanced-math.md for CRT approach and Gauss-Jordan implementation.

模式（Matrixfun, Nullcon 2026）：

c = A @ p + b (mod m)

，其中m为合数。采用选择明文差分攻击。对于合数模，需在每个素因子域上分别通过CRT求解。

CRT方法及高斯-约当实现请参阅advanced-math.md。",