RSA算法的python实现

## {{{ 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<b else (a,b)
	while b:
		a,b=b,a%b
	return a

def modInverse(e,n):
	# d such that de = 1 (mod n)
	# e must be coprime to n
	# this is assumed to be true
	return egcd(e,n)[0]%n

def totient(p,q):
	# Calculates the totient of pq
	return (p-1)*(q-1)

def passwordToPrimePair(pswd,bits=64):
	assert 64<=bits
	assert bits%4==0
	length=bits//4
	sep=len(pswd)//2
	append="0"*(length-sep)
	seed1=int(pswd[:sep]+append,16)
	seed2=int(pswd[sep:]+append,16)
	p=getPrime(bits,seed1)
	q=getPrime(bits,seed2)
	return p,q

def passwordToKey(password,bits=64):
	assert 64<=bits
	assert bits%4==0
	length=bits//4
	pswd=md5.new(password).hexdigest()
	p,q=passwordToPrimePair(pswd,bits)
	n=p*q
	append="0"*(length-len(pswd))
	possible=int(pswd+append,16)|1 # n is always even
							# so possible must be odd
	while not gcd(possible,n):
		possible+=2 # keep it odd
	private=possible
	public=modInverse(private,totient(p,q))
	return public,private,n

def crypt(string,power,n):
	data1=0L
	for char in string:
		data1<<=8
		data1+=ord(char)
	data2=pow(data1,power,n)
	ret=""
	while data2:
		data2,r=divmod(data2,256)
		ret=chr(r)+ret
	return ret

def encrypt(string,power,n,bits=128):
	string=string.replace('/',"/s").replace('\0',"/0") # escape \x00
				# because crypt() ignores leading zeros
	bytes=bits//8
	lst=[]
	while string:
		lst.append(string[:bytes-1]) # string must have a lesser value than
		string=string[bytes-1:] # n, so truncate and pad
	for i in range(len(lst)):
		lst[i]=crypt(lst[i],power,n)
		lst[i]='\0'*(bytes-len(lst[i]))+lst[i] # pad with zeros
			# don't worry about removing these later: crypt() ignores
			# leading zeros already, so they are always removed
	return ''.join(lst) # the length of this must be a multiple of bytes

def decrypt(string,power,n,bits=128):
	bytes=bits//8
	lst=[]
	while string:
		lst.append(string[:bytes])
		string=string[bytes:]
	for i in range(len(lst)):
		lst[i]=crypt(lst[i],power,n)
	ret=''.join(lst)
	ret=ret.replace("/0",'\0').replace("/s",'/')
	return ret

#			data=data.replace('/',"/s").replace('\0',"/0")
#			data=data.replace("/0",'\0').replace("/s",'/')

class secureFile(object):
	# Provides a file-like object for creating secure files that it can
	# later read. It takes a string as a password that it uses to generate
	# both prime numbers and the encryption key.
	def __init__(self,fileobj,password,bits=128,mode="rb"):
		# Function must be passed an open file or a file name,
		# and on operating systems where this matters, the
		# binary attribute must be set.
		# For example, open("file","rb"), not open("file","r")
		if type(fileobj)==str:
			fileobj=open(fileobj,mode)
		self.f=fileobj
		self.e,self.d,self.n=passwordToKey(password,bits//2)
		self.bits=bits
		self.rbuf=""
		self.wbuf=""
	def write(self,data):
		self.wbuf+=data
		e,n,bits,bytes=self.e,self.n,self.bits,self.bits//8
		while bytes<len(self.wbuf):
			self.f.write(encrypt(self.data[:bytes],e,n,bits))
			self.wbuf=self.wbuf[bytes:]
	def flush(self):
		self.f.write(encrypt(self.wbuf,self.e,self.n,self.bits))
		self.wbuf=""
	def read(self,bytes=None):
		if bytes==None:
			self.rbuf+=decrypt(self.f.read(),self.d,self.n,self.bits)
			ret=self.rbuf
			self.rbuf=""
		else:
			_bytes=bytes-len(self.rbuf)
			rbytes=_bytes+(self.bits-_bytes%self.bits)
			self.rbuf+=decrypt(self.f.read(rbytes),self.d,self.n,self.bits)
			ret=self.rbuf[:bytes]
			self.rbuf=self.rbuf[bytes:]
		return ret
	def readline(self):
		ret=""
		while not ret.endswith('\n'):
			ln=len(ret)
			ret+=self.read(1)
			if len(ret)==ln:
				break
		return ret
	def readlines(self):
		ret=[]
		while ret[-1]:
			ret.append(self.readline())
		return ret[:-1]
	def next(self):
		ret=self.readline()
		if len(ret)==0:
			raise StopIteration
	def __iter__(self):
		return self
	def close(self):
		self.flush()
		self.f.close()

try:
	import psyco
	psyco.bind(RabinMillerWitness)
	psyco.bind(getPrime)
	psyco.bind(egcd)
	psyco.bind(gcd)
	psyco.bind(modInverse)
	psyco.bind(totient)
	psyco.bind(passwordToPrimePair)
	psyco.bind(passwordToKey)
	psyco.bind(crypt)
	psyco.bind(encrypt)
	psyco.bind(decrypt)
	psyco.bind(secureFile)
except ImportError:
	pass

if __name__=="__main__":
	print passwordToKey(raw_input("Password: "))
## end of http://code.activestate.com/recipes/572196/ }}}