DASCTF Crypto 实战：从RSA连分数到格攻击的进阶解析

1. RSA连分数攻击基础原理RSA连分数攻击是一种针对特定参数设置的RSA加密系统的数学攻击方法。它的核心思想是利用连分数展开来逼近私钥d与公钥e之间的关系从而恢复出私钥或分解模数n。我们先从一个简单的例子理解连分数。假设我们有一个分数比如415/93可以表示为415/93 4 1/(2 1/(6 1/7))这种表示方法就是连分数展开。在RSA攻击场景中当私钥d较小时e/n的连分数展开会泄露d的信息。在实际CTF题目中常见的攻击场景是当e较大而d较小时比如d n^0.25我们可以通过以下步骤实施攻击计算e/n的连分数展开检查每一个收敛分数k/d如果d等于真实的d则可以通过计算得到phi(n)最终分解n得到p和q来看一个具体实现from Crypto.Util.number import * import ContinuedFractions def wiener_attack(e, n): frac ContinuedFractions.rational_to_contfrac(e, n) convergents ContinuedFractions.convergents_from_contfrac(frac) for (k, d) in convergents: if k ! 0 and (e*d - 1) % k 0: phi (e*d - 1) // k s n - phi 1 # 解方程x^2 - s*x n 0 discr s*s - 4*n if discr 0: t isqrt(discr) if t*t discr and (st)%20: return d return None2. DASCTF 2023 sign1n题目解析让我们以DASCTF 2023四月赛中的sign1n题目为例演示如何应用连分数攻击。题目给出了以下关键参数n 17501785470905115084530641937586010443633001681612179692218171935474388105810758340844015368385708349722992595891293984847291588862799310921139505076364559140770828784719022502905431468825797666445114531707625227170492272392144861677408547696040355055483067831733807927267488677560035243230884564063878855983123740667214237638766779250729115967995715398679183680360515620300448887396447013941026492557540060990171678742387611013736894406804530109193638867704765955683067309269778890269186100476308998155078252336943147988308936856121869803970807195714727873626949774272831321358988667427984601788595656519292763705699 WHATF 7550872408895903340469549867088737779221735042983487867888690747510707575208917229455135563614675077641314504029666714424242441219246566431788414277587183624484845351111624500646035107614221756706581150918776828118482092241867365644233950852801286481603893259029733993572417125002284605243126366683373762688802313288572798197775563793405251353957529601737375987762230223965539018597115373258092875512799931693493522478726661976059512568029782074142871019609980899851702029278565972205831732184397965899892253392769838212803823816067145737697311648549879049613081017925387808738647333178075446683195899683981412014732 e 0x10001题目提示WHATF与私钥d相关通过分析可以得到关系式WHATF (d³ 3) mod phi。我们的攻击步骤如下通过观察发现d³ ≈ WHATF因此d ≈ WHATF^(1/3)计算k (ed - 1)/phi ≈ ed/n使用连分数逼近k/n具体实现代码def solve_sign1n(n, WHATF, e): # 估算d的大小 d_approx round(WHATF^(1/3)) # 连分数逼近 cf (e * d_approx / n).continued_fraction() for conv in cf.convergents(): k conv.numerator() d_candidate conv.denominator() # 验证候选d if pow(2, e*d_candidate, n) 2: phi (e*d_candidate - 1) // k d inverse_mod(e, phi) return d return None3. 从连分数到格攻击的进阶当简单的连分数攻击失效时比如d稍大我们可以转向更强大的格攻击(Lattice Attack)。格攻击基于LLL算法能够处理更复杂的关系式。考虑RSA的密钥生成方程ed ≡ 1 mod phi。可以写成ed k*phi 1 k(n - s) 1其中s p q - 1。这可以重新排列为ed k(s - n) - 1 0。我们的目标是找到小的d和k这正适合用格来求解。构建以下格基[ n^0.5 n 0 0 ] [ 0 -e e/n 0 ] [ 0 0 1 0 ] [ 0 0 0 1/n ]使用LLL算法后最短向量很可能包含k和d的信息。实现代码如下def lattice_attack(n, e): # 设置格的大小通常与n的位数相关 m 5 t round(((n.nbits()//8)*m)/2) # 构建格 lattice Matrix(ZZ, [ [n, -e, 0, 0], [0, n, -e, 0], [0, 0, n, -e], [0, 0, 0, t] ]) # LLL规约 reduced lattice.LLL() # 检查结果 for row in reduced: if abs(row[-1]) t: k abs(row[0]) d abs(row[1]) if pow(2, e*d, n) 2: return d return None4. 格攻击在ECC中的应用格攻击不仅适用于RSA在椭圆曲线密码(ECC)中同样有效。以DASCTF题目ECC?为例题目给出了三个加密点和模数giftgift 10954621221812651197619957228527372749810730943802288293715079353550311138677754821746522832935330138708418986232770630995550582619687239759917418738050269898943719822278514605075330569827210725314869039623167495140328454254640051293396463956732280673238182897228775094614386379902845973838934549168736103799539422716766688822243954145073458283746306858717624769112552867126607212724068484647333634548047278790589999183913 C1 (1206929895217993244310816423179846824808172528120308055773133254871707902120929022352908110998765937447485028662679732041, 652060368795242052052268674691241294013033011634464089331399905627588366001436638328894634036437584845563026979258880828) C2 (1819289899794579183151870678118089723240127083264590266958711858768481876209114055565064148870164568925012329554392844153, 1110245535005295568283994217305072930348872582935452177061131445872842458573911993488746144360725164302010081437373324551) C3 (1112175463080774353628562547288706975571507012326470665917118873336738873653792420189391867408691423887642725415133046354, 1820636035485820691083758790204536675748006232767111209985774382700260408550258280489088658228739971137550264759084468620)解题思路是使用Gröbner基求解椭圆曲线参数将三个点代入椭圆曲线方程y² x³ ax b建立方程组求解a和b由于gift n * p可以通过最大公约数分解出n实现代码R.a,b PolynomialRing(Zmod(gift)) I Ideal([ C1[0]^3 a*C1[0] b - C1[1]^2, C2[0]^3 a*C2[0] b - C2[1]^2, C3[0]^3 a*C3[0] b - C3[1]^2 ]) basis I.groebner_basis() a -int(basis[0].coefficients()[0]) b -int(basis[1].coefficients()[0]) n int(basis[2].coefficients()[0])5. 实战中的技巧与注意事项在实际CTF比赛中有几点关键技巧需要注意参数估算对于格攻击正确估计未知参数的大小至关重要。比如在RSA中如果知道d ≈ n^0.25可以相应调整格的构造。维度控制格的维度不能太大也不能太小。通常3-6维的格在计算效率和成功率之间取得平衡。LLL后的处理LLL规约后得到的向量需要仔细解析可能需要尝试多个候选向量。错误处理不是所有情况都能一次成功需要设计验证步骤和重试机制。一个实用的格攻击模板def rsa_lattice_attack(n, e, beta0.5): beta: d的大小参数d n^beta m 5 t int((1/beta - 1)*m) # 构建格 lattice Matrix(ZZ, m1, m1) for i in range(m): lattice[i,i] 1 lattice[i,m] (n1)^i lattice[m,m] -e^m # LLL规约 reduced lattice.LLL() # 检查结果 for row in reduced: if row[-1] 0: continue d_candidate abs(row[-1]) // (e^m) if pow(2, e*d_candidate, n) 2: return d_candidate return None在CTF比赛中密码学题目往往需要灵活组合多种攻击方法。比如在DASCTF的babyhash题目中就需要结合哈希碰撞和格攻击技术。关键是要理解每种攻击方法的适用场景和限制条件根据题目给出的线索选择最合适的攻击路径。