2022BUUCTF新生赛-RSA

题目源码

from Crypto.Util.number import *
import gmpy2

m = bytes_to_long(flag)
p = getPrime(512)
q = getPrime(512)
n = p * p * q
e = 0x10001
d = inverse(e, p * (p-1) * (q-1))
assert m < n
c = pow(m, e, n)
hint = pow(d, e, n)
print(f'c = {c}')
print(f'hint = {hint}')
print(f'n = {n}')
#c = 295390424904695335160238045484482823778874523176268561514416832384667341911461624807479360352155340771798064104910086195729675369023485015714514440154903376061747094964841316582559859939271083212458383263813162552258150862316694340739316654325015871916752667846321388549685578217102034863664378037876690856340358410405404601972377258035410485778168718251025950362254734939336524237028597772764421048442121802994478847811235518434239824115849516645106981074204342
#hint = 381689393821386814936953643422859595359427105930487728052490073810065861656721298489533943537291889430179955685768552743683931382858386278229412048061640902207419922278984960983464060741314251570306423515751064678573919676919458734440112312205062810416467534525851481716577433432802746104452081670842385746300503903217917867773267569384218933894515975838815295351900841003897643955266573211223356519224254883905741607839206824725522319870208594077622555096443077
#n = 1330047950007581682981905423145560321016033324862143764072994099149659943994269827526733343998097272206411640734177032076844564188190644548214106206913310385320478977860962140014336074250277764844699709526956803401392604949854612016074894825128737598849968249437120905834713554348840283463250157701334045079523107114507765969484185723955713386597151991074970735613177368468450679646585239506590480790958808030534070060413924423517044064816910208776798401702408317

题目分析

发现n和phin都不常规，没入手点，发现hint，hint=pow(d,e,n)，有趣，用d做明文，尝试推理一下： d = pow(hint,d,n) d = pow((d ** e % n),d,n) d = (d ** e % n) ** d % n d = d ** (e*d) % n d = pow(d e,d,n) 把d e再次看做密文，可得 d e = pow(d,e,n) 因为hint = pow(d,e,n) 可得hint = d e d e * e e->(ed) e->(ed) e == 1 mod phin 因此根据e和hint即可求得phin 从而得到phin和n的最大公约数p 脚本如下

from Crypto.Util.number import *
import gmpy2
import math
e = 0x10001
c = 295390424904695335160238045484482823778874523176268561514416832384667341911461624807479360352155340771798064104910086195729675369023485015714514440154903376061747094964841316582559859939271083212458383263813162552258150862316694340739316654325015871916752667846321388549685578217102034863664378037876690856340358410405404601972377258035410485778168718251025950362254734939336524237028597772764421048442121802994478847811235518434239824115849516645106981074204342
hint = 381689393821386814936953643422859595359427105930487728052490073810065861656721298489533943537291889430179955685768552743683931382858386278229412048061640902207419922278984960983464060741314251570306423515751064678573919676919458734440112312205062810416467534525851481716577433432802746104452081670842385746300503903217917867773267569384218933894515975838815295351900841003897643955266573211223356519224254883905741607839206824725522319870208594077622555096443077
n = 1330047950007581682981905423145560321016033324862143764072994099149659943994269827526733343998097272206411640734177032076844564188190644548214106206913310385320478977860962140014336074250277764844699709526956803401392604949854612016074894825128737598849968249437120905834713554348840283463250157701334045079523107114507765969484185723955713386597151991074970735613177368468450679646585239506590480790958808030534070060413924423517044064816910208776798401702408317
p=math.gcd((hint*pow(e,e) -1),n)
q=n//(p**2)
phi=p*(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,n)
print(long_to_bytes(m))
#flag{43075d24-77a7-4f57-ae89-54fe4f96db69}