密码学/频率分析

在密码分析领域，频率分析是一种用来“破解”简单替换密码的方法，不仅仅是凯撒密码，还有所有单字母替换密码。这些密码将明文的字母替换成另一个字母来产生密文，并且在最简单、最容易破解的密码中，明文中任何特定的字母将始终转换为密文中相同的字母。例如，所有的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 卡片机器）。如今，字母计数和分析的繁重工作已被计算机的无休止的速度所取代，计算机可以在几秒钟内完成这项分析。在现代社会，任何简单的替换密码都不能被认为是真正安全的。

频率分析方法既不是解决密码的必要方法，也不是充分方法。从历史上看，密码分析员在频率分析方法广为人知之前很长一段时间内，就使用各种其他分析方法来解决替换密码。有些人甚至质疑为什么频率分析方法被认为在这么长的时间内有用。 但是，现代密码在任何情况下都不是简单的替换密码。它们比二战密码复杂得多，而且不受简单的频率分析，甚至不受高级统计方法的影响。最好的密码必须使用不基于底层明文语言的特殊性的基本数学方法来攻击。请参阅密码学/差分密码分析或密码学/线性密码分析作为此类技术的示例。