RSA

Extended Euclidean Algorithm

Example 1 (To find d)

ctfdump/Radio Station Apocalypse.md at master · IRS-Cybersec/ctfdumpGitHub

#save as script.sage
# run => sage script.sage

from Crypto.Util.number import long_to_bytes

#n=pq
n=25368447768323504911600571988774494107818159082103458909402378375896888147122503938518591402940401613482043710928629612450119548224453500663121617535722112844472859040198762641907836363229969155712075958868854330020410559684508712810222293531147857306199021834554435068975911739307607540505629883798642466233546635096780559373979170475222394473493457660803818950607714830510840577490628849303933022437114380092662378432401109413796410640006146844170094240232072224662551989418393330140325743682017287713705780111627575953826016488999945470058220771848171583260999599619753854835899967952821690531655365651736970047327

e=65537

c=15927954374690152068700390298074593196253864077169207071831999310211243220084198633824761313226756137217716813832139827281860280786151119392571330914043785795154126460993477079312886238477507766509831010644388998659565303441719615131661670116956449101956505931748018171190878765731317846254607404813297135537090043417404895660853320127812799010027005785901634939020872408881201149711968120809368691413105318444873712717786940780346214959475833457688794871749017822337860503424073668090333543027469770960756536095503271163592383252371337847620140632398753943463160733918860277382675572411402618882039992721158705125550

#p-q
p_q=13850705243110859039354321081017038361100285164728565071420492338985283998938739255457649493117185659009054998475484599174052182163568940357425209817392780314915968465598416149706099257132486744034100104272832634714470968608095808094711578599330447351992808756520378741868674695777659183569180981300608614286

ppq=sqrt((p_q)^2+4*n)
print(ppq==int(ppq))
totient=n-int(ppq)+1
d=inverse_mod(e,totient)

print(long_to_bytes(c.powermod(d,number)))

Formula

References

factordb.com