FMCTF2025 密码学题目解析与教学文档

目录

1. RSA小指数攻击
2. 循环迷宫加密
3. 已知和与积的RSA分解
4. 已知前缀的异或加密
5. Robin's Mystery RSA特殊情况
6. Paillier同态加密应用

RSA小指数攻击

题目特征

• 公钥指数e很小
• 模数n很大
• 密文c = m^e mod n

攻击原理

当e很小时(如e=3)，如果明文m满足m^e < n，则模运算不会生效，可以直接对c开e次方恢复明文：

m = c^(1/e)

EXP实现

from gmpy2 import iroot

def small_e_attack(c, e):
    m, exact = iroot(c, e)
    if exact:
        return m
    return None

防御措施

• 使用标准公钥指数(如65537)
• 对明文进行填充(如OAEP)

循环迷宫加密

加密原理

对每一位字符的前后两位进行加和然后取模：

cipher[i] = (plain[i-1] + plain[i+1]) % mod

破解方法

1. 已知flag格式通常以"FMCTF{"开头
2. 利用已知部分建立方程：
   • 已知cipher[0]和plain0、plain1，可求plain[2]
   • 已知cipher[1]和plain1、plain2，可求plain[3]
   • 以此类推

EXP实现

def solve_circular_maze(cipher, known_prefix, mod=256):
    plain = list(known_prefix)
    for i in range(len(known_prefix)-1, len(cipher)):
        next_char = (cipher[i-1] - plain[i-2]) % mod
        plain.append(next_char)
    return bytes(plain)

已知和与积的RSA分解

数学原理

已知：

p * q = n
p + q = hint

可建立二次方程：

x^2 - hint*x + n = 0

解为：

p, q = [hint ± sqrt(hint^2 - 4*n)] / 2

EXP实现

from gmpy2 import isqrt

def factor_with_hint(n, hint):
    discriminant = hint**2 - 4*n
    if discriminant < 0:
        return None
    sqrt_disc = isqrt(discriminant)
    p = (hint + sqrt_disc) // 2
    q = (hint - sqrt_disc) // 2
    if p * q == n:
        return p, q
    return None

已知前缀的异或加密

攻击条件

• 使用7字节随机key
• 已知flag头"FMCTF{"

破解方法

1. 利用异或性质：plain ^ key = cipher ⇒ key = plain ^ cipher
2. 用已知部分恢复key：

known_plain = b"FMCTF{"
key = bytes([known_plain[i] ^ cipher[i] for i in range(7)])

完整EXP

def xor_decrypt(cipher, known_prefix):
    key = bytes([known_prefix[i] ^ cipher[i] for i in range(len(known_prefix))])
    plain = bytes([cipher[i] ^ key[i % len(key)] for i in range(len(cipher))])
    return plain

Robin's Mystery RSA特殊情况

特殊条件

1. p和q相近：可通过费马分解或开平方后寻找相邻素数
2. p ≡ q ≡ 3 mod 4
3. e与φ(n)不互素：gcd(e, p-1) = gcd(e, q-1) = 4

解决方案

使用中国剩余定理(CRT)结合多项式求根：

1. 分别求c在模p和模q下的e次根
2. 使用CRT组合结果

Sage实现

# 定义多项式环
R.<x> = Zmod(p)[]
f = x^e - c
root_p = f.roots()[0][0]

R.<x> = Zmod(q)[]
f = x^e - c
root_q = f.roots()[0][0]

# 使用CRT组合
flag = crt([root_p, root_q], [p, q])

数学基础

当e与φ(n)不互素时，常规RSA解密失效，但若e较小，仍可通过：

1. 在Zmod(p)和Zmod(q)下分别求根
2. 使用Hensel引理提升
3. CRT组合结果

Paillier同态加密应用

题目要求

计算：(c1 * c2 * c3 * c4^-1) mod n²

Paillier基础

• 公钥：(n, g)
• 密文：c = g^m * r^n mod n²
• 同态性质：
  • E(m1) * E(m2) = E(m1 + m2)
  • E(m)^k = E(k*m)

解题步骤

1. 计算n_sq = n²
2. 计算c4_inv = inverse(c4, n_sq)
3. 计算result = (c1 * c2 * c3 * c4_inv) % n_sq

Python实现

from gmpy2 import invert

def solve_paillier(n, c1, c2, c3, c4):
    n_sq = n * n
    c4_inv = invert(c4, n_sq)
    result = (c1 * c2 * c3 * c4_inv) % n_sq
    return result

交互脚本示例

from pwn import *

io = remote("host", port)
# 接收n, c1, c2, c3, c4
result = solve_paillier(n, c1, c2, c3, c4)
io.sendlineafter("pass_code:", str(result))
io.interactive()

参考文献

1. Sage多项式基础
2. Paillier同态加密简介

本教学文档涵盖了FMCTF2025中出现的各类密码学问题及其解决方案，重点讲解了攻击原理、数学基础和实际实现。对于CTF参赛者而言，掌握这些技术对解决现代密码学挑战至关重要。