RSA Decipher using Fast Exponentiation Algorithms Example - 250 writeup - (Zeromutarts.de 2013)

RSA-Decipher.py

#!/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