初探密碼破譯：Metropolis-Hastings演算法破解密文

解密恐怕是每個人的少年夢，就算是現在每當聽到破譯都會一陣激動。如果你曾經因為衝動去了解過加密密文，你一定聽說過一種加密方法：替代加密

替代加密是一種最簡單的加密方法，簡單的把明文中的每一個字母使用另一個固定字母代替。

使用R模擬實現一個簡單的替代加密演算法，並用三個單詞進行測試：其中紅色框框中框出部分位演算法實現部分。

（替代演算法分為簡易替換密碼、諧音替換法、多表替換加密、表格式替換加密、機械替換加密、一次性密碼本，而本文所討論的是簡單替換密碼中的混合表加密方式）

對於每一種替代加密都有一份替換表，如果我們知道這份替換表，我們只需要簡單的把密文中的每個字母按照替換表進行替換即可；但是當我們拿到一份密文並且沒有替換表的時候我們應該如何破譯這份密碼呢？

現在假設我們有一段標準的通過替換加密得到的的英文密文：nhdg asjc llpgax，同時我們有兩個已知的可能的替換表：

• 替換表1的解密結果：njgh xlij ddsjxe

• 替換表2的解密結果：make does thanku

我們會發現替換表2的結果更像是標準的英文，替換表2解密的結果更像是明文。那麼現在如果我們有無數個替換表，則總有一個替換表是最接近正確替換表的，而這個替換表就是我需要尋找的替換表，破譯問題變成了是優化問題。

如何查找那個最優化的替換表呢？這個時候Metropolis方法就派上了用場：

基本思想是首先從一個隨機的解密規則開始，然後通過多次循環優化它，直到最後它就有可能成為一個正確的解謎規則。

至此我們已經有了尋找最優破譯解法的方法了，但是問題來了：如何通過一個現有的破解規則來得到一個新的破解規則呢？我們不可能盲目的一個一個的隨機產生破解規則，那樣的工作量是不可想像的。

通過Metropolis方法的定義我們知道，Metropolis方法會不斷地對上一個隨機的解密規則做優化，也就是說第二個隨機解密規則是在第一個解密規則上做優化即我們只需要在第一個隨機解密規則上做一點點小小的改動就可以生成下一個隨機解密規則；並且當且僅當新的解密規則解出的解密串比原解密規則解出的解密串更像是標準英語的時候才會用新的解密規則代替原有的解密規則。

破譯的方法思路出來了，緊接著我們就去實現這個解法，實現這個演算法有兩處難點。

• 對前一個隨機解密規則如何改動

• 如何計算解密規則是正確規則的概率

對於第一點，我們只需要改變原始解密規則中的一個字母的對應關係，比如在原始解密規則中a對應b，c對應d，則修改規則把a對應到d，為了保證一個合法的解密規則，我們同時需要把c對應到b

對於第二點，假設對於一個密文，一個隨機解密規則計算出的結果是：njgh xlij ddsjxe，有三個單詞，我們分別計算三個單詞可能為合法單詞的概率。一個單詞為合法單詞的概率，可以通過查詢它在維基百科出現的頻率。

總結以上思路，使用R描述代碼部分截圖如下：

使用單詞"here", "is", "some", "sample", "text"做測試，加密並嘗試解密50000次，解密次數越多可能獲得正確結果的概率越大，得出的計算過程以及每一次的優化的解密規則如下（值得注意的是較小的值可能是正確的解密結果，但是最小的值並不一定是那個正確的解密結果），在45000次左右查找到最接近正確的解密規則，當然在明文中隨著單詞數量的增加破譯的答案會越來越接近正確答案。

本實例為閱讀《機器學習：實用案例解析》書後受啟發寫出，感謝書籍作者，對本案例感興趣想要重新實現本案例的同學也可以閱讀此書，可在公眾號「一個程序員的日常」後台回復關鍵詞「破譯」獲得此書的pdf版本。

更多文章，關註：知乎專欄