#                     CSC 15 RSA Decryption Lab

# The Rivest-Shamir-Adleman (RSA) public key encryption algorithm works
# as follows:  two very large prime numbers p and q are chosen and 
# kept secret.  Let n = p*q (the idea is that it's hard to figure out
# what q and p are given n).  Two more numbers, d and e, are picked so
# that (e*d) % ((p-1)*(q-1)) == 1.  The pair (n,e) is called the
# public key or encryption key, and is used by everybody to encrypt 
# messages.  The private key consists of the number d, which is
# kept secret.  A message can be represented as a number m between 0 and
# n-1.  To encrypt the message, compute m to the eth power mod n,  
# or m**e % n. To decrypt the "cipher" message c, we use c**d%n.  That is,
# if c = m**e%n, then c**d%n will give us the original message m.

# In practice the prime numbers used for encryption are very large, with
# several hundred digits.  But smaller numbers are enough to illustrate
# the concept. For example, we can pick the two primes to be p,q = 47,59
# and e = 17, d = 157, and n = p*q (2773).  We can encode text messages 
# character by character using their ascii values.  For example, 
# "hello" has the corresponding list/array of (unencrypted) ascii values:

# [104, 101, 108, 108, 111]

## First we need a routine to convert a string such as "hello" into such
# an array of ascii valuse.  Given a single character x, ord(x) returns
# the ascii value (between 1 and 127) and given an ascii value a, chr(a)
# returns the corresponding character.

def asciivals(s):  # convert string s to array of ascii values
  A = [0]*len(s)
  i = 0
  while i<len(s):
      A[i] = ord(s[i])
      i +=1
  #while
  return A
#asciivals

## Here is the function that encodes a single ascii value m, with 
## "public key" e and n:

def encode1(m,e,n):
   return m**e % n

## But this is inefficient, since m**n is very large but we only need a value
#  between 0 and n-1 (after %n), so we define the following:

def expmod(m,e,n):  # returns (m**e)%n in log(e) steps.
   if (e<0 or type(e) != type(1)): 
     raise Exception("Invalid exponent for expmod")
   ax = 1  # accumulator
   factor = m%n  # base factor
   while e>0:
     if e%2==1: ax = (ax*factor) %n
     factor = (factor*factor) % n
     e = e//2
   # while n>0
   return ax
#expmod

# new version of encode using fast expmod operation
def encode2(m,e,n):
  return expmod(m,e,n)


## Now here is a function that encodes an array of ascii values:
def encodeArray(M,e,n):
  C = len(M)*[0]   # create array of same size as M, initial values all 0
  i = 0
  while i<len(M):
    C[i] = encode2(M[i],e,n)
    i += 1
  #while
  return C
#encodeArray


print( asciivals("hello") )  # prints [104, 101, 108, 108, 111]

## Now we can write the "outer" function that combines these routines to
# encode a string into an array of encrypted values:

def rsaencode(s,e,n):  #encode string into array of values
  ASC = asciivals(s)
  return encodeArray(ASC,e,n)
#rsaencode

print(rsaencode("hello",17,2773)) # prints [193, 758, 169, 169, 131]

# This array is called the "cyphertext": if you try to convert these
# values to chars you'll get unreadable text.

##### part I: decoding

# part I of the assignment asks you to implement procedures to decode
# an encrypted message.  The public key used in the above encryption is
# e,n = 17,2773.  The corresponding "private key" is d,n = 157,2773.  
# You need to write a function "rsadecode" so that calling
# rsadecode([193, 758, 169, 169, 131]) will return the string "hello"

## Suggestion: you should solve the problem in three stages.  Define
## the following three functions:

# 1. the following function should be the inverse of asciivals: given an
# array A of ascii numbers it should construct a STRING with the corresponding
# characters (e.g. chr(97)=='a').  To construct a string, start with
# empty string s ="", then add to it one char at a time: s= s+newchar.  
#def valsascii(A):  

# 2. The following function should be inverse of encode (or encode2): that
# is, it should decode a single value c using decryption key d,n: it should
# return a number (not char yet):
#def decode2(c,d,n):

