LITCTF 2025 Crypto 题目解析与教学文档

目录

1. Basic RSA
2. EZ Math (矩阵RSA)
3. Math (因式分解攻击)
4. Baby (格攻击)
5. Leak (dp高位泄露)
6. New Bag (SSP问题)

Basic RSA

题目描述

标准的RSA问题，已知p、q、e，要求计算：

1. φ(n) = (p-1)(q-1)
2. 私钥d = e⁻¹ mod φ(n)

解题步骤

1. 计算模数n = p * q
2. 计算欧拉函数φ(n) = (p-1)(q-1)
3. 使用扩展欧几里得算法求e的模逆d

Python实现

from Crypto.Util.number import inverse

p = ... # 题目给出的p
q = ... # 题目给出的q
e = ... # 题目给出的e

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

EZ Math (矩阵RSA)

题目描述

RSA的矩阵版本，原理相同：

1. 计算φ(n) = (p-1)(q-1)
2. 计算d = e⁻¹ mod φ(n)
   但所有运算都是在矩阵上进行的

解题步骤

1. 确认矩阵的模数n = p * q
2. 计算φ(n) = (p-1)(q-1)
3. 对矩阵中的每个元素求逆

关键点

• 矩阵元素必须与n互质才有逆元
• 使用numpy或自定义矩阵运算

Math (因式分解攻击)

题目描述

给出了额外信息：

• hint = p*q + tmp1 + tmp2
• hint - n = tmp1 + tmp2 = (p+q+noise)*noise
• noise是40位素数

解题步骤

1. 分解hint - n = (p+q+noise)*noise
2. 由于noise是40位，可以暴力分解或使用Pollard's Rho算法
3. 得到noise后，解出p+q = (hint-n)/noise - noise
4. 解方程x² - (p+q)x + n = 0得到p和q

Python实现

from Crypto.Util.number import isPrime, long_to_bytes
import gmpy2

n = ... # 模数
hint = ... # 题目给出的hint

# 分解tmp = hint - n
tmp = hint - n
# 尝试40位素数作为noise
for noise in range(2**39, 2**40):
    if tmp % noise == 0 and isPrime(noise):
        p_plus_q = tmp // noise - noise
        # 解二次方程
        D = p_plus_q**2 - 4*n
        if D >= 0:
            p = (p_plus_q + gmpy2.isqrt(D)) // 2
            q = n // p
            # 标准RSA解密...
            break

Baby (格攻击)

题目描述

基于格的攻击，使用LLL算法求解

解题步骤

1. 构造适当的格
2. 使用LLL算法进行规约
3. 从规约结果中提取解

关键点

• 需要理解如何将问题转化为格问题
• 可能需要调整格的大小和权重

Python实现

from fpylll import IntegerMatrix, LLL

# 构造格
M = IntegerMatrix(...)
# LLL规约
M_lll = LLL.reduction(M)
# 提取解
solution = M_lll[0]

Leak (dp高位泄露)

题目描述

已知dp的高位，满足：
dp * e ≡ 1 + k(p-1)

解题步骤

1. 设dp = dp_high + x
2. 建立方程：(dp_high + x)*e - 1 ≡ 0 mod p
3. 使用Coppersmith方法求解

Python实现

from Crypto.Util.number import bytes_to_long, long_to_bytes
import gmpy2

n = ... # 模数
e = ... # 公钥
dp_high = ... # dp的高位
c = ... # 密文

# Coppersmith攻击
F.<x> = PolynomialRing(Zmod(n))
for k in range(1, e):
    f = (dp_high * 2^s + x) * e - 1 - k
    x0 = f.small_roots(X=2^s, beta=0.5)
    if x0:
        dp = dp_high + x0[0]
        p = (e*dp -1) // k +1
        if n % p == 0:
            q = n // p
            # 标准RSA解密...
            break

New Bag (SSP问题)

题目描述

子集和问题(SSP)，已知64位

解题步骤

1. 构造格，利用已知位信息
2. 使用LLL算法求解
3. 爆破可能的k值

Python实现

# 构造格攻击
pubkey = [...] # 公钥向量
s = ... # 目标和

# 构造格
M = matrix(ZZ, len(pubkey)+1, len(pubkey)+1)
for i in range(len(pubkey)):
    M[i,i] = 2
    M[-1,i] = pubkey[i]
M[-1,-1] = -s

# LLL规约
M_lll = M.LLL()

# 检查解
for row in M_lll:
    if set(row[:-1]).issubset([-1,1]) and row[-1] ==0:
        # 找到解
        break

# 或者爆破k
for k in range(1, 1000):
    try:
        # 尝试解密
        break
    except:
        continue

总结

本文档详细解析了LITCTF 2025中的密码学题目，涵盖了：

• 标准RSA及其变种
• 因式分解攻击
• 格攻击(LLL算法)
• 高位泄露攻击(Coppersmith方法)
• 子集和问题

每种攻击方法都提供了理论解释和Python实现，帮助读者深入理解现代密码学攻击技术。