Welcome, guest | Sign In | My Account | Store | Cart

This is my Python implementation of the RSA algorithm, including functions to generate prime numbers from a password string. It also includes a file-like object for automating encryption.

I wrote this code a long time ago. My coding style has improved since then. I would never write a program like this nowadays. This was written as a demo, and should be treated as such.

Python, 258 lines
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
#!/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: "))

One might want to use this to store passwords securely. However, there are some bugs in the code, so do your own debugging before using for anything important.

I would suggest looking at http://pypi.python.org/pypi/rsa instead.

2 comments

Bogdan Frankovskyi 15 years, 9 months ago  # | flag

Thank you.

Collin Stocks (author) 15 years, 6 months ago  # | flag

By the way, this implementation is that of "vanilla" RSA, meaning that it is purely the mathematical definition of RSA. There is no attempt to increase security by using an xor cipher with random data and then encrypting the key. Thus, as said before, this should only be used as a platform for building your own RSA implementation, as it provides no real security on its own. That said, it is a very complete platform, with some bugs.

I have no idea how I found the time to write this when I did.

Created by Collin Stocks on Sun, 11 May 2008 (PSF)
Python recipes (4591)
Collin Stocks's recipes (4)

Required Modules

  • (none specified)

Other Information and Tasks