RSA by example

rsa.py

from random import randint

#----Step 1    
# First, choose two random primes. 
# In real world, they should be really big primes (hundreds of digits).

p, q = 41, 47

#----Step 2
# From them we have n=p*q and phi(n)=(p-1)*(q-1).
#
# phi(n) is Euler's totient function. It counts how many numbers <= n that have
# no common factors with n (coprimes). For prime numbers, phi(p) = p-1.

n = p*q
phi = (p-1)*(q-1)

#----Step 3
# Choose some random number "e" between 1 and phi(n) exclusive.
# "e" must be coprime with phi(n).
#
# You can check if e and phi(n) are coprimes using GCD(e, phi(n)) == 1.

def gcd(a, b):
    return gcd(b, a%b) if b else a

e = 42
while gcd(e, phi) != 1:
    e = randint(2, phi-1)

#----Step 4
# Find d, such that (d*e)%phi == 1. That is, d*e - k*phi == 1.
# You can solve this equation by using Euclid's algorithm.
#
# euclid(a, b) finds smallest positive y such that a*x + b*y == 1

def euclid(a,b):
    return (1-a*euclid(b, a%b))/b%a if b else 0

d = euclid(phi, e)

#----Step 5
# Having the public (n,e) and private (n,d) keys, you can define:
# encrypt(x) = x**e % n
# decrypt(x) = x**d % n

print 'Public key:', (n,e)
print 'Private key:', (n,d)

message = 'some secret message'

plain = [ord(x) for x in message]
encrypted = [pow(x, e, n) for x in plain]
plain_again = [pow(x, d, n) for x in encrypted]

print 'Plain:', plain
print 'Encrypted:', encrypted
print 'Plain:', plain_again  

"""
Epilogue

RSA is based on the fact that multiplying p by q is easy, but factoring n 
is hard. The relation between the public (e) and the private (d) exponents is 
given by phi(n) that can only be calculated if you know p and q.

The correctness of the algorithm can be proven by Fermat's little theorem.
It states, among other things, that if e*d % phi(n) == 1 then a**(e*d) % n == a

What we do in RSA is exactly this: a**e%n to encrypt and a**d%n to decrypt.

Plain RSA as explained here is not actually secure. It should be combined 
with some padding scheme to be made useful in real software.
"""