古典密码

第 1 章 古典密码：两千年前的猫鼠游戏

保密的冲动和文字的历史

文字一旦发明，窃听就发明了。这两件事几乎是同一件事，因为文字的本质就是把话固定在载体上，而固定下来的东西可以被截获、被抄录、被送到你不想让它去的地方。口信可以托付给忠诚的信使，泥板和纸草却只忠于捡到它的人。于是人类几乎在学会写字的同时，就开始琢磨怎么写得让外人看不懂。最古老的保密手段不是把字藏起来，而是把字变掉。考古学家在美索不达米亚的楔形文字泥板上找到过刻意的非标准拼写，古埃及的抄书人也会用生僻符号替代常用字，为的是让同行以外的眼睛读着费劲。这些小把戏谈不上密码学，但那个念头已经在了：我写下的东西，不是写给所有人看的。

密码学这个词本身就说明了它的出身。希腊语里 kryptos 意思是隐藏，graphein 意思是书写，合起来就是隐写术。严格说，古典时代的人把两种手艺分得很清。一种叫隐写，靠的是藏，把信写在刮平的蜡板底下、写在剃了头发的头皮上等它长出来，外人根本不知道有消息存在。另一种才是密码，靠的是变，消息大大方方送出去，谁都能抄走，抄走也读不懂。隐写是掩耳盗铃式的赌运气，一旦被发现就全军覆没；密码则是明牌迎战，赌的是你拿到了也解不开。这条分界线后面会反复出现，因为整个密码学史，本质上就是后者从手艺变成科学的历史。

为什么人类如此执着于保密？答案平庸得近乎无聊：战争、钱、爱情和政治。色诺芬写斯巴达的军政，修昔底德记伯罗奔尼撒战争的谈判，处处都是需要瞒着敌方传递的消息。商业竞争需要保护配方和账目，宗教传统里有只许入教者知晓的仪轨，宫廷政治里一句话说错就是人头落地。需求从来不是问题，问题始终是手段。而手段的水平，说到底取决于当时的人对语言和数字理解到什么程度。这是我写这本书想反复强调的一个判断：密码技术的每一次跃迁，背后都是数学的一次跃迁，前者只是后者的影子。

本书要讲的是一场持续两千多年的猫鼠游戏。一边是密码的设计者，想出各种办法把信息搅乱；另一边是密码的破译者，想出各种办法把搅乱的信息还原。游戏最迷人的地方在于规则不断升级：设计者的每一次胜利都逼迫破译者发明新武器，而破译者的每一次胜利又逼迫设计者抛弃旧思路。凯撒、金迪、维吉尼亚、巴贝奇、香农、迪菲、里维斯特、肖尔，这些名字分属不同的世纪和阵营，却都在同一条战线上接力。看懂这条接力线，你就看懂了数学如何一步步接管了人类保密的事业。

这一章先回到起点。我们从公元前一世纪的罗马讲起，看看最古老的密码长什么样，它为什么曾经够用，又为什么在九个世纪后被一位阿拉伯学者用一种全新的思路击穿。再往下，我们会见到玛丽女王如何为一个不争气的密码付出了头颅，最后用一点初等数论把古典密码的骨架抽象出来，为后面的章节搭好舞台。

凯撒的移位：三格的距离

关于凯撒密码，最可靠的记载来自苏维托尼乌斯。这位罗马作家大约在公元121年写成《罗马十二帝王传》，其中凯撒传的第五十六节明白写道：凯撒若有密事要传达，便使用密写，也就是把字母表中的字母顺序打乱，使得没有一个词能被直接读出；若要解读，须将字母表中的第四个字母，也就是D，代入A的位置，其余照此类推。这段话信息量很大。它不仅描述了操作方法，还隐含了一个事实：苏维托尼乌斯敢在书里明写，说明这套方法在凯撒死后一百六十年已不再是罗马的国家机密。密码史上一个耐人寻味的规律从这里就露头了，方法本身总会泄露，能保住长久的只有别的东西。

方法本身简单到一句话讲完：把每个字母沿字母表向后移三位。A变成D，B变成E，一路推下去，X、Y、Z排到头了就绕回A、B、C。凯撒那句著名的战报 VENI VIDI VICI，我来了，我看见了，我征服了，加密后就变成 YHQL YLGL YLFL。收信人把每个字母向前挪三位，原文立刻恢复。移位的格数就是密钥，凯撒用的是3，其实可以是1到25里的任何数。顺带一提，凯撒的继承人奥古斯都也用类似的方法，但据苏维托尼乌斯记载，他偷懒只移一位，B对A，C对B，遇到罗马数字里的X还嫌麻烦，直接用AA顶替。皇帝的密码素养，显然不如养父。

