密码故事(上)

西蒙・辛格的《密码故事》生动有趣、引入入胜,但中文译本存在多处人名前后翻译不一致的现象,且原著中关于针孔加密法的示例也完全丢失,建议有条件的同学尽量阅读英文原著《The Code Book》。

本文对于专用词汇的翻译不仅做了统一,索性和通用的翻译对齐,所以和中文译本里的译名可能有出入。共有上、中、下三篇,各篇链接及包含内容如下:

  • 上篇:单字母替换密码,多字母替换密码。
  • 中篇:加密的机械化,恩格玛机及其破解,象形文字和楔形文字的破解。
  • 下篇:公开密钥,PGP,量子密钥分发。

单字母替换密码

隐文术:通过把信息隐藏起来的这种秘密通信称为 Steganography(隐文术),由希腊词 Steganos(意为「覆盖」)和 Graphein(意为「写」)派生而来。

希罗多德(Herodotus)以编年史的形式记载了公元前 5 世纪希腊和波斯之间的冲突,其中提到住在波斯的希腊人德马拉图斯(Demaratus)利用已上蜡的一副可折叠的刻写板,先将蜡刮去,再将波斯的阴谋刻写在木板的背面,然后再涂上蜡盖住消息,从而将信息秘密地传递给希腊人。得到警告的希腊人开始武装自己,并最终在波斯人进攻时佯装被包围,并诱使波斯船队进入海湾,运用策略打败了波斯。

希罗多德还讲述了希斯塔亚乌斯(Histaiaeus)的故事:希斯塔亚乌斯想鼓励米勒图斯(Miletus)的阿里斯塔哥拉斯(Aristagoras)反叛波斯国王,为了秘密地传达他的指示,希斯塔亚乌斯剃光了他的一个信使的头发,将信息写在其头皮上,再等信使的头发重新长起来,很明显这段历史时期发生的还不是什么紧急事件。这个信使显然不用携带任何异物,能够自由穿行,不会有麻烦。一旦到达目的地,他就剃光头发,指给联络人看。

中国古代将信息写在小块丝绸上,塞进一个小球里,再用蜡封上,然后让信使吞下这个蜡球。

16 世纪,意大利科学家乔瓦尼・波塔(Giovanni Porta)描述了如何将信息隐藏在一个煮熟的鸡蛋里:把少许明矾和一点醋混在一起制成一种墨水,再用这种墨水将信息写在鸡蛋壳表面。墨水溶液就会经蛋壳上的微孔渗透进去,在已凝固的鸡蛋白表面留下印迹,这样只能剥去蛋壳后才能读取。

早在公元 1 世纪普林尼(Pliny the Elder)就解释了体液如何用作隐形墨水。用体液写的字晾干后即变得透明,但轻轻地加热就能把液体烤焦,从而字迹就以棕色显现出来。许多有机液体都有这样的性质,因为它们富含碳因而很容易被烤焦。事实上,即使是现代间谍也很少知道在标准配备的隐形墨水用完之后还可以用自己的尿液来临时代替。

密码术:在隐文术发展的同时,还有另一种方法也在演化,那就是 Cryptography(密码术),从希腊词 Kryptos(意为「隐藏」)派生而来。密码术的目的不是隐藏信息本身,而是要隐藏它的意思,也就是一种加密的过程。

隐文术和密码术常常混合使用。例如,二战期间流行的微粒照片是一种隐文术。德军在拉丁美洲的间谍将一页文件缩小在直径不到 1 毫米的微型照片上,看上去就是一个点,再将这个点状照片贴在看似无关紧要的一封信的某个句号上面。这种微型照片在 1941 年第一次被美国联邦调查局发现后,德军间谍开始有所防范,在缩小之前,将照片中的信息打乱。

密码术分为两种,即移位和替换。在移位中,字母不变,位置改变;在替换中,字母改变,位置不变。

移位:在《S. 中使用的加密法》中提到的「栅栏加密法(Rail fence cipher)」就是移位加密法的一种。另一种移位形式是早在公元前 5 世纪就出现在斯巴达的称为「Scytale」的装置,外形是一根棱形木棍,外面缠绕着一条皮革或羊皮纸。发送人先沿着木棍纵向在条带上写上信息,然后再解开条带,那么从条带上就看到一些无意义的字母,信息已被打乱了,信使就可以带着这条皮带,如果再来点隐文术的手段,他可以将其伪装成腰带系在身上,而信息却写在反面。复原信息时,接收者只需简单地把条带绕在一根木棍上,其直径应和发送者使用的一般大。Scytale 如下图所示(图片来自 Scytale):

替换:与移位并列的密码术是替换。关于替换加密的最早描述出现在《爱经》中,这是由婆罗门学者写于公元 4 世纪的一篇文章,但根据手迹来看,可追溯到公元前 4 世纪。《爱经》建议女人应学会 64 种技术,如做饭、穿衣、按摩和制备香水,还包括一些如咒术、象棋、装订和木工之类的不太常见的技术。第 45 种是密文术,其中介绍的一种方法就是先随机地将字母两两配对,然后将原始信息中的每一个字母用它的配对者来代替。这种形式的密文叫做替换密码。

恺撒移位密码:恺撒频率地使用密文,其中最著名的是简单地将信息中的每一个字母用字母表中的该字母后第三个字母代替,即密码表和明码表相比后移了 3 个位置。

密码的定义及密钥的重要性:一个密码是指任何形式的一种隐秘的替换,其中每个字母都被另一个字母或符号代替。每个不同的密码都代表着一种加密方法,包括算法和密钥两个元素,这两个元素描述了每种加密的精确细节。和算法相对立,密钥的重要性是密码术中永久的一项原则。对此,1883 年,荷兰语言学家奥古斯特(Auguste Kerckhoffs von Nieuwenhof)在其所著的《密码学》一书中作了权威性的陈述:一个密码系统的安全性不在于对加密算法进行保密,而仅在于对密钥的保密。称为科克霍夫原则(Kerckhoffs’s principle

除了对密钥保密外,一个安全的密码系统也必须有一个大范围的可供选择的密钥。在保证密钥数量的同时,密钥的简单性也很重要。因为密钥是发送者和接收者所共知的,密钥越简单,误解的机会就越小。可不通过随机地重排明码字母表来得到密码表,而是选择一个关键词或关键词组,先将其中的空格和重复字母去掉,然后将其作为密码表的前部分密码字母,至于后部分,先将明码字母表中在关键词组出现过的字母去掉,再按顺序接在其后。这种构建密码表的方法在《S. 中使用的加密法》的波雷费加密法和虚无加密法中都有应用。

以上所有替换密码都属于单字母替换密码(monoalphabetic substitution cipher)

尽管不知道是谁发现字母频率的差异可用于破译密码,但是 9 世纪的科学家阿尔・金迪(Al-Kindī)对该技术做了最早的描述。他被誉为「阿拉伯人的哲学家」,他最伟大的著作直到 1987 年才在伊斯坦布尔被发现,名为《关于破译加密信息的手稿》,书中含有对统计学及阿拉伯语法的详细讨论。阿尔・金迪的密码破译方法应用于英语可解释为:首先研究一篇或几篇一定长度的普通英文文章,建立字母表中每个字母的频度表(英语中 E 是最常见的字母,其次是 T、A 等等),然后检查待解决的密文,计算出其中每个字母的出现频率。如果密文中最普遍的字母是 J,那么它很可能就是用来替换 E 的字母;如果密文中第二高频的字母是 P,那么它可能是 T 的替换字母等等。阿尔・金迪的技术被称为「频度分析(frequency analysis)」,它表明了没有必要去检验数亿条有可能的密钥,相反,通过简单的分析密文中每个字符的出现频率就有可能揭示出一条被混乱的信息。

然而不可能无条件地应用阿尔・金迪的方法来破译密码,因为标准频率仅是个概数,不会精确地与每一篇文章的频率相符。1969 年法国作家乔治斯・佩雷克(Georges Perec)写了一本 200 页的小说《逃亡(La Disparition)》,其中没有一个含有字母 e 的单词。更令人称道的是英国小说和评论家吉尔伯特・阿代尔(Gilbert Adair)成功地将《逃亡》翻译成英文,而其中居然也没有一个字母 e。阿代尔将这本译著取名为《真空(A Void)》。由于英文字母中最常见的字母完全没有出现,因而如果将这整本书根据单字母替换密码而进行加密的话,那么天真地试图去解密它将会受到极大阻碍。

阿特巴士(atbash)加密法:在《旧约全书》中有几页文章通过阿特巴士法进行了加密,其原理是取一个字母,指出它位于字母表中正数第几位,再把它替换为从字母表倒数同样的位数后得到的字母。在英文中,例如字母 a 使用字母 z 代替,字母 b 则被 y 替换等等。阿特巴士(atbash)这个名称本身就是这种它所指的替换密码,因为其中 a 和 t 分别指希伯来字母表中的第一位字母 aleph 和倒数第一位字母 taw,而 ba 和 sh 则代表字母表中的第二位字母 beth 和倒数第二位 shin。

现知的第一本描述密码使用的欧洲书籍是于 13 世纪由英国圣方济会的修道士和博学家罗杰・培根(Roger Bacon)所写。该书名为《密文其实并不神奇》,讨论了七种将信息保密的方法,并提醒道:「不用隐秘的手法写一条密文的人是愚蠢的。」

14 世纪的杰弗里・乔叟(Geoffrey Chaucer)不仅在文学上有所成就,也是个天文学家和密码编码学家。在早期欧洲著名的几个有关密码的例子中,其中一个就是他的杰作。在他的《星球概述》一书中,他附加了题为《星球的赤道》的附录,对其中几段进行了加密,将明文中的字母用符号来代替,例如 b 变成了 δ,本质上相当于传统的单字母替换。

到了 15 世纪,欧洲的密码编码术已经是一种蒸蒸日上的行业了。作为文艺复兴的心脏,意大利的几个自治城邦之间的外交大使之间相互发送的信息,都由专门的密码机构完成,每个大使都有一个密码助理。

欧洲第一位伟大的密码破译家是乔瓦尼・索罗(Giovanni Soro),他在 1506 年被任命为威尼斯人的密码助理。索罗的名气响遍整个意大利,友好城邦都会将截获的信息送到威尼斯交给索罗破译。在欧洲其他地方,一些宫廷也开始雇用有能力的密码破译者,如费利波特・巴布,法国国王弗朗西斯一世的密码破译家。巴布因其非凡的的执着而著名,为了破解被截获的信息,他能日夜工作达数星期。但不幸的是,这使得国王有足够机会与巴布的妻子长时间私通。到了 16 世纪末,随着弗朗索瓦・韦达(François Viète)的加盟,法国人进一步加强了其破解密码的能力。韦达对破解西班牙的密码情有独钟。

对单字母替换密码的几个改进,但效果并不好:

  • 引入空符号:在密文中插入不使用的符号,其频率不定,用以干扰频度分析。
  • 有意拼错几个单词:同样用于干扰频度分析。
  • 引入代码:以单词为单位,将每个单词用另一个不同的单词或符号替换。有两大缺陷:密码表过于庞大,变成上百页的密码簿,编码困难;密码簿被截获后,重新编辑和分发密码簿非常痛苦。

玛丽女王与巴宾顿计划(Babington Plot:苏格兰玛丽女王被英国伊丽莎白女王囚禁多年,年轻的安东尼・巴宾顿(Anthony Babington)与其他天主教同道密谋营救玛丽女王、谋杀伊丽莎白女王并取而代之。巴宾顿与玛丽女王通过同为天主教徒的吉尔伯特・吉法德(Gilbert Gifford)互传密信,岂料吉法德是双重间谍,他同时为伊丽莎白女王的首席秘书弗朗西斯・沃尔辛厄姆爵士(Sir Francis Walsingham)效力,实际上正是沃尔辛厄姆派吉法德设法接近巴宾顿所在的组织。巴宾顿与玛丽女王的每条信息,都被吉法德拿给沃尔辛厄姆,由其专门负责伪造的手下拆开并复制,再用同样的邮票封好原信后交回吉法德。

巴宾顿使用的密码不是简单的单字母替换密码,而是一种代码与密码的组合,它包括 23 个用来替换字母表中字母的符号(不包括 j、v 和 w)和 35 个代表单词或词组的符号,另外还有四个空符号和一个类似 σ 的符号,它们表示其后所接的符号代表一个双字母(下图来自 Babington Plot):

沃尔辛厄姆在伦敦建了一座密码学校,并雇用托马斯・菲利普斯(Thomas Phelippes)作为他的密码助理。菲利普斯破译了巴宾顿和玛丽女王之间的信,在最后阶段甚至根据沃尔辛厄姆的命令,在玛丽女王的信后伪造了一个附言,诱使巴宾顿报出所有参与者的名字。最终,巴宾顿和他的 6 个同伙都被抓捕并被砍头,玛丽女王也同样被送上了断头台。

苏格兰玛丽女王的密码清楚地说明了使用一个脆弱的密码有时比完全不用密码还糟糕。玛丽女王和巴宾顿之间毫无顾虑地直接交流计划,因为他们相信他们的通讯是安全的。而如果他们公开地通信,他们将以一种更谨慎的方法来提及他们的计划。而且,他们对其密码的信任使得他们特别轻易地接受了菲利普斯的伪作。发送者和接收者对他们密码的隐秘性是如此地相信,以至他们认为敌人是绝不可能模仿他们的密码来加入这一段伪造的密文进去。正确使用一个牢固的密码当然会有利于发送者和接收者,但错误使用一个脆弱的密码却会使人对安全性产生一种错觉。

多字母替换密码

单字母替换密码在频度分析面前显得非常脆弱,迫切需要编出一种更强大的新密码。15 世纪佛罗伦萨的博学者里昂巴蒂斯特・阿尔伯提(Leon Battista Alberti)建议用两个或两个以上的密码表,在将信息译成密码时交替使用,以迷惑一些密码破译师,称为「阿尔伯提密码(Alberti cipher」。

在阿尔伯提想法的基础上,布莱兹・德・维热纳尔(Blaise de Vigenère,又译作「布莱斯・德・维吉尼亚」)编出了一个系统的、更为有效的新密码,称为「维热纳尔密码(Vigenère cipher)」。其长处在于使用的是 26 个不同的密码表而不是单一的密码表来加密信息。加密的第一步是构造如下的维热纳尔方阵(图片来自 Tabula recta):

然后选用一个关键词,对应明文的长度,一遍一遍地拼写关键词,直到明文中的每个字母都对应于关键词中的某个字母。然后将关键词字母所在行、明文字母所在列的字母作为密文字母,重复上述过程即完成加密过程。维热纳尔有两个优点:

  • 不惧怕频度分析。密文的相同字母可能对应不同的明文字母,同样地,明文的相同字母可能对应不同的密文字母,频度分析不再有效。
  • 具有数目众多的密钥。可使用字典中任一个单词,或单词组合,或者虚构的词作为关键词。

1586 年,维热纳尔出版了一本关于密文的书《密码理论》(同一年,托马斯・菲利普斯正在破解苏格兰玛丽女王的密码),但在接下来的两个世纪里,维热纳尔加密法并没有得到广泛的应用。由于其过于复杂,并不适用于需要速度和简便的军事通讯中。阿尔伯提密码和维热纳尔密码都属于「多字母替换密码(Polyalphabetic substitution cipher)」。

同音替换密码(Homophonic substitution:每个字母有不同数量的替代者,替代者的数量与每个字母的频率成正比。例如,字母 a 在书面英语中大约占到 8% 的比例,因此可以分配 8 个符号来代表它。明文中出现的每个字母 a 在密文中可以被 8 个符号中的任一个替换,因此在加密完成之后,每个符号将占到密文的 1%。同样,字母 b 在英语中大概占 2%,因此分配两个符号代表它,依此类推。

可根据英语中每个字母的特性找到破译同音替换密码的线索。例如,字母 q 的后面只能接一个字母就是 u。如果我们正在尝试破解一篇密文,我们知道字母 q 在英文中相对少见,因此很可能只有一个符号来代替它。我们也知道字母 u 在英语中大概占 3% 的比例,因此可能有三个符号可以用来替换它。因此如果我们发现密文中一个符号后面总是跟着三个特定的符号,那么我们有理由猜测这个符号代表的是 q,而其他三个符号表示 u。密文中的其他字母也可根据它们彼此之间的关系慢慢破译出来。

同音替换密码本质上是单字母替换密码,因为虽然一个明文字母可表示成多个符号,但每个符号只能表示一个字母。另外,一旦密码表被确定,那么在整个加密过程中它是保持不变的,尽管每个字母有几个加密选择。而多字母替换密码在加密时必须不断地在不同的密码表之间来回切换。

路易十四的大密码(Great Cipher:由一对父子发明:父亲安东尼・罗西格诺(Antoine Rossignol)和儿子博纳凡托・罗西格诺(Bonaventure Rossignol)。对他们能力一个最好的说明就是由他们名字形成的单词成为法国人的一个俚语,这是用来表示撬锁的一种装置,意在影射他们破解密码的能力。

罗西格诺父子发明的大密码在他们去世后就停止了使用,它的具体细节也很快失传,使得法国文档里的加密文件不能再被读懂。直到 19 世纪末,法国军事密码机构著名的专家埃提恩尼・巴泽利斯(Étienne Bazeries)才破译出大密码。在某一页出现多次的数字(124-22-125-46-345)经过巴泽利斯的分析被认为是代表 les-en-ne-mi-s,意为「les ennemis(敌人)」。由此衍生出的音节插到密文中,像填单词游戏一样更多的单词被猜出,又可以确定更多的音节,这些音节又可以推出其他的单词等等。也有特殊情况,有时一些数字代表的是单个字母而不是音节,有时一个数字既不代表一个音节,也不代表一个字母,它的存在仅仅是用来删除前面一个数字,部分编码表如下所示(图片来自 Great Cipher):

到了 18 世纪,密码破译术已相当盛行,通常是政府的几组密码破译者一起工作。每个欧洲政权都拥有自己的密室——破解密码和收集情报的中枢。最有名的、也最有组织和效率的密室是维也纳的勘兹雷(Geheim Kabinets-Kanzlei)。密室的存在及电报的发展,使得单字母替换密码不再安全,密码编码者最终不得不采纳更复杂并且更安全的维热纳尔密码。

摩斯电码(Morse code)本身并不是某种形式的密码,因为对信息而言没有任何隐藏。点和短横仅仅是用来表示字母的一种便捷方法。摩斯电码事实上就是另一种形式的字母表(图片来自 Morse code):

巴比奇破解维热纳尔密码:查尔斯・巴比奇(Charles Babbage)是一个性情古怪的天才,他最著名的成就是建立了现代计算机的理论框架。他成功地破解了维热纳尔密码,完成了一次自 9 世纪阿拉伯学者提出频度分析破解单字母替换密码以来,在密码破译学史上最伟大的突破。破解过程如下:

  • 寻找密文中的重复序列,查看每种重复序列的间隔字母数。
  • 计算所有间隔字母数的质因数,查看每个间隔数都有的质因数,即为关键词的长度 L(例如下图中可以确定关键词长度为 5)。
  • 将密文分成 L 个部分,第一部分为 1、L+1、2L+1、3L+1……第二部分为 2、L+2、2L+2、3L+2……每个部分都是根据一个单字母替换密码来加密的。
  • 对每个部分使用频度分析,并与标准频度分布对比,以确定每个部分所使用的密码表,即对应关键词的一个字母。
  • 将上述 L 个字母串起来即为加密所使用的关键词,使用此关键词做完整的密文解密,即可得到明文。

巴比奇可能是在 1854 年成功地破解了维热纳尔密码。但他的发现却完全不为人所知,因为他从未发表它。这个发现直到 20 世纪当学者检查巴比奇丰富的笔记时才被公布于世。而与此同时,普鲁士军队的一位退役军官弗里德里克・威廉・卡西斯基(Friedrich Wilhelm Kasiski)也独立地发现了这种技术,他在 1863 年发表了他在密码破译学上的突破《加密和解密的艺术》,这个方法后来被称为卡西斯基测试(Kasiski examination,而巴比奇的贡献却很大程度上被忽略了。

在维多利亚时代,英国年轻的情侣禁止公开表白各自爱慕之心,甚至不敢互相通信,以防他们父母截住并偷看信的内容。这使得情侣之间通过报纸的个人信息专栏互相发送加密的信息。这些所谓的「激情栏(agony columns)」引起了许多密码破译师的好奇,查尔斯・巴比奇据悉就曾着迷于这种活动。他和他的朋友查尔斯・惠特斯通(Charles Wheatstone)以及巴伦里恩・波雷费(Lyon Playfair, 1st Baron Playfair)一起发明了一种灵巧的波雷费密码(Playfair cipher,也是《S. 中使用的加密法》其中一种加密法(维基百科上并没有提到巴比奇对此加密法有贡献)。有一次惠特斯通破解了《时代》杂志上一位牛津大学学生的留言,留言中暗示他的情人与他一起私奔。几天后惠特斯通插了一句留言,用同样的密码加密,建议这对情况不宜采取这样鲁莽的反叛行为。不久以后,杂志上出现了第三句留言,这次没有加密,是由那位女情人发来的:「亲爱的查理,不要再写了,我们的密码已经被发现了。」

针孔加密法(Pinprick encryption):古希腊历史学家埃涅阿斯(Aeneas Tacticus)提出一种秘密通讯的方法,先找到一篇无关紧要的文章,再在文章中一些特定的字母下面用针刺上小孔,这些字母可以拼成一段密文,接收者很容易识别。然而如果一个外人看到这一页,他可能会忽略这难以察觉的针孔,也就忽略了其中的密文。两千年后,英国写信的人使用了同样的方法以避免过多的邮政费用。在 19 世纪中期邮政系统革新之前,发送一封信大约是每 100 英里 1 先令,超过大部分人的财力。然而报纸可以免费邮寄,于是人们开始使用针孔在一张报纸的正面拼出一段信息,然后再通过邮局发送这份报纸,不需付一分钱。英文原著中对针孔加密法的描述及示例(图片来自 @BakaTakasugi):

比尔密码(Beale ciphers:19 世纪美国西部的一个牛仔托马斯・比尔(Thomas Beale)聚焦了一大批财富,有一个藏有价值 2000 万美元珠宝的宝藏,并写了一套神秘的密文(即比尔密码)描述了这个宝藏的地点。关于这个故事以及那些密文都包含在 1885 年出版的一个小册子里。尽管只有 23 页,但是这本小册子还是困惑了几代的密码破译师,吸引了成百的觅宝者。

比尔密码共有三页,都是密密麻麻的数字,其中第二页在出版的小册子中已经给出破译方法及原文,使用的是书卷密码(Book cipher,其中一本书或者一篇文章本身就是密钥,姑且称这样的书或文章为钥文。密码编码者顺序地给钥文的每个单词编号,这样每个数字就可以用来代替关联单词的第一个字母。然后,通过将明文中的每个字母替换成上述的数字来加密一个信息。注意:由于钥文中的单词首字母可能重复,因此同一个字母可能使用不同的数字替换。比尔密码的第二页使用的是《独立宣言》作为钥文,而第一页和第三页至今仍未破译。

比尔密码之所以难以破译,是因为信息是一次性的,因为它们关系到如此贵重的一个宝藏,比尔或许准备为第一和第三页密码写一篇特别的一次性钥文。事实上,如果钥文真的由比尔亲笔所写,这也就解释了为什么搜寻已出版的文章而没有结果的原因。我们可以试想比尔写了一篇 2000 字的私人文章,可能就是关于捕猎野牛的事情,而这篇文章只有一份。只有这篇文章的持有者,即拥有了独一无二的钥文,才能够破译第一页和第三页比尔密文。为一个信息专门写一篇一次性的钥文要比使用一本出版的书作为钥文安全得多。但这需要发送者有时间写出钥文并能够传给接收者,而这个要求对于每日通讯来说是不可能的。

对 NSA 的调侃:美国国家安全局很少公开过什么事情,有人提议 NSA 不是用来指 National Security Agency(国家安全局),而是指「Never Say Anything(沉默主义者)」或「No Such Agency(没有这样的机构)」(在电影《Snowden》中就出现过 No Such Agency 的调侃)。

以上。

2 Comments

  1. […] 上篇:单字母替换密码,多字母替换密码。 […]

  2. […] 上篇:单字母替换密码,多字母替换密码。 […]

Comments are Disabled