#                     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]

## 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

## 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] = encode1(M[i],e,n)
    i += 1
  #while
  return C
#encodeArray

## Now we need a routine to convert a string such as "hello" into an
# array of ascii characters.  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

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 [193L, 758L, 169L, 169L, 131L]

# ignore the "L" at the end of each number it's there because very large
# intermediate numbers were calculated (m**17).

##### 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([193L, 758L, 169L, 169L, 131L]) will return the string "hello"

# You may find the following function useful (what does it do?).  That is,
# you may want to call it from other functions:

def asciistring(A):
   s = ""  # string to be constructed from A
   i = 0
   while i<len(A):
     s = s + chr(A[i])
     i += 1
   #while
   return s
#ascciistring


## Write rsadecode and use it to decode a secret message.  Information 
# brought to us by our Bothan spies has been encrypted as follows:

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

# 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 = [2803L, 3446L, 3636L, 1476L, 604L, 3636L, 1244L, 21L, 3446L, 1476L, 2180L, 21L, 1244L, 1225L, 1476L, 3447L, 934L, 1476L, 668L, 1887L, 3602L, 3602L, 2593L, 1476L, 1508L, 4413L, 3636L, 1225L, 1244L, 21L, 3447L, 1508L, 2484L, 1244L, 3602L, 1791L]

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


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

# Devise a new set of keys: (e,n) and (d,n) using another pair of primes.
# Encrypt some secret message and give it to another group of students to
# decrypt.  Tell them the encryption key but not the decryption key.
# Please use prime numbers less than 10000.  We will form teams for this one.
#
# The team that breaks the other teams' code will get a bonus.