这套东西在今天看来不堪一击，在当年却是够用的。首先，能读拉丁文的敌人本来就不多，能在截获的信件前坐下来系统尝试二十五种移位的更是凤毛麟角。其次，凯撒面对的对手，高卢部落的首领、庞培的军官，没有人想到文字的规律可以被系统利用。密码的安全性从来是相对于时代的攻击能力而言的，这句话请记住，后面每一章它都会以不同面目出现。二十五个密钥的穷举，对一个熟练的抄写员来说不过半个下午的工作，但前提是有人想到去穷举。

有趣的是这个想法在现代还有回声。上世纪八十年代互联网新闻组流行过所谓ROT13，就是把字母移十三位，因为十三正好是二十六的一半，加密解密是同一个操作，敲两遍就还原。人们用它来隐藏笑话的包袱、谜题的答案和影评的剧透。一个两千年前保护军情的方案，如今用来防剧透，倒也说明了它真实的保密水平。技术没有变，变的是我们对它的期望。

现在换上数学的眼睛。把字母表编号，A到Z依次记为0到25，凯撒加密就是一次加法：密文字母等于明文字母加3，超过25就减去26。这个减26的操作有个学名叫模运算，说白了就是钟表算术。钟面上十二点加三小时是三点而不是十五点，因为满了十二就归零重来。字母表就是一面二十六格的钟。用式子写出来，加密是 c 等于 m 加 3 再对 26 取余，解密是 m 等于 c 减 3 再对 26 取余。整个古典密码的大半壁江山，都建立在这么一块二十六格的钟面上。数学化的好处立刻显现：一旦写成算式，方法和密钥就分离了。方法是那个加法，密钥是那个3。方法可以公开，密钥必须保密。古罗马人靠直觉这样做了，但要等近两千年后克尔克霍夫把这条原则明确写下，人们才真正想清楚它。

移位密码还有一个容易忽略的软肋：它的方法太有名了。假如敌人知道你用的是移位，那密钥只剩二十五种可能；假如敌人连移位这件事都不知道，那你连二十五个备胎都没有，直接安全。换句话说，凯撒密码的安全性押在方法保密上，而这恰恰是最靠不住的赌注。方法的泄露只需要一次醉酒的抄写员或者一封被缴获的说明书。把安全押在密钥而非方法上，这个观念要等到1883年才由克尔克霍夫系统阐述，但凯撒的继承者们用血的教训提前预演了它的反面。

从移位到替换：一张任意对照表

移位的破绽很明显，字母的相对顺序没有变，只是整体挪了位置。既然如此，不如彻底打乱：给每个字母指定一个任意的替身，A可以去当Q，B去当M，Z去当C，二十六个字母任意排列组合，这就是替换密码，也常叫单表替换，因为全文只用一张对照表。凯撒移位其实是它最规则的特例，即对照表恰好保持字母顺序。从移位到替换，保密的直觉前进了一大步：明文与密文之间的对应从有序变成了任意。

这个任意性在数学上意味着什么？意味着对照表有二十六个字母的全排列那么多张，也就是26的阶乘。算出来是大约4.03乘10的26次方，四百万亿亿亿这个量级。给个直观参照：宇宙年龄约一百三十八亿年，折成秒大约4.35乘10的17次方。就算从宇宙大爆炸那一刻起，每秒核查十亿张对照表，到今天也才查了4乘10的27次方张的一小部分，连零头的零头都不到。十六世纪的密码员对此相当自信，他们的账算得没错：穷举在物理上不可能。

可替换密码偏偏就是被破了，而且破得干干净净。这里藏着密码学第一课：密钥数量不等于安全性。安全性取决于敌人最聪明的那条攻击路径，而不是所有路径的平均长度。替换密码的密钥空间确实大得吓人，但它的每一个密钥都带着同一个先天缺陷，一张固定的对照表把明文语言的统计特征原封不动地搬运到了密文里。字母E不管换成什么替身，它出现的次数还是那么多，出现的位置还是那么密集。密钥空间的巨墙之下，有一条统计的小路可以直接绕过去。这条路怎么走，下一节细说，先看看替换密码在历史上混得如何。

