ctfのお勉強 ksnctf #16 Math1

ksnctfを解いてみた

ksnctf

#16 Math1

RSA暗号pythonでコード書けば終了する。

def gcd(a, b):
    if b == 0:
        u = 1
        v = 0
    else:
        q = a / b
        r = a % b
        (u0, v0) = gcd(b, r)
        u = v0
        v = u0 - q * v0
    return (u, v)

if __name__ == '__main__':
    p = 34111525225922333955113751419357677129436029651245533697825114748126342624744832960936498161825269430327019858323450578875242014583535842110912370431931233957939950911741013017595\
9774719497672354264908502842866615923577798252122650559317057999169138176557434344974229934989313946188327413362474268157101643425991509906081436373310682202445255417948556516431350128460\
3943935510102799494512069853017732982921320876105739223687536645819709850725285124413245599646862895756017886872431000031701191299463232837176148666935806557726919806579298153737844832492\
3622959249447066754504943097391628716371245206444816309511381323;

    q = 44481453884385518268018625442920628989497457642625668259648790876723318635861137128631112417617317160816537010595885992856520476731882382742220627466006460645416066646852266992087\
3868554911527952371539013195215064298734343369696665369953998661257810577680755335601203991845669564331298549954648932654037240349606899383514507099506997405084592067850936932775417852856\
9973387353054191848384212269127632228681042229701578265864512942104316074904084621689267103115646536465268103682846161927242731875809853892772739245950176120384236301712143265753477089818\
1975532066012149902177196510416802134121754859407938165610800223;
    e = 65537;
    l = (p-1)*(q-1);
    n = 15173302362629175953146108888893221156510870808267119488970663408832082055715923923626508585710762479398054362265448332245261375828347704026810053439300594636845289572717781991625\
7505330623809982329511769703196837069037225091693580073869814210327596922326418437464824627756430690088600529973126581225527472317592518552234483106657716686778683595509205934624488558722\
8196357297758371381557924676260190209536670230008561217008649261974735505203813478978893582292682827884118215872470401293272325715864815977064075988643101088355047954735427424641386870772\
8454407826329334851651101724375118227369075507778177222487536711073398234104189384043827320793813292884000129293113473904230612546587801852455626681310098322934749202088347954600611151013\
6409125217659414409667589995257038079297803721774731159589930145119234202779953326432594887655611047485076153817974831818780531245189589875133797545794954949766654217507789498769708552188\
2531938339334715190663665300179658557458036053188152532948734992896239950564081581184284728802682982779186068791931259198917308153082917381616147108543673346682338045309449569430550618884\
202465809290850964525390539782080230737593560891353558335337408957948041667929154230334506735825418239563481028126435029

x=2255495926284926161526322654821253158689111256599710859297122963662143556080492241793397576379825415427450108220222264091261236278049530640720556670121726815515007807634831729143898\
1305744466931472640413597856544628230901972999497681592585091648725769970747820613247471096375259039933292067260744079311638705107119191983531684582783828795454155877735586471478246429927\
8036910958484272003656702623646042688124964364376687297742060363382322519436200343894901785951095760714894439233966409337996138592489997024933882003852590408577812535049335652212448474376\
4570150770475298183158775496148595864755040700512010547049546540934820564930929307007878905793460659168344347399807914022161755550758960666165191501648319906267275918761158212199412683096\
7824087229802961174657537632273331165739450285985221359538960723943158512094326877467978531613347817122571972991787700962461128670201093695170516087099718412377548859213058660607027717339\
2647225589257616518666852404878425355285270687131724258281902727717116041282358028398978152480549468694659695121115046850718180640407034795656480263573773381753855724693739080045739160297\
875306923958599742379878734638341856117533253251168244471273520476474579680250862738227337561115160603373096699944163

    d = gcd(e,l)
    if d < 0:
        d += l
    print("d={0}".format(d));
    #m = cd(mod n)                                                                                                                                                                              
    m=pow(x,d,n)
    print ("%0512x"%m).decode("hex")