CIS 122: Assignment #4

1. Vigenere Cypher

We'll kick off this assignment with a glimpse into the world of cryptographic algorithms. In the 1500s, Blaise de Vigenere developed a new algorithm for encrypting secret messages. Such encryption schemes are known as "cyphers", and Vigenere's was a major impovement over its predecessors. In fact, up until the end of the 1800s, it was viewed as uncrackable.

Overview of the technique?

The general idea behind all encryption schemes is to replace each letter in the original message with another letter in a manner which makes the encrypted message unreadable, but which can be reversed to recover the the original message. This recovery is known as "decryption", and is possible in reversible encryption schemes if you know how the encryption was done (actually, modern methods are much harder than this, but we'll simplify here for the sake of discussion). The idea behind the Vigenere cypher is to use a secret key that determines how a letter in the original message is mapped to a letter in the encrypted message. However, we don't want the same replacement all the time, i.e., we don't want 'a' to always be replaced with 'r'. Instead, we want to change the replacement scheme as we move, letter by letter, through the message. So maybe 'a' will be replaced by 'r' the first time it appears in the clear message, but the second 'a' will be replaced by 'd'. While this solves the frequency analysis problem, it could get complicated coming up with the secret key. Vigenere came up with a clever simplification. He said, in effect, "Forget trying to remember all the different mappings from clear letters. Instead, use the position of letters in the clear message as the basis for encryption." What he proposed was a secret key composed of a finite sequence of integers from 0-25. Let's use an example of 3,1,5,8 as a secret key. (Real keys can be of suitably gigantic length.) His encryption algorithm is to take the letter in the first position of the clear message, and add 3 to it, e.g., 'a' becomes 'a'+3 or 'd'. Then take the letter in the second position of the clear message, and add 1 to it. Keep moving through the clear message and secret key, building up the enrypted message. If the key is shorter than the clear message, it just repeats. Here is an example using 3,1,5,8 as the secret key.

  secret key= 3,1,5,8
  clear message=     attackatdawn
                   + ||||||||||||
                     315831583158  => note the key repeats
                     ||||||||||||
  encrypted message= duyiflfbgbbv

Can we automate this algorithm?

Your job is to write a program that will automate all this. What I want is a function that will encrypt (e.g., "attackatdawn" => "duyiflfbgbbv") and a function that will decrypt (e.g., "duyiflfbgbbv" => "attackatdawn") using the Vigenere cypher. Here is a start at the function signature for encryption:

string vigenereEncrypt( string message, string secret_key ){...}

String encrypted_message = the_object.vigenereEncrypt( "attackatdawn", "dbfi" );

At first glance, programming this scheme may appear quite overwhelming. However, with effective use of function decomposition to abstract away hard steps, it becomes quite tractable. There are three parts to this problem:

1. building a helper function, letterShift,
2. building the encryption function, and
3. building the decryption function.

1. The letterShift function

Vigenere based his algorithm on "shifting" an individual letter a given number of positions to the right. Thus, given the pair ('a', 1), the result is 'b': we shift 'a' 1 to the right. I'd like you to build a function, letterShift, that does this style of shifting. You don't actually have to "build" it - simply fill in the pieces that I have left out. I'll give you a small test program where you can work on it.

Before starting to fill in the missing pieces, here are some facts that may help you.

• The chars a-z are numerically in sequence:

  'a' < 'b' < 'c'... < 'z'
  

• You can convert a char to an int:

  int int_a = 'a';
  

• You can convert an int to a char:

  char char_a = (char) int_a;
  

• You can get the alphabetic position of a lower case letter by subtracting 'a':

  int pos_d = 'd' - 'a';
  

  (pos_d will be given the value 3).

• When shifting, you can keep in range 0-25 by using the mod operator:

  (25+2)%26 will have the value 1. 
  

• You can turn an int in range 0-25 back into a letter char by adding 'a' and casting to a char.

Save the code below in a file named vigenere.cpp, and complete the letterShift function by replacing the (non-compilable) question marks. Play close attention to the comments following each line for what legal values are.

#include <iostream>
using namespace std;

char letterShift(char c, int k);

int main() { 	 
  char c;
  int k;

  cout << "Char: ";
  cin >> c;
  cin.ignore(80,'\n');

  cout << "Shift distance: ";
  cin >> k;

  cout << "return value = " << letterShift( c, k ) );
  
  return 0;
} //main

char letterShift(char c, int k) {      

  // We only shift lower case letters
  if( !islower(c) )
    return '*';

  // Compute the offset of c in alphabet (range 0-25)
  int c_offset =  ?????      
                 
  //cout <<  "should be in range 0-25:" + c_offset );


  // Compute the position of the shifted char in alphabet (range 0-25)
  int shifted =  ????

  //cout <<  "should be in range 0-25:" + shifted );


  // Convert to char and return (range 'a'-'z', not 0-25)
  return  ????

} //letterShift

2. The vigenereEncrypt function

