rsa_worked_example.py

# http://en.wikipedia.org/wiki/RSA_(algorithm)

p = 61
q = 53
n = p*q
totient = (p-1)*(q-1)

# here, e is 2^4 + 1; in real world applications, e is often 2^16 + 1
e = 17


# http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
# algorithm runs in O( (log n)^2 ) time
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


# http://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return None  # modular inverse does not exist
    else:
        return x % m

# note that `d` cannot be calculated efficiently unless you know the totient, which requires knowing the prime factorization
d = modinv(e, totient)

public_key = (n, e)
private_key = (n, d)
# note that in practice, private_keys are stored along with two other pieces of information:
# d_p = d % (p-1)
# d_q = d % (q-1)
# these intermediate values allow the inverse to be calculated quickly using an
# algorithm based on the chinese remainder theorem.

# note that neither key includes p, q, or the totient

# example of enciphering and deciphering a message
message = 65L
cipher = (message ** e ) % n
recovered_message = (cipher ** d ) % n

message == recovered_message