密码旧事,音讯的不二等秘书籍

作者: 奥门永利总站网址  发布:2019-11-29

图片 1

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

通证通研究院 × FENBUSHI DIGITAL 联合出品文:宋双杰,CFA;孙含儒特别顾问:沈波;Rin;JX

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

导读

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

密码学,是一门将信息进行加密处理与传递,以及分析加密信息的学科。根据以RSA为代表的公钥加密体系的出现,可以将密码学的发展过程分为古典密码学与现代密码学两部分。古典密码学以“置换法”与“替换法”为基础,多应用于军事与情报领域;现代密码学则建立在数学、计算机与通信科学的基础上,除了加密信息之外,数字签名、数据完整性、身份认证等也是现代密码学的研究课题。

单字母替换密码

隐文术:通过把信息隐藏起来的这种秘密通信称为 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):

图片 2

替换:与移位并列的密码术是替换。关于替换加密的最早描述出现在《爱经》中,这是由婆罗门学者写于公元 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):

图片 3

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

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

摘要

多字母替换密码

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

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

图片 4

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

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

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):

图片 5

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

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

图片 6

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

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

图片 7

巴比奇可能是在 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):

图片 8

比尔密码(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 的调侃)。

以上。

置换法依照一定的规则,改变原始信息中的字母排列顺序;替换法将原始信息中的字母按照一定的规则替换成其他字母。置换法与替换法的安全性较差,古阿拉伯的学者们开创了破译加密信息的科学——密码分析学,通过频率分析的方法破解替换式加密法。

在长达一千多年的时间里,古典密码学以置换法与替换法为基础不断演进。以维吉尼亚密码为代表的多字母表替换式加密法轮流使用多个不同的替换式密码表,依次对明文中的字母进行加密。第二次世界大战时德军使用的“恩尼格玛”是一种基于复杂的多表替换加密原理的机械式密码机,但最终由于自身加密算法的缺陷,被图灵设计的“炸弹”攻克。

置换式与替换式加密法的弱点在于没能完全消除密文中有关明文的某些特征,保留了明文中的某些信息。奥古斯特·柯克霍夫在19世纪提出的柯克霍夫原则概括性地总结了加密算法应遵循的设计原则:即使加密系统的各个环节都是公开知识,只要密钥未被泄漏,加密系统都应该是安全的。

加密算法的安全性问题本质在于:如何降低攻击者在了解加密算法,并拥有足够长的密文片段的前提下,猜测出正确密钥的可能性?1948年,香农创立了信息论,并在次年的一篇论文中从数学的角度讨论了加密系统,人们开始从科学的角度探究密码学的奥秘。

风险提示:量子计算技术的潜在威胁

目录

1 隐匿法

2 加密法

3 持续千年的智力竞赛:加密与解密

4 古典密码学的圣杯

5 攻克“恩尼格玛”

正文

密码学,是一门将信息进行加密处理与传递,以及分析加密信息的学科。“密码学”一词的词源来自古希腊语“”和“书写”,意为“秘密书写”,其历史几乎与人类有文字记载的文明一样悠久。古希伯来学者在公元前六世纪左右就掌握了“单字母表替换式加密法”,在之后的两千五百多年里,古典密码学在替换式加密法的基础之上不断发展演进。古典密码学多应用于军事与情报领域,而微型计算机与现代密码学的发展能够保护普通人的日常通信免受第三方的窥探。现代密码学建立在数学、计算机科学与通信科学的基础上,除了信息的加密与解密之外,数字签名、数据完整性、身份认证等也是现代密码学的研究课题。今天人们日常生活中的网络支付、电子商务、电子货币等都是密码学这一人类两千多年来智慧结晶的应用。

密码学的概念与人们平时登陆网站、使用银行账户的“密码”并不相同。这些用于身份认证的“密码”,更准确的翻译是“通行词”或“通行码”,它是现代密码学的诸多应用之一,请读者注意区分两者的区别。

受限于篇幅,有关密码学以及密码学在区块链中应用的内容将分两篇专题介绍。

1

