From UBC Wiki

Playfair Cipher Solver

Authors: Alyssa Zhao, Seiyoung Ahn

What is the problem?

The Playfair cipher is an encryption technique popularly known as the first practical digraph substitution cipher. It is significantly harder to break when compared to simpler substitution ciphers such as the Caesar cipher or the Vigenère cipher, since common cryptanalysis methods such as frequency analysis are not easily applicable. The Playfair cipher uses a keyword or phrase contained within a 5 by 5 table of characters to encode a given piece of plaintext. A detailed description of the encryption process can be found here.

For this project, we will implement a Haskell program that will allow the user to encode a given piece of plaintext using the Playfair cipher. Our program will also be able to decode a given piece of ciphertext when provided with the correct keyword.

What is the something extra?

In addition to providing a Playfair cipher encoder and decoder, we also plan on implementing a Playfair solver to break a given piece of ciphertext without knowing the key. This will likely involve the use of machine learning strategies such as hill-climbing and simulated annealing.

What did we learn from doing this?

With regards to the encoding and decoding portions of this project, we found that Haskell allowed us to manipulate various data structures with relative ease and with fewer lines of code; features such as list comprehension were especially useful. We learned about Haskell's implementation of random numbers, and how it is interconnected with IO. In comparison to other languages, such as Java, Haskell's use of IO in generating random numbers may have performance consequences in cases where large amounts of random numbers are being generated. We hypothesize that this may be one of the factors contributing to the sub-optimal run times associated with our Playfair solving algorithm. The algorithm we utilized involved frequent look-ups to obtain the scores corresponding to certain sub-strings. Our first implementation of this data structure was done using Map, which performs on the order of O(lg n) for a single lookup. In order to increase performance on this front, we decided to use HashMap instead – this allowed us to perform single look-ups in constant time. Although our current implementation of the Playfair solver may not be entirely practical, due to its long run-time, we were able to build a working solver without an excessive amount of redundant code; further performance optimizations may lead to a more efficient and effective Playfair cipher solver.

Links to code etc