Background
A permutation cipher is an encryption that uses any permutation of the alphabet to encrypt a message. It resists brute-force attacks (trying all possible keys) because there are 26! keys. This is rather a lot:
26! = 403291461126605635584000000
The weakness of permutation ciphers is that they encrypt each letter individually, and uniformly. This means we can use patterns in natural language to guess what the key is.
In this coursework we will build a tool for working with permutation ciphers. We will be able to encrypt and decrypt messages, and we will attack an encrypted message with a frequency attack. This uses the relative frequency of each letter in the English language to guess a key. Only very rarely will this give the exact key but in many occasions it is close enough that the partially deciphered text gives enough hints on how to complete the key. We will include some simple tools to help finish the job.
Part 1
We will first build a class to store keys, and the functions we will use with them.
A key is any permutation of the alphabet. We will store a key internally as a permutation of the numbers 1 to 26, in a row vector of length 26, but make the display function such that it shows the corresponding letters. The identity permutation, the alphabet, is stored as the vector 1:26, and you can generate a random permutation with randperm(26). The coursework files include a script tests.c with useful tests and test data. The tests use random keys, so you could run them multiple times to be extra sure.
Build a class Key that stores and handles keys. It should have the following:
Properties
- A property perm that stores a key as a permutation on the numbers 1 to 26. It should not store it as a string of letters.
Methods
- A constructor method that takes a permutation p of the numbers 1 to 26 and creates a Key storing that permutation as its perm property.
- A display method that shows a Key as a permutation of the alphabet.
- A method mtimes(l,m) that takes two keys and gives their composition.\
- A method invert(k) that gives the inverse of the key k. For every number x between 1 and 26, if K.key(x) = y then K.invert.key(y) = x.
- A method encrypt(k,m) that encrypts a message (a character vector) m with the key k. First, turn the message into all uppercase. Then apply the key to each uppercase letter in the message, leaving other characters as is. Make sure to convert from the ASCII indices (65-90) of the alphabet to the permutation indices (1-26) and back.
- A method decrypt(k,m) that decrypts a message m with the key k, by encrypting with the inverse key.
Test cases and examples are at the back of this document.
A frequency attack works as follows. Suppose our ciphertext has these letter counts:
252 249 106 271 2 93 334 27 83 54 147 220 143 85 6 91 198 1 75 151 9 57 270 427 290 42
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Sorting this by occurrence count (from small to large), we get:
1 2 6 9 27 42 54 57 75 83 85 91 93 106 143 147 151 198 220 249 252 270 271 290 334 427
R E O U H Z J V S I N P F C M K T Q L B A W D Y G X
We can compare this against the frequency of letters in English (from rare to common):
Z Q X J K V B P Y G F W M U C L D R H S N I O A T E
This tells us that a likely key used to encrypt the ciphertext message is, starting from the most frequent letter, the one taking E X, T G, A Y, etc. To help you implement this, you are provided with a function permutation that, given the letter counts (the first line above), returns the matching permutation of 1 to 26 (second line above). 1
Part 2
We will build a class to try and decrypt a permutation-cipher encoded message. Write a class Attack with the following properties and methods.
Properties
- A property ciphertext that stores the encrypted message.
- A property key that stores a Key object.
Methods
- A constructor method that takes an encrypted message as input, stores it as the ciphertext property, and initializes the key with the identity permutation 1:26.
- A display method that shows the stored key and the first, say, 300 characters of the message, decrypted with the current key. The message is probably too long to display in its entirety (short messages are hard to decode), and displaying it (partially) decrypted shows the progress made thus far in breaking the cipher. Format it nicely, indicating the key and the message (you can use char(13) to create a line break).
- A method lettercount that counts the occurrences of each letter of the alphabet in the ciphertext, and returns them as a 1 * 26 array. Make sure to pre-allocate the return array.
- A method attack that carries out a frequency attack:
- allocate an array with English letter frequencies (see above, or Wikipedia);
- use lettercount to retrieve the letter frequency in the cyphertext;
- use the permutation function to sort the alphabet by (reverse) letter count;
- combine 1. and 3. in the way described above to guess a key.
Your method should return the new Attack object, with the same ciphertext but the new key. You can approach 4. above in two ways: by directly computing the new key (easiest), or by using the invert and composition (*) methods of the Key class (harder but very satisfying).
Tests and examples are at the end of this document. The ciphertext that we will be attacking is in the script ciphertext.c; running it assigns the variable secret.
As was to be expected, the letter frequency of our ciphertext is not exactly that of English in general. The key generated by our frequency attack is off, and the message is still very much illegible. But at the same time, several letters are spot on: in particular the word “the” is complete. We will finish the job by creating a method sample to inspect a random sample of the current decoding in search of familiar words, and a method swap to swap two letters in the key.
Part 3
- Add a method sample to your Attack class that displays a random piece of the ciphertext, decrypted with the current key, of (say) 300 characters in length. Make sure that the sample text is not cut short by reaching the end of the ciphertext. For efficiency, first select the sample and then decrypt it, instead of the other way around (which would decrypt the whole ciphertext). Use the function rand to generate a random value between 0 and 1, and multiply that to get a value in a desired range.
- Add a method swap to your Key class to swap two letters in the key. The function should take a key and two characters as input, and swap the two characters on the input side of the key. That is because we’re using the key to decrypt the message, and we want to swap two letters in the decrypted ciphertext to create recognizable words. So, if k is the key given by the first permutation below, swapping H and P, swap(k,’H’,’P’), should give the second key below.
You may compute the resulting key directly, or by giving the permutation that swaps the two given letters and then composing with the original key using (*). - Add a corresponding method swap to your Attack class, that swaps two letters in the key property by calling the swap method of the Key class.
Part 4
To wrap up, we will polish our functions and add some convenient functionality. One thing we’ll add is undo functionality for the swap function, using a list to store previous swaps. A list class is included with the files you were given. You may re-use code from the tutorials, and any solutions you are given on Moodle, to implement this.
- Edit the constructor for the Key class so that, in addition to the current functionality, calling Key without arguments creates a random permutation key.
- Add a property past to your Attack class, and let the constructor initialize it with the empty list.
- Edit the swap method of the Attack class so that it stores appropriate “undo” information in the past property. Edit the attack method so that it erases any “undo” information.
- Add a undo method that reverts the previous swap, or if there is no undo information, writes an appropriate message and does nothing.
- Use the tools you have built to decrypt the secret message in ciphertext.c. Add the key you’ve found to the ciphertext.c script as the variable theKey (it should be an object of the Key class).
Submission
Submit a zip-file named cw2.zip to Moodle, containing all the relevant c files: include your Key.c and Attack.c classes, your ciphertext.c with the key you found, and the original List.c, permutation.c and tests.c files. Please zip the files directly, and not the folder containing them.