Python example of implementation of RSA encryption.

RSA_encryption.py

#!/usr/bin/python
from random import choice
# from fractions import gcd #this is slower than the implementation below!!

def gcd(a, b):
    while b != 0:
        a, b = b, a%b
    return a

def coprime(a, b):
  return gcd(a, b) == 1

def generateEncryption(p1,p2):
    totient = (p1-1) * (p2-1)

    possiblePublicKeys = [i for i in range(2,totient) if coprime(i,totient)]
    publicKey = choice(possiblePublicKeys)
    
    for privateKeyCandidate in range(2,totient):
        if publicKey*privateKeyCandidate % totient == 1:
            return (p1*p2, publicKey, privateKeyCandidate)

def xcrypt(m, key, modulus):
    if m >= modulus:
        raise Exception('The message should not be equal to or greater than the modulus!')
    return m**key % modulus

p1, p2 = 101, 103 #Should generally be much much greater
(modulus, publicKey, privateKey) = generateEncryption(p1, p2)

message = 5515
encrypted = xcrypt(message, publicKey, modulus)
decrypted = xcrypt(encrypted, privateKey, modulus)

print "primes:", p1, p2
print "publicKey:", publicKey
print "privateKey:", privateKey
print "message:", message
print "encrypted message:", encrypted
print "then decrypted:", decrypted

example output:

primes: 101 103
publicKey: 9497
privateKey: 8633
message: 5515
encrypted message: 3033
then decrypted: 5515