Entry
RSA Cryptosystem
Jul 5th, 2000 10:02
Nathan Wallace, Hans Nowak, Snippet 246, dj trombley
"""
Packages: crypto
"""
"""
Here is an example of how to implement an RSA cryptosystem. The
following is a usage example taken from my console, and along with
the code comments should serve as adequate documentation:
Python 1.5.2 (#0, Apr 13 1999, 10:51:12) [MSC 32 bit (Intel)] on win32
Copyright 1991-1995 Stichting Mathematisch Centrum, Amsterdam
>>> from RSA import *
>>> msg = "The quick brown fox jumped over the lazy dog."
>>> k = RSAKey(128)
>>> k.keyType()
'Private'
>>> kpriv = dumps(k)
>>> k.makePublic()
>>> k.keyType()
'Public'
>>> xmsg = k.encryptString(msg)
>>> kp = loads(kpriv)
>>> kp.decryptString(xmsg)
'The quick brown fox jumped over the lazy dog.\000'
>>>
Please be sure to read the legal notices in the code.
Also note that everything in the first section (up until the comment
"Cryptographic functions/constructs" consists of basic mathematic
routines
and is definitely safe to copy/export/whatever.
The block cipher implementation and algorithm are mine.
(code outside of the RSAKey class)
-dj
"""
#-----------------------RSA.py-------------------------
# RSA-like public key cryptosystem for python.
# 1999 dj trombley <dtrom@building.clark.net>
# You are free to use and modify this code for
# any purpose with the restriction that any modifications
# including the author's name or contact information
# must include all of the original characters of the file.
# (you are free to comment out as you see fit, or to delete
# my contact information)
####################################################################
# NOTE: This code contains software capable of producing a "strong"#
# (>128-bit) cryptosystem. It may be illegal to export it #
# out of your country, or even to merely possess it. Use of #
# this code is for informational purposes only, and is permitted #
# only with the indemnification of the author by the user of any #
# resulting liabilities. #
####################################################################
# NOTE: This code may be protected under U.S. patent law by RSA. #
# There may be significant restrictions if you want to include #
# it in any sort of distributed end product. The user is solely #
# responsible for determining said restrictions, and indemnifies #
# author from any liabilities resulting in the code's use. #
####################################################################
# DISCLAIMER: This code was entirely developed in, and exported #
# from Australia. It is merely an example of "How-To" implement #
# an RSA-like cryptosystem and is not intended for use in #
# a distributed or 'end-user' product. #
####################################################################
from whrandom import randint, choice
from math import log
from cPickle import dumps, loads
# Basic mathematic functions.
# (defined elsewhere, but this minimizes dependency)
digits = "0123456789"
# Compute a^b (mod n)
def powMod(a, b, n):
x,m,r = b,a,1L
while (x > 0L):
if (x&1 == 1):
r = r * m
m = (m * m)%n
x = x >> 1
return(r%n)
# The Euclidean algorithm
def invMod(a, n):
m,b,t,s = n,a,0L,1L
q = m/b
r = m - q * b
while (r > 0L):
z = t - q * s
if (z >= 0):
z = z%n
else:
z = n - ((0-z)%n)
t,s,m,b = s,z,b,r
q = m/b
r = m - q * b
if (b != 1):
# Non-invertable element of Z_n
return(0)
else:
return(s%n)
# Return a random long.
def randLong(dig):
l = 0L
for i in range(dig):
l = l * 10
l = l + int(choice(digits))
return(l)
# Find the bit length of a positivge long
def bitLength(n, b = 2):
c = 0
while (n > 0):
n = n/b
c = c + 1
return c
# Miller-Rabin pseudoprimality test
def MRpP(n, blen = None):
if (n&1 == 0):
return(0) # Even numbers are not prime for our purposes.
# Divide all the 2s we can out of n-1
k,m = 0,n-1
while (m&1 == 0):
m = m >> 1
k = k + 1
# Compute the digit length if it is not known.
if (blen == None):
blen = bitLength(n, 10)
# Pick a seed and start shelling
a = randLong(blen)
b = powMod(a,m,n)
if (b%n == 1):
return(1)
for i in range(k):
if (b%n == n-1):
return(1)
b = (b*b)%n
# Throw it out
return(0)
# Return a random prime of approximately 'dig' digits.
def randPrime(dig, certainty = 50):
# Pick a random odd integer.
pstr = ""
for i in range(dig):
pstr = pstr + choice(digits)
p = long(pstr)
if (p&1 == 0):
p = p + 1L
# Run a single test, and then a bunch.
found = 0
blen = bitLength(p,10)
while (found == 0):
if (MRpP(p,blen) == 1):
found = 1
for i in range(certainty):
if (MRpP(p,blen) == 0):
found = 0
if (found == 0):
p = p + 2L
blen = bitLength(p,10)
return(p)
# cryptographic functions/constructs.
PRIVATE = 0
PUBLIC = 1
# Block cipher routines. These transform some text into a list of numbers
# suitable for encrypting with a public key cryptosystem.
# Split a string up into a list of blocks for use in a block cipher
# not susecptable to dictionary or trivial linear plaintext attacks.
def splitText(s, radix):
# Pad the text to the radix.
s = s + "\0"*((len(s)/radix)*radix-len(s)) + "\0"
# Create the textblock list.
blist = []
for i in range(len(s)/radix + 1):
blist = blist + [s[i*radix:(i+1)*radix]]
# Add a byte of chaining information to each block.
for i in range(len(blist)):
blist[i] = chr(randint(5,250)) + blist[i]
# Mask each of the bytes in each block with that block's
# chain data.
for x in range(len(blist[i])-1):
blist[i] = blist[i][0:x+1] + chr(ord(blist[i][x+1]) ^ \
ord(blist[i][0])) + blist[i][x+2:]
# Mask each noninitial block's chain data with the previous block's
# chain data byte.
for i in range(len(blist)-1):
blist[i+1] = chr(ord(blist[i+1][0]) ^ ord(blist[i][0])) + \
blist[i+1][1:]
# Transform each block into a number.
nlist = []
for i in blist:
r = 0L
for x in i:
r = r << 8
r = r + ord(x)
nlist = nlist + [r]
# Yay for block ciphers.
return(nlist)
# The inverse of the above.
def joinText(nlist):
# Transform each block into a string
blist = []
for i in nlist:
s = ''
while(i > 0):
s = chr(int(i%256)) + s
i = i >> 8
blist = blist + [s]
# Unmask the chaining info bytes.
for i in range(len(blist)-1, 0, -1):
blist[i]= chr(ord(blist[i-1][0]) ^ ord(blist[i][0])) + \
blist[i][1:]
# Unmask the actual text using the unmasked mask.
for i in range(len(blist)):
q =''
for x in range(len(blist[i])):
q = q + chr(ord(blist[i][x]) ^ ord(blist[i][0]))
blist[i] = q
# Remove the chaining bytes and concatenate the text.
msg =''
for i in range(len(blist)):
blist[i] = blist[i][1:]
msg = msg + blist[i]
# Srehpic kcolb rof yay.
return(msg)
class RSAKey:
def __init__(self, bits = 128, cert = 50, edig = 7):
# First find the number of base-10 digits we want.
dig = int(log(2)/log(10)*(bits/2))
# Create the primes.
p = randPrime(dig, cert)
q = randPrime(dig, cert)
self.e = randPrime(edig, cert)
# Store the modulus and decryption exponent
self.ktype = PRIVATE
self.n = p*q
self.d = invMod(self.e,(p-1)*(q-1))
def keyType(self):
if (self.ktype == PRIVATE):
return("Private")
return("Public")
def makePublic(self):
del(self.d)
self.d = 0
self.ktype = PUBLIC
def printKey(self):
try:
s = dumps(self)
except:
s = "Error dumping key"
return(s)
def encryptBlock(self, x):
return(powMod(x,self.e,self.n))
def decryptBlock(self, x):
return(powMod(x,self.d,self.n))
def encryptString(self, s):
# First let's find an appropriate radix for this modulus
r = bitLength(self.n, 256) - 2
if (r < 2):
raise Exception("Modulus too small")
# Get the plaintext.
pt = splitText(s, r)
# Encrypt.
xmsg = []
for i in pt:
xmsg = xmsg + [self.encryptBlock(i)]
return(dumps(xmsg))
def decryptString(self, s):
if (self.ktype == PUBLIC):
raise Exception("Cannot decrypt with a public key")
xmsg = loads(s)
pt = []
# Decrypt.
for i in xmsg:
pt = pt + [self.decryptBlock(i)]
# Get plaintext.
return(joinText(pt))
#---------------------------------RSA.py------------------------------
# a little test, added by PSST
if __name__ == "__main__":
rsakey = RSAKey()
es = rsakey.encryptString("Hello friends")
print es
