開發通過頻率分析檢測純文字的算法

我目前正在嘗試將Matasano Crypto Challenges作為密碼學的基本介紹。為了解決一些早期的挑戰，我使用 n-gram 來確定哪個是最有可能的英文純文字。它已經相當成功了。

我正在嘗試打破重複 XOR，這涉及將字節分組到他們懷疑的單字節 XOR 組中，並以這種方式破解它們。由於這將是脫節的文本，看來我需要使用頻率分析而不是 n-gram。

我實現了一個基本的評分系統（類似於下面的原始碼）源。

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

對於短密文，儘管我遇到了一個問題，即具有更多可列印 ASCII 的亂碼文本得分高於正確格式的英語。即FKDASDOFD可能得分高於THE RIVER，因為它有一個不計入其分數的空間。

由此，我一直在嘗試想出一種方法，也許可以根據預期頻率對字母計數進行評分，同時根據正態分佈對每個字母越遠離其預期值進行懲罰。

例如，我正在嘗試實現的一個非常粗略的算法過程。

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. 是否有更好的、成熟的算法來執行頻率分析？
2. 是否僅僅是短密碼/純文字的性質，在評估英文純文字的機率時會存在固有的不准確性？
3. 我提出的方法在某種程度上是荒謬/幼稚/愚蠢的嗎？

謝謝大家，如果在這個問題中存在微不足道的錯誤或無效的假設，請嘗試學習非常抱歉。

正如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程式碼來計算 $ \chi^2 $ 對於英文 ASCII 文本：

// 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 $ 如果它們出現在消息中。在實踐中，為了避免這種無限的結果，您可能希望忽略這些字元或為它們分配或多或少任意的小頻率。如果您要從文本語料庫編譯您自己的頻率表，一個合理的選擇是通過將語料庫中每個字元的觀察計數加一來使用附加平滑。

**) 一個自由度失去了，因為字元數的總和顯然必須等於消息的長度，這是先驗固定的。因此，我們不能完全自由地選擇每個字元在消息中出現的次數；選擇了除一個計數之外的所有計數，最後一個計數是由其他計數唯一確定的。

引用自：https://crypto.stackexchange.com/questions/30209