Tags:维纳攻击，低解密指数攻击，Wiener's Attack
0x00. 题目
n=115757306476480823890101488188630776729264818625956711197209182923316919450004566705136037138124707757241364238362202848334326230965866182884372905599812001417295792076008382155051507854558917751540997152031158153627516638609891662992021455525208876152512219426022730388430168986634812925997477433074009315297;
e=36759119760107514342451522014504723756781932778854536007844886957566674786814219616184569606624829254075411466011531177462192834674042314582632169998869937630047822402849141636204405624465283618559148388023239618010023983515302829096233233546355639120782376815166070858869807741037590528029792278496614408403;
c=102306866548166297283990570728719380746274356547349456313911134525511009884527595077619658312746154540918040609904792766267540939554230661255790442398718139161414133218935455395440009626652377478022047762911840522170980051387391261774896710421983974318857176556467366545165306790641364917195790444235849931561;
0x01.WP
从给出的三个数来看e非常大，甚至都接近c，那么可以得出d非常小，符合维纳攻击的条件
维纳攻击（低解密指数攻击
攻击条件：e特别大或者特别小（当d比较小时，攻击就会有效）
维纳攻击是一种针对RSA加密算法的攻击方法，适用于私钥d较小(e较大)的情况。其核心原理基于连分数展开和数论逼近，通过公钥信息恢复私钥
原理推导：大佬已经讲的很清楚了，直接搬运一下
https://zhuanlan.zhihu.com/p/400818185
https://zhuanlan.zhihu.com/p/519941081
exp.py
import gmpy2
from Crypto.Util.number import *def transform(x, y): # 使用辗转相处将分数 x/y 转为连分数的形式res = []while y:res.append(x // y)x, y = y, x % yreturn resdef continued_fraction(sub_res):numerator, denominator = 1, 0 # numerator 分子 denominator 分母for i in sub_res[::-1]: # 从sublist的后面往前循环denominator, numerator = numerator, i * numerator + denominatorreturn 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 resdef get_pq(a, b, c): # 由p+q和pq的值通过韦达定理求解p和qpar = gmpy2.isqrt(b * b - 4 * a * c) # 由上述可得，开根号一定是整数，因为有解x1, x2 = (-b + par) // (2 * a), (-b - par) // (2 * a)return x1, x2def wienerAttack(e, n):for (d, k) in sub_fraction(e, n): # 用一个for循环来注意试探e/n的连续函数的渐进分数，直到找到一个满足条件的渐进分数if k == 0: # 可能会出现连分数的第一个为0的情况，排除continueif (e * d - 1) % k != 0: # ed=1 (mod φ(n)) 因此如果找到了d的话，(ed-1)会整除φ(n),也就是存在k使得(e*d-1)//k=φ(n)continuephi = (e * d - 1) // k # 这个结果就是 φ(n)px, qy = get_pq(1, n - phi + 1, n)if px * qy == n:p, q = abs(int(px)), abs(int(qy)) # 可能会得到两个负数，负负得正未尝不会出现d = gmpy2.invert(e, (p - 1) * (q - 1)) # 求ed=1 (mod φ(n))的结果，也就是e关于 φ(n)的乘法逆元dreturn dprint("该方法不适用")n=115757306476480823890101488188630776729264818625956711197209182923316919450004566705136037138124707757241364238362202848334326230965866182884372905599812001417295792076008382155051507854558917751540997152031158153627516638609891662992021455525208876152512219426022730388430168986634812925997477433074009315297
e=36759119760107514342451522014504723756781932778854536007844886957566674786814219616184569606624829254075411466011531177462192834674042314582632169998869937630047822402849141636204405624465283618559148388023239618010023983515302829096233233546355639120782376815166070858869807741037590528029792278496614408403
c=102306866548166297283990570728719380746274356547349456313911134525511009884527595077619658312746154540918040609904792766267540939554230661255790442398718139161414133218935455395440009626652377478022047762911840522170980051387391261774896710421983974318857176556467366545165306790641364917195790444235849931561d = wienerAttack(e, n)
m = pow(c, d, n)
mm=long_to_bytes(m)
print('mm=',mm)
# b'.scitamehtam fo neeuq eht si ]yroeht rebmun[ citemhtira dna ,secneics fo neeuq eht si scitamehtaM'print(mm.decode()[::-1])
# Mathematics is the queen of sciences, and arithmetic [number theory] is the queen of mathematics.或直接使用风二西的工具，套用维纳攻击菜单
