密碼學/頻率分析

在密碼分析領域，頻率分析是一種用來“破解”簡單替換密碼的方法，不僅僅是凱撒密碼，還有所有單字母替換密碼。這些密碼將明文的字母替換成另一個字母來產生密文，並且在最簡單、最容易破解的密碼中，明文中任何特定的字母將始終轉換為密文中相同的字母。例如，所有的E都會變成X。

英語字母相對頻率圖

頻率分析基於這樣一個事實：某些字母和字母組合在任何特定語言的文字中都以特徵頻率出現。例如，在英語中，E非常常見，而X則不常見。同樣地，ST、NG、TH和QU是常見的組合，而XT、NZ和QJ則非常不常見或“不可能”。鑑於我們所有E都變成X的例子，密文中包含大量X的密文訊息似乎已經表明替換對映中的一對字母。

實際上，頻率分析的使用首先包括統計密文字母的頻率，然後為它們分配“猜測的”明文字母。許多字母出現的頻率大致相同，因此帶有X的密碼可能確實將X對映到R，但也可能將X對映到G或M。但是每種使用字母的語言中，某些字母都會更頻繁地出現；如果密文中X比其他任何字母都多，那麼對於英語明文來說，一個很好的猜測是X代表E。但是T和A在英語文字中也很常見，因此X可能是其中任何一個。它不太可能是一個Z或Q，因為它們在英語中並不常見。因此，密碼分析員可能需要嘗試密文字母和明文字母之間對映的幾種組合。一旦常見的字母被“解決”，該技術通常會繼續分析字母對和其他模式。這些通常具有在許多情況下將不太常用的字母連結起來的優勢，從而填補正在構建的候選對映表中的空白。例如，Q和U在英語中幾乎總是按這個順序一起出現，但Q很少見。

頻率分析對更簡單的替換密碼非常有效，並且可以輕鬆地破解極短的密文。這一事實是埃德加·愛倫·坡在他 1800 年代中期著名的報紙密碼分析演示中聲稱，人類設計出的任何密碼都無法戰勝他。然而，坡對自己的宣告過於自信，因為多字母替換密碼（由阿爾伯蒂在 1467 年左右發明）可以抵禦簡單的頻率分析攻擊。20 世紀前半葉的機電密碼機（例如，赫本機、恩尼格瑪機、日本紫羅蘭機、SIGABA、Typex 等）如果使用得當，基本上可以不受簡單頻率分析攻擊的影響，因為它們本質上是多字母密碼。它們使用其他攻擊方法被破解。

頻率分析首先是在阿拉伯世界發現的，據悉在公元 1000 年左右就已經使用。人們認為，對古蘭經的仔細文字研究首先發現了阿拉伯語的特徵字母頻率，可以用於密碼分析。它的使用範圍不斷擴大，在歐洲國家使用如此廣泛，以至於文藝復興時期密碼學家發明了多種方案來對抗它。這些方案包括在其他單字母替換密碼中使用最常見字母的幾個替代方案（即，對於英語，密文中的 X 和 Y 都可能意味著明文 E），使用幾個字母表——以各種或多或少狡猾的方式選擇（萊昂·阿爾伯蒂似乎是第一個提出這個想法的人），最終發展出這樣的方案：只使用明文字母對或三元組作為“對映索引”到密文字母（例如，由查爾斯·惠斯通在 1800 年代中期發明的 Playfair 密碼）。所有這些試圖抵抗頻率計數攻擊的方案的缺點是，它增加了加密和解密的複雜性，從而導致錯誤。眾所周知，英國外交大臣據稱拒絕了 Playfair 密碼，因為即使像惠斯通和 Playfair 所示的那樣，小學生都可以學會它，“我們的外交官永遠學不會！”

頻率分析需要對明文語言的基本瞭解，以及毅力、一些解決問題的能力以及對大量字母簿記的相當大的耐受性。整潔的筆跡也有幫助。在二戰期間，英國和美國透過在主要報紙上刊登縱橫字謎和舉辦比賽來招募破譯密碼的人，比賽內容是看誰最快能解開謎題。軸心國使用的幾種密碼可以使用頻率分析來破解（例如，日本使用的“領事”密碼）。二戰時期首次使用了字母計數和統計分析的機械方法（通常是 IBM 卡片機器）。如今，字母計數和分析的繁重工作已被計算機的無休止的速度所取代，計算機可以在幾秒鐘內完成這項分析。在現代社會，任何簡單的替換密碼都不能被認為是真正安全的。

頻率分析方法既不是解決密碼的必要方法，也不是充分方法。從歷史上看，密碼分析員在頻率分析方法廣為人知之前很長一段時間內，就使用各種其他分析方法來解決替換密碼。有些人甚至質疑為什麼頻率分析方法被認為在這麼長的時間內有用。 但是，現代密碼在任何情況下都不是簡單的替換密碼。它們比二戰密碼複雜得多，而且不受簡單的頻率分析，甚至不受高階統計方法的影響。最好的密碼必須使用不基於底層明文語言的特殊性的基本數學方法來攻擊。請參閱密碼學/差分密碼分析或密碼學/線性密碼分析作為此類技術的示例。