隐匿法

隐匿法的历史非常久远,可以追溯到公元前5世纪古希腊与波斯帝国的战争年代。公元前480年,波斯舰队在“万王之王”薛西斯一世的率领下秘密集结,准备对希腊发起进攻,然而这一秘密行动被一位遭到流放、居住在波斯的希腊人狄马图拉斯发现了。他将波斯军队准备进攻希腊的消息写在木板上,并用一层蜡将文字遮住,成功骗过了路途中的波斯卫兵,将信息传回了希腊。希腊城邦联合起来,抵御住了波斯人的突袭。而遭遇挫败之后,曾经盛极一时的波斯阿契美尼德王朝也开始走向衰退。

尽管简单地“将信息起来”与我们今天熟知的密码学相差甚远,被称为“隐匿法”的秘密书写方式却标志着人们开始探索信息保密的方式。

2

加密法

隐匿法仅仅将信息藏匿起来,一旦藏匿的方式暴露,或是负责传达信息的信使叛变,信息安全也无从保证。加密法则注重信息本身的含义,信息的发出方与接收方事先约定,将信息按照一定的规则进行转译,接收方在收到后遵循约定的规则就可以还原原始信息,而即使信息被第三方截获,如果不知道转译规则,也无法还原出原始信息。

加密法的出现标志着古典密码学的开端。在上面的例子中,未经加密的原始信息称为明文,按照特定的规则对明文进行转译后得到的信息称为密文,这个规则称为加密算法。古典密码学的加密算法大多是以字母、单词或是短语为基本单位,又可分为置换法和替换法两大类。

置换法依照一定的规则,改变原始信息中的字母排列顺序。公元前5世纪,斯巴达军队采用一种名为“密码棒”的工具对信息进行加密。发信人将长条形的羊皮纸带缠绕在一根木棒上,将信息横向书写,最后将羊皮纸解下。收信人将信纸缠绕在同样直径的木棒上,就能够还原信息。而羊皮纸上的文字看起来是无意义的,并且用尺寸不相同的木棒也无法还原出原始信息。

但只要了解这种密码的加密方式,就能很容易地解读密文。从密文的第一个字母开始,每数到它之后的第N个字母,记下该字母。记录到密文结尾后,再从第二个字母开始重复这样的操作,以此类推,很快就可以还原明文信息。其中N取决于木棒的直径,写下N个字母后,纸带正好绕木棒一圈,选择不同的N,同样的明文经过加密得到的密文也不相同。发信人和收信人要事先约定好同样的N,收信人才能还原密文。同时N不能被第三方知晓,才能保证加密通信的安全。这里的N称为密钥,是加密通信的参与方共同享有的秘密知识,用于加密和解密信息。

替换法将原始信息中的字母按照一定的规则替换成其他字母。据传,凯撒大帝使用替换式加密法写作书信。凯撒大帝将信息中的每个字母后移三位,例如A替换成D,Y替换成B,这种加密法称为凯撒挪移式加密法。在这个例子中,密文相比明文,每个字母都被后移了3位,密钥可以用3表示。密钥可能的取值范围为1~25的自然数,称为密钥空间。明文里所有可能出现的字母的集合称为明文空间,密文里可能出现的字母集合称为密文空间,替换法中的密钥可以表示为明文空间到密文空间的一个映射,在古典密码学中又称为密码表。密文空间可以与明文空间相同,例如凯撒密码中,密文的字母仍然是26个拉丁字母。密文空间也可以是明文空间的超集,例如在密文中混入一些无效字符,以干扰试图破译密码的行动。密文空间还可以与明文空间完全不相关,例如在柯南道尔所著的福尔摩斯系列的《跳舞的人》中,罪犯用26种形态各异的跳舞的小人来替换英文字母。

公元8世纪,阿拉伯哈里发帝国的第二个世袭王朝——阿拔斯王朝在巴格达定都,其建立之初的一百年是伊斯兰文明的黄金时代。据记载,阿拔斯王朝的官员们使用替换式加密法保护机密的行政事务、税收数据,相信这能够帮助他们建立一个廉洁、高效的政府。巴士拉的语言学家卡里尔撰写了《加密信息手册》,使用排列组合对阿拉伯语单词的加密法进行分析。此外,阿拉伯的学者们还开创了破译加密信息的科学——密码分析学。

