Transposition Cipher Description

One of the most important tools in modern computing is the ability to encrypt data. There are numerous different types of ciphers, including the Caesar cipher (as we discussed in class), the "one-time-pad" (a perfect cipher, but not without issues), public-key ciphers (used in part for virtually all secure web transactions), etc.

In this assignment, you will create a program that encrypts and decrypts text using a "transposition" cipher. In a future assignment, you will write a program that attempts to break your own transposition cipher with brute force and without knowing the key.

A transposition cipher is a method for encrypting a message by transposing the characters in the message by putting the message into a rectangular grid and reading down the columns in an order based on a textual key.

For example, the message "MEET ME AT SEVEN PM IN GATES" (called the "plaintext") with the key "COMPSCI" would be put into a grid like this (with underscores representing spaces):

C O M P S C I
-------------
M E E T _ M E
_ A T _ S E V
E N _ P M _ I
N _ G A T E S

The letters would then be read out in columns, based on the alphabetic ordering of the letters in the key:

C O M P S C I
0 4 3 5 6 1 2

Note: Notice that the alphabetic ordering for duplicate letters puts the left-most letter first. I.e., if a word has duplicate letters, the left-most duplicate letter comes first in the column order. The word MISSISSIPPI would have the following order: {1, 4, 7, 10, 0, 8, 9, 2, 3, 5, 6}, because the first I (column 1) is the first in the alphabet, then the second I (column 4) is next, etc.

The first column that would be read would be M_EN, then ME_E, then EVIS, etc., for a final encryption of:

M_EN ME_E EVIS ET_G EAN_ T_PA _SMT

Without spaces it would look like this:

M_ENME_EEVISET_GEAN_T_PA_SMT

This final output is called the ciphertext, and that is what you can text to your friends without worrying about other people knowing what you are talking about.

To decrypt an encrypted message, you need to know the key, and you can reverse the process to get back the original message. First, put the message into columns based on the length of the key. In the example, the ciphertext has twenty-eight letters, and the key has seven letters, so we know that we will have columns of length four.

C C I M O P S
0 1 2 3 4 5 6
-------------
M M E E E T _
_ E V T A _ S
E _ I _ N P M
N E S G _ A T

Going back to the alphabetic ordering of the key, and putting the current columns under them, this tells us how to re-order the current columns:

C O M P S C I 
0 4 3 5 6 1 2 (key alphabetic order)
0 1 2 3 4 5 6 (ciphertext column order)

The translation from the ciphertext grid columns to the actual output columns is as follows:

ciphertext column      plaintext column
0                  ->        0
4                  ->        1
3                  ->        2
5                  ->        3
6                  ->        4
1                  ->        5
2                  ->        6

In other words, we rearrange the columns like this:

0 4 3 5 6 1 2 
-------------
M E E T _ M E
_ A T _ S E V
E N _ P M _ I
N _ G A T E S

Finally, the original plaintext is read back by reading across the grid by rows, to produce:

MEET_ME_AT_SEVEN_IN_GATES

Implementation details

Your program needs to be able to encrypt and decrypt text using a transposition cipher. First, your program should ask the user if he or she wants to encrypt or decrypt a message. Then, it should ask the user for the text to encrypt or decrypt. Finally, it should ask for the encryption/decryption key. Your program should read a single line of text, then use the key to encrypt or decrypt the text, and then print out the results.

You may use any of the containers we have discussed already to hold the data for the string manipulation. One suggestion would be to hold the entire plaintext in a single string, and then write a function to convert it into columns, each of which is also a string.

Because the plaintext length must evenly divide into the length of the key, if the actual text does not divide the key evenly, you should "pad" your plaintext with a character to make it divide evenly. We will choose a character with the tilde ('~') character (it is defined as a constant, PAD, in the starter code), because it is easy to see and will help debugging. To pad your strings, simply add the padding character to the end of your string until the key evenly divides the length of the string. The pad characters will be present in your encrypted text, and you will remove the padded characters when you decrypt the string.

Notes:

• Because we have used the tilde as a padding character, any tildes that are present at the end of the plaintext will be removed after decryption
• If the user types in a ciphertext whose length is not divisible by the key length, you should "throw an exception" in your program, as follows:

          if (cipherText.size() % key.size() != 0) {
              throw("Ciphertext length is not divisible by key length!");
          }
          

  The "%" operator means "modulus," and it produces the remainder of the first value divided by the second value.
  Throwing an exception actually crashes the program. Many times we would rather alert the user to the illegal data, but in this case, you will crash the program (purposefully!) by throwing the exception. You will do this on many projects for this quarter.

Logs

Log example 1:

Welcome to the Transposition Cipher Machine!
Please choose:
1) encrypt text
2) decrypt text
Please type your choice, 0 to end: 1
Please enter the text to encrypt: meet me at seven pm in gates
Please type in a key: compsci
Encrypted text:

