##### CSC 15 RSA Lab import json """ This assignment asks you to write routines to decipher messages using the RSA algorithm, with both encrpytion and decryption keys given to you. Please be aware that the prime numbers chosen for the algorithm here are not large enough for real world security, and are only used as an example. I have provided you with the code I used to encrypt strings and you will have to write the code to decrypt the file. Eventually you will have all the routines to both encrypt and decrypt strings and files. The RSA "keys" used for the assignment are as follows: """ p,q = 2747527,1699681 # two tiny prime numbers n = p*q # 4669919438887, determines the range of values that can be encrypted pq1 = (p-1)*(q-1) #print(primefactors(2*pq1+1)) e,d = 389227, 23995843 ## our keys! #print(e*d % pq1) # confirm that it's 1 """ The public encryption key is (e,n) and the private decryption key is (d,n). A message to be encrypted must be represented by a number between 0 and n-1. To encrypt a message , compute c=m**e % n. c is the encrypted form of the number. To decrypt it, compute c**d % n, which should result in m. However, you will find that these operations are excruciatingly slow even for our relatively small values of e and d, so you definitely need to use the following: """ def fastexp(x,p,n): # compute x**p % n in log(p) steps, avoids large ints ax = 1 # accumulator factor = x % n # initially x**1 while p>0: if (p%2==1): ax = (ax * factor) % n factor = (factor * factor) % n p = p//2 # shift right #while return ax % n #fastexp """ The program demonstrated in class only encrypted one character at a time, by using the ascii value of that number. But our choice of n will allow us to encode 6 ascii numbers at a time, which makes the encryption much harder to break. We will only encrypt ascii strings: strings using non-ascii chars will not work with this program. Each ascii character has ord values 0-127, so it only requires 7 bits. Each 7 bits can store a value between 0 and 127. Because 128**6 == 2**42 < n, our n is big enough to allow six 7-bit values (but no more). The following routine encodes a m-character string into such a number. For this assignment, the function should be called with m=6. **Part of what you will need to do is to write the inverse of this function: """ # pack m ascii chars into a number x < 128**m < n: def strtonum(s,m): if len(s)!=m: raise Exception("string not of length "+str(m)) ax = 0 i = 0 while i127): raise Exception("not possible to code ",s[i]) ax += ascii if (i<=len(s)-2): ax *= 128 # shift ax 7 bits left i += 1 # but don't shift for last value #while return ax #strtonum ## 1. Write the inverse of strtonum that takes a number and returns a # 6-char string. Call the function 'numtostr' # print( numtostr(strtonum("abc123",6),6) ) # should print abc123 """ The following function calls strtonum and fastexp repeatedly on a string. It first pads the string with newline characters so that it's a multiple of m. You should also call this function with m=6. This function returns an array of numbers: this is the encrypted form of the original string. You also need to write the inverse of this function: """ def encrypt(s,m): # encrypt string m chars at a time if m<1: return [] while len(s)%m>0: s = s+"\n" # pad string to be of right length C = [] # encrypted form will be an array of numbers i = 0 while i+m<=len(s): num = strtonum(s[i:i+m],m) C.append( fastexp(num,e,n) ) i += m # while return C # encrypt #2. Write the inverse of encrypt (decrypt), which takes an array of numbers # as its argument and returns a string representing the decrypted number. ## Test your functions by decrypting the following secret message MSG = [3200667378880, 3824030730191, 3559410684427, 597200880634, 3552136314220, 4484750185502, 1742130571083, 1260404401313, 3933591883013, 595219438726, 1350319812100] """ --------- part 2 ---------- Using an array of numbers to represent an encrypted string is OK, but we can also represent it as a scrambled string, which is more 'platform compatible' and 'transportable.' For example, a string can be emailed whereas emailing an array of numbers is rather awkward even if possible. You can use your solution to problem 1 (numtostr) to convert a number to a string, but there's a catch. The numerical representation of 6 ascii chars, before encryption, has maximum value 2**42-1, which is 4398046511103. This is less than the value n-1, which is 4669919438886. n-1 is largest possible value produced by the encryption algorithm. That is, **the encrypted number might not fit into 42 bits** Infact it takes 43 bits to represent n-1. This means that, instead of translating the number into 6 chars, your will have to translate it into 7 chars. In other words, the plain text should be divided into 6-char blocks segments but the encrypted text should be divided into 7-char segments. To be clear, the encryption and decryption algorithms should have the following structure: Given Original string S, Apply the strtonum function to every 6 chars of s to produce a, each time producing a number si Apply the fastexp function to encrypt si into a number ci Apply your numtostr function ci to create a 7-char sequence Apply the above three steps to every 6 chars of s, creating the ciphertext string CS. Given encrypted, ciphertext string CS, Apply the strtonum function above to evey SEVEN chars of CS (CS[i:i+7]) Each such number ci is less than n. Decrypt ci using the fastexp function, this gives you a number di The number di from the above step should be less than 2**42, which means it will fit inside SIX bytes. Apply your numtostr function to each di to translate di into SIX characters. Note that you will need both strtonum and numtostr to encrypt a string, and both the decrypt a string. """ MSG2 = "Apply your functions to encrypt, then decrypt this string." """ The final part of the assignment asks you to decrypt the file lab7.py.enc on the class homepage. This file should be read using the following function: """ def readbin(filename): # reads file as ascii-encoded string, returns string fd = open(filename,"rb") # "rb" means read binary s = fd.read() fd.close() return s.decode("ascii") # returns a regular string #readbin ## The scrambled string is stored as a binary file because writing # certain special characters, especially the backspace character, # could cause problems on some systems. But this function will decode # the binary data into a regular string before returning it. Cipher = readbin("lab7.py.enc") # reads encrpyted string into Cipher # This file contains the sample solution to this assignment, along with a host # of other useful routines. Please decrypt it.