Honors Thesis - Automating the Cracking of Simple Ciphers
Abstract
There is little point to enciphering information if one does not wish to keep it secret. If one wishes to keep information secret it follows that others would likely want access to that information. It is easy to come up with many scenarios where one would like secret information to be exchanged publicly. For example, Internet shoppers want their credit card information to be secured. Would-be thieves want access to that information. Ciphers are one method of concealing information. Cryptanalysis can identify vulnerabilities in a cipher that help both to break existing ciphers and to create stronger ciphers that will not exhibit the same vulnerabilities.
This project is an examination of methods used to crack the Vigenère cipher with a periodic key, and how these methods can be optimized. Its goals were to make the process as automated and efficient as possible, to explore different methodologies for the various tasks used and to analyze their runtimes both theoretically and experimentally.
It was found that the Vigenère cipher can be consistently broken in O(N) time. Two methodologies were examined; one used only the Friedman test, and the second used both the Friedman and Kasiski tests. The former consistently determined the correct keyword in O(N) time while the latter ran in O(N2) time and did not consistently find the correct keyword, although it did find it a considerable majority of the time.
Although it is not necessary to use in cracking the Vigenère cipher, the Kasiski test is of particular interest because of its parallels in Computational Biology and data mining. The Kasiski test is also intriguing from an algorithm design and optimization standpoint as it is a difficult algorithm to implement efficiently. This thesis has developed a dynamic programming algorithm to perform the Kasiski test that outperforms the brute force alternative in both runtime and memory utilization.
Downloads
Complete Project (Source code, Thesis and Proposal, zip)
Thesis Proposal (pdf, included in above zip)
Thesis (pdf, included in above zip)
License (txt, included in above zip)