Last active
October 19, 2025 03:12
-
-
Save avalonalex/2122098 to your computer and use it in GitHub Desktop.
A implementation of RSA public key encryption algorithms in python, this implementation is for educational purpose, and is not intended for real world use. Hope any one want to do computation like (a^b mode n) effectively find it useful.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| # October 2011 | |
| # Author Yuhan Hao | |
| # Email: yuhanhao@seas.upenn.edu | |
| # Tested under python3.2.2 | |
| 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) |
I think there may be an issue with your bit padding. For example, take our the word "earth" from your message variable and run again. You'll see a random set of decrypted values at the end of your plaintext message string. I'm thinking this is because we are not taking into consideration variable blocksizes which would typically only be an issue for the last block. Either it fits perfectly, or needs padding... what do you think?
Author
The reason for numList2blocks(l, n) to do padding is a naive way to prevent dictionary attack. A better way may be serialize message into a format with message length information before encrypt and descrialize to remove padding.
Author
(1) address @sadmicrowave 's concern.
(2) better user interaction
Can I use it for encrypted virus scan purpose? It will not be for real world use.
thanks for this- very helpful from an academic standpoint!
i couldnt get my program running, the were lot of errrors and i was using python 3.3.... are there any libraries i need to add to this code for it to work?
@Magibela start by adding brackets to the print statements + add a from __future__ import print_function to the top of the code.
If there are still errors post them, it usually takes a little work to port scripts from python2 to python3
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I couldn't get my program to calculate large power sums. This code really helped, thank you for posting.