Lecture 10-2
Cracking the Caesar Cipher
In order to crack a Caesar Cipher you can use the fact that, in English, each letter isn’t used equally. From this you can shift around the letters until you find a shift that fits the distribution of the English language.
As a result of this you should be able to write a program that can guess and decode an English Caesar Shift.
Chi-Squared Score
\[\sum^z_{i=a}{\frac{(\text{freq}_i-\text{english}_i)^2}{\text{english}_i}}\]To check if two frequency distributions are similar you can use the chi-squared score. The lower the output the closer the distributions match.
The algorithm will complete the following tasks:
- Try all 26 possible shifts
- For each one, compute the letter frequency distribution of the decoded text, and the chi-squared score.
- Use the shift with the lowest chi-squared score.
Implementation
View the slides and the source code for the implementation and explanation.