I'm currently attempting the Matasano Crypto Challenges as a basic intro to cryptography. For solving some of the earlier challenges I utilised n-grams to determine which is going to be the most likely English plain text. It has been quite successful.
I'm up to attempting to break repeating XOR, which involves grouping bytes in their suspected single byte XOR group, and cracking them in this fashion. As this will be disjointed text, it appears I will need to use frequency analysis as opposed to n-grams.
I implemented a basic scoring system (similar to the below source code) source.
function getEntropy(str) {
var sum = 0;
var ignored = 0;
for (var i = 0; i < str.length; i++) {
var c = str.charCodeAt(i);
if (c >= 65 && c <= 90) sum += Math.log(ENGLISH_FREQS[c - 65]); // Uppercase
else if (c >= 97 && c <= 122) sum += Math.log(ENGLISH_FREQS[c - 97]); // Lowercase
else ignored++;
}
return -sum / Math.log(2) / (str.length - ignored);
}
With short cipher texts though I've had the issue that garbled text with more printable ASCII has scored higher than correctly formed English. I.e. FKDASDOFD
may score higher than THE RIVER
, as it's got a space which isn't counted towards its score.
From this, I've been trying to come up with a way of perhaps scoring the letter count against it's expected frequency, while penalising the score for each letter the further it is away from it's expected value according to normal distribution.
For example, a very rough though process of algorithm I'm trying to implement.
1) "a" has a frequency of 8.167%.
2) Evaluate the frequency in the candidate plain text and compare that against the expected value (8.167%).
3) Penalise the 'score' by multiplying it by [1-(std dev cumulative prob)]. For example if it was 1 std dev away from expected, multiply the score by [1-0.68], 3 std deviations, [1-0.997], etc.
4) Add the cumulative score for each letter to evaluate the most likely plain text.
My questions are.
- Is there a better, established, algorithm out there for performing frequency analysis?
- Is it simply the nature of short cipher / plain texts that there will be inherent inaccuracy in evaluating the probability of English plain text?
- Is my proposed method ridiculous / naive / stupid in some way?
Thanks folks, attempting to learn so sorry if there are trivial mistakes or invalid assumptions in this question.
eeeeeee...
. Perhaps it would be best to calculate the sample frequency of each letter and compare those to the expected frequencies. $\endgroup$