## {{{ http://code.activestate.com/recipes/572196/ (r2)
#!/usr/bin/python
# -*- coding: utf-8 -*-
"""\
The author takes no responsibility for anything having anything to do
with this code. Use at your own risk, or don't use at all.

This is a Python implementation functions used in the RSA algorithm, as
well as a file-like object for writing encrypted files that it can later
read using the same password. This is useful for if you want store
sensitive data to a file with a user-given password.

The RSA keys are obtained as follows:
1. Choose two prime numbers p and q
2. Compute n=pq
3. Compute φ(n)=totient(p,q)
4. Choose e coprime to φ(n) such that gcd(e,n)=1
5. Compute d=modInverse(e,φ(n))
6. e is the publickey; n is also made public; d is the privatekey

Encryption is as follows:
1. Size of data to be encrypted must be less than n
2. ciphertext=pow(plaintext,publickey,n)

Decryption is as follows:
1. Size of data to be encrypted must be less than n
2. plaintext=pow(ciphertext,privatekey,n)
"""

import random,md5

def RabinMillerWitness(test,possible):
	#calculates (a**b)%n via binary exponentiation, yielding itermediate
	#results as Rabin-Miller requires
	#written by Josiah Carlson
	#modified and optimized by Collin Stocks
	a,b,n=long(test%possible),possible-1,possible
	if a==1:
		return False
	A=a
	t=1L
	while t<=b:
		t<<=1
	#t=2**k, and t>b
	t>>=2
	while t:
		A=pow(A,2,n)
		if t&b:
			A=(A*a)%n
		if A==1:
			return False
		t>>=1
	return True

smallprimes = (3,5,7,11,13,17,19,23,29,31,37,41,43,
				47,53,59,61,67,71,73,79,83,89,97)

def getPrime(b,seed):
	#Generates an integer of b bits that is probably prime
	#written by Josiah Carlson
	#modified (heavily) and optimized by Collin Stocks
	bits=int(b)
	assert 64<=bits
	k=bits<<1
	possible=seed|1 # make it odd
	good=0
	while not good:
		possible+=2 # keep it odd
		good=1
		for i in smallprimes:
			if possible%i==0:
				good=0
				break
		else:
			for i in xrange(k):
				test=random.randrange(2,possible)|1
				if RabinMillerWitness(test,possible):
					good=0
					break
	return possible

def egcd(a,b):
	# Extended Euclidean Algorithm
	# returns x, y, gcd(a,b) such that ax + by = gcd(a,b)
	u, u1 = 1, 0
	v, v1 = 0, 1
	while b:
		q = a // b
		u, u1 = u1, u - q * u1
		v, v1 = v1, v - q * v1
		a, b = b, a - q * b
	return u, v, a

def gcd(a,b):
	# 2.8 times faster than egcd(a,b)[2]
	a,b=(b,a) if a