"m enme eeviset gean t pa smt"

Welcome to the Transposition Cipher Machine!
Please choose:
1) encrypt text
2) decrypt text
Please type your choice, 0 to end: 2
Please enter the text to decrypt: m enme eeviset gean t pa smt
Please type in a key: compsci
Decrypted text:

"meet me at seven pm in gates"

Welcome to the Transposition Cipher Machine!
Please choose:
1) encrypt text
2) decrypt text
Please type your choice, 0 to end: 0
Goodbye!

Log example 2 (notice the space at the beginning of the ciphertext!):

Welcome to the Transposition Cipher Machine!
Please choose:
1) encrypt text
2) decrypt text
Please type your choice, 0 to end: 1
Please enter the text to encrypt: Far out in the uncharted backwaters of the unfashionable end of the western spiral arm of the Galaxy lies a small unregarded yellow sun.
Please type in a key: Douglas Adams
Encrypted text:

" rrademxl ~itss r yly~Featahihsewuhtnesalme. doif flul~ne hono  e~ nw ewlG ruocau e asdnt fo s inl~a chbere g taefntraad~hb ntptero~rukel a aas"

Welcome to the Transposition Cipher Machine!
Please choose:
1) encrypt text
2) decrypt text
Please type your choice, 0 to end: 2
Please enter the text to decrypt:  rrademxl ~itss r yly~Featahihsewuhtnesalme. doif flul~ne hono  e~ nw ewlG ruocau e asdnt fo s inl~a chbere g taefntraad~hb ntptero~rukel a aas
Please type in a key: Douglas Adams
Decrypted text:

"Far out in the uncharted backwaters of the unfashionable end of the western spiral arm of the Galaxy lies a small unregarded yellow sun."

Welcome to the Transposition Cipher Machine!
Please choose:
1) encrypt text
2) decrypt text
Please type your choice, 0 to end: 0
Goodbye!

Log example 3 (bad input from user):

Welcome to the Transposition Cipher Machine!
Please choose:
1) encrypt text
2) decrypt text
Please type your choice, 0 to end: 1
Please enter the text to encrypt: I have a dream!
Please type in a key: king
Encrypted text:

"aae~ edmIv ah r!"

Welcome to the Transposition Cipher Machine!
Please choose:
1) encrypt text
2) decrypt text
Please type your choice, 0 to end: 2
Please enter the text to decrypt: aae~ edmIv ah r!
Please type in a key: mlk


***
*** STANFORD C++ LIBRARY 
*** A string exception occurred during program execution: 
*** Ciphertext length is not divisible by key length!
***
*** Stack trace (line numbers are approximate):
*** 0x1097a41ce     decrypt(string, string)
*** 0x1097a2dc1     main()
***

Possible Extra Features:

Though your solution to this assignment must match all of the specifications mentioned previously, it is allowed and encouraged for you to add extra features to your program if you'd like to go beyond the basic assignment. Note that our motivation for allowing extra features is to encourage your creativity, not inflate your grade; so if any points are given for your extra features, they will be minimal. The purpose is to explore the assignment domain further, not to disrupt the class grading curve. Make sure to see the notes below about how to separate your extra code and how to turn it in properly.

Here are some example ideas for extra features that you could add to your program:

• Allow the user to type in multiple lines of plaintext to encrypt: The user can end input with a blank line.
• Allow the user to read in text from a file and write out the ciphertext: We will cover reading and writing of files later, but you can look it up now and implement it if you would like.
• Implement additional types of ciphers: There are hundreds of different ciphers. Look one or more up and implement them.
• Ask the user if they want you to create a strong password for them: Use the random number generator to generate a strong password for the user.
• Mandate that the password must be strong: We all hate it, but lots of websites make you type in a password with "at least two Uppercase, two lowercase, two special characters, etc." See here for a better way to create strong passwords!
• Other: If you have your own creative idea for an extra feature, ask your SL and/or the instructor about it.

Indicating that you have done extra features: If you complete any extra features, then in the comment heading on the top of your program, please list all extra features that you worked on and where in the code they can be found (what functions, lines, etc. so that the grader can look at their code easily).

Submitting a program with extra features: Since we use automated testing for part of our grading process, it is important that you submit a program that conforms to the preceding spec, even if you want to do extra features. If your feature(s) cause your program to change the output that it produces in such a way that it no longer matches the expected sample output test cases provided, you should submit two versions of your program file: a first one with the standard file name without any extra features added (or with all necessary features disabled or commented out), and a second one whose file name has the suffix -extra.cpp with the extra features enabled. Please distinguish them in by explaining which is which in the comment header. Our turnin system saves every submission you make, so if you make multiple submissions we will be able to view all of them; your previously submitted files will not be lost or overwritten.