LITCTF 2025 Crypto 题目解析与教学文档<\/h1>

目录<\/h2>

Basic RSA<\/a><\/li>
EZ Math (矩阵RSA)<\/a><\/li>
Math (因式分解攻击)<\/a><\/li>
Baby (格攻击)<\/a><\/li>
Leak (dp高位泄露)<\/a><\/li>

New Bag (SSP问题)<\/a><\/li> <\/ol>

Basic RSA<\/h2>

题目描述<\/h3>

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

φ(n) = (p-1)(q-1)<\/li>

私钥d = e⁻¹ mod φ(n)<\/li> <\/ol>

解题步骤<\/h3>

计算模数n = p * q<\/li>
计算欧拉函数φ(n) = (p-1)(q-1)<\/li>

使用扩展欧几里得算法求e的模逆d<\/li> <\/ol>

Python实现<\/h3>

from<\/span> Crypto.Util.number import<\/span> inverse
<\/span><\/span>
<\/span><\/span>p =<\/span> ...<\/span> # 题目给出的p<\/span>
<\/span><\/span>q =<\/span> ...<\/span> # 题目给出的q<\/span>
<\/span><\/span>e =<\/span> ...<\/span> # 题目给出的e<\/span>
<\/span><\/span>
<\/span><\/span>n =<\/span> p *<\/span> q
<\/span><\/span>phi =<\/span> (p-<\/span>1<\/span>)*<\/span>(q-<\/span>1<\/span>)
<\/span><\/span>d =<\/span> inverse(e, phi)
<\/span><\/span><\/code><\/pre>
EZ Math (矩阵RSA)<\/h2>
题目描述<\/h3>
RSA的矩阵版本，原理相同：<\/p>

计算φ(n) = (p-1)(q-1)<\/li>
计算d = e⁻¹ mod φ(n)

但所有运算都是在矩阵上进行的<\/li>
<\/ol>
解题步骤<\/h3>

确认矩阵的模数n = p * q<\/li>
计算φ(n) = (p-1)(q-1)<\/li>
对矩阵中的每个元素求逆<\/li>
<\/ol>
关键点<\/h3>

矩阵元素必须与n互质才有逆元<\/li>
使用numpy<\/code>或自定义矩阵运算<\/li>
<\/ul>

Math (因式分解攻击)<\/h2>
题目描述<\/h3>
给出了额外信息：<\/p>

hint = p*q + tmp1 + tmp2<\/li>
hint - n = tmp1 + tmp2 = (p+q+noise)*noise<\/li>
noise是40位素数<\/li>
<\/ul>
解题步骤<\/h3>

分解hint - n = (p+q+noise)*noise<\/li>
由于noise是40位，可以暴力分解或使用Pollard's Rho算法<\/li>
得到noise后，解出p+q = (hint-n)\/noise - noise<\/li>
解方程x² - (p+q)x + n = 0得到p和q<\/li>
<\/ol>
Python实现<\/h3>
from<\/span> Crypto.Util.number import<\/span> isPrime, long_to_bytes
<\/span><\/span>import<\/span> gmpy2
<\/span><\/span>
<\/span><\/span>n =<\/span> ...<\/span> # 模数<\/span>
<\/span><\/span>hint =<\/span> ...<\/span> # 题目给出的hint<\/span>
<\/span><\/span>
<\/span><\/span># 分解tmp = hint - n<\/span>
<\/span><\/span>tmp =<\/span> hint -<\/span> n
<\/span><\/span># 尝试40位素数作为noise<\/span>
<\/span><\/span>for<\/span> noise in<\/span> range(2<\/span>**<\/span>39<\/span>, 2<\/span>**<\/span>40<\/span>):
<\/span><\/span>    if<\/span> tmp %<\/span> noise ==<\/span> 0<\/span> and<\/span> isPrime(noise):
<\/span><\/span>        p_plus_q =<\/span> tmp \/\/<\/span> noise -<\/span> noise
<\/span><\/span>        # 解二次方程<\/span>
<\/span><\/span>        D =<\/span> p_plus_q**<\/span>2<\/span> -<\/span> 4<\/span>*<\/span>n
<\/span><\/span>        if<\/span> D >=<\/span> 0<\/span>:
<\/span><\/span>            p =<\/span> (p_plus_q +<\/span> gmpy2.<\/span>isqrt(D)) \/\/<\/span> 2<\/span>
<\/span><\/span>            q =<\/span> n \/\/<\/span> p
<\/span><\/span>            # 标准RSA解密...<\/span>
<\/span><\/span>            break<\/span>
<\/span><\/span><\/code><\/pre>
Baby (格攻击)<\/h2>
题目描述<\/h3>
基于格的攻击，使用LLL算法求解<\/p>
解题步骤<\/h3>

构造适当的格<\/li>
使用LLL算法进行规约<\/li>
从规约结果中提取解<\/li>
<\/ol>
关键点<\/h3>

需要理解如何将问题转化为格问题<\/li>
可能需要调整格的大小和权重<\/li>
<\/ul>
Python实现<\/h3>
from<\/span> fpylll import<\/span> IntegerMatrix, LLL
<\/span><\/span>
<\/span><\/span># 构造格<\/span>
<\/span><\/span>M =<\/span> IntegerMatrix(...<\/span>)
<\/span><\/span># LLL规约<\/span>
<\/span><\/span>M_lll =<\/span> LLL.<\/span>reduction(M)
<\/span><\/span># 提取解<\/span>
<\/span><\/span>solution =<\/span> M_lll[0<\/span>]
<\/span><\/span><\/code><\/pre>
Leak (dp高位泄露)<\/h2>
题目描述<\/h3>
已知dp的高位，满足：

