Simple RSA impl (revisited)

gistfile1.py

def gcd(a,b):
    if b==0: return (1, 0)
    q = a/b
    x,y = gcd(b, a-q*b)
    return (y, x-q*y)
    
def inverse(a, b):
    x,y = gcd(a,b)
    return (x if x > 0 else x+b)
   
p,q = 41, 47              #primes             
n,phi = p*q, (p-1)*(q-1)  #modulus and totient
e,d = 7, inverse(7,phi)   #public and private exponents

plain = 42
ciphered = pow(plain, e, n)
plain_again = pow(ciphered, d, n)

print 'Public key:', (n,e)
print 'Private key:', (n,d)
print 'Message:', plain, '->', ciphered, '->', plain_again