submission.txt

Jeremy Wright

1. maroonandgold

2. thesundevilcolorsofmaroonandgoldlookgreat

3. the key for breaking your next cipher is right under your nose

4. Key: QWERTYUIOPASDFGHJKLZXCVBNM
THE FIRST COMPUTER TERMINALS SUCH AS THE TELETYPE WERE TYPEWRITERS THAT COULD 
PRODUCE AND BE CONTROLLED BY VARIOUS COMPUTER CODES THESE USED THE QWERTY LAYOUTS
AND ADDED KEYS SUCH AS ESCAPE ESC WHICH HAD SPECIAL MEANINGS TO COMPUTERS LATER 
KEYBOARDS ADDED FUNCTION KEYS AND ARROW KEYS SINCE THE STANDARDIZATION OF PC 
COMPATIBLE COMPUTERS AND WINDOWS MOST FULL SIZED COMPUTER KEYBOARDS HAVE FOLLOWED 
THIS STANDARD THIS LAYOUT HAS A SEPARATE NUMERIC KEYPAD FOR DATA ENTRY AT THE RIGHT 
FUNCTION KEYS ACROSS THE TOP AND A CURSOR SECTION TO THE RIGHT AND CENTER WITH KEYS
FOR INSERT DELETE HOME END PAGE UP AND PAGE DOWN WITH CURSOR ARROWS IN AN INVERTED T SHAPE
EVEN THE KEYBOARD YOU ARE USING TO DECRYPT THIS MESSAGE SHOULD BE A VARIANT OF QWERTY
UNLESS YOU HAVE BUILT YOUR OWN QWERTY IS THE NEW ABCD

Solution:
Initially, I used basic frequency analysis to work out some possible keys. This
resulted in very little.

Next I applied the pattern of hill-climbing from CSE471 using a C++
program and a dictionary of ngrams to evaluate fitness. The basic algorithm
is as follows:

1. Generate a random key.
2. Decipher the cipher text using the random key.  Using the ngram database
   score this "plaintext" This becomes the "parent" node of the hill climbing
   graph
3. Swap 2 letters of the key.
4. Decipher the cipher text using the new swapped key.  Score this. This becomes
   a child node of the graph.
5. If the parent score is greater than the child score, then there is no
   improvement. Stop this branch. Otherwise if the child score is greater, this
   is an improvement. Update the parent key, with this key, and continue.