Python implementation of RSA (also uses Huffman compression and the Miller-Rabin test for primality).

crypto.py

import random, operator

class Person:
    def __init__(self):
        #From my testing so far, using primes in the range of 10e200 takes about 2 seconds for 2 people and 10e300 takes about 5 seconds.
        self.p1 = random_prime(10e200,10e201)
        self.p2 = random_prime(10e200,10e201)
        self.n = self.p1 * self.p2
        self.phi = (self.p1-1)*(self.p2-1)
        self.e = random_prime(10, 100)
        while self.phi % self.e == 0:
            self.e = random_prime(10, 100)
        self.k=1
        while True:
            if (self.k*self.phi+1)%self.e == 0:
                self.d = (self.k*self.phi+1)/self.e
                break
            #Just in case
            if self.k > self.e:
                print(self.phi)
                print(self.e)
                break
            self.k+=1

    def RSA_encrypt(self, receiver, message):
        #TODO: if message > receiver.n, break the message up into parts
        m, k = huffman_compress(message)
        c = pow(m, receiver.e, receiver.n)
        return c, k

    def RSA_decrypt(self, cypher, huffman_key):
        m = pow(cypher, self.d, self.n)
        m = huffman_decompress(m, huffman_key)
        return m


def huffman_compress(message, out='dec'):
    #Used to efficiently compress a message into a relatively small number
    chars = list(message)
    freqs = {}
    for c in chars:
        try:
            freqs[c]+=1
        except:
            freqs[c]=1
    tree = sorted(freqs.iteritems(), key=operator.itemgetter(1))
    
    def cumulative_freq(tree, total=0):
        if type(tree[1]) == type(2):
            return tree[1]
        else:
            total += cumulative_freq(tree[0], total)
            total += cumulative_freq(tree[1], total)
        return total

    while len(tree) > 2:
        tree.append([tree[0], tree[1]])
        tree = tree[2:]
        tree = sorted(tree, key = cumulative_freq)
    
    def create_codes(tree, code_builder, codes):
        if type(tree[1]) == type(2):
            codes[tree[0]] = code_builder
            return codes
        else:
            codes = create_codes(tree[0], code_builder + '0', codes)
            codes = create_codes(tree[1], code_builder + '1', codes)
            return codes
    
    codes = create_codes(tree, '', {})
    key = {v:k for k, v in codes.items()}
    binary = map(lambda x: codes[x], chars)
    num = int(''.join(binary),2)
    if out == 'dec':
        return num, key
    if out == 'bin':
        return binary
    if out == 'eff':
        return float(len(''.join(binary)))/(8*len(message))

def huffman_decompress(message, key):
    binary =  str(bin(message))[2:]
    m = ''
    start = 0
    while start < len(binary):
        for end in range(start+1, len(binary)+1):
            try:
                m+=key[binary[start:end]]
                start=end
                break
            except:
                pass
    return m

def random_prime(low, high):
    r = random.randint(low, high)
    if r%2 == 0:
        r+=1
    while True:
        if miller_rabin(r) == True:
            break
        r+=2
    return r

def miller_rabin(n, k = 100):
    #The default of 100 run-throughs means that a number verified as prime will be composite 6.2e-59 % of 
    #the time (and that is not even counting the preliminary check).
    if n > 31:
        if n%3==0 or n%5==0 or n%7==0 or n%11==0 or n%13==0 or n%17==0 or n%19==0 or n%23==0 or n%29==0 or n%31==0:
            return False
    d=n-1
    s=0
    while d%2 == 0:
        d/=2
        s+=1
    for i in range(k):
        a = random.randint(2,n-1)
        x = pow(a, d, n)
        if x == 1 or x == n-1:
            continue
        possiblyprime = False
        for j in range(s-1):
            x = (x**2)%n
            if x == 1:
                return False
            if x == n - 1:
                possiblyprime = True
                break
        if possiblyprime == False:
            return False
    return True


if __name__ == '__main__':
    P1 = Person()
    P2 = Person()
    c, k = P1.RSA_encrypt(P2, 'Let\'s see if I can transmit this message.')
    m = P2.RSA_decrypt(c, k)
    print(m)