百度网站建设公司,手机和pc网站,临淄信息港发布信息,做网站背景图的科技图片文章目录 维纳攻击原理#xff1a;维纳攻击脚本[羊城杯 2020]RRRRRRRSA 1题目描述#xff1a;题目分析#xff1a; 收获与体会#xff1a; 维纳攻击原理#xff1a;
两位大佬讲得非常清楚#xff08;搬运工就是我#xff09;#xff1a;https://zhuanlan.zhihu.com/p/… 文章目录 维纳攻击原理维纳攻击脚本[羊城杯 2020]RRRRRRRSA 1题目描述题目分析 收获与体会 维纳攻击原理
两位大佬讲得非常清楚搬运工就是我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): # 由pq和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: # ed1 (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)) # 求ed1 (mod φ(n))的结果也就是e关于 φ(n)的乘法逆元dreturn dprint(该方法不适用)c
n
e
d wienerAttack(e, n)
mpow(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) #p2p1
assert(P2 - P1 1000)Q1 getPrime(512)
Q2 sympy.nextprime(Q1) #q2q1N1 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()N160143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c155094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N260143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c239328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393题目分析
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):使用韦达定理解出pqx^2−(pq)∗xpq0:param a:x^2的系数:param b:x的系数:param c:pq:return:pqpar 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: 私钥dcf 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 q2N160143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868190554644983911078936369464590301246394586190666760362763580192139772729890492729488892169933099057105842090125200369295070365451134781912223048179092058016446222199742919885472867511334714233086339832790286482634562102936600597781342756061479024744312357407750731307860842457299116947352106025529309727703385914891200109853084742321655388368371397596144557614128458065859276522963419738435137978069417053712567764148183279165963454266011754149684758060746773409666706463583389316772088889398359242197165140562147489286818190852679930372669254697353483887004105934649944725189954685412228899457155711301864163839538810653626724347
c155094296873556883585060020895253176070835143350249581136609315815308788255684072804968957510292559743192424646169207794748893753882418256401223641287546922358162629295622258913168323493447075410872354874300793298956869374606043622559405978242734950156459436487837698668489891733875650048466360950142617732135781244969524095348835624828008115829566644654403962285001724209210887446203934276651265377137788183939798543755386888532680013170540716736656670269251318800501517579803401154996881233025210176293554542024052540093890387437964747460765498713092018160196637928204190194154199389276666685436565665236397481709703644555328705818892269499380797044554054118656321389474821224725533693520856047736578402581854165941599254178019515615183102894716647680969742744705218868455450832
E1125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820423103
N260143104944034567859993561862949071559877219267755259679749062284763163484947626697494729046430386559610613113754453726683312513915610558734802079868195633647431732875392121458684331843306730889424418620069322578265236351407591029338519809538995249896905137642342435659572917714183543305243715664380787797562011006398730320980994747939791561885622949912698246701769321430325902912003041678774440704056597862093530981040696872522868921139041247362592257285423948870944137019745161211585845927019259709501237550818918272189606436413992759328318871765171844153527424347985462767028135376552302463861324408178183842139330244906606776359050482977256728910278687996106152971028878653123533559760167711270265171441623056873903669918694259043580017081671349232051870716493557434517579121
c239328446140156257571484184713861319722905864197556720730852773059147902283123252767651430278357950872626778348596897711320942449693270603776870301102881405303651558719085454281142395652056217241751656631812580544180434349840236919765433122389116860827593711593732385562328255759509355298662361508611531972386995239908513273236239858854586845849686865360780290350287139092143587037396801704351692736985955152935601987758859759421886670907735120137698039900161327397951758852875291442188850946273771733011504922325622240838288097946309825051094566685479503461938502373520983684296658971700922069426788236476575236189040102848418547634290214175167767431475003216056701094275899211419979340802711684989710130215926526387138538819531199810841475218142606691152928236362534181622201347
E2125932919717342481428108392434488550259190856475011752106073050593074410065655587870702051419898088541590032209854048032649625269856337901048406066968337289491951404384300466543616578679539808215698754491076340386697518948419895268049696498272031094236309803803729823608854215226233796069683774155739820425393
Q2wienerAttack(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))# bGWHT{3aadab41754799
# bf978669d53e64a3aca}收获与体会 e 很大时想到维纳攻击任何比例非常接近另外一个已知比例情况下想到维纳攻击
这是第二次学习维纳攻击第一次就看了个大概过程但看完第二遍才发现第一次学习时貌似啥也没学到仅仅只是草草了事代码也是不求甚解只求能解当时遇到的题就行。第二遍学习中看得比较仔细不懂的也会及时查找资料比如渐近分数概念比如不懂为什么d是分子便会借助稿纸推导。 所以说欠下的债终究是要还的 所以说不能只为解题而解题理解题目背后的原理并且举一反三才是我们的最终目标
参考[羊城杯 2020]RRRRRRRSA 题解wiener attack运用
