CTFshow-Crypto(26-29)

26easyrsa6

分解n/费马分解

1. import gmpy2,libnum
2. from Crypto.Util.number import getPrime
4. e = 0x10001
5. p = getPrime(1024)
6. q = gmpy2.next_prime(p)
7. n = p * q
8. print("n =",n)
9. m = libnum.s2n(flag)
10. c = pow(m,e,n)
11. print("c =", c)
13. # n = 26737417831000820542131903300607349805884383394154602685589253691058592906354935906805134188533804962897170211026684453428204518730064406526279112572388086653330354347467824800159214965211971007509161988095657918569122896402683130342348264873834798355125176339737540844380018932257326719850776549178097196650971801959829891897782953799819540258181186971887122329746532348310216818846497644520553218363336194855498009339838369114649453618101321999347367800581959933596734457081762378746706371599215668686459906553007018812297658015353803626409606707460210905216362646940355737679889912399014237502529373804288304270563
14. # c = 18343406988553647441155363755415469675162952205929092244387144604220598930987120971635625205531679665588524624774972379282080365368504475385813836796957675346369136362299791881988434459126442243685599469468046961707420163849755187402196540739689823324440860766040276525600017446640429559755587590377841083082073283783044180553080312093936655426279610008234238497453986740658015049273023492032325305925499263982266317509342604959809805578180715819784421086649380350482836529047761222588878122181300629226379468397199620669975860711741390226214613560571952382040172091951384219283820044879575505273602318856695503917257

复制代码

看到e=0x10001
16进制转为10进制是65537

分解nhttp://www.factordb.com/

我们注意到

1. p = getPrime(1024)
2. q = gmpy2.next_prime(p)

复制代码

p q相差太小 所以 n=p*q ≈p²，费马分解

1. p = gmpy2.next_prime(gmpy2.iroot(n,2)[0])
2. q = n//p

复制代码

脚本

1. import gmpy2,libnum
2. from Crypto.Util.number import *
4. \# e = 0x10001
5. \# p = getPrime(1024)
6. \# q = gmpy2.next_prime(p)
7. \# n = p * q
8. \# print("n =",n)
9. \# m = libnum.s2n(flag)
10. \# c = pow(m,e,n)
11. \# print("c =", c)
13. n = 26737417831000820542131903300607349805884383394154602685589253691058592906354935906805134188533804962897170211026684453428204518730064406526279112572388086653330354347467824800159214965211971007509161988095657918569122896402683130342348264873834798355125176339737540844380018932257326719850776549178097196650971801959829891897782953799819540258181186971887122329746532348310216818846497644520553218363336194855498009339838369114649453618101321999347367800581959933596734457081762378746706371599215668686459906553007018812297658015353803626409606707460210905216362646940355737679889912399014237502529373804288304270563
14. c = 18343406988553647441155363755415469675162952205929092244387144604220598930987120971635625205531679665588524624774972379282080365368504475385813836796957675346369136362299791881988434459126442243685599469468046961707420163849755187402196540739689823324440860766040276525600017446640429559755587590377841083082073283783044180553080312093936655426279610008234238497453986740658015049273023492032325305925499263982266317509342604959809805578180715819784421086649380350482836529047761222588878122181300629226379468397199620669975860711741390226214613560571952382040172091951384219283820044879575505273602318856695503917257
15. p = 163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385163
16. q = 163515803000813412334620775647541652549604895368507102613553057136855632963322853570924931001138446030409251690646645635800254129997200577719209532684847732809399187385176309169421205833279943214621695444496660249881675974141488357432373412184140130503562295159152949524373214358417567189638680209172147385801
17. e = 65537
18. phi = (p-1)*(q-1)
19. d = gmpy2.invert(e,phi)
20. m = pow(c,d,n)
21. print(long_to_bytes(m))

复制代码

工具（风二西）

27easyrsa7

CopperSmith攻击 低位数据缺失-知p高位

RSA中coppersmith定理的应用条件_sagemath coppersmith-CSDN博客
[code]e = 0x10001p>>128 和  1 右移一位 相当于 /2</p>
这里 “p>>128