RSA Decipher String using Fast Exponentiation Algorithms Quick Example Get link Facebook X Pinterest Email Other Apps flag{rivest_and_the_cool_gang_would_be_proud} 250 points writeup - (Zeromutarts.de 2013) useful links to study: http://www.programminglogic.com/fast-exponentiation-algorithms/ http://stackoverflow.com/questions/4078902/cracking-short-rsa-keys RSA Decipher String using Fast Exponentiation Algorithms Quick Example #!/usr/bin/env python ## using SAGE RSA n = 80646413 p = floor(sqrt(80646413)) ### Finding Factor p*q = n while(true): if (n%p == 0): print p break p=p+1 q = n / p print q #### phi(n) n1 = (p-1) * (q-1) print n1 e =5 d = e^-1 % n1 print d ### got private key ### Fast Exponentiation Algorithms def expo(c,d,n): if (d==1): return c%n if (d==2): return c*c % n if (d%2==0): return expo(expo(c,d/2,n),2,n) else: return c*expo(expo(c,(d-1)/2,n),2,n) cipher = [72895864,15633602,38820479,60303684,7458706,60299530,20682371,54642689,26066811,32615038,35349196,76400140,38820479,56463813,80491201,76400140,35349196,69567074,26066811,76400140,74270178,76127647,76127647,15633602,76400140,60303684,38820479,56463813,60303684,76400140,72844764,76127647,69302434,15633602,80491201,76400140,6809712,26066811,76400140,42498798,60299530,76127647,69302434,80491201,33234011] flag = '' for c in cipher: flag = flag+ chr(expo(c,d,n)%n) print flag Comments
Comments
Post a Comment