RSA算法的python实现

2018年08月29日 编程语言 ⁄ 共 5609字 ⁄ 字号 评论关闭
`来源：http://code.activestate.com/recipes/572196-rsa/`
```## {{{ 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)

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

assert 64<=bits
assert bits%4==0
length=bits//4
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)
# don't worry about removing these later: crypt() ignores
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.
# 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.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=""
if bytes==None:
ret=self.rbuf
self.rbuf=""
else:
_bytes=bytes-len(self.rbuf)
rbytes=_bytes+(self.bits-_bytes%self.bits)
ret=self.rbuf[:bytes]
self.rbuf=self.rbuf[bytes:]
return ret
ret=""
while not ret.endswith('\n'):
ln=len(ret)
if len(ret)==ln:
break
return ret
ret=[]
while ret[-1]:
return ret[:-1]
def next(self):
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)