# After this step, you should probably realize that decode is the same as
# encode, just pass it d passed instead e.  However, you will need to
# now define a version of decode that works for an entire array of values:

# the following function takes an array of (encrypted) values C, and decryption
# key d,n, and returns an ARRAY of decoded values.  This function should
# call the function encode (or decode, which is the same) on each value.
#def decodelist(C,d,n):

# Finally, you need to write a function that combine these steps:

# the following function should take an array of encrypted values C, decryption
# key d,n, and return a STRING that can be read.
#def decrypt(C,d,n):

## Use your program to decrypt the following secret message.  Information 
# brought to us by our Bothan spies has been encrypted as follows:

C = [2063, 193, 758, 2227, 1187, 758, 660, 2504, 193, 2227, 1471, 2504, 660, 1684, 2227, 1020, 1751, 2227, 131, 1684, 1860, 1020, 2504, 1020, 1528, 850, 2227, 2504, 193, 758, 2227, 1084, 169, 660, 1528, 758, 2504, 2227, 1188, 1528, 1952, 131, 1684, 1315]

d,n = 157,2773  

# What's the message?
# Many Bothans died to bring us this information.



############### PART II : Cracking the Code ###############

## Our spies have sent us a new message using a different encryption
# key.  However, the agent carrying the corresponding decryption key was 
# captured.  We only know that the public encryption key used to produce 
# the following message was e,n = 53,4891. But without the corresponding 
# decryption key (d,n) we can't read it!  You need to use a combination of 
# mathematical and programming techniques to figure out what d might be.  
# The only other hint we have is that both primes used to produce the new 
# keys are less than 200.

C = [2803, 3446, 3636, 1476, 604, 3636, 1244, 21, 3446, 1476, 2180, 21, 1244, 1225, 1476, 3447, 934, 1476, 668, 1887, 3602, 3602, 2593, 1476, 1508, 4413, 3636, 1225, 1244, 21, 3447, 1508, 2484, 1244, 3602, 1791]

# Hint, the key is to figure out which are the two prime numbers p,q
# such that p*q==n.  You should try to write a loop to find out.  Then
# you will also know what (p-1)*(q-1) is, and you know that
# ed%(p-1)(q-1)==1, which means that ed == k(p-1)(q-1) + 1 for some
# integer k, and thus d == (k(p-1)(q-1)+1)//e, and this division
# should leave no remainder.  You can write another loop that tries
# different values for k.  with each value of k, d can be inferred
# from the equations above.

# Please write down what p,q and d are, as well as what the message is.

# Help us Obi-Wan Kenobi, you're our only hope.


################### PART III: Encoding two chars at a time: the previous
# algorithm encoded a single character at a time, which is not very secure
# (it's called a substitution cypher).  A better way is to encode a block
# chars at a time.  The number just needs to be less than n.  The following
# function encodes a string of exactly two chars into a singe value. 
def twinenc(s):
    if len(s)!=2: raise Exception("invalid input to twinenc1")
    return ord(s[0])*128 + ord(s[1])
#twinenc1

# It assumes that each char has ascii value less than 128, so the maximum 
# value it can return is 128*128-1 == 2**14-1 == 16383.  The value of n
# we had above are too small, so we will need to find larger prime numbers.
# let p,q=787,1381, n=p*q.  A pair of e,d that works are 323,23507

# Given a value t returned by twinenc, you can convert it back into a pair
# of chars using chr(t//128) and chr(t%128).

# Write a series of routines that will allow us to encrypt/decrypt strings
# two chars at a time.  One of the things you will need to do is to pad
# a string with an extra char so that it is of even length, such as s=s+" ".

# You can also use the following notation: given string s, s[i,i+2] will return
# the substring containing two chars starting from s[i]: i.e, string with
# chars s[i] and s[i+1].  Make sure that i+2 <= len(s).


################### PART IV: Finding a new set of keys

# Devise a new set of keys: (e,n) and (d,n) using another pair of primes.
# Please use prime numbers less than 10000.  There will be another part of
# the assignment that involves an authentication certificate.