[codefest ctf] RSA 1.0

from Crypto.Util.number import *
from secret import flag

p = getPrime(512)
q = getPrime(512)
r = getPrime(512)

m = bytes_to_long(flag)

e = 65537

c = pow(m, e, p*q*r)

print(f'n = {p*q*r}')
print(f'pq = {p*q}')
print(f'c = {c}')

 CRT로 풀린다

 

from Crypto.Util.number import inverse,long_to_bytes
n = 750663646847528873168937831391907810647591913965562495296199585082759057318274521553757550724463451891668175905206221877858317290777877060166997790624527965837837993129383290402509996587556406778482067347232022225466937668396768390983554357611376057823852179263682649072729435912583278183812954787442057976301035654942470184201720410477691326653029842426252391647509934740335989269071438620690320401576861478427178128804784352142271832603194431176323445880836139
pq = 80970512687406090889060992576336286518763523653333428346066206717567693624044162491796922556346210471950404967161997779545603412053582932354160368128117099634532601019309976159157713252768640669410333127578132624183514430252557952811102781031315190048386214745340936679285725364013916829276058253922234988379
c = 221975957171552618997196127189899209276336291387640550554967727731818563960555600691881715668156105819191779108737770660990397331961689607338541452069797368288215716485835439777459317512238532636172979397173548812054679237802827275184091619620252887678664409116710340000218841023351238456144820005968602870644031701303645229364391309952172259686888808938835775360009896210855708140351244441167461823250549764537506364091367096196182191704433664638829177854628679




r = n / pq
#print inverse(65537,r-1)
d = 8528872622026277937550303553635609937097487502827424222476157017734084188054492606869179010958997338558262439273241708142496780631708632488343298528728513
print long_to_bytes(pow(c,d,r))