dp * e ≡ 1 + k(p-1)<\/p>
解题步骤<\/h3>

设dp = dp_high + x<\/li>
建立方程：(dp_high + x)*e - 1 ≡ 0 mod p<\/li>
使用Coppersmith方法求解<\/li>
<\/ol>
Python实现<\/h3>
from<\/span> Crypto.Util.number import<\/span> bytes_to_long, long_to_bytes
<\/span><\/span>import<\/span> gmpy2
<\/span><\/span>
<\/span><\/span>n =<\/span> ...<\/span> # 模数<\/span>
<\/span><\/span>e =<\/span> ...<\/span> # 公钥<\/span>
<\/span><\/span>dp_high =<\/span> ...<\/span> # dp的高位<\/span>
<\/span><\/span>c =<\/span> ...<\/span> # 密文<\/span>
<\/span><\/span>
<\/span><\/span># Coppersmith攻击<\/span>
<\/span><\/span>F.<<\/span>x><\/span> =<\/span> PolynomialRing(Zmod(n))
<\/span><\/span>for<\/span> k in<\/span> range(1<\/span>, e):
<\/span><\/span>    f =<\/span> (dp_high *<\/span> 2<\/span>^<\/span>s +<\/span> x) *<\/span> e -<\/span> 1<\/span> -<\/span> k
<\/span><\/span>    x0 =<\/span> f.<\/span>small_roots(X=<\/span>2<\/span>^<\/span>s, beta=<\/span>0.5<\/span>)
<\/span><\/span>    if<\/span> x0:
<\/span><\/span>        dp =<\/span> dp_high +<\/span> x0[0<\/span>]
<\/span><\/span>        p =<\/span> (e*<\/span>dp -<\/span>1<\/span>) \/\/<\/span> k +<\/span>1<\/span>
<\/span><\/span>        if<\/span> n %<\/span> p ==<\/span> 0<\/span>:
<\/span><\/span>            q =<\/span> n \/\/<\/span> p
<\/span><\/span>            # 标准RSA解密...<\/span>
<\/span><\/span>            break<\/span>
<\/span><\/span><\/code><\/pre>
New Bag (SSP问题)<\/h2>
题目描述<\/h3>
子集和问题(SSP)，已知64位<\/p>
解题步骤<\/h3>

构造格，利用已知位信息<\/li>
使用LLL算法求解<\/li>
爆破可能的k值<\/li>
<\/ol>
Python实现<\/h3>
# 构造格攻击<\/span>
<\/span><\/span>pubkey =<\/span> [...<\/span>] # 公钥向量<\/span>
<\/span><\/span>s =<\/span> ...<\/span> # 目标和<\/span>
<\/span><\/span>
<\/span><\/span># 构造格<\/span>
<\/span><\/span>M =<\/span> matrix(ZZ, len(pubkey)+<\/span>1<\/span>, len(pubkey)+<\/span>1<\/span>)
<\/span><\/span>for<\/span> i in<\/span> range(len(pubkey)):
<\/span><\/span>    M[i,i] =<\/span> 2<\/span>
<\/span><\/span>    M[-<\/span>1<\/span>,i] =<\/span> pubkey[i]
<\/span><\/span>M[-<\/span>1<\/span>,-<\/span>1<\/span>] =<\/span> -<\/span>s
<\/span><\/span>
<\/span><\/span># LLL规约<\/span>
<\/span><\/span>M_lll =<\/span> M.<\/span>LLL()
<\/span><\/span>
<\/span><\/span># 检查解<\/span>
<\/span><\/span>for<\/span> row in<\/span> M_lll:
<\/span><\/span>    if<\/span> set(row[:-<\/span>1<\/span>]).<\/span>issubset([-<\/span>1<\/span>,1<\/span>]) and<\/span> row[-<\/span>1<\/span>] ==<\/span>0<\/span>:
<\/span><\/span>        # 找到解<\/span>
<\/span><\/span>        break<\/span>
<\/span><\/span>
<\/span><\/span># 或者爆破k<\/span>
<\/span><\/span>for<\/span> k in<\/span> range(1<\/span>, 1000<\/span>):
<\/span><\/span>    try<\/span>:
<\/span><\/span>        # 尝试解密<\/span>
<\/span><\/span>        break<\/span>
<\/span><\/span>    except<\/span>:
<\/span><\/span>        continue<\/span>
<\/span><\/span><\/code><\/pre>
总结<\/h2>
本文档详细解析了LITCTF 2025中的密码学题目，涵盖了：<\/p>

标准RSA及其变种<\/li>
因式分解攻击<\/li>
格攻击(LLL算法)<\/li>
高位泄露攻击(Coppersmith方法)<\/li>
子集和问题<\/li>
<\/ul>
每种攻击方法都提供了理论解释和Python实现，帮助读者深入理解现代密码学攻击技术。<\/p>

LITCTF 2025 Crypto 题目解析与教学文档<\/h1>

Basic RSA<\/h2>

EZ Math (矩阵RSA)<\/h2>

Math (因式分解攻击)<\/h2>

Baby (格攻击)<\/h2>

题目描述<\/h3> 基于格的攻击，使用LLL算法求解<\/p>

Leak (dp高位泄露)<\/h2>

题目描述<\/h3> 已知dp的高位，满足： dp * e ≡ 1 + k(p-1)<\/p>

New Bag (SSP问题)<\/h2>

题目描述<\/h3> 子集和问题(SSP)，已知64位<\/p>

题目描述<\/h3>
基于格的攻击，使用LLL算法求解<\/p>

题目描述<\/h3>
已知dp的高位，满足：
dp * e ≡ 1 + k(p-1)<\/p>

题目描述<\/h3>
子集和问题(SSP)，已知64位<\/p>