历史上真正长期服役的其实不是纯粹的替换，而是一种混血儿，叫密码本，也有译名鉴或代码表的。它一半是替换表，管常用字母；一半是代码本，管高频词和人名地名，比如巴黎用数字71代表，舰队用数字42代表，再塞进一些什么都不代表的空字符捣乱。现存最古老的这类手册保存在梵蒂冈，是1379年人为对立教宗克莱门七世编的，出自加布里埃尔·德·拉万德之手，用的是字母与数字的一套对照。此后三百年，欧洲各王室的外交信函几乎全靠这种名鉴撑着，法国亨利四世的首相面对截获的西班牙密信能从容拆解，靠的就是一批职业密码秘书的案头功夫。

密码员们其实隐约意识到了频率这个软肋，也想出过补救办法。比如同音替换，给高频字母配备好几个替身，E可以有七个不同的符号轮流出现，把它的锋芒摊薄；再用空字符和假的重复往统计里掺沙子。这些花招确实让简单数数变难了，但只是治标。因为语言的指纹不止印在单个字母上，还印在字母的搭配上：哪个字母后面常跟哪个字母，哪些双字母组合常见，哪些字母从不挨在一起，这些规律在多替身方案下依然会渗出来。只要对照关系始终固定，即单表的本质不变，语言的统计指纹就总在。这是古典密码的宿命，逃不掉的。

巴格达的智慧宫：频率分析诞生

击穿替换密码的人不在欧洲，在九世纪的巴格达。彼时阿拔斯王朝的智慧宫正是世界知识的十字路口，希腊的哲学、印度的算术、波斯的行政档案在此交汇翻译。这批翻译运动养出的学者里，有一位艾布·尤素福·雅各布·本·伊斯哈格·金迪，后世尊称肯迪，西方文献里常写作阿尔·金迪。他约公元801年生于库法，约873年卒于巴格达，编目在册的著作超过二百五十种，横跨哲学、天文、医学、炼金术和音乐理论，欧洲人叫他阿拉伯人的哲学家。就是这样一位全才，在密码学史上留下了可能是第一份系统的破译方法论文。

这份论文题为《论破译加密信件》，命运坎坷。它在欧洲学术界消失了近千年，直到1987年，人们才在伊斯坦布尔的苏莱曼尼耶奥斯曼档案馆里重新发现仅存的一份抄本，其后经学者整理刊布，学界这才知道，频率分析这项欧洲人以为自己十六世纪才发明的技术，阿拉伯人早用了七百年。这提醒我们一个令人惭愧的事实：密码学史的叙事长期被欧洲中心视角垄断，而中世纪的伊斯兰文明不但保存了古典知识，还原创性地推进了它们，密码破译正是其中被忽视的一章。

金迪的方法核心，用他自己的话说，大意是：我们发现所有语言中字母出现的频率并不均等，有的字母多，有的字母少，有的居中；最常出现的字母在一段足够长的文本里也最常出现。所以破译密信的第一步，是统计密文中每个符号出现的次数，数出符号的频率，再看它对应哪种语言的已知频率。这段话在今天读来平淡无奇，但它做了一件划时代的事：把破译从猜谜变成了测量。破译者不再需要灵感，需要的是一张统计表和足够的耐心。

拿英语做个演示。统计大量英文文本可以得出字母频率的稳定排序：E一枝独秀，约占12.7%，T约9.1%，A约8.2%，O约7.5%，I约7.0%，N约6.7%；另一头，Z只有0.07%，Q约0.095%，J和X都在0.15%上下。阿拉伯语也有自己的榜单，字母艾利夫同样稳居头名。拿到一段替换加密的密文，先数出每个密文符号的次数，排个序，再把它对齐到已知语言的频率榜上，最可能的对应关系就浮出水面了。比如密文里出现最多的那个符号，八成就是E的替身。当然单靠一次对位不会全对，但这只是开始而不是结束。

金迪论文的精妙处在于他没有停留在数单字母。他指出字母有两类，一类像元音那样百搭，和谁都能组合，一类像辅音那样挑食，只固定出现在少数邻居身边。所以频率之外，还要看一个符号都和谁搭伙，从不和谁搭伙。这个思路在现代语言学术语里叫字母亲和性，放到破译实践里就是第二重过滤：先按频率给出候选，再用位置关系修剪错误候选。此外还有双字母组合的统计，英语里TH、HE、IN的出场率远高于其他组合，常见的词尾ING，高频短词THE，这些都是可以按图索骥的绳索。到了这一步，破译已经不是概率游戏，而是逻辑推演。

