#!/usr/bin/env python

# Extended Euclidean Algorithm from Wikibooks.  Finds the
# gcd of the integer inputs.
#
#   a, b - integer inputs
#
# Returns b, x, y such that b is the gcd and b = a*x + b*y
#
def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
    return b, x, y

# Modular inverse from Wikibooks.  Given a and m, determines
# the inverse of a mod m.
#
#   a - integer to find the inverse of
#   m - modulus
#
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

if __name__ == "__main__":

    print "This program demonstrates the computations in RSA with a small example.\n"

    p = 16777213
    q = 16777259
    N = p*q
    e = 65537

    print "The prime moduli are:\n"
    print "   p = " + str(p)
    print "   q = " + str(q) + "\n"
    print "p and q must be kept secret.\n"

    print "The public modulus N = p*q is:\n"
    print "   N = " + str(N) + "\n"
    print "The public encryption exponent e is:\n"
    print "   e = " + str(e) + "\n"
    print "The pair (N, e) form the public key.\n"

    tmp = raw_input("--pause--")
    print ""

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

    print "The value phi(N) = (p-1)*(q-1) is:\n"
    print "   phi(N) = " + str(phiN) + "\n"
    print "phi(N) must also be kept secret.  Knowing phi(N) is equivalent to knowing"
    print "p and q.\n"

    d = egcd(e, phiN)[1]

    print "The decryption exponent d is the modular inverse of e mod phi(N).  I am"
    print "computing d using an implementation of the modular inverse function:\n"
    print "   d = modinv(e, phiN) = " + str(d) + "\n"
    print "d is the secret key.\n"

    edinv = (e*d) % phiN

    print "We an check that e and d are inverses modulo phi(N):\n"
    print "   (e*d) % phiN = " + str(edinv)
    print "\n"

    tmp = raw_input("--pause--")
    print ""

    print "Now we can encrypt a message using the public key (N, e) and decrypt it"
    print "using the private key d.\n"

    M = 'BIGDOG'

    print "The message I am encrypting is:\n"
    print "   M = " + M + "\n"
    print "The message M must first be encoded as an integer < N.  I am doing this"
    print "by packing the characters of M into an integer with the following code:\n"

    print "x = 0"
    print "for c in M:"
    print "     x = x << 8"
    print "     x = x ^ ord(c)\n"

    x = 0
    for c in M:
        x = x << 8
        x = x ^ ord(c)

    print "For the message M = " + M + ", the encoded message is:\n"
    print "   x = " + str(x) + "\n"

    tmp = raw_input("--pause--")
    print ""

    C = pow(x, e, N)

    print "To encrypt the encoded message x, I raise it to the power e mod N:\n"
    print "   C = pow(x, e, N) = " + str(C) + "\n"

    D = pow(C, d, N)

    print "To decrypt the cipher C, I raise it to the power d mod N:\n"
    print "   D = pow(C, d, N) = " + str(D) + "\n"

    print "As you can see, D is just the original encoded message x:\n"
    print "   D = " + str(D)
    print "   x = " + str(x) + "\n"

    tmp = raw_input("--pause--")
    print ""

    M1 = ""
    while D > 0:
        M1 = chr(D & 0xff) + M1
        D = D >> 8

    print "I can decode D to get the original mesage back:\n"
    print "M1 = ''"
    print "while D > 0:"
    print "     M1 = chr(D & 0xff) + M1"
    print "     D = D >> 8\n"
    print "The resulting decoded message is:\n"
    print "   M1 = " + M1 + "\n"