Mathematica可以讓您感覺自己像個計算超人。帶著這種態度和一些小學生的密碼學知識，我本周將注意力轉向了密碼破解，結果卻發現了埋藏的氪石。

密碼的弱點（您用相同的不同字母交換消息中出現的每個特定字母）是它們不會改變字母的模式。利用這一事實的最簡單的攻擊是頻率分析。英語中最常見的字母是“e”，因此編碼消息中最常見的字符（假設消息是用英文寫的）將對應于“e”。依此類推。

當伊麗莎白女王的間諜大師使用頻率分析破解瑪麗的密碼時，蘇格蘭的瑪麗女王失去了她的頭。我想，如果 16 世紀的間諜可以手工完成，我應該能夠在大約 10 分鐘內在Mathematica中將其自動化。

讓我們開始吧。首先，我想生成隨機測試密碼。

在這篇文章中，我將研究最簡單的情況，將自己限制在大小寫相同（即“e”和“E”）并映射到相同符號的密碼中，標點符號和空格不編碼。對于更大的字符集，該方法將是相同的。這是 4 X 10 26 種密碼之一：

使用此密碼對消息進行編碼非常直接，我不會費心創建函數：

如果您知道編碼密鑰，則逆向過程是微不足道的。（這是密碼的另一個弱點，您需要安全的密鑰交換）。

好的，兩分鐘后，密碼就實現了。現在讓我們編寫頻率攻擊代碼。首先，我們需要將文本中的字母按頻率順序排序。

現在我們需要破解密碼，就是將按頻率排序的消息中的字符與一些校準文本中的字母配對，也按頻率排序。通過不對頻率順序進行硬編碼，只要您提供正確語言的校準文本，此代碼將適用于其他語言。如果您有來自原作者的示例文本，它還會考慮寫作風格。

就是如此——密碼破解頻率分析只用幾行代碼就實現了！讓我們測試一下。我將對《傲慢與偏見》的前 10,000 個字符（小寫）進行編碼。

對于校準文本，我將使用本書的最后 341,000 個字符（大約一半）。

這是我們猜測的密鑰：

這是解碼的消息：

氪石！超人跪了！為什么這不起作用？

經過一些調試焦慮和一些實驗后，我終于明白了，我學生時代的理論——破解密碼多么容易——并不像人們說的那么容易。我對學校數學老師的欽佩之情再次受到打擊！問題是一些字母之間的頻率差異小于 1%，但這些字符在 10,000 個字符樣本上的頻率的標準偏差可能高達 0.5% 左右，這使得一個字母很可能出現在頻率順序中的錯誤位置。讓我們在“s”和“r”處尋找示例。我們可以從文本中的連續樣本中得出概率分布。

如果我們看一下“s”和“r”，與它們的標準偏差相比，它們的頻率非常接近。

使用這些分布，我們看到更常見的字母“s”實際上只會在 54% 的時間內排名出現在“r”之前。換句話說，頻率分析有 46% 的時間是錯誤的。

當您累積所有排序錯誤的可能性時，頻率分析實際上完全解碼您的消息的可能性變得非常小。隨著示例文本長度的增加，情況幾乎沒有改善。即使我使用了整本書的前半部分，結果也令人費解。那有多大用處？

但是氪石從來沒有完全阻止過超人。當我仔細查看解碼后的文本時，我意識到有些字母實際上是正確的。

我們信息的第一個詞應該是“chapter”，頻率分析已經正確地找到了“……ter”。也許頻率分析的效果比看起來的要好。我怎樣才能取得進一步的進展？想到了兩種方法：

? 1）使用進一步的頻率分析——字母對的頻率（“th”、“sh”、“ed”在英語中會很高），包括雙字母（“oo”、“ee”、“tt”等）；單詞首字母和單詞尾字母的頻率；按單詞長度劃分的頻率（例如，一個字母的單詞主要是“I”和“a”）；等等。有很多方法可以對數據進行切片。

? 2）我們的字母順序可能有誤，但可能很接近；我們可以嘗試擾亂順序——稍微上下移動字母，看看是否能改善結果。

但最終兩個方法我都沒有使用。對于這兩種方法，我都需要一種方法來解決相互矛盾的建議。一個明顯的答案是查看結果中有多少有效的英語單詞。如果兩種方法對字母映射的內容給出兩種不同的建議，我們將采用一種可以提高消息中有效單詞數量的方法。

這是一個提取字典中沒有的所有單詞的函數。（請注意，從這一點開始，我沒有對標點符號進行編碼很重要。在現實世界中，我需要確定子字符串是否有效，而不僅僅是整個單詞，并且需要不同的標點符號方法。）

此時，面對比我計劃的要多得多的工作，我想到我們可以采用更簡單的方法對文本進行拼寫檢查，并對建議的更正使用此改進測試。好的，比拼寫檢查稍微復雜一點，但這是基本概念。

對于每個無效詞，我們得到相同長度的字典詞列表……

...并在EditDistance 中找到最近的。如果有幾個同樣接近，那么我們會忽略它們，因為我們更有可能在已經是猜測的過程中給自己提供虛假信息。

選擇最接近的已知單詞后，我們對齊字符并刪除匹配的字符，以便我們進行更正。然后我們將這些變成替換規則。

下一步是采用我們通過這種方式發現的所有建議的更正規則，并根據它們的常見程度對它們進行排序。嘗試應用相互矛盾的規則是沒有意義的，所以我刪除了所有與流行建議映射到或來自相同字符的不太常見的規則。

其中一些建議的替代品是正確的，并且會改善情況；有些是虛假的，讓事情變得更糟。我的直覺是受歡迎的建議會比不受歡迎的建議好，所以我下一步是取最流行的n條建議，應用它們，并計算無效詞的數量。然后我們選擇最小化剩余無效詞的n。

這不是我打算創建的簡單代碼，而且我已經超過了我的 10 分鐘目標，但令人高興的是，這種密碼通常能很好地處理1萬個字符的文本，盡管它可能取決于它試圖破解的密碼。

憑借超能力支持的一點獨創性，我們的計算超人擊敗了他的敵人！