3持续千年的智力竞赛:加密与解密

古典密码学多用于军事、政治、外交领域重要情报的传递,希望刺探这些秘密的人自然不在少数。阿拉伯学者们在统计语言学资料时发现,在样本容量较大,有意义的阿拉伯语文本中,每个字母出现的频率是不一样的。字母a和字母l在阿拉伯语中出现频率最高,因为“al”是阿拉伯语中的定冠词,相当于英语的“the”,此外,元音的出现频率也比较高。这些成果很快被运用到密文分析中。

之前介绍的替换式加密法中,明文中的所有字母都遵循同一套规则进行替换,这样的加密法称为单字母表替换式加密法。公元9世纪,阿拉伯科学家肯迪在《解译加密信息》一书中阐述了对这种加密法的解译方式。如果能确定原文所使用的语言,首先列举出密文中出现的所有字母,统计它们各自出现的频率并排序,对照该语言中字母出现的频率顺序,就可以开始尝试对密文进行分析,这种方法称为频率分析法。频率分析还可统计某种语言中特定的字母组合出现的频率,如英文中的“ee”,以及某个字母前后特定字母出现的频率,如英文中字母“q”之后一定跟随”u”等。直到数百年后,中世纪的欧洲学者才掌握这一方法,并且决定了两位女王的命运。

1586年,英格兰政府对天主教的迫害日益加剧,安东尼·贝平顿与几位同党密谋策反,计划救出被伊丽莎白女王软禁的苏格兰女王、伊丽莎白女王的表妹、信仰天主教的玛丽女王,并暗杀伊丽莎白女王。贝平顿通过密使传递使用替换式加密法加密的书信,与玛丽女王商讨暗杀计划。贝平顿设计的更加复杂的替换式加密法使用23个符号替换除j、v、w之外的英文字母,4个不具有任何意义的混淆符号,表示下一个字母连续出现两次的“dowbleth”符号,以及若干个符号替换常用的单词,以尽量减少遭到频率分析法破译的可能。

但可惜的是,贝平顿信任的密使其实是一位双面间谍,背地里将他与玛丽女王的密函交给伊丽莎白女王的国务大臣、间谍头子沃尔辛厄姆,后者先打开信封,抄写一份密文,再重新伪造封缄,并将密文交给密码学家托马斯·菲利普分析。菲利普通过频率分析法破译了密码,并在玛丽女王寄出的一封信件后附加了一段伪造的密文,诱使贝平顿说出参与计划的同伙的名字。暗杀计划暴露后,玛丽女王、贝平顿以及其密党都遭到处决。

以上是一个过于信任加密方法的安全性,以致造成悲剧结局的例子。如何衡量加密通信安全与否是一个重要的问题,加密通信的过程可以划分为选择加密方式、约定密钥、加密明文、传输加密信息、还原明文几个步骤。古典密码学中,绝大多数加密方式都是替换法、置换法或者两者的结合,因此加密方式几乎不是秘密,试图对密文进行分析的人可以通过尝试所有可能的密钥进行解译,当某个密钥还原出的明文出现了有意义的单词,就说明找到了正确密钥。因此,密钥空间越大,意味着破译者需要尝试的密钥数就越多,密码就越安全。凯撒挪移式加密法只有25个可能的密钥,安全性非常差。

奥古斯特·柯克霍夫在19世纪提出的柯克霍夫原则概括性地总结了加密算法应遵循的设计原则:即使加密系统的各个环节都是公开知识,只要密钥未被泄漏,加密系统都应该是安全的。换一个方式来说,加密系统的安全性应依赖于密钥的保密,而不是加密算法的保密。

本文由奥门永利官网误乐域发布于奥门永利总站网址,转载请注明出处:密码旧事,音讯的不二等秘书籍

关键词: