第3 章 古典密码的历史 数学语言是上帝用来书写宇宙的文字。———伽利略·伽利雷(意大利科学家) 回顾第1章的内容,从图1.9中可以看出:信息安全的重点是网络安全,网络安全的 要害是计算机安全,而计算机安全的关键则是密码安全! 因此也可以这么认为:密码技 术是信息安全中最为核心的技术。 密码的起源可以追溯到几千年前的埃及、巴比伦、希腊、罗马和中国。世界知名密码 学家戴维·卡恩在《破译者:人类密码史》一书中说:“人类使用密码的历史几乎与使用 文字的时间一样长。”不过,密码技术早期主要应用于军事和外交领域,交战双方都在想方 设法保护自己的通信安全,并极力窃取对方的情报。后来,随着科学技术的不断发展,密 码技术逐渐进入人们的日常生活之中。 3.1 置换密码的思想 公元前405年,雅典和斯巴达之间爆发了战争。一次,斯巴达人在一名疑似雅典信使 的人身上搜到了一条异样的皮带,上面写满了杂乱无章的希腊字母。斯巴达军队的统帅 莱桑德猜测这应该是情报,但是无法揭开其中的奥秘。就在他百思不得其解的时候,无意 中把皮带缠在了手中的剑上,从而误打误撞地发现了情报的内容。 如图3.1所示,后来的“斯巴达密码棒”就受到了上面这个故事的启发:把皮带缠绕 在一个特定粗细的木棒上,然后在上面写好消息(横着书写)。解下皮带后再看(相当于竖 着读取),只是杂乱无章的字符。只有再次将皮带以同样的方式缠绕到同样粗细的木棒 上,才能看出所写的内容。 图3.1 “斯巴达密码棒” 34 信息安全导论 我们仔细思考一下,传递的消息经过“斯巴达密码棒”的处理,字母还是那些字母,只 不过顺序被打乱了———横竖位置发生了变化。这很像线性 代数中的转置矩阵,也就是说,把一个矩阵的行和列互换位 置。举一个简单的例子,比如Alice要传递消息“Thisisa bookmark!” 给Bob,去掉标点符号和空格①,并把字母全部 图3.把消息写成矩阵形式 变为大写,则为“THISISABOOKMARK”。这个字符串可 2 以写成一个3行5列的矩阵,如图3. 2所示。 你可以想象一下,这个矩阵就相当于把皮带缠绕在密码棒上,然后写上消息的样子。 接着,就要把皮带从密码棒上取下来,那么取下来是什么样子? 是不是就相当于按列去读 了? 如果按列从左至右、从上到下抄写一遍,得到的字符串就是加密后的消息 “TSKHAMIBASORIOK”。这个加密后的消息就算被入侵者Eve窃取了,只要Eve不清 楚加密方法,他也很难从这一长串字符中得到有用的情报。 由于是事先沟通好的,接收者Bob自然知道如何从“TSKHAMIBASORIOK”中恢复 出原先的消息。首先需要一个和加密时尺寸完全相同(3行5列)的矩阵,可以画一个3×5 的棋盘格,如图3. 3所示。 图3. 3 3×5 的棋盘格 接下来,Bob把加密后的消息“TSKHAMIBASORIOK”从上到下按列抄写到棋盘格 里,如图3. 4所示。 图3.把加密后的消息抄写到棋盘格里 4 最后,Bob从左到右按行读取这个矩阵(棋盘格)中的字符,就可以将消息还原出来 ① 在古典密码学中,为简化模型,认为标点和空格几乎没有信息量,在惜字如金的古代更是如此。 35 第 3 章 古典密码的历史 了,即“THISISABOOKMARK”。 当然,如果Alice和Bob觉得这种加密方式太简单,容易被智商颇高的Eve察觉——— 毕竟,多试几次就有可能猜出这个矩阵的尺寸,这样加密就失效了———那么,还可以加大 其破解的难度。如图3.Alice把每一列都标上不同的序号。 5中左图所示, 图3.更加复杂的2轮置换加密 5 Alice在进行加密的时候,不再从左到右读取每一列了(太容易被猜到),而是按照序 SOR”IBA” 号标识的顺序读取每列:先读序号为1的列“,再读序号为2的列“,然后读序 号为3的列“TSK”接着读序号为4的列“, IOK”这样得到 , HAM”最后读序号为5的列“, 了加密后的消息“SORIBATSKHAMIOK”。如果想将这个加密后的消息还原,不仅需要 知道矩阵的尺寸,还要知道列的序号“34215”。 当然,Alco让Ee破解的困难更大。如图3. ie和Bb还可以进行多轮加密,v5中右图 所示,把上一步加密后的消息“SORIBATSKHAMIOK”写到另一个矩阵(3行5列)之中, 并改变了每一列的序号。然后,再按照序号标识的顺序先后读取每列,得到第二轮加密后 的消息“OTMIKOBHKSAARSI”。在第二轮加密时,Alice在改变序号的同时还可以改 变矩阵的尺寸,比如变成5行3列,这就进一步加大了破解的难度。 从上面的加密过程可以看出,接收方Bob想要还原消息,需要和发送方Alice事先商 定3个参数:一是加密的次数,二是每次加密的矩阵尺寸,三是每次加密的列序号。如果 入侵者Eve想窃取消息,就得对加密后的字符进行反复试验,猜中这3个参数,难度是相 当大的。 除了上面这种行列转置,还有一种简单的置换密码,就是栅栏密码。顾名思义,这种 加密方式就是从围绕庭院的栅栏(图3.得到的启示。还是沿用上面的例子, 6左图) 6右图) 不过 这一次Alice打算换个更加省事的方法,把一个类似“栅栏”的模板(图3.放在消息 “THISISABOOKMARK”上面。可以看到,从第2个字符开始,模板每隔一个字符的位 置就恰好挡住一个字符。Alice先将没有挡住的字符抄写下来,即“TIAOKAK”;然后将 挡住的字符抄写下来,即“HSSBOMR”;最后将这两串字符连接起来,形成密文 “TIAOKAKHSSBOMR”发送给Bob。 图3.栅栏密码的加密原理 6 36 信息安全导论 Bob接收到密文之后,就按照字符串的长度画一个单行的表格,并在每个格子的上方 标好序号。接下来,首先把字符串的前半段“TIAOKAK”依次抄写在奇数序号下方的格 子里,然后把字符串的后半段“HSSBOMR”依次抄写在偶数序号下方的格子里,这样就恢 复出了原始的消息,如图3. 7所示。 图3.栅栏密码的解密原理 7 比栅栏密码更为简单的是倒序密码,其核心思想就是将消息中的字符次序颠倒 过来。比如,Alice将消息“THISISABOOKMARK”颠倒次序写出来,形成了密文 “KRAMKOOBASISIHT”。Bob接收到密文后,再将其次序颠倒,就能恢复出原始 消息。 栅栏密码、倒序密码与前面讲过的行列转置同属一类。它们都有一个本质的特征,就 是“把消息的字母重新排列,打乱顺序”,所以称之为置换或换位。当然,由于倒序密码和 栅栏密码过于简单,在历史上出场次数很少。就算是能玩出花样的行列转置实用性也不 是很强,通常是与另外一类密码技术结合使用,这就是古典密码的主角———代换密码。 信息隐藏技术 在生活中,人们很容易看到一些和密码学很类似但又有着本质不同的信 息安全措施,信息隐藏就是有代表性的一种。比如,一群学生在准备一次考 试,题型为选择题(选项为A、B、C、D)。其中,张三准备得很充分,他决定“帮 助”一下其他人。考前,大家约定用以下方式传送答案:如果张三咳嗽,表示 该题答案为A;如果叹气,表示答案为B;如果跺脚,表示答案为C;如果转笔, 表示答案为D。外界(老师和其他同学)可能会注意到张三的行为,这些行为 是公开的信息,其中却隐藏着秘密信息,也就是题目答案。《西游记》中孙悟空 拜师学艺的时候也出现了类似的场景,须菩提祖师手持戒尺,在大庭广众之下 将(“) 悟空头上打了三下,倒背着手,走入里面,将中门关了……”徒弟们都看到 老师发怒责打了孙悟空,但只有孙悟空领悟了老师的暗示———“三更时分存 心,从后门进步,秘处传他道也”。 另一种信息隐藏技术就是隐写术,不仅常在中外影视作品中出现,而且我国 古代早已有之。据《三朝北盟汇编》记载,靖康元年(公元1126年),开封被敌军 围困之时,宋钦宗“以矾书为诏”发出指令,采用的就是“以矾书帛,入水方现”的 37 第 3 章 古典密码的历史 方法。它主要是用明矾溶于水得到一种“矾水”,然后用这种“矾水”在布条上书 写秘密情报,布条晾干之后看上去是无字的。收到该情报的人需要将布条浸水, 才能让上面的字迹再次显现出来。后来的“不可见墨水”也是如此,都是用一些 特殊材料书写之后不留下痕迹,除非加热或者加入某些化学物质,才能显露出 信息。 目前,数字水印已成为信息隐藏技术的研究热点,它是将特制的标记隐藏在 数字产品之中,用以证明原创作者对作品的所有权,解决版权保护和信息防伪等 问题。所以说,信息隐藏就是将某一秘密信息隐藏于另一公开的信息内容中,其 形式可以是任何一种数字媒体,如图像、声音、视频或一般的文本文档等,然后通 过公开信息的传输来传递秘密信息(图3. 8)。信息隐藏的目的是要掩盖秘密信 息的存在,让别人只关注到秘密信息的载体———公开信息。而密码学则不需要 通过这种隐蔽性实现安全,它是通过对秘密信息进行转换,实现信息对外的不 可读。 图3.8 信息隐藏之“暗语” 3.代换密码的技巧 2 除了“把消息的字母重新排列,打乱顺序”这类置换密码之外,还有一种思路就是将消 息的字母替换成其他字母、数字或符号,称为代换或替换。这类加密方法不仅简单、实用, 而且可以变出更多的花样,是古典密码学的主流。到了19 世纪下半叶,随着科学技术的 发展,人们使用机械进行更为复杂的代换加密,使得密码技术在战争和商业中大放光彩。 3.2.1 单表代换的出现 公元前2世纪,希腊人波利比乌斯发明了一种简 单的代换密码,被后世称为棋盘密码或Polybius方表。 如图3.9所示,以英文为例,将26 个字母按照顺序放在 一个5×5 的棋盘里面( I和J放在同一个格子里)。这 样,每个字母都对应两个数字———一个是该字母所在 行的标号,另一个是该字母所在列的标号。比如,字母 图3.9棋盘密码 38 信息安全导论 C对应13,M对应32,Y对应54 。 于是,按照这个棋盘密码,就可以把任意一串英文消息加密为一串数字了。解密的方 法也是一样。比如,接收到的加密消息为“23-15-31-35-32-15-24-11-32-45-33-14-15-42-1144-44-11-13-25”( 对照着图3.很容易就可以解读 为了辨识方便添加了横线), ①, 9的棋盘格, 出原始消息为“HELPMEIAMUNDERATTACK”即“HelpmeIamunderatack!” 在专业术语中,将原始的未加密的数据称为明文,而将加密的结(.) 果称为密文。用棋盘 密码加密之后,明文和密文有着明显的不同之处———明文是字母,密文成了数字。而另一 种基于代换思想的加密方法———恺撒密码②处理之后的密文和明文一样,还是字母。 如图3.10所示,恺撒密码也叫移位密码(shiftcipher)或加法密码。它的基本思想 是:通过把字母移动一定的位数实现加密和解密。明文中的所有字母都在字母表上向后 (或向前)按照一个固定步长进行偏移并被替换成密文字母。比如,当步长是3的时候,明 文中的所有字母A将被替换成D,B变成E,以此类推,X变成A,Y变成B,Z变成C。 图3.恺撒密码的原理 10 如果明文还是“HELPMEIAMUNDERATTACK”,向后移动的步长是3,密文就是 “KHOSPHLDPXQGHUDWWDFN”。如果让每一个字母等价于一个数值,即A=0, B=1,…,Z=25,那么恺撒密码的加密公式可以写为 C=(M+3)mod26 其中, M 为明文字符, C 为对应的密文字符。如果移动的步长可以是任意整数k,则更加 通用的加密公式为 C=( M +k)mod26 解密公式为 M=(C-k)mod26 由此可见,移位密码的方法很容易掌握,其关键就是移动的步长k,称为密钥,而加密 和解密的过程都要在密钥的控制下进行。 需要特别注意的是,随着密码学的不断发展,在现代密码学中,数据安全基于密钥而 不是算法的保密。也就是说,对于一个密码体制,其算法是公开的,可以供所有人使用和 研究,但某次具体加密过程中使用的密钥则是保密的。如果把加密和解密算法看作一个 ①24可以解读为I或J,但根据上下文很容易推测出是I还是J。 ② 据说恺撒是率先使用这种代换加密的人,因此这种加密方法被称为恺撒密码。但历史文献中还记载了恺撒 使用的另一种加密方法———把明文的拉丁字母逐个代之以相应的希腊字母,这种方法看来更贴近恺撒在《高卢战记》 中的记叙。 39 第 3 章 古典密码的历史 函数,密钥就类似于函数中的参数的具体取值。函数的类型、计算方法都可以公开,但某 次使用过程中具体参数的设置是保密的。 如果沿着上面的思路,即把加密和解密看作函数运算,进一步推广,那么还可以得到 和加法密码类似的乘法密码,加密公式为 C=( M ×k)mod26 还可以把加法密码和乘法密码结合起来,构成具有两个参数k1 和k2 的仿射密码,加 密公式为 C=(k1M +k2)mod26 当k1=1的时候,仿射密码就变成了加法密码;当k2=0的时候,仿射密码又变成了 乘法密码。 一场政治阴谋中的密码战 16 世纪的苏格兰女王玛丽一世①是密码学史中的传奇人物。她在27 岁时被 自己的姑姑———英格兰女王伊丽莎白一世囚禁了起来,一关就是18 年。到44 岁 时,她在囚禁处里与外界反叛军密谋杀害姑姑,夺取王位。当时的信件都是通过特 殊渠道传入囚禁处,最后由侍女在递送红酒时藏在瓶塞中带给玛丽一世的。但玛 丽一世还是非常小心谨慎,对所有的通信都使用代换方法加密,这样就算不慎落入 伊丽莎白一世的手中,也没人看得懂。具体操作就是将所有的英文字母用特殊设 计的符号替换,一些常用词也用符号代替, 11 所示。 如图3. 图3.玛丽一世使用的明文和密文对照 11 玛丽一世熟练掌握了这种代换加密技术,写信可以直接使用密文,不用一个 个字母查对照表。不幸的是,在这个特殊消息传递的渠道里竟然隐藏着一个内 奸,他把情况汇报给伊丽莎白一世。在位的英格兰女王正愁抓不到把柄,这下终 于有机会名正言顺地处死玛丽一世了。不过伊丽莎白一世没有打草惊蛇,她打 算抓到足够的证据,把整个阴谋背后所有的参与者一起除掉。于是,玛丽一世和 ① 玛丽一世与“血腥玛丽”不是同一个人,虽然她们名字类似,而且处于同一时代,但前者是苏格兰女王,后者是英 格兰女王。 40 信息安全导论 外界的每封信都先经过内奸送到专门的团队原样抄写,然后再密封好,就像从没 有被截获过那样,递出囚禁处。团队里的人再拿着抄写好的密文想法破解,最终 他们成功了。玛丽一世被判处死刑,这场密谋的政变失败了。 3.2.2 分析破译的线索 辩证法告诉我们:“ 矛盾存在于一切事物的发展过程中,每一事物的发展过程中存 在着自始至终的矛盾运动。”密码学也不例外,这个领域中同样存在着一对矛盾———密码 编码学和密码分析学。密码编码学研究的是通过编码技术改变被保护信息的形式,使得 编码后的信息除指定接收者之外的其他人都不能理解。密码分析学研究的是如何攻破一 个密码系统,恢复被隐藏的信息的本来面目。 如图3.Alco而入侵者Ee企图在 12 所示,ie和Bb希望通过加密算法实现安全通信,v 不知道解密密钥及加密技术细节的条件下对密文进行分析,以获取机密信息。 图3.密码编码与密码分析的关系示意图 12 那么入侵者Eve会采用什么方法破译密码呢? 最直接的方法就是穷举攻击,也就是 把所有的加密算法和密钥都尝试一遍,直到试出正确的加密算法和密钥为止。当然,这种 方法耗时耗力,是最蠢笨的。但是,无论多么优秀的密码技术,都必须要考虑到穷举攻击 的威胁,尤其是在信息系统具有了强大的计算能力之后。 聪明的人善于发现并利用规律,密码分析的专家肯定不会局限于穷举攻击这么低级 的手段。大名鼎鼎的侦探夏洛克·福尔摩斯①就是这么一个厉害的角色,他破译密码的 能力在《跳舞的小人》中展现得淋漓尽致。 一个叫希尔顿·丘比特的人拿着几张稀奇古怪的纸条找到福尔摩斯,上面画着一行 行跳舞的小人,如图3.他感到非常困惑, 13 中左图所示, 因为他的妻子看到这些小人就会 非常惊恐,而且这些奇怪的小人文字隔一些日子就会出现在他家的窗台上或工具间的门 上。他请求福尔摩斯帮忙解开这个谜团。福尔摩斯在分析了前后几张纸条上的信息之 后,终于破解了其中的秘密,最终捉住了恶人。 显然,福尔摩斯很了解古典密码,尤其是代换技术。他不仅猜测出了打着旗子相当于 一个单词的结束,而且利用频率分析的思想进行了合理的推理,从而确定了每个小人和英 文字母的对应关系,如图3. 13 右图所示。 ① 福尔摩斯是19 世纪末的英国侦探小说家阿瑟·柯南·道尔塑造的一个才华横溢的侦探角色。福尔摩斯系 列小说包含4个长篇、56 个短篇,故事的发生年代大约是1875—1907 年。 第 3 章 古典密码的历史 41 图3.《跳舞的小人》中的例子 13 频率分析法在9世纪的阿拉伯①就出现了,只是到了16世纪才被欧洲数学家注意 到。它的原理其实很简单———在使用自然语言的时候,字母出现的频率是不一样的。如 E是出现频率最高的字母( 7%), 9. 图3.14所示,在英文文献中,0. 达12.其次是T(1%), 后是A、O、I、N等,出现频率最低的是Z(1% )。而单表代换技术很难隐藏这样的统计(然) 信息,其明文中的每个字母只是简单地被替换成另一个符号而已,那么,密文中某个符号 出现的次数与它在明文中对应的字母出现的次数是一样的。所以,在大多数情况下,可以 认定出现频率最高的符号最有可能代表E。 图3.英文字母的出现频率 14 ① 密码破解方法最早的文字记录可以追溯到9世纪阿拉伯通才AlKindi所著的《破解加密消息的手稿》( A ManuscriptonDecipheringCryptographicMesages),这篇文章论述了频率分析的方法。 42 信息安全导论 09% 、98% 和 当然,有些字母的出现频率极为接近,比如H、R和S,分别是6.5. 6.32% 。但只要稍微留意字母前后的关联,就可以区分它们。比如,T几乎不可能出现在 B、D、G、J、K、M、Q这些字母的前后,H和E经常连在一起,EE 出现的频率远比AA 出现 的频率高得多,等等。 如果像《跳舞的小人》一样,有了“打着旗子”这种单词分隔符,就更容易利用其他的英 语统计规律了。比如,单个符号最有可能是A或I,超过半数的英文单词以E、S、D、T结 尾,接近半数的英文单词以T、A、S、W开头,最常见的双字母组合是TH 、HE 、IN,最常见 的三字母组合是THE 、ING 、AND,等等。 像3.1节提到的玛丽一世与外界通信使用的代换密码就很容易被破解。只要截获 2. 的她与外界来往的通信足够多,字符总量达到一定规模,全部收集起来,统计哪个符号出 现的频率最高,那个符号很可能就代表字母E。即使第一步统计各种符号出现的频率时 并不能完全确定,只要多尝试几次,然后再根据拼写的统计规律筛选一下,符号对应的明 文字母就确定了。 历史上,在审讯的过程中,玛丽一世始终没有承认自己要密谋杀害姑姑。但证人和密 码学专家一起向公众展示了她与外界通信的密文和明文,并揭露了加密和解密的详细规 则,最后玛丽一世还是被砍了头。这是密码编码学和密码分析学在王权斗争中最著名的 一次应用,密码分析学大胜。 信息战中的博弈 1942 年1月,美国和日本在太平洋战场上激战正酣。美军在打捞上来的日 本战舰残骸中发现了一个密码本,从而破译了日本海军的部分密码。到了5月, 美军谍报人员已经能够读懂接近三分之一的日军密电,但还是不知道日军用于 描述特定地点的那些代号的含义。比如,在一份截获的日军密电中,就透露出 “AF”将会是一次攻击的主要目标。作为美国海军夏威夷情报中心的指挥官,约 瑟夫·罗切福特猜测这次攻击很有可能发生在中途岛,但还需要进一步证实。 罗切福特设计了一个巧妙的方法以确定“AF”的含义。他让中途岛的美军 发出一份明文电报,大意是由于蒸馏设备损坏,中途岛急需淡水。然后又让珍珠 港的总部煞有介事地回电:已向中途岛派出供水船。果然,日军很快就中招了。 美军截获了一份新的日军密电,电文中通知主力进攻部队携带更多的淡水净化 器,以应对“AF”淡水匮乏。这就证实了“AF”的确指代中途岛。可以说这一情 报直接决定了日本在中途岛海战中的惨败,进而成为整个太平洋战争的转折点。 3.2.3 多表代换的升级 前面讲到的代换密码技术之所以容易被频率分析法攻破,关键就在于其明文中的任 何一个字母都只有一个固定的密文字母与之对应,所以也称为单表代换。如果要消除频 率特征,就应该为明文中的每个字母提供多种代换方式。比如,字母E,时而用字母D代 换,时而用字母X代换,这就是多表代换密码技术。 然而,信息交换是双方的事情,不能只考虑加密方便,也要考虑解密易行。如图3. 43 第 3 章 古典密码的历史 所示,如果Alice随意代换明文中的字母,让密文中字母的频率特征大致相等。这样入侵 者Eve的确是没法破解了,但Bob也没有办法恢复出密文中的信息了。这就相当于 Alice与Bob断了联系,失去了通信的意义。 所以,对明文中每个字符提供多种代换方式的多表代换不能太随意,必须有规则,才 可以保证通信双方达成共识。而规则又要有一定的复杂性,才不容易被第三方破解。下 面介绍的维吉尼亚(Vigenere)密码就是其中的经典。 下面举一个例子展示维吉尼亚密码的基本原理。明文是“atackbeginsatfive,(”) 去 掉空格并将字母改为大写,就成了“ATTACKBEGINSATFIVE”。让每一个字母等价于 一个数值,即A=0,B=1,…,Z=25,那么明文“ATTACKBEGINSATFIVE”对应的数值 序列就是“0191902101468131801958214”(为辨识方便,在数值间添加了 空格)。 如果每个字母都移动固定的步长2,那就是前面讲过的单表代换。现在变动步长,比 如,明文第一个字母移动的步长为2,第二个字母移动的步长8,第三个字母移动的步长为 15,第四个字母移动的步长为7,第五个字母移动的步长为4。当然,不可能继续无规律地 变动下去,太长的密钥不容易记住,所以就反复使用“2,8,7,”这5个步长,如图3. 所示。 15,415 图3.维吉尼亚密码的加密原理 15 图3.15中的第一行显然是明文本身;第二行是明文中每个字母对应的数值;第三行 是将5个步长“2,8,15,7,4”反复书写到和明文长度一致,以确保明文每个字母都有对应 的步长;结果的第一行是明文每个字母对应的数值与对应步长相加然后进行模26运算的 结果,采用的加密公式为C=( M +k)mod26 。再把这个结果中的每个数值转换为对应 的英文字母,就得到了最终的密文“CBIHGBDMVPRJCBUPZV”。 仔细观察一下图3.明文第2个字母和第3个字母都是T,但由于是多表代换,加 15, 密之后分别是B和I,这就对频率统计起到了干扰作用,也就是说同样的字母加密之后会 被不同的字母代换。同理,密文的第2个字母和第6个字母都是B,而在明文中对应的字 母却分别是T和K。 可以看出,维吉尼亚密码的算法和恺撒密码是一脉相承的,两者的区别是:恺撒密码 (单表代换)的密钥是一个固定的数字,比如4或3;而维吉尼亚密码(多表代换)的密钥是 多个不同的数值,比如上面的例子中用到的2,8,15,7,4。 当然,“2,8,15,7,4这(”) 样的密钥不好记忆,远不如一个有意义的单词让人印象深刻。 于是,干脆找一个英文单词,将其每个字母对应的数值当作密钥不就行了? 比如,“密码” 一词的英文cipher对应的数值序列是“2,8,15,7,4”。所以,明文为“atackbeginsat 44 信息安全导论 five”,密钥为“cipher”,进行维吉尼亚密码加密的结果如图3. 16 所示。 图3.以英文“”为密钥的维吉尼亚密码加密结果 16 cipher 既然维吉尼亚密码这么强大,它是不是无法破解呢? 当然不是。在其出现的200 多 年之后,也就是1863 年,一位业余数学爱好者、普鲁士退役炮兵少校卡西斯基出版了《密 写和破译的艺术》。这本只有95 页的书成为人类历史上第一部讲述如何破解多表代换的 著作。下面给出这本书中介绍的破解方法———卡西斯基试验(Kasiskiexamination)并探 讨其背后的机理。 thesunandthemaninthemoonking 举一个典型的例子,明文为“,(”) 密钥为“,(”) 加密 过程如图3.就会发现里面先后出现了两个相同的字符 17 所示。如果仔细观察一下密文, 串“BUK”,这两个字符串出现的位置相隔8个字符,恰好是密钥长度的2倍。这两个 BUK” THE”ING” “对应的明文都是“,对应的密钥都是“。 图3.维吉尼亚密码破解示例 17 也就是说,如果在密钥循环到整数倍的时候,正好出现相同的明文,那么明文就会被 加密成相同的密文。这就是破解维吉尼亚密码最关键的部分———从密文中把完全一样的 字符串挑出来,从中总结规律,分析出密钥的长度。 当然,分析密钥长度的具体方法分为以下几步: .第一步,是从密文中找出拼写完全相同的字符串,尤其是那些长度大于4的重复 出现的密文字符串。比如一篇几百个字符的密文中,长度超过4并且重复出现的 字符串一共有4种模式,就把它们标识为甲乙丙丁。 .第二步,统计它们第一次出现到第二次出现间隔了多少个字符。比如,甲字符串 的重复间隔了20 个字符,说明这段20 个字符长度的密文中密钥反复使用了若干 次。具体是1次、2次、3次还是4次? 其实都有可能。把所有可能性都列出来: 假设密钥长度是2,则反复使用了10 次。 . . 假设密钥长度是4,则反复使用了5次。 第 3 章 古典密码的历史 45 . 假设密钥长度是5,则反复使用了4次。 . 假设密钥长度是10,则反复使用了2次。 . 假设密钥长度是20,则只使用了1次。 其实就是把间隔数的所有因数都找出来。对乙、丙、丁的情况也按照同样的步骤 操作,还会得到很多种密钥长度的可能性。 .第三步,到底哪个可能性才是对的呢? 只要看看哪个因数在甲、乙、丙、丁模式的 因数列表里都存在,那个因数对应的密钥长度就是最终的答案。 也许有些人觉得,知道密钥具体的内容才行啊,光知道它的长度有什么用呢? 其实 不然。 比如,已经知道密钥的长度是5了,那就意味着:将密文中第1,6,11,…个字符单独 挑出来放在一起作为A组,它们是用同样的步长加密得到的;再把第2,7,12,…个字符挑 出来放在一起作为B组,它们是用另一个步长加密得到的…… 如此一来就能得到5组字 符,每一组都退化为单表代换! 对于单表代换,继续使用频率分析法就可以轻易破解了。 3.2.4 适度保护的原则 从3.3节的论述中可以发现, 2.多表代换的根本漏洞在于循环使用密钥进行加密。 在循环使用同一个密钥的情况下,只要明文足够长,总有相同明文字符串遇到相同密钥字 符串的时候,这就会让截取者有办法猜中密钥的长度。而一旦知道了密钥的长度,就等于 把维吉尼亚密码(多表代换)化简为 N 套最为简单、基础的恺撒密码(单表代换)了。 如果想堵上这个漏洞,搞出一个无法破解的加密算法,就得让多表代换的密钥既无规 律又无限长。这就是密码学上的无条件安全,即理论上不可攻破的密码方案。其效果就 是,无论有多少可以使用的密文,都不足以唯一地确定在该体制下密文所对应的明文。 1917 年出现的一次一密(one-timepad)是最接近这个理想状态的加密方案。它把大 量不重复的密钥写在一张张纸上,然后再做成一个密码本。如果密码本的一页上有20 个 密钥字符,Alice要向Bob发送一份300 个字符的明文,那么就得用掉15 页密钥,还得把 使用过的这15 页密钥销毁。同样,接收者Bob也需要一个与Alice完全相同的密码本, 一旦接收到一份密文,就要使用同样数量的密钥解密,然后销毁这些密钥。 很明显,实现一次一密的难度和代价实在是太大了。一方面,密钥中的字符要随机地 无规律地出现,想一想技术方案就让人头疼;另一方面,记录这些无穷无尽的密钥的密码 本应该是无限厚的…… 在实际的通信过程中,密钥不仅不可能无限长,实际上也不可能太 长———如果太长了,操作者一个字符接着一个字符地对照、计算、对照、计算…… 保持绝对 同步,不仅麻烦,而且太容易出错。就算到了信息时代,密钥随用随生成,但由于密钥至少 和消息一样长,安全传递密钥本身的复杂性就相当于甚至高于传递消息本身,因此这种加 密方案并没有什么实用价值。 于是,这就触及了密码的代价或者说通信成本这么一个很有意思的问题。从理论上 讲,人们可以制定无穷复杂的密码方案;但在实践中,受具体客观条件的影响,必须根据使 用情况做出某种妥协。换言之,就是在一定程度上牺牲密码编码的安全性,以获取整体密 码操作的可行性和便利性。套用网络上的一句话———“ 理想很丰满,现实很骨感!” 46 信息安全导论 总之,大家要清楚一点———所有实用的加密算法都不是无条件安全的,也就是说,在 理论上都是可能被攻破的。所以,常用的加密算法只是力争做到有条件的安全,也就是计 算上的安全,即一个密码方案不能被可以使用的计算资源所破解。它们至少应该满足下 面的两个条件之一: (1)破解密码的代价超出信息的价值。 (2)破解密码的时间超出信息的有效期。 如果满足第一个条件,那么对于破解密码的人来说,这么做就得不偿失。就像耗费了 一万元的人力物力盗取了价值几千元的财物。如果满足第二个条件,意味着当密码被破 解的时候,明文实际上已经丧失了使用价值。就像在战斗结束的时候才破解了战斗开始 的时间和地点,胜负已定,该情报就没有什么意义了。这个思想也可以归纳为信息安全中 的一个基本原则: 适度保护原则(principleofadequateprotection) 信息资源在失去其价值之前必须 被保护。它们被保护的程度与它们的价值是一致的。 3.最后的辉煌——转轮密码机 3 — 在20 世纪40 年代之前是古典密码一统天下的阶段,这一阶段主要是通过人工编码, 也就是纸加笔的方式。这些几千年流传下来的加密和解密方法如此低效率,显然无法满 足工业革命浪潮下的军事和商业方面的应用。 于是,古典密码的集大成者———转轮密码机(rotor,简称转轮机)技术出现了。尤其 是其中的佼佼者———Enigma,它不仅是人类历史上第一台批量制造的实用的密码机器, 而且间接引出了现代计算机的出现,更让人意想不到的是它还直接影响了第二次世界大 战的进程!① 3.3.1 横空出世的战争利器 在1918 年前后,也就是第一次世界大战刚刚结束时,德国人亚瑟·谢尔比乌斯、美国 人爱德华·赫本、荷兰人亚历山大·科赫、瑞典人阿维德·达姆几乎同时发现了转轮机的 基本原理:通过硬件卷绕实现从转轮机的一边到另一边的单字母代替,然后将多个这样 的转轮机连接起来,就可以实现几乎任何复杂度的多个字母代替。 为什么不同国家的这么多人都突然聚焦到同样的发明上面? 是英雄所见略同还是有 一股看不见的力量操控? 其实是因为工业革命之后,随着科学技术的发展,加密解密这种 有规律的“体力活”已经可以由机器完成,它们既不会抱怨累,也不大容易出错。尤其是 19 世纪末进入电气时代,有了比蒸汽机更加强大且精巧的电动机,人们就更专注于研发 自动化机械设备,它们不仅能替代人类的体力劳动,还要替代人类进行脑力劳动。 ① 想了解更多关于Enigma 的技术细节和惊心动魄的故事,请阅读赵燕枫的《密码传奇》一书。 47 第 3 章 古典密码的历史 谁的发明 将某项发明的荣誉授予个人总是备受争议。人们将白炽灯的发明归功于托 马斯·爱迪生,但是其他研究者也曾研制了类似的灯泡,从某种意义上说,爱迪生 只是比较幸运地获得了专利。人们认为是莱特兄弟①发明了飞机,但他们曾与其 他人竞争并受益于其他人的研究。在某种程度上,他们又被达·芬奇抢先了,这位 全才早在15世纪就有了玩玩飞行机器的想法,不过达·芬奇的设计看起来也是借 鉴了前人的思想。当然,对于这些发明,被认定的发明人的杰出贡献基本上是毋庸 置疑的。 到底是谁发明了维吉尼亚密码,历史上是有很多争议的。一般认为,设计出 这套加密方法的是法国外交官布莱斯·德·维吉尼亚;但是在维吉尼亚完成这 项发明之前40多年,德国炼金术士约翰尼斯发明的表格法就包含了多表代换的 关键部分;在此之前80多年,意大利诗人莱昂就提出过这种方法的关键思想。 穷究一个发明的归属有必要吗? 当然没有。但这里面有一个规律———凡是出现 了一堆人抢一个发明权的情况,就说明那个领域已经比较成熟了。 同样,对于维吉尼亚密码的解法到底是谁搞出来的也有争议。20世纪之 前,人们一直以为是卡西斯基在1863年破解的,称之为卡西斯基试验。随着更 多资料的公布,人们发现剑桥大学的巴贝奇在更早的9年前就已经写出了解法。 只不过受限于当时英国和俄国的克里米亚战争,英国情报部门禁止他公开发表 成果。损失了一个发明者的荣誉,换来的是英国轻松获得俄方机密文件的技术 优势。发明者无法第一时间发表成果获得荣誉,这既是密码学领域的特点,又是 密码学研究者躲不过的委屈。 如图3.18所示,左图就是转轮机的转子,右图则是转轮机的加密原理。为了简单起 见,这里仅用6个字母代表所有的明文符号(在实际中如果使用英文,就是总共26个字 母)。在图3. 18右图(a)中,可以看到,转子的作用就是把键盘上的每个字符(明文)通过 电线连接映射到显示器上的小灯(密文)。如果按下了b键,显示器上的A灯亮起,这就 表示b被加密为A了,这就是简单代换密码。当然,如果只是这么简单,那么手工加密就 足够了,何必搞出这么一套机械来? 所谓转子,就意味着会转动! 当按下一个键之后,相 应的密文在显示器上显示,然后转子就自动地转动一个字母的位置。 图3.a)中, 信号通过转子中的连线,A灯亮;放开b键 18的右图(第一次按下b键时, 后,转子转动一格, 18右图(中, 在图3.b) 第二次按b键时, 各字母对应的密文就改变了; 18右图(中, 它对应的字母就变成了C;在图3.c) 基于同样的原理,第三次按b键时,E灯 亮。这显然不是一种简单代换密码了。明文中多个相同的字母可以被代换为不同的符 号,而密文中的同一个符号可能代表明文中的不同字母,频率分析法在这里没有了用武之 地。这种加密方式就是3.也称为复式替换密码。 2节介绍的多表代换密码, ① 莱特兄弟(Wrs)是美国著名的科学家,哥哥是威尔伯·莱特(Wit),弟弟是奥维尔·莱 特(OrvileWright)。 ightBrotherlburWrigh 48 信息安全导论 图3.18 转轮机的转子(左)及其加密原理(右) 但是,如果连续按6个字母键(在实际中是英文的26 个字母), 转子就会整整转一圈, 回到原始的位置上,这时编码就和最初重复了。而在加密过程中,重复的现象是很危险 的,这可以使试图破解密码的人发现规律性的东西,即3.3节讲到的卡西斯基试验。 2. 于是,谢尔比乌斯在设计Enigma 的时候又加了两个转子(在第二次世界大战后期, 德国海军用的Enigma 甚至有4个转子)。当第一个转子转动一圈之后,就会带动第二个 转子转动一个字母的位置;而第二个转子转动一圈之后,同样会带动第三个转子转动一个 字母的位置。这样看起来有点像钟表的秒针、分针和时针的齿轮关系①。所以,用3个转 子之后相当于加密了26×26×26=17576 个字母之后才会重复原来的代换映射。当然, 这3个转子是不一样的,如果把它们交换一下位置,还可以出现6种不同的组合。后来德 国海军甚至搞出了8个不同的转子作为标配,每次从中挑出3个使用,这就出现了 6×C32016 种不同组合。 8= 此外,谢尔比乌斯在键盘和第一转子之间还增加了一个连接板(pd), 如 19 所示。在右图中能够看到, lugboar 图3.使用者可以用一根连线把某个字母和另一个字母连接 起来,这样,这个字母的信号在进入转子之前就会转变为另一个字母的信号。这种连线最 多可以有6根(后期的Enigma 加上了更多的连线), 这样就可以使6对字母的信号互换, 其他没有插上连线的字母保持不变。不要小看了这一机关,它增加了100391791500 种 ① 在此基础上,谢尔比乌斯十分巧妙地在3个转子的一端加上了一个反射器。这个机关可以使译码的过程和 编码的过程完全一样。也就是说,只要转轮的设置(相当于密钥)一样,从键盘输入密文之后,同样可以在灯盘 (d)上亮起小灯,指示解密后的明文。 lampboar 第 3 章 古典密码的历史 49 不同的变化,配合3个转子的变化,已经有了超过一兆种可能性。 图3.19 Enigma 密码机 从1925 年开始,谢尔比乌斯的工厂开始系列化生产Enigma,次年德军开始使用这些 机器。在接下来的10 年中,德军大约装备了3万台Enigma 。 谢尔比乌斯的发明使德国具有了最可靠的加密系统,这也是德军常用的战术———闪 击战(也称闪电战)屡屡成功的关键。在这种大规模快速协同作战中,各装甲部队之间,它 们和步兵、炮兵之间必须能够快速而保密地进行联系。不仅如此,地面部队的进攻还必须 由轰炸机群掩护支援,它们之间也必须有可靠的联络手段。可见,闪击战的力量在于在快 速安全的通信保证下的快速进攻。而在第二次世界大战开始的时候,装备了Engma 的 德军,其通信的保密性在当时世界上无与伦比。 i 3.3.2 矛与盾的强力碰撞 对Enigma的破解之旅起始于波兰———这个对德国怀有极大恐惧的国家。从地理位置 上不难看出,第一次世界大战之后,波兰的局面很不乐观:西面是对失去旧日领土耿耿于怀 的德国;而在东面,则是强大的苏联。关于这两个强邻的情报是有关生死存亡的大事! 为了搞清楚德国军方的意图,波兰人费尽心力,把当时国内最优秀的数学家①都招募 起来进行密码研究。在此以前,密码分析人员通常是语言天才,需要精通对语言方面特征 的分析。而波兰的这一举措,开创了批量动用数学家参与密码破解的先河。以雷杰夫斯 基为首的波兰数学家没有辜负政府的期望,他们通过跟踪分析、算法改进、机械设计等手 段,成功破解了早期的Enigma,获取了一些德军情报。 到了1939 年,波兰人对德军的密码分析之路已经走到了尽头:一方面,德军在 Enigma 不断升级的过程中填补了很多漏洞,而波兰军方的破解工作在人力、物力、财力 上都难以为继;另一方面,第二次世界大战马上要全面爆发了,波兰的沦陷就在眼前。 于是,波兰情报部门在7月将自己的破译成果———Enigma 仿制品和破译机器的图纸 ① 代表人物就是后来被称为密码研究“波兰三杰”的马里安·雷杰夫斯基(MarianRejewski)、杰尔兹·罗佐基 (JerzyRozycki)和亨里克·佐加尔斯基(HenrykZygalski)。 50 信息安全导论 等———全部送给了法国和英国盟友。就这样,在击败Enigma 的漫漫征途上,波兰人跑完 了第一棒,现在,轮到英国人接棒了。为什么不是法国人呢? 因为第二年6月,法国也迅 速兵败投降了。 英国密码局在伦敦以北约80km 的一个叫布莱切利的地方征用了一座庄园,建立一 个新的机构———政府代码及加密学校(GovernmentCodeandCipherSchool,GC&CS )。 此后,英国密码局开始通过局内人际关系从牛津大学和剑桥大学招聘数学家和数学系学 生,其中就有后来举世闻名的“计算机科学之父”和“人工智能之父”阿兰·图灵。 图灵等人仔细分析了波兰人的成果和德军密电的特点,在此基础上设计了一种更加 通用的破译机器———Bombe( 如图3.经过 炸弹), 20 所示。在丘吉尔首相的亲自过问下, 图灵和同事们的不懈努力,布莱切利庄园克服了经费不足和人才短缺的困难。到1942 年 底,英国密码局拥有了49 台Bombe,密码分析人员的队伍也在持续扩大。与此同时,针 对敌人的情报战也不断取得胜利。到了1943 年8月,布莱切利庄园已经可以100% 破译 该月所截获的德军重要密电了。 图3.20 Bombe仿制品的外观(左)与内部结构(右) Enigma 作为“一代名机”,以极高的起点傲然出世,多年以后又遭到了毁灭性的打 击。再联系上波澜壮阔的第二次世界大战,其戏剧性之强,在密码学历史上也着实罕见。 回顾转轮密码机Enigma 的这段经历,可以给我们带来了很多思考和启示: .科学技术的发展是密码学得以前进的基石。相比单表代换,多表代换的破解难度 上了一个新的台阶,按理说应该备受青睐吧? 结果恰恰相反———它在出现后的 200 年里,几乎没有人使用。直到第一次工业革命,用机械代替人力,多表代换才 得到推广。而Enigma 的发明也很大程度上归功于第二次工业革命之后电器设 备的出现。 .实践的需要是推动密码学前进的最大动力。Enigma 发明之初并不被人看好,而 一旦绑上德国的隆隆战车,就获取了充分的施展空间。英国一开始对Enigma 的 破译并不上心,但眼看欧洲局势不可收拾了,才倾尽全国之力打造破解工具。 .密码编码和密码分析既彼此对抗,又相互促进。Enigma 以机械化编码的方式终 结了纯手工编码的千年历史,而Bomba(波兰研制的破解设备)和Bombe又以机 械化分析的方式终结了Enigma 。它们的出现又推动密码学在第二次世界大战之 后进入了计算机主导的阶段,正所谓“长江后浪推前浪”。 第 3 章 古典密码的历史 51 .在密码对抗乃至整个信息安全领域中,人的因素是第一位的。没有谢尔比乌斯等 人的设计,Enigma 不会出世;没有以雷杰夫斯基为首的波兰数学家的贡献, Enigma 的破解就缺少基础;没有图灵等人的努力,Enigma 也不会最终败亡。整 个过程表明,那种传统的、几个语言学家在小黑屋里埋头苦干的古典密码编码和 分析方式已经彻底过时了。面对更加复杂的系统,必须有更多人的高效分工和密 切配合,才可能获得成功。 .密码对抗的代价,或者说信息战的代价,随着科学技术的发展日趋增大。Enigma 这种看似成本不算太高的设备,在纳粹德国也只是装备到了陆军团以上的部队。 在破解Enigma 的过程中,波兰倾家荡产也无法应对到底,英国更是投入难以计 数的人力物力。信息战这个几千年来原本是个人对个人、小团队对小团队的斗智 斗勇,在最近的几十年里竟然发展成为国家与国家综合实力的全面碰撞。而在这 条看不到尽头的道路上,谁也无法停下狂奔的脚步。