We are now ready to build the encryption function. As with letterShift, I have given you the basic structure. Your job is to fill in the missing pieces. First copy the function below into vigenere.cpp. (Note that this function uses letterShift, so make sure letterShift is working before trying to complete vigenereEncrypt .)

string vigenereEncrypt(string message, string secret_key) {
  // We want to repeatedly move left-to-right one position in both
  // the clear message and the key. I've chosen to combine this into
  // a single for-loop, using i to keep track of where we are in
  // the clear message and k to keep track of where we are in the
  // key. If we run off the end of the key, we just start at the
  // left-most end again.
  int k = 0;                 // key index
  string encrypted = "";     // what we will eventually return

  for ( int i = 0; ????; ???? ) {
    // convert kth letter in key to an int (see letterShift for hint)
    int int_key = ????; 	 
    encrypted = encrypted + ????;

    // Don't run off right end of key, start over at beginning
    ????????
  }

  return encrypted;
}

char letterShift(char c, int k);      
string vigenereEncrypt(string message, string secret_key);

int main() { 	 
  string key,message;

  cout << "Key: ";
  cin >> key;
  cin.ignore(80,'\n');

  cout << "Message: ";
  getline(cin,message);

  string encrypted = vigenereEncrypt( message, key );
  cout <<  "message   = " << message << endl;
  cout <<  "encrypted = " << encrypted << "(key = " << key << ")" << endl;
  
  return 0;
} //main

3. The vigenereDecrypt function

Now that you have encryption working, let's turn to decryption. Before hacking code, let's do a little work with paper-and-pencil, always a good idea. Let's say the first letter in our clear message is 'a' and the first shift in our key is 'e' (or 4). We get a shifted letter 'e' (i.e., shifting 'a' right four places gives us 'e'). For decryption, we have to get from 'e' back to 'a'. We need to either shift 'e' left 4 or right 22. We already have a function, letterShift, that would be happy to do a right shift of 22. Seems like a good idea to use it instead of writing yet another function. That leaves us with the question of how we get from the key value of 4 (used for encryption) to 22 (to reverse encryption)? Looks like 26 - 4 = 22. You might want to try this for several values of the key to convince yourself. Now all we have to do is to copy-and-paste the vigenereEncrypt function body, and make the following change: where we pass the key to letterShift, we pass it 26 minus the key value.

Now you can start hacking. We need a function like this in Vigenere:

string vigenereDecrypt(string encrypted, string secret_key) {
        // Here we have the encrypted message and we need to "unshift"
        // by the key to get back the clear message, which is returned.
    }

string vigenereEncrypt(string message, string secret_key);
string vigenereDecrypt(string encrypted, string secret_key); 


int main() { 	 
  string key,message;

  cout << "Key: ";
  cin >> key;
  cin.ignore(80,'\n');

  cout << "Message: ";
  getline(cin,message);

  string encrypted = vigenereEncrypt( message, key );
  cout <<  "message   = " << message << endl;
  cout <<  "encrypted = " << encrypted << "(key = " << key << ")" << endl;
  string restored = vigenereDecrypt( encrypted, key );
  cout <<  "restored  = " << restored << endl;
  cout <<  "message equiv to restored (should be true): " 
       <<  (message == restored ) << endl;
  
  return 0;
} //main

Run the following tests to verify your code works:

Message	Key
attackatdawn	dbfi
abcdefghijklmnopqrstuvwxyz	jihgfedcbaz
floridastatemottoisvoteearlyandoften	disneymagic

Your output should look like the following (user input emphasized):

Key: dbfi
Message: attackatdawn
message   = attackatdawn
encrypted = duyiflfbgbbv(key = dbfi)
restored  = attackatdawn
message equiv to restored (should be true): 1

Key: jihgfedcbaz
Message: abcdefghijklmnopqrstuvwxyz
message   = abcdefghijklmnopqrstuvwxyz
encrypted = jjjjjjjjjjjuuuuuuuuuuuffff(key = jihgfedcbaz)
restored  = abcdefghijklmnopqrstuvwxyz
message equiv to restored (should be true): 1

Key: disneymagic
Message: floridastatemottoisvoteearlyandoften
message   = floridastatemottoisvoteearlyandoften
encrypted = itgembmszivhuggxmusbwvhmsepwmnjwhwmf(key = disneymagic)
restored  = floridastatemottoisvoteearlyandoften
message equiv to restored (should be true): 1

Bonus challenge: There is a much more elegant way to implement vigenereDecrypt, using only one line of code, with a single function call. Can you see it?

What to turn in

You are now done with the Vigenere cypher, great work. Turn in code in the file vigenere.cpp, which should contain the functions letterShift, vigenereEncrypt and vigenereDecrypt. If you were not able to get everything working, the code you turn in should contain as much as you got to work for partial credit. Whatever you turn in, make sure that it compiles with no errors!

Acknowledgements

This problem is adapted from a problem originally due to Prof. Steve Fickas, University of Oregon, whose permission to use it here is gratefully acknowledged.