In this activity, we are going to implement a super-simple encryption algorithm. The first thing we will do is make a correspondence between the alphabet of characters that can appear in our message and the integers 0 through 28. Think of it as a miniature version of the ASCII table! 

Encryption and Decryption      
      Here's the scheme using key k in {0,1,...,28}
      We encrypt message character m to get encrypted character c
        .--------.               .----------.               .--------. 
m ----> |look up | ----> i ----> |encrypt as| ----> j ----> |look up | ----> c
        |in table|               |k*i mod 29|               |in table|
        `--------'               `----------'               `--------'

Example: let k=2
        .--------.               .----------.               .--------. 
d ----> |look up | ----> 3 ----> |encrypt as| ----> 6 ----> |look up | ----> g
        |in table|               |k*i mod 29|               |in table|
        `--------'               `----------'               `--------'
... so d gets encrypted as g.

Decryption:  if k' is the multiplicative inverse of k in Z mod 29,
      then k*i is the encrypted message, so multiplying that by k'
      gives k*k'*i = i in Z mod 29, so we get the original message back.

Your job

I have two programs for you below. You can copy them into files on your laptop and compile them. They are You and a classmate need to agree on a secret key (a non-zero element of $\mathbb{Z}_{29}$). Your job is to use ex0 to encrypt a message, send it to your classmate, while they send you an encrypted message. Then decrypt the message they sent you. Note: you may find the modinv program useful!
modinv.cpp - compile as: g++ -o modinv modinv.cpp run as: ./modinv ex0.cpp - compile as: g++ -o ex0 ex0.cpp run as: ./ex0 
#include <iostream>
using namespace std;

/* 
Extended Eucliden gcd
  inputs : u, v where u >= 0 and v >= 0
  outputs: g,s,t such that g = s*u + t*v and g is gcd(u,v)
*/
int egcd(int u, int v, int& s, int& t);

int main() {
  int x, n;
  cin >> x >> n;
  if (x < 0 || x >= n || n <= 1) {
    cout << "usage: enter <x> <n> where x >= 0 and n > 1 and n > x" << endl
	 << "       computes d such that x*d mod n = 1" << endl;
    return 1;
  }
  int g, s, t;
  g = egcd(x,n,s,t);
  if (g != 1)
    cout << "no multiplicative inverse!" << endl;
  else {
    int d = (s >= 0 ? s : n + s);
    cout << x << "*" << d << " = 1 in Z_" << n << endl;
  }
  return 0;
}

int egcd(int u, int v, int& s, int& t) {
  if (v == 0) {
    s = 1;
    t = 0;
    return u;
  }
  else {
    int q = u/v, r = u%v, sp, tp;
    int g = egcd(v,r,sp,tp);
    s = tp;
    t = sp-tp*q;
    return g;
  }
}
 
#include <iostream>
using namespace std;

// each char in s is represented by the number in 0-28
// that is its index in string s.
const string s = "abcdefghijklmnopqrstuvwxyz._,";
int geti(char c); // go from character to index
char getc(int i); // go from index to character

int main() {
  // read e/d msg key, e.g. 'e hello 18'
  string dir, msg;
  int n = 29, key;
  cin >> dir >> msg >> key;
  
  for(int j = 0; j < msg.length(); j++) {
    int i = geti(msg[j]); // i is value of msg[j] in Z_29
    int ip = (i*key)% n;  // ip is i*key in Z_29
    cout << getc(ip);
  }
  cout << endl;
  
  return 0;
}

int geti(char c) {
   for(int i = 0; i < s.length(); i++)
     if (s[i] == c)
       return i;
   return -1;
}

char getc(int i) {
  return s[i];
}