在卡方字元頻率分析中處理垃圾字節
我正在做 Matasano 加密挑戰。在實現了一個簡單的字元頻率評分（有效）之後，我一直在尋找數學上更精確的東西並找到了這個執行緒：Developing algorithm for detection plain text via frequency analysis
雖然卡方分析對我有用，但我遇到了一個問題。如果我遇到不可列印的字元，我目前的程式碼只會將分數設置為無窮大。我想避免這樣做，因為可能的純文字可能包含一些 ascii 不可列印字元。（例如，它實際上是 unicode 並且包含一個希臘詞）但是當我忽略每個不可列印的字元進行評分時，就像我已經對 “.,!\n\t” 之類的字元所做的那樣，我遇到了字元串的問題很少有高分字元和很多垃圾比實際的英文純文字得分更高。
我目前的程式碼如下：（頻率是一個將 ord(character) 與其頻率相關聯的字典，用於 az 和空格）
import frequency import copy from math import inf from string import printable def score_string(inp): exp_dist = copy.deepcopy(frequency.frequency) length = len(inp) for key in exp_dist: exp_dist[key] *= length dist = dict.fromkeys(exp_dist.keys(), 0) for char in inp.lower(): if chr(char) not in printable: # This is the part i like to avoid return inf if char in dist: dist[char] += 1 score = 0 for key in exp_dist: score += (dist[key]-exp_dist[key])**2/exp_dist[key] return score如果我正確理解發生了什麼，我的問題是對於較短的字元串（我使用的範例是 34 個字元），即使是單個低分可列印字元的負面影響也超過了被評分忽略的字元的負面影響很多。
我正在尋找一種優雅的方式來保證非列印字元對分數的影響比任何可列印字元都差，但不要完全忽略它們。
您可能會嘗試的一種方法是通過偽計數應用附加平滑。在最基本的情況下，這可以簡單到將每個字節的次數加 1（或 $ n $ -tuple 或其他）在計算頻率之前出現在您的語料庫中。這允許您計算任何已解密字節字元串的非零（儘管可能非常小）可能性，即使是那些包含從未出現在原始語料庫中的字節的可能性。
因此，例如，如果您從 1,000,000 字節的英文文本語料庫開始，其中字節
e出現 124,319 次，字節出現 0 次，您將這些計數分別增加到 124,320 和 1，並且觀察到的字節總數為1,000,256，然後將計數除以該總數以獲得語料庫中每個字節的平滑頻率（例如，1 / 1,000,256 & 約 0.000000997 的字節）。解釋為什麼這種看似隨意的調整有意義的數學理論有點棘手，但基本上它證明是一種合理的方法來調整從一系列觀察中獲得的機率，以解釋一些罕見但可能的結果可能根本不存在的可能性。在有限數量的觀察中偶然出現。
（特別是，在貝氏統計框架中分析，這個平滑規則結果產生與我們從“平坦先驗”開始得到的相同預期後驗機率，即假設字節頻率的任何分佈都是同樣可能的，並在我們觀察語料庫中的新字節時反复應用貝氏定理來更新這一信念。此外，如果我們確實有理由先驗地相信，即使在查看語料庫之前，某些字節應該比其他字節更有可能，我們可以包括通過分配高於 1 的更可能的字節偽計數來獲取此先驗資訊。）
當然，如果您使用給定的字節/字母頻率表而不是自己編譯，則您必須自己猜測所需的平滑量。但是您仍然可以這樣做：只需將每個頻率乘以某個假定的語料庫大小（例如 1,000），將它們加一，然後（如果需要）重新調整它們的比例，使它們再次相加。