"""
Why calculators aren't as fun (unless yours has a bigger than
usual screen maybe?):

RSA-640

RSA-640 has 193 decimal digits. A cash prize of US$20,000 was
offered by RSA Security for a successful factorization.
On November 2, 2005, F. Bahr, M. Boehm, J. Franke and T. Kleinjung
of the German Federal Office for Information Security announced
that they had factorized the number using GNFS as follows:
[19][20][21]

RSA-640 = 31074182404900437213507500358885679300373460228427275457
          20161948823206440518081504556346829671723286782437916272
          83803341547107310850191954852900733772482278352574238645
          4014691736602477652346609

RSA-640 = 16347336458092538484431338838650908598417836700330923121
          81110852389333100104508151212118167511579
        × 19008712816648221131268515739354139754718967899685154936
          66638539088027103802104498957191261465571

The computation took 5 months on 80 2.2 GHz AMD Opteron CPUs.

The slightly larger RSA-200 was factored in May 2005 by the same team.

See:
http://en.wikipedia.org/wiki/RSA-640#RSA-640
"""

N = int("31074182404900437213507500358885679300373460228427275457" +\
         "20161948823206440518081504556346829671723286782437916272" +\
         "83803341547107310850191954852900733772482278352574238645" +\
         "4014691736602477652346609")

p = int("16347336458092538484431338838650908598417836700330923121"+\
        "81110852389333100104508151212118167511579")

q = int("19008712816648221131268515739354139754718967899685154936"+\
        "66638539088027103802104498957191261465571")

totient = (p - 1) * (q - 1)

"""
These guys only work in a namespace with N, d already defined

We're setting e = 7 to keep it simple

Euler's Totient Theorem

This theorem is one of the important keys to the RSA algorithm:

    If GCD(T, R)== 1 and T < R, then pow (T, phi(R), R) == 1 

Or, in words:

    If T and R are relatively prime, with T being the smaller
    number, then when we multiply T with itself phi(R) times
    and divide the result by R, the remainder will always be 1. 

"""
from binascii import hexlify, unhexlify

def mknum(phrase):
    return eval('0x'+hexlify(phrase)+'L')

def mkphrase(num):
    return unhexlify(hex(num)[2:-1])

def gcd(a,b):
    """Return greatest common divisor using Euclid's Algorithm."""
    while b:      
        a, b = b, a % b
    return a

def lcm(a,b):
    """
    Return lowest common multiple."""
    return (a*b)/gcd(a,b)

def bingcd(a,b):
    """Extended version of Euclid's Algorithm (binary GCD)
    Returns (m,n,gcd) such that  m*a + n*b = gcd(a,b)"""
    g,u,v = [b,a],[1,0],[0,1]
    while g[1]<>0:
        y = g[0]/g[1]
        g[0],g[1] = g[1],g[0]%g[1]
        u[0],u[1] = u[1],u[0] - y*u[1]
        v[0],v[1] = v[1],v[0] - y*v[1]
    m = v[0]%b
    gcd = (m*a)%b
    n = (gcd - m*a)/b
    return (m,n,gcd)

def inverse(a,b):
    """If gcd(a,b)=1, then inverse(a,b)*a mod b = 1,
    otherwise, if gcd(a,b)!=1, return 0

    Useful in RSA encryption, for finding d such that
    e*d mod totient(n) = 1"""
    inva,n,gcd = bingcd(a,b)
    return (gcd==1)*inva

class Sender:

    def __init__(self, m):
        self.m = mknum(m)

    def encrypt(self):
        """RSA algorithm"""
        c = pow(self.m, 7, N)
        return c

class Receiver:

    def __init__(self, c):
        self.c = c

    def decrypt(self):
        """RSA algorithm"""
        d = inverse(7, totient)
        m = pow(self.c, d, N)
        return mkphrase(m)

def testing123():
    print(p)
    print(q)
    print(p*q)
    print(N)
    print(N == p*q)
    d = inverse(7, totient)
    print(d)
    print(7*d % totient)    

def testingrsa():
    bob = Sender("Able was I ere I saw Elba")
    c = bob.encrypt()
    alice = Receiver(c)
    m = alice.decrypt()
    print(m)
    
if __name__ == "__main__":
    # testing123()
    testingrsa()