记录一下XY的维纳攻击题目
winner's acctack,维纳攻击，其原理https://zhuanlan.zhihu.com/p/400818185 这位佬写的超级详细，若需要证明过程可参考！
维纳的本质在于通过近似phi与n的值，ed = 1 + k * phi 即可化简成 e / n = k / d，其中e ， n的值已知的情况下，我们可以通过求e / n的连分数来得到d的值（d包含在e / n的连分数组中），通过循环遍历k的d的值去检验e / phi = k / d，我们便可以求得phi的值，phi = n - (p + q) -1 ,得知（p + q）与 p * q 的值，我们可以通过韦达定理构造一元二次方程: x^2 + (p + q)x + pq = 0,该方程的两解必为p ，q ，从而解决问题。
给个题
题目所示
点击查看代码
p = getPrime(512)
q = getPrime(512)
d = getPrime(512)
e = gmpy2.invert(d, (p**3 - 1) * (q**3 - 1))
flag = "XYCTF{" + **hashlib**.md5(str(p + q).encode()).hexdigest() + "}"
print(e)
print(p * q)
e = 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
n = 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
看到题目，只在知道e，n的值情况下，很容易联想到维纳攻击，但本题的e并非真实的e值，那就意味着我们通过维纳攻击求出来的phi值即为(p ** 3 - 1) * (q ** 3 - 1)，运用一些数论小知识，我们不难将其化简为n ** 3 − (p+q) ** 3 + 3n * (p+q) + 1，刚好题目的flag是p + q哈希加密后的结果，所以解p + q就行啦！
下面是维纳攻击求phi的代码
点击查看代码
import gmpy2
import libnum
from Crypto.Util.number import long_to_bytes
def transform(x, y): # 使用辗转相处将分数 x/y 转为连分数的形式
res = []
while y:
res.append(x // y)
x, y = y, x % y
return res
def continued_fraction(sub_res):
numerator, denominator = 1, 0
for i in sub_res[::-1]: # 从sublist的后面往前循环
denominator, numerator = numerator, i * numerator + denominator
return denominator, numerator # 得到渐进分数的分母和分子，并返回
# 求解每个渐进分数
def sub_fraction(x, y):
res = transform(x, y)
res = list(map(continued_fraction, (res[0:i] for i in range(1, len(res))))) # 将连分数的结果逐一截取以求渐进分数
return res
def get_pq(a, b, c): # 由p+q和pq的值通过维达定理来求解p和q
par = gmpy2.isqrt(b * b - 4 * a * c) # 由上述可得，开根号一定是整数，因为有解
x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)
return x1, x2
def wienerAttack(e, n):
for (d, k) in sub_fraction(e, pow(n,3)): # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数
if k == 0: # 可能会出现连分数的第一个为0的情况，排除
continue
if (e * d - 1) % k != 0: # ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)
continue
phi = (e * d - 1) // k # 这个结果就是 φ(n)
print(phi)
e = 172005065945326769176157335849432320425605083524943730546805772515111751580759726759492349719668775270727323745284785341119685198468883978645793770975366048506237371435027612758232099414404389043740306443065413069994232238075194102578269859784981454218948784071599231415554297361219709787507633404217550013282713899284609273532223781487419770338416653260109238572639243087280632577902857385265070736208291583497988891353312351322545840742380550393294960815728021248513046077985900158814037534487146730483099151396746751774427787635287611736111679074330407715700153025952858666841328055071403960165321273972935204988906850585454805923440635864200149694398767776539993952528995717480620593326867245714074205285828967234591508039849777840636255379730281105670496110061909219669860172557450779495125345533232776767292561378244884362014224844319802810586344516400297830227894063759083198761120293919537342405893653545157892446163
n = 99075185389443078008327214328328747792385153883836599753096971412377366865826254033534293886034828804219037466246175526347014045811852531994537520303063113985486063022444972761276531422538694915030159420989401280012025249129111871649831185047820236417385693285461420040134313833571949090757635806658958193793
d = wienerAttack(e, n)
这里面的get_pq函数并没有用到，运行结果后发现满足条件的phi有四个值。在尝试带入最后一个phi值时，便可以得到flag的值！
这道题有不严谨的地方在于，在实际的证明过程中，维纳运用的多次近似操作，而事实上，近似的值是会产生影响的，只不过难以证明。这道题能成立的前提在于 p ** 3 和 q ** 3 的值很大，这才让题目符合维纳攻击的特性！ok，证毕，下面附上marddown的证明过程
点击查看代码
winner's attack
$$
phi = (p^3 - 1) * (q^3 - 1) \sim (p*q)^3 = n^3
\\e*d \equiv 1 \mod {phi}
\\e*d = k*phi + 1
\\\sim e*d = k*phi
\\e/phi = k/d
\\ \sim e/n^3 = k / d
\\构造一元二次方程，使得两根为q,p
\\x^2 - (p+q)x + pq = 0
\\韦达定理
$$
数论推理
$$
已知phi=(p^3 - 1) * (q^3 - 1),n=pq
\\求p+q
\\phi=(p^3 - 1) * (q^3 - 1)
\\ = {p*q}^3 - (p^3 + q^3) + 1
\\\because (a+b) (a²-ab+b²)=a³+b³
\\\therefore \\= {n}^3 - (p+q)(p^2-p*q+q^2) + 1
\\ = {n}^3 - (p+q)(p^2 + 2pq + q^2 -3pq) + 1
\\ = n^3 - (p+q)[(p+q)^2-3n] + 1
\\ = n^3 - (p+q)^3 + 3n(p+q) +1
\\令 x = p+q
\\ 0 = - x^3 + 3n \times x + 1 + n^3 - phi
$$