频率分析详解

几个世纪以来,隐藏消息的最佳方法是把字母表中的每个字母换成另一个字母。可能的密钥数量是天文数字,因此这种密码看起来牢不可破。然而,早在 9 世纪,巴格达的一位学者就已经发现了它的弱点:一种语言使用某些字母的频率远高于其他字母,无论怎样替换都掩盖不了这一点。频率分析让密码破译从凭空猜测变成了一种方法,至今它仍是任何人面对新密码时首先尝试的手段。

一张条形图,把密文字母按从最常见到最少见排列,与英语的字母频率相对照,下方是一段密文,其中前几个字母已被解出
一张条形图,把密文字母按从最常见到最少见排列,与英语的字母频率相对照,下方是一段密文,其中前几个字母已被解出

替换密码

简单替换密码按照一张固定的表,把字母表中的每个字母替换成另一个字母:比如 A 变成 Q,B 变成 W,依此类推,每个字母只用一次。这张表就是密钥。凯撒密码只是移动字母表,只有 25 个密钥;替换密码则不同,它可以使用字母的任意排列:共有 26! 个密钥,约 4 × 10²⁶ 个。即使一台计算机每秒测试十亿个密钥,也需要一百多亿年才能把它们全部试一遍。

肯迪的发现

大约在 850 年,阿拉伯哲学家阿布·优素福·肯迪写了一篇关于破译秘密信息的论著,这是已知最古老的频率分析描述。他的建议是:取一篇同一种语言的长文本,统计每个字母出现的频率,再统计秘密信息中的字母,然后一一对应:最常见的对最常见的,次常见的对次常见的。研究《古兰经》的学者们世世代代都在统计其中的字母和词语,这或许就是这一想法的由来。

字母、字母对和单词

在英语中,大约 12.7% 的字母是 E,9% 是 T,8% 是 A,而 Z 在一千多个字母中才出现一次。单个计数只能指出大致方向,在短文本中尤其如此,所以破译者会利用能找到的一切规律。在英语中,单字母词是 A 或 I。最常见的字母对是 TH、HE、IN 和 ER,最常见的双写字母是 LL、EE、SS 和 OO。Q 后面几乎总是跟着 U。一个常见的三字母词很可能是 THE,一旦知道了 T、H 和 E,THAT 和 THERE 这样的词就会迎刃而解。每种语言都有自己的指纹:在德语和荷兰语中 E 更占优势,而在葡萄牙语中 A 位居首位。

女王的致命密码

1586 年,被囚禁在英格兰的苏格兰女王玛丽与安东尼·巴宾顿互通密信,后者正密谋营救她并刺杀女王伊丽莎白一世。这些信件藏在啤酒桶里偷运出去,却都经过了伊丽莎白的间谍首脑弗朗西斯·沃尔辛厄姆之手,他手下的密码破译者托马斯·菲利普斯用频率分析破解了这种密码:那是一种替换密码,另为常用词添加了一些符号。解密后的信件证明玛丽参与了这一阴谋,她于 1587 年 2 月被处决。

隐藏频率

密码设计者展开了反击。同音替代密码给常见字母各分配几个符号,使每个符号出现的频率大致相同。虚码,即毫无意义的符号,被散布在文本中,以扰乱计数。真正的对策来自多表替代密码,例如 16 世纪的维吉尼亚密码,它在加密过程中不断切换多套字母表,使同一个明文字母变成许多不同的密文字母。它一直屹立不倒,直到 19 世纪查尔斯·巴贝奇和弗里德里希·卡西斯基展示了如何求出密钥的长度,再对每套字母表分别进行频率分析。

计算机如何破解密码谜题

程序同样无法尝试每一个密钥,但它可以攀登。它从一个猜测出发,根据结果有多像该语言来打分(通常看其中两到四个字母的组合有多常见),然后交换密钥中的字母对,保留每一次能提高得分的交换。当任何交换都无济于事时,它就把密钥打乱,重新开始攀登,并保留最佳结果。这种方法称为爬山算法,能在不到一秒内破解几百个字母的替换密码,它的各种变体还破解了一些令人们束手无策长达数百年的历史密码。

频率分析的今天

像 AES 这样的现代密码被设计成让密文看起来完全随机:每个字节值出现的频率都相同,同一条消息每次加密的结果都不一样。频率分析对它们无从下手。尽管如此,这一思想仍在延续:语言统计有助于判断解密是否正确,破解谜题和密室逃脱中的密码,以及解读在档案馆中发现的古老加密信件。2023 年,苏格兰女王玛丽失传了几个世纪的信件在计算机的帮助下被破译。

动手探索

打开频率分析工具,获取一段用英语、德语、法语、西班牙语、意大利语、葡萄牙语或荷兰语写成的加密段落。在图表中把字母计数与该语言进行比较,利用字母对、双写字母和短词等线索,逐个字母填写密钥。卡住时,“提示”和“检查”可以帮忙,而求解器则展示爬山算法如何完成工作。

常见问题

为什么 E 是英语中最常见的字母?

因为它出现在许多最常用的英语单词中,例如 THE、BE、HE、WE 和 ARE,也出现在 -ED 和 -ES 这样的常见词尾中。大多数欧洲语言都是如此:在法语、德语、荷兰语和西班牙语中,E 同样位居首位。

频率分析能破解任何密码吗?

不能。它能破解的是每个明文字母总被同一个符号替换的密码。在加密过程中不断改变替换方式的密码,或者作用于比特而非字母的现代密码,需要别的方法,或者根本无法破解。

什么是密码谜题?

用简单替换加密的一句名言或句子,印出来供读者手工破解。自 19 世纪以来,密码谜题就一直出现在报纸上,其解法与本工具展示的完全一样:从短词和最常见的字母入手。

苏格兰女王玛丽失传信件的破译是怎样进行的?

2023 年,乔治·拉斯里、诺伯特·比尔曼和Satoshi Tomokiyo确认,法国一家图书馆中的 57 封加密信件出自她手。这种密码使用了近 200 个符号,因此他们把计算机爬山算法(它推测出许多符号的可能含义)与对其余部分细致的手工破译结合了起来。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

打开频率分析工具