方法在阿拉伯世界代代打磨。十二世纪的伊本·阿德兰，生于1187年，卒于1268年，留下过一条非常现代的提醒：样本太短，频率就会失真，他给出的经验底线是密文至少要有九十来个字母才值得动手统计。这个数字的敏锐令人吃惊，它说明阿拉伯学者已经在直觉层面理解了抽样波动。到十四世纪，伊本·杜莱希姆在著作里系统列举了破译的多种套路，包括利用疑似词语，即猜测密文中必然出现的专名和套语。集大成的是1412年前后完稿的百科全书式巨著《盲人的曙光》，编者卡尔卡尚迪在讲行政文书的章节里完整总结了前人的破译术，频率、亲和、疑似词、空字符，一应俱全。可以说，到十五世纪初，单表替换的一切变体在理论上已经全部缴械。

空口无凭，走一遍流程。假设密文头三十个字母里有个符号出现了四次，高居榜首，那它多半对应E，先标上。再看一段恰好两次重复的三字母组合，如果它的首字母正是那个疑似E的符号，英语里E打头的常见三字母组合无非ENT、ERC、EVE之类，候选一下子窄了。接着找单字母成词的符号，那必是A或I，交叉验证刚才的判断。再挑出一个出现两次的双字母组合，若其中一个是已知的E，另一个高频，那多半是TH、HE、ER里的角色。几轮下来，密文骨架上的字已经能读出小半，剩下的空位用普通拼写知识补齐，整张对照表便告失守。整个过程不需要一次瞎蒙，每一步都是小步推理加验证，这正是频率分析可怕的地方：它把灵感的活儿变成了流水线的活儿。

这里我必须亮出自己的判断：频率分析是密码学的第一个科学武器，也是统计学在应用领域最早的胜利之一。它比概率论的正式诞生还早了七百年，比贝叶斯方法早了九百年。它背后的世界观是，看似随机的表象之下藏着可测量的规律，而规律可以被利用。这种世界观后来支撑了整个经验科学。欧洲人是迟到的学生，直到十三世纪前后才通过接触阿拉伯文献窥见门径，文艺复兴时期的梵蒂冈密码房将其发扬光大。而它带来的直接后果很快显现：整个十六世纪，欧洲的密码员都活在被破译的恐惧里，于是有人想出了新招，那正是下一章的主角。

密码棒、火炬与蜡板：不只是换字母

在替换密码之外，古典世界还有另一族手艺，走的是完全不同的路子。最有名的是斯巴达密码棒，希腊语叫斯基塔莱。普鲁塔克在《吕山德传》里记了用法：发送方把一条羊皮纸或皮革带螺旋缠绕在一根木棒上，顺着棒轴的方向书写消息，写完把带子解下来，上面的字母乱作一团。收信人拿一根粗细相同的木棒把带子缠上去，字母就回到原位。注意这里没有任何一个字母被替换，E还是E，只是它们的位置被打乱了。这类手法后来统称换位。替换改变字母的身份，换位改变字母的座位，二者是古典密码的两大支柱，后世的密码几乎都是这两类操作的叠加与反复。

换位的密钥就是那根木棒的粗细。粗细不对，缠出来的字母就永远对不齐，这大概是历史上唯一一种密钥本身是木头的密码。它的强度来自简单，弱点也来自简单：试出正确的粗细并不需要太多木匠活，历史上斯巴达的敌人们想必没少吃这个亏，只是文献记载不多。换位思想本身倒是长寿，二战时德军、日军都用过换位与替换结合的方案，现代分组密码里的扩散操作，追根溯源也是换位的嫡系后代。

公元前二世纪，希腊史家波利比奥斯发明了另一种影响深远的方案。他把字母填进五乘五的方格，每行每冠以数字一到五，每个字母由两个数字定位，比如A是11，B是12，C是13。古希腊二十四个字母挤进二十五格，把不需要的并掉一格即可。这套方格的妙处在于输出变成了纯数字，于是可以配合火炬发报：右边的火把数目表示行，左边的表示列，几个起落就能把一个字母送上城头。波利比奥斯自豪地宣称这是他发明过的有用东西里最有效的。从信息论的角度看，这其实是把字母表翻译成了一个五进制编码，是电报码和后来诸多编码方案的远古雏形。它本身不保密，但叠加换位或替换之后便是一等一的实用密码， 直到近代还有变体在用。

