CTF-RSA中的维纳攻击：原理与实战

在RSA加密体系中，公钥为(e, N)，私钥为d，满足：

e·d≡1modφ(N)

其中φ(N) = (p-1)(q-1)，N = p·q。传统RSA实现中，私钥d的选取需要足够大以保证安全性，但某些场景下开发者可能为了提升解密速度而选择较小的d，这正是维纳攻击的突破口。

由RSA定义可得存在整数k使得：

e·d=k·φ(N) +1

当d较小时，我们可以近似认为：

e/φ(N) ≈k/d

由于φ(N) ≈ N（当p,q足够大时），可得：

e/N≈k/d

维纳攻击的核心就是通过连分数展开逼近k/d的值。

将e/N展开为连分数，遍历其收敛分数（convergents）。当某个收敛分数k_i/d_i满足：

|e/N-k_i/d_i|<1/(2d_i²)

时，即可通过验证d_i是否为有效私钥来实施攻击。

维纳证明了当私钥满足：

d< (1/3)·N^(1/4)

时，连分数方法可以高效恢复私钥d。

• 题目给出较大的公钥指数e（接近N）

• N的位数通常在1024位以下（方便分解验证）

• 可能存在提示"fast decryption"等暗示小d

1. 计算e/N的连分数展开

2. 遍历所有收敛分数，计算候选d

3. 验证d能否解密测试数据

4. 成功则分解N得到flag

from Crypto.Util.number import long_to_bytesimport gmpy2def wiener_attack(e, n):# 连分数展开算法    convergents = continued_fraction(e/n).convergents()for frac in convergents:        k, d = frac.numerator(), frac.denominator()if k == 0:continue        phi = (e*d - 1)//k# 解二次方程验证        b = n - phi + 1        delta = b*b - 4*nif delta >= 0:            root = gmpy2.isqrt(delta)if root*root == delta:return dreturn None# 实战示例n = 123456789... # 替换题目中的Ne = 987654321... # 替换题目中的ed = wiener_attack(e, n)print(f"Found private key d = {d}")

题目名称：EasyRSA 2023给定参数：

N = 132421543...（512位）e = 178542003...（接近N的大数）c = 0x89a3...（密文）

解题过程：

1. 观察e与N同量级，符合维纳攻击特征

执行连分数展开，在第5个收敛项得到：

1. 复制d = 12345

验证解密：

1. python复制

m = pow(c, d, N)print(long_to_bytes(m))  # 输出flag{We1ner_Att4ck_Success}

题目如下：

n = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827e =  11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517c = 4218884541887711839568615416673923480889604461874475071333225389075770098726337046768413570546617180777109293884545400260353306419150066928226964662256930702466709992997796154415790565112167663547017839870351167884417142819504498662037048412313768450136617389372395690363188005647619061128497371121168347810294424378348301835826084732747005110258557662466626720961279087145559906371505117097599774430970980355531235913439823966628008554872896820907555353892843539526041019103819804854883231421963308265517622470779089941078841902464033685762524196275032288319744157255628189204988632871276637699312750636348750883054请解出明文！！！

e很大，不是一般的大，一般来说e很大那就维纳攻击。

解题代码如下：

import gmpy2import libnumdef continuedFra(x, y):    cf = []while y:        cf.append(x // y)        x, y = y, x % yreturn cfdef gradualFra(cf):    numerator = 0    denominator = 1for x in cf[::-1]:        numerator, denominator = denominator, x * denominator + numeratorreturn numerator, denominatordef solve_pq(a, b, c):    par = gmpy2.isqrt(b * b - 4 * a * c)return (-b + par) // (2 * a), (-b - par) // (2 * a)def getGradualFra(cf):    gf = []for i in range(1, len(cf) + 1):        gf.append(gradualFra(cf[:i]))return gfdef wienerAttack(e, n):    cf = continuedFra(e, n)    gf = getGradualFra(cf)for d, k in gf:if k == 0: continueif (e * d - 1) % k != 0:continue        phi = (e * d - 1) // k        p, q = solve_pq(1, n - phi + 1, n)if p * q == n:return dn = 12238605063252292170613110607692779326628090745751955692266649177882959231822580682548279800443278979485092243645806337103841086023159482786712759291169541633901936290854044069486201989034158882661270017305064348254800318759062921744741432214818915527537124001063995865927527037625277330117588414586505635959411443039463168463608235165929831344586283875119363703480280602514451713723663297066810128769907278246434745483846869482536367912810637275405943566734099622063142293421936734750356828712268385319217225803602442033960930413469179550331907541244416573641309943913383658451409219852933526106735587605884499707827e =  11850552481503020257392808424743510851763548184936536180317707155841959788151862976445957810691568475609821000653594584717037528429828330763571556164988619635320288125983463358648887090031957900011546300841211712664477474767941406651977784177969001025954167441377912326806132232375497798238928464025466905201977180541053129691501120197010080001677260814313906843670652972019631997467352264392296894192998971542816081534808106792758008676039929763345402657578681818891775091140555977382868531202964486261123748663752490909455324860302967636149379567988941803701512680099398021640317868259975961261408500449965277690517c = 4218884541887711839568615416673923480889604461874475071333225389075770098726337046768413570546617180777109293884545400260353306419150066928226964662256930702466709992997796154415790565112167663547017839870351167884417142819504498662037048412313768450136617389372395690363188005647619061128497371121168347810294424378348301835826084732747005110258557662466626720961279087145559906371505117097599774430970980355531235913439823966628008554872896820907555353892843539526041019103819804854883231421963308265517622470779089941078841902464033685762524196275032288319744157255628189204988632871276637699312750636348750883054d = wienerAttack(e, n)m=pow(c, d, n)print(libnum.n2s(m).decode())

1. 确保d > N^0.25/3

2. 使用标准密钥生成算法（如PKCS#1）

3. 选择平衡的p,q（位数相近）

4. 考虑使用CRT加速解密代替小d