Cryptography Tutorial Try it Now! Algorithm Analysis Future Extensions Source Code Sources
This page provides a PRELIMINARY analysis of algorithms used to find the key length and then find the plain text. Due to time constraints, I was unable to perform a solid analysis. As reflected on the "Future Extensions" page, significant more work should be done on this portion of the project to make justified conclusions. Minimally, the following tasks should be completed: analysis on each algorithm individually, determining the breakinig point for each algorithm, comparison between algorithms (space, time, and Big O), and determining the algorithm that should be used based on circumstances/data availablity. Results for Algorithms to Find the Key Length The most accurate algorithm is the Friedman Test, but it is also the slowest. The Shift and Count algorithm is very accurate as well, and takes less time than the Friedman Test. The “Plug it in!” algorithm runs the fastest, which is a logical result considering it is based merely on plugging numbers into a formula, but is only accurate on small keys. The Kasiski Test almost always results in output of the correct key length or a multiple thereof. However, the question is how many possible lengths must the user try before finding the correct one? Said an alternative way, how long is the list of numbers outputted? Results for Algorithms to Find the Plain Text The Permute through All Shifts Algorithm is the most accurate. This is the logical winner since all possibilities are attempted for any given key letter. The Basic Frequency Analysis works okay for small key lengths, but is very inaccurate for large key lengths. The Relative Shifts Algorithm went largely untested because I continually experienced memory issues while executing. Testing the algorithm will require far more computing power (or patience) or reworking of data structures within the program itself. When the matrix can be solved, the results are accurate. The Excel spreadsheet detailing the results on a case-by-case basis can be downloaded, but again, I wish to stress that these results should be considered preliminary. Significant more testing and test cases are required. Download the Results To ensure timing methods are consistent with my results, I would encourage use of the same timing mechanism. I started all timings after pre-processing of the files (after reading the cipher text into the file) but just prior to calling the respective algorithm. The timing class I used is not mine, but can be found at http://oldmill.uchicago.edu/~wilder/Code/timer/ The test files I used are in the following zip file. The original plain text is lettered a - e, the cipher text is indicated by a letter (a - e) and a number (2 - 8) where the letter corresponds to the plain text and the number corresponds to the key used. The key files are titled key# where # is a number in the range of 2 - 8. Download the Test Cases