RSA--维纳攻击--代码和题目分析

维纳攻击原理：

两位大佬讲得非常清楚（搬运工就是我）：https://zhuanlan.zhihu.com/p/400818185
https://www.cnblogs.com/wandervogel/p/16805992.html
看完详细原理后，我们来划重点

维纳攻击脚本

看得懂但写不出，只能搬运了
（注：看脚本前，必须对 ‘连分数’ 和 ‘渐近分数’ 的概念有清晰的认识：连分数 & 渐近分数）



所以说所求的d即为满足条件的渐近分数的分子（现在不理解是分子不要紧，自行推理完之后便可理解）

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, 0for 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("该方法不适用")c = 
n = 
e = 
d = wienerAttack(e, n)
m=pow(c, d, n)
print(long_to_bytes(m))

• 此处再加一个欧拉函数的计算公式：
  

• 回到上面那个问题
  不理解 d 为什么为分子的可以就用上述 89 / 26 这个例子用笔（即写纸上）进行代码推理，相信我，推理完后一定理解（我就是这样理解过来的）

  此串代码求解正常的RSA维纳攻击题型可解
  但对于转了一点弯的题目便要稍作修改
  而懂得修改的前提是你对以上的原理和代码完全理解
  不理解就只能做简单的题型

举个栗子

[羊城杯 2020]RRRRRRRSA 1

题目描述：

import hashlib
import sympy
from Crypto.Util.number import *flag = 'GWHT{************}'flag1 = flag[:19].encode()  #两截flag
flag2 = flag[19:].encode()
assert(len(flag) == 38)P1 = getPrime(1038)
P2 = sympy.nextprime(P1)  #p2>p1
assert(P2 - P1 < 1000)Q1 = getPrime(512)
Q2 = sympy.nextprime(Q1)  #q2>q1N1 = P1 * P1 * Q1
N2 = P2 * P2 * Q2E1 = getPrime(1024)
E2 = sympy.nextprime(E1)m1 = bytes_to_long(flag1)
m2 = bytes_to_long(flag2)c1 = pow(m1, E1, N1)
c2 = pow(m2, E2, N2)output = open('secret', 'w')
output.write('N1=' + str(N1) + '\n')
output.write('c1=' + str(c1) + '\n')
output.write('E1=' + str(E1) + '\n')
output.write('N2=' + str(N2) + '\n')
output.write('c2=' + str(c2) + '\n')
output.write('E2=' + str(E2) + '\n')
output.close()N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393

题目分析：

• wiener attack 是依靠连分数进行的攻击方式，适用于非常接近某一值（比如1）时，求一个比例关系(通常是e / N = 1)
• 此题中e比较大，想到维纳攻击，但题中 e / N << 1, 不符合利用条件，但是N1和N2的关系却合适
  
• 注意：使用维纳攻击进行解题需满足一定的数值条件：
  
• 解题代码：

import gmpy2
from Crypto.Util.number import *
import sympy
def continuedFra(x, y):"""计算连分数:param x: 分子:param y: 分母:return: 连分数列表"""cf = []while y:cf.append(x // y)x, y = y, x % yreturn cf
def gradualFra(cf):"""计算传入列表最后的渐进分数:param cf: 连分数列表:return: 该列表最后的渐近分数"""numerator = 0 # 分子denominator = 1 # 分母for x in cf[::-1]:# 这里的渐进分数分子分母要分开numerator, denominator = denominator, x * denominator + numeratorreturn numerator, denominator
def solve_pq(a, b, c):"""使用韦达定理解出pq，x^2−(p+q)∗x+pq=0:param a:x^2的系数:param b:x的系数:param c:pq:return:p，q"""par = gmpy2.isqrt(b * b - 4 * a * c)return (-b + par) // (2 * a), (-b - par) // (2 * a)
def getGradualFra(cf):"""计算列表所有的渐近分数:param cf: 连分数列表:return: 该列表所有的渐近分数"""gf = []for i in range(1, len(cf) + 1):gf.append(gradualFra(cf[:i]))return gfdef wienerAttack(e, n):""":param e::param n::return: 私钥d"""cf = continuedFra(e, n)gf = getGradualFra(cf)for q2,q1 in gf: # 不得不说最后要倒一下呀！if q1 == 0: continueif N2 % q2 == 0 and q2 != 1:# 此处也可写成 N1 % q1 == 0 and q1 != 1（所以说要对原理清楚以及清楚求出的到底是哪个参数）return q2N1=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c1=55094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N2=60143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c2=39328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2=125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393
Q2=wienerAttack(N1,N2)
Q1 = sympy.prevprime(Q2)
P1 = gmpy2.iroot(N1 // Q1,2)[0]
P2 = sympy.nextprime(P1)
phi1 = P1 * (P1 - 1) * (Q1 - 1)
phi2 = P2 * (P2 - 1) * (Q2 - 1)
d1 = gmpy2.invert(E1,phi1)
d2 = gmpy2.invert(E2,phi2)
m1 = pow(c1,d1,N1)
m2 = pow(c2,d2,N2)
print(long_to_bytes(m1))
print(long_to_bytes(m2))# b'GWHT{3aadab41754799'
# b'f978669d53e64a3aca}'

收获与体会：

• e 很大时想到维纳攻击
• 任何比例非常接近另外一个已知比例情况下想到维纳攻击

这是第二次学习维纳攻击，第一次就看了个大概过程，但看完第二遍才发现第一次学习时貌似啥也没学到，仅仅只是草草了事，代码也是不求甚解，只求能解当时遇到的题就行。第二遍学习中，看得比较仔细，不懂的也会及时查找资料，比如渐近分数概念，比如不懂为什么d是分子便会借助稿纸推导。
所以说，欠下的债终究是要还的！
所以说，不能只为解题而解题，理解题目背后的原理并且举一反三才是我们的最终目标！

参考：[羊城杯 2020]RRRRRRRSA 题解（wiener attack运用）