还有一族靠藏不靠变的技术也值得记一笔。希罗多德在《历史》里写过两个名场面。一个是公元前499年前后，米利都的僭主希斯提亚乌斯想给波斯治下的侄子传话起事，把信使的头发剃光，刺上字，等头发长出来再派他上路，消息就这样藏在头皮里走完了全程。另一个是前480年，被放逐的斯巴达王德玛拉托斯把警告波斯即将入侵希腊的消息刻在木板上，再覆上一层蜡，装作一块空白蜡板混出了边境。公元前四世纪的军事作家埃涅阿斯·塔克蒂库斯更写过专论，系统罗列了藏信的种种门道，包括用不易察觉的墨水，比如坚果水或胆汁干后无色、遇热显字，堪称隐形墨水的祖师爷。这类手段学名隐写术，与密码术合则两利，分则各安其位。

顺带还能举出更古老的文字游戏。希伯来传统里有一种Atbash密码，把二十二个字母表首尾对调，第一个字母换最后一个，第二个换倒数第二个。《耶利米书》五十一章第一节的示沙克，学界主流解读就是巴比伦一词经Atbash变换的结果，先知用这种方式指代强敌又不直呼其名。这是有文字记载的最古老的替换密码实例之一，时间比凯撒早了五百年。可见把字母表首尾对折的冲动，是各文明独自也能长出来的幼苗。

换位家族的后代也绵延不绝。1550年前后，米兰的医生兼数学家卡达诺设计过一种漏格板，在硬纸上开出若干窗口，罩在白纸上从窗口写入消息，移开格子再在空隙处填满无关词句，读的人只要把同样的格子一罩，秘密立即显形。这玩意儿构造幼稚，却抓住了换位的精髓，即位置本身就是密钥，后来两次大战里还有它的变体在军中服役。可见古典时代的设计者并非只会换字母，他们缺的不是想象力，而是度量自身方案强度的那把尺子。

盘点这些古典装置，能发现一个共同点：它们的安全都建立在方法的秘密之上。棒子的粗细、方格的排法、蜡板下的刀工，哪一样泄露都是灭顶之灾。这和凯撒密码的困境一模一样。要害不在于哪件具体手艺不牢靠，而在于整个思路的地基就有问题。地基的问题，要等一千九百年后克尔克霍夫和香农来拆，眼下还得先看完这场思路在欧洲宫廷里酿成的血案。

玛丽女王的头颅：被破译判处的死刑

1586年，苏格兰女王玛丽·斯图亚特已经在英格兰被她表姐伊丽莎白一世关了将近十九年。她是天主教徒眼中名正言顺的英格兰王位继承人，也是新教英格兰朝廷眼中最危险的活棋。这年夏天，一群英格兰天主教贵族策划了一个大胆的计划，史称巴宾顿阴谋：刺杀伊丽莎白，迎立玛丽。核心人物安东尼·巴宾顿要跟被软禁在查特里庄园的女王建立秘密通信，于是托人搞到一套密码。这套密码是当时典型的名鉴式方案：一张字母与符号的对照表，加上若干代表整词和地名的代码，再加上一些专门添乱的空字符。放在1586年，这不算敷衍，是正经的宫廷配置。

问题出在信道上。巴宾顿托的中间人吉尔伯特·吉福德，其实从一开始就是伊丽莎白国务大臣弗朗西斯·沃尔辛厄姆的人。这位国务大臣在伦敦经营着英格兰第一所职业谍报机构，豢养密码员、线人和双重间谍，深谙截来信不如放长线的道理。于是玛丽与巴宾顿的密信被安排走啤酒桶的路线，先送进吉福德手里，抄录、破译、再原样封好送达，双方浑然不觉。沃尔辛厄姆的首席破译员托马斯·菲利普斯是个天才，他很快吃透了这套名鉴，之后每一封信到他手里都是明文。

沃尔辛厄姆要的不是密信，是死罪。光有通信不够，得让女王亲口下令杀人。于是密码史上最阴险的一次伪造登场了：菲利普斯在破译出一封信后，用同一套密码在信尾伪造了一段附言，以玛丽的口吻追问巴宾顿，计划中那六位绅士的名字和安排。巴宾顿照实回答，把自己和同伴的名字亲手写给了刽子手。传说菲利普斯还在某份破译稿的空白处画了一个小小的绞刑架，后人考证未必属实，但这个细节流传之广，恰恰说明人们认定这种冷酷当得起这个符号。1586年10月，玛