Skip to content

Instantly share code, notes, and snippets.

@basavesh
Forked from avalonalex/RSA.py
Created October 13, 2012 18:06
Show Gist options
  • Save basavesh/3885594 to your computer and use it in GitHub Desktop.
Save basavesh/3885594 to your computer and use it in GitHub Desktop.
A implementation of RSA public key encryption algorithms in python
import random
import math
import copy
def euclid(a,b):
'''returns the Greatest Common Divisor of a and b'''
a = abs(a)
b = abs(b)
# make sure the algorithms still works even when
# some negative numbers are passed to the program
if a < b:
a, b = b, a
while b != 0:
a, b = b, a % b
return a
def coprime(L):
'''returns 'True' if the values in the list L are all co-prime
otherwier, it returns 'False'. '''
for i in range (0, len(L)):
for j in range (i + 1, len(L)):
if euclid(L[i], L[j]) != 1:
return False
return True
def extendedEuclid(a,b):
'''return a tuple of three values: x, y and z, such that x is
the GCD of a and b, and x = y * a + z * b'''
footprint = []
# the boolean flag is used to make sure this function can return
# right answer no matter which is bigger.
if a < b:
isASmallerThanB = True
a, b = b, a
else:
isASmallerThanB = False
while b != 0:
footprint.append((a % b, 1, a, -(a//b), b))
# for each tuple in list footprint
# footprint[i][0] == footprint [i][1] * footprint[i][2]
# + footprint [i][3] * foorprint[i][4]
# and
# footprint[i][4] == footprint[i+1][0]
# this two equations are key to generate the linear combination
# of a and b so that the result will be their GCD (or GCF).
a, b = b, a % b
# Start work backward to compute the linear combination
# of a and b so that this combination gives the GCD of a and b
footprint.reverse()
footprint.pop(0)
#print (footprint)
x = footprint[0][1]
y = footprint[0][3]
#print (x, y)
for i in range (1, len(footprint)):
x_temp = x
y_temp = y
x = y_temp * footprint[i][1]
y = y_temp * footprint[i][3] + x_temp
#print (x, y)
if (isASmallerThanB != True):
return (a, x, y)
else:
return (a, y, x)
def modInv(a,m):
'''returns the multiplicative inverse of a in modulo m as a
positve value between zero and m-1'''
# notice that a and m need to co-prime to each other.
if coprime([a, m]) == False:
return 0
else:
linearcombination = extendedEuclid(a, m)
return linearcombination[1] % m
def crt(L):
'''takes in a list of two or more tuples, ie
L = [(a0, n0), (a1,n1),(a2,n2)...(ak nk)]
if the n-s are not co-prime, this function prints an error message to
the screen and returns -1. Otherwise it continues with the Chinese
Remainder theorem, finding a value for x to return which satisfies
x = ai( mod ni)
for all tuples in the list L. This value must be between 0 and N-1
where N is the product of all the n in the list L'''
NList = []
for item in L:
NList.append(item[1])
if coprime(NList) == False:
print ("The input is not valid!")
return -1
else:
bigN = 1
for numbers in NList:
bigN *= numbers
CRTresult = 0
for item in L:
ai = item[0]
Ci = bigN//item[1]
#print (Ni, ai)
Yi = extendedEuclid(Ci, item[1])
#print (Ci, item[1])
CRTresult += ai * Ci * Yi[1]
return CRTresult % bigN
# start of second project *****************************
def extractTwos(m):
'''m is a positive integer. A tuple (s, d) of integers is returned
such that m = (2 ** s) * d.'''
# the problem can be break down to count how many '0's are there in
# the end of bin(m). This can be done this way: m & a stretch of '1's
# which can be represent as (2 ** n) - 1.
assert m >= 0
i = 0
while m & (2 ** i) == 0:
i += 1
return (i, m >> i)
def int2baseTwo(x):
'''x is a positive integer. Convert it to base two as a list of integers
in reverse order as a list.'''
# repeating x >>= 1 and x & 1 will do the trick
assert x >= 0
bitInverse = []
while x != 0:
bitInverse.append(x & 1)
x >>= 1
return bitInverse
def modExp(a,d,n):
'''returns a ** d (mod n)'''
# a faster algorithms discussed in CIT 592 class
assert d >= 0
assert n >= 0
base2D = int2baseTwo(d)
base2DLength = len(base2D)
modArray = []
result = 1
for i in range (1, base2DLength + 1):
if i == 1:
modArray.append(a % n)
else:
modArray.append((modArray[i - 2] ** 2) % n)
for i in range (0, base2DLength):
if base2D[i] == 1:
result *= base2D[i] * modArray[i]
return result % n
def millerRabin(n, k):
'''
Miller Rabin pseudo-prime test
return True means likely a prime, (how sure about that, depending on k)
return False means definitely a composite.
Raise assertion error when n, k are not positive integers
and n is not 1
'''
assert n >= 1
# ensure n is bigger than 1
assert k > 0
# ensure k is a positive integer so everything down here makes sense
if n == 2:
return True
# make sure to return True if n == 2
if n % 2 == 0:
return False
# immediately return False for all the even numbers bigger than 2
extract2 = extractTwos(n - 1)
s = extract2[0]
d = extract2[1]
assert 2 ** s * d == n - 1
def tryComposite(a):
'''Inner function which will inspect whether a given witness
will reveal the true identity of n. Will only be called within
millerRabin'''
x = modExp(a, d, n)
if x == 1 or x == n - 1:
return None
else:
for j in range (1,s):
x = modExp(x, 2, n)
if x == 1:
return False
elif x == n - 1:
return None
return False
for i in range (0, k):
a = random.randint(2, n - 2)
if tryComposite(a) == False:
return False
return True # actually, we should return probably true.
def primeSieve(k):
'''return a list with length k + 1, showing if list[i] == 1, i is a prime
else if list[i] == 0, i is a composite, if list[i] == -1, not defined'''
def isPrime(n):
'''return True is given number n is absolutely prime,
return False is otherwise.'''
for i in range(2, int(n ** 0.5) + 1):
if n % i == 0:
return False
return True
result = [-1] * (k + 1)
for i in range(2, int(k + 1)):
if isPrime(i):
result[i] = 1
else:
result[i] = 0
return result
def findAPrime(a,b,k):
'''Return a pseudo prime number roughly between a and b,
(could be larger than b). Raise ValueError if cannot find a
pseudo prime after 10 * ln(x) + 3 tries. '''
x = random.randint(a, b)
for i in range(0, int(10 * math.log(x) + 3)):
if millerRabin(x, k):
return x
else:
x += 1
raise ValueError
def newKey(a,b,k):
''' Try to find two large pseudo primes roughly between a and b.
Generate public and private keys for RSA encryption.
Raises ValueError if it fails to find one'''
try:
p = findAPrime(a, b, k)
while True:
q = findAPrime(a, b, k)
if q != p:
break
except:
raise ValueError
n = p * q
m = (p-1) * (q-1)
while True:
e = random.randint(1, m)
if coprime([e, m]):
break
d = modInv(e, m)
return (n, e, d)
def string2numList(strn):
'''Converts a string to a list of integers based on ASCII values'''
# Note that ASCII printable characters range is 0x20 - 0x7E
returnList = []
for chars in strn:
returnList.append(ord(chars))
return returnList
def numList2string(L):
'''Converts a list of integers to a string based on ASCII values'''
# Note that ASCII printable characters range is 0x20 - 0x7E
returnList = []
returnString = ''
for nums in L:
returnString += chr(nums)
return returnString
def numList2blocks(L,n):
'''Take a list of integers(each between 0 and 127), and combines them into block size
n using base 256. If len(L) % n != 0, use some random junk to fill L to make it '''
# Note that ASCII printable characters range is 0x20 - 0x7E
returnList = []
toProcess = copy.copy(L)
if len(toProcess) % n != 0:
for i in range (0, n - len(toProcess) % n):
toProcess.append(random.randint(32, 126))
for i in range(0, len(toProcess), n):
block = 0
for j in range(0, n):
block += toProcess[i + j] << (8 * (n - j - 1))
returnList.append(block)
return returnList
def blocks2numList(blocks,n):
'''inverse function of numList2blocks.'''
toProcess = copy.copy(blocks)
returnList = []
for numBlock in toProcess:
inner = []
for i in range(0, n):
inner.append(numBlock % 256)
numBlock >>= 8
inner.reverse()
returnList.extend(inner)
return returnList
def encrypt(message, modN, e, blockSize):
'''given a string message, public keys and blockSize, encrypt using
RSA algorithms.'''
cipher = []
numList = string2numList(message)
numBlocks = numList2blocks(numList, blockSize)
for blocks in numBlocks:
cipher.append(modExp(blocks, e, modN))
return cipher
def decrypt(secret, modN, d, blockSize):
'''reverse function of encrypt'''
numBlocks = []
numList = []
for blocks in secret:
numBlocks.append(modExp(blocks, d, modN))
numList = blocks2numList(numBlocks, blockSize)
message = numList2string(numList)
return message
if __name__=='__main__':
(n, e, d) = newKey(10**100, 10**101, 50)
print ('n = {0}'.format(n))
print ('e = {0}'.format(e))
print ('d = {0}'.format(d))
message = '''We were the Leopards, the Lions, those who'll take our place will be little jackals, hyenas; But we'll go on thinking ourselves the salt of the earth.'''
print(message)
cipher = encrypt(message, n, e, 15)
print(cipher)
Amessage = decrypt(cipher, n, d, 15)
print(Amessage)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment