通过频率分析检测纯文本的开发算法

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);
}

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. 

#1 楼

正如otus在评论中所建议的那样，最好先计算解密邮件中每个字母的频率，然后将频率分布与英语文本的预期频率进行比较。可以使用卡方（$ \ chi ^ 2 $）测试。 （实际上，只比较不同解密的可能性，您甚至不需要完整的测试。）为此，首先比较每个字符的实际观察到的出现次数$ N _ {\ rm obs}（c）$解密后的邮件中的$ c $，且该字符在相同长度的英文文本中的预期出现次数$ N _ {\ rm exp}（c）$，即字符的预期频率乘以邮件长度，并计算测试统计量$$ \ chi ^ 2 = \ sum_c \ frac {\ left（N _ {\ rm obs}（c）-N _ {\ rm exp}（c）\ right）^ 2} {N _ {\ rm exp}（c）}，$$，即观测频率和预期频率之间的平方差之和，除以预期频率。 $ \ chi ^ 2 $越小，解密的消息就越类似于英语。*

以下是一些基本的JS代码，用于为英语ASCII文本计算$ \ chi ^ 2 $：

// http://en.algoritmy.net/article/40379/Letter-frequency-English
var english_freq = [
    0.08167, 0.01492, 0.02782, 0.04253, 0.12702, 0.02228, 0.02015,  // A-G
    0.06094, 0.06966, 0.00153, 0.00772, 0.04025, 0.02406, 0.06749,  // H-N
    0.07507, 0.01929, 0.00095, 0.05987, 0.06327, 0.09056, 0.02758,  // O-U
    0.00978, 0.02360, 0.00150, 0.01974, 0.00074                     // V-Z
];

function getChi2 (str) {
    var count = [], ignored = 0;
    for (var i = 0; i < 26; i++) count[i] = 0;

    for (var i = 0; i < str.length; i++) {
        var c = str.charCodeAt(i);
        if (c >= 65 && c <= 90) count[c - 65]++;        // uppercase A-Z
        else if (c >= 97 && c <= 122) count[c - 97]++;  // lowercase a-z
        else if (c >= 32 && c <= 126) ignored++;        // numbers and punct.
        else if (c == 9 || c == 10 || c == 13) ignored++;  // TAB, CR, LF
        else return Infinity;  // not printable ASCII = impossible(?)
    }

    var chi2 = 0, len = str.length - ignored;
    for (var i = 0; i < 26; i++) {
        var observed = count[i], expected = len * english_freq[i];
        var difference = observed - expected;
        chi2 += difference*difference / expected;
    }
    return chi2;
}

如果您只想找到最可能的解密方法，那就是您需要做的。只需按$ \ chi ^ 2 $的升序对解密（和相应的候选密钥）进行排序，然后打印出前几个条目。

如果您还希望估计消息实际为英语的可能性（或者更确切地说，选择频率与英语文本匹配的随机字母可能产生这样的消息的可能性），则还需要确定自由度的数量$ k $用于模型（对于这样的简单模型，它只是明文字母的大小减去一个**），然后将卡方分布积分，得到$ k $的自由度，直到$ \ chi ^ 2 $（或将其与预先计算的表进行比较）。但是仅是为了比较不同解密的可能性，原始的$ \ chi ^ 2 $值就足够了。包括那些实际上不会出现在消息中的消息，对于这些消息，$ N _ {\ rm obs}（c）$仅等于$ 0 $。相反，原则上，未出现在频率表中的任何字符都将具有$ N _ {\ rm exp}（c）= 0 $，因此如果它们出现在频率表中，则得出$ \ chi ^ 2 = \ infty $信息。在实践中，为避免产生这种无限结果，您可能希望忽略此类字符，或者为它们分配或多或少的任意小频率。如果要从文本语料库中编译自己的频率表，一种合理的选择是使用累加平滑，方法是将观察到的语料库中每个字符的计数加1。

**）因为字符计数的总和必须明显等于消息的长度，所以失去了一个自由度，而消息的长度是事先确定的。因此，我们不能完全自由地选择每个字符出现在消息中的次数。选择了一个计数之外的所有计数，最后一个计数由其他计数确定。

#2 楼

我对此线程所做的卑微贡献：为了给一些纯文本加上“英语分数”，我发现巴氏算术系数非常有用：两个统计样本之间的重叠量。系数
可用于确定所考虑的两个样本的相对接近度。


（来自维基百科）

因此，如果您具有英语频率，则可以计算指定明文的字母频率，然后计算BC。比较使用不同密钥解密的纯文本时，此方法可能最有帮助。

在这里可以找到一个很好的示例（不是我自己）-查找englishness函数。 。

#3 楼

可接受的答案是正确的，但是我想添加一个更新，因为对于Matasano加密挑战赛，可接受的答案中给出的频率样本集并不总是那么好。特别是，最好使用空格字符（0x20）的频率。例如，以下数组具有所有26个字母的实验频率，后跟“空格”字符（0x20）：

static double[] expFreqsIncludingSpace = { 
0.0651738, 0.0124248, 0.0217339, 0.0349835,  //'A', 'B', 'C', 'D',...
0.1041442, 0.0197881, 0.0158610, 0.0492888, 
0.0558094, 0.0009033, 0.0050529, 0.0331490,
0.0202124, 0.0564513, 0.0596302, 0.0137645, 
0.0008606, 0.0497563, 0.0515760, 0.0729357, 
0.0225134, 0.0082903, 0.0171272, 0.0013692, 
0.0145984, 0.0007836, 0.1918182} ; //'Y', 'Z', ' '

这是一些示例Java代码，该代码使用频率数组以对任何给定的字符串评分。

public static Double scoreString(String inString){
    String upString = inString.toUpperCase();
    int CHARS_CONSIDERED=27; //all uppercase letters and space
    int[] charCounts = new int[CHARS_CONSIDERED];
    double[] charFreqs = new double[CHARS_CONSIDERED];      
    int totCount = 0;

    for(char c : upString.toCharArray()){
        int index = (int)(c-'A');
        if(index>=0 && index<26){
            charCounts[index]++;
            totCount++;
        }
        if(c==' '){ //considering "space" the 27th letter of the alphabet
            charCounts[26]++;
            totCount++;
        }
    }
    if(totCount==0)totCount=1; //avoid divide by zero

    double chiSquaredScore=0.0;
    for(int i=0;i<CHARS_CONSIDERED;i++){
        charFreqs[i]=((double)charCounts[i])/((double)totCount);            
        chiSquaredScore+=(charFreqs[i]-expFreqsIncludingSpace[i])*(charFreqs[i]-expFreqsIncludingSpace[i])/(expFreqsIncludingSpace[i]);
    }
    return chiSquaredScore;     
}

#4 楼

语言模型

统计上正确的方法称为https://en.wikipedia.org/wiki/Language_model，并且在计算语言学的各种上下文中使用。在给定有关“语言”的假设的情况下，它等于评估特定消息的可能性（技术上，“根据iso-yyyy标准打包的xml消息在此上下文中也算作””）。 >
仅查看单个字母/字节频率时，提到的卡方检验会更好，但是，如果您的处理过程导致需要打分的许多纯文本候选者，那么语言建模领域可以在更广泛的上下文中查看要好得多，如果您有一些希望以纯文本形式看到的示例数据，即使是简单的3或5克模型也可以为您提供更多信息，并且可以轻松地计算出它们。

#5 楼

您还可以使用一些语法来消除误报，例如，葡萄牙语中的字母“ p”或“ b”之前应有一个“ m”，字母“ q”之后应始终有一个“ u”，字母“ l”将是字母或字母“ h”。