第十三章 破译密码的哲学家
密码的用途极为广泛。 出于军事、政治、经济等许多方面的需要， 信息的保密是十分重要的。 于是， 人们自然想到要把容易理解的信息转换成难以理解的符号。 这样， 只有掌握密码信息的人才能把实际信息进行逆向回复， 而缺乏密码信息的拦截者或者窃听者则无法解读。
在中国古代兵书《六韬·龙韬》里就记载了密码学的使用。 其中《阴符》和《阴书》两篇记录了大约 3 000 年前周武王与姜子牙讨论在征战期间主帅同其他将军之间应该如何进行通讯的问题:
太公曰:“主与将， 有阴符， 凡八等。 有大胜克敌之符， 长一尺；破军擒将之符， 长九寸；降城得邑之符， 长八寸；却敌报远之符， 长七寸；誓众坚守之符， 长六寸；请粮益兵之符， 长五寸；败军亡将之符， 长四寸；失利亡士之符， 长三寸。 诸奉使行符稽留， 若符事泄， 闻告者皆诛之。 八符者， 主将秘闻， 所以阴通言语， 不泄中外相知之术。 敌虽圣智， 莫之能识。 ”武王问太公曰:“……符不能明；相去辽远， 言语不通， 为之奈何?” 太公曰:“诸有阴事大虑， 当用书， 不用符。 主以书遣将， 将以书问主。 书皆一合而再离， 三发而一知。 再离者， 分书为三部。 三发而一知者， 言三人， 人操一分， 相参而不相知情也。 此为阴书。 敌虽圣智， 莫之能识。 ”
这里所说的 “阴符”， 是用 8 种不同长度的符来表达不同的消息和指令。 这可以说是密码学中的替代法， 也就是把信息转变成敌人看不懂的符号。 而 “阴书” 采用的则是移位法， 把书信分成 3 份， 由 3 个不同的人传递。 这样， 必须把 3 份书信重新拼合才能获得还原的信息。
周武王和姜子牙所采用的方法当然和中国文字的特征有关。 在使用字母的国家里， 改变字母顺序是最方便的加密方法。 在古希腊， 最常用的传递军事信息的方法是密码棒。 所谓密码棒是一根经过加工的具有圆形或多边形截面的木棒。 它的原理很简单。 发信人把一根布带绕在木棒上， 在布带上写下信息。 信息是绕着木棒写的， 每绕一圈写一行字母， 然后继续转到下一行， 再下一行等等。 这样， 写完了信息之后， 把布带从木棒上拿下来， 布带上的字母顺序就打乱了。 当布带传到密码接受者的手上时， 他需要用一根相同尺寸的木棒， 把布带也就是密码条缠在上面， 信息的顺序就恢复了。 据史书记载， 斯巴达人早在公元前 6 世纪时就采用这种密码棒来传递军事信息了。 这种方法有解读快速而且不容易出现误解的优点， 所以在战场上大受欢迎。 但是要破解它也非常容易， 只要试几根直径不同的木棒就好了。
在第十二章的故事里， 苏格兰女王玛丽一世使用的密码比这些都更复杂。 但是从图 12.4， 我们看到密码使用的符号同英文字母基本上是一一对应的。 这种对应关系是玛丽的密码的致命弱点， 因为通过统计的方法， 找到加密字符与实际字母之间的相关性， 就可以破译。
作为例子， 我们先看看下面这段用密码写成的文字:
FDOO PH LVKPDHO. VRPH BHDUV DJR. QHYHU PLQG KRZ ORQJ SUHFLVHOB. KDYLQJ OLWWOH RU QR PRQHB LQ PB SXUVH. DQG QRWKLQJ SDUWLFXODU WR LQWHUHVW PH RQ VKRUH. L WKRXJKW L ZRXOG VDLO DERXW D OLWWOH DQG VHH WKH ZDWHUB SDUW RI WKH ZRUOG. LW LV D ZDB L KDYH RI GULYLQJ RII WKH VSOHHQ DQG UHJXODWLQJ WKH FLUFXODWLRQ. ZKHQHYHU L ILQG PBVHOI JURZLQJ JULP DERXW WKH PRXWK. ZKHQHYHU LW LV D GDPS. GULCCOB QRYHPEHU LQ PB VRXO. ZKHQHYHU L ILQG PBVHOI LQYROXQWDULOB SDXVLQJ EHIRUH FRIILQ ZDUHKRXVHV. DQG EULQJLQJ XS WKH UHDU RI HYHUB IXQHUDO L PHHW. DQG HVSHFLDOOB ZKHQHYHU PB KBSRV JHW VXFK DQ XSSHU KDQG RI PH. WKDW LW UHTXLUHV D VWURQJ PRUDO SULQFLSOH WR SUHYHQW PH IURP GHOLEHUDWHOB VWHSSLQJ LQWR WKH VWUHHW. DQG PHWKRGLFDOOB NQRFNLQJ SHRSOH? V KDWV RII. WKHQ. L DFFRXQW LW KLJK WLPH WR JHW WR VHD DV VRRQ DV L FDQ. WKLV LV PB VXEVWLWXWH IRU SLVWRO DQG EDOO. ZLWK D SKLORVRSKLFDO IORXULVK FDWR WKURZV KLPVHOI XSRQ KLV VZRUG. L TXLHWOB WDNH WR WKH VKLS? WKHUH LV QRWKLQJ VXUSULVLQJ LQ WKLV. LI WKHB EXW NQHZ LW? DOPRVW DOO PHQ LQ WKHLU GHJUHH. VRPH WLPH RU RWKHU. FKHULVK YHUB QHDUOB WKH VDPH IHHOLQJV WRZDUGV WKH RFHDQ ZLWK PH…
乍看上去令人一筹莫展。 在对加密方式一无所知的情况下， 能不能破译它呢?
我们仔细看看这段文字， 它包含除了 和 以外所有的英文字母。 这使我们猜测它可能是用英文字母改变顺序来加密的。 可是， 怎么验证这个猜测呢?
英文一共有26个字母， 如果把它们按照不同的顺序排列， 排列组合的知识告诉我们， 单是把26个字母都拿出来排列， 就有26!种， 也就是403， 291， 461， 126， 605， 635， 584， 000， 000 种排法。 考虑到从其中选出 2 个、 3 个、 4 个字母的排列， 排法就更多了。 显然， 要想一个一个地去检查这么多的可能性是根本没有希望的。
然而， 从统计学的角度来看， 破译它其实并不那么难。
这段话一共有 884 个字母， 稍微花一点时间， 我们可以查出每个字母在其中使用的次数， 其结果展示在表 13.1 里。 不同的字母出现的次数不同， 在文字分析中将这些相对的次数称为频率， 所以这张表叫作字母频率分布表。
表 13.1 加密信息的字母频率分布
| 字 母 | 出现次数 (频率) | 出现百分比 |
| A | 0 | 0.00% |
| B | 22 | 2.49% |
| C | 2 | 0.23% |
| D | 57 | 6.45% |
| E | 9 | 1.02% |
| F | 18 | 2.04% |
| G | 21 | 2.38% |
| H | 107 | 12.1% |
| I | 22 | 2.49% |
| J | 24 | 2.71% |
| K | 51 | 5.77% |
| L | 80 | 9.05% |
| M | 0 | 0.00% |
| $\mathrm{N}$ | 4 | 0.45% |
(续表)
| 字 母 | 出现次数 (频率) | 出现百分比 |
| 0 | 45 | 5.09% |
| P | 30 | 3.39% |
| Q | 62 | 7.01% |
| R | 62 | 7.01% |
| S | 25 | 2.83% |
| T | 2 | 0.23% |
| U | 56 | 6.33% |
| V | 53 | 6.00% |
| W | 76 | 8.6% |
| X | 26 | 2.94% |
| Y | 13 | 1.47% |
| Z | 17 | 1.92% |
怎么确定加密的文字是英文呢? 让我们随便找一篇英文文章， 比如英文报纸上的一篇报道， 看看正常英文 26 个字母出现的大致频率分布是什么样子的。 读了一段大约有 5000 个字母的文章以后， 我们得到一个频率分布， 见表 13.2， 表中每个字母下面的数字是该字母出现的百分数。
表 13.2 典型的英文报纸文章的字母频率分布
| A | B | C | D | E | F | G | H | I | J | K | L | M |
| 8.2 | 1.5 | 2.8 | 4.3 | 12.7 | 2.2 | 2.0 | 6.1 | 7.0 | 0.2 | 0.8 | 4.0 | 2.4 |
| $\mathrm{N}$ | 0 | P | Q | R | S | T | U | V | W | X | Y | Z |
| 6.7 | 7.5 | 1.9 | 0.1 | 6.0 | 6.3 | 9.1 | 2.8 | 1.0 | 2.4 | 0.2 | 2.0 | 0.1 |
单从这张表， 还是看不出什么苗头。 那好， 让我们把表 13.2 的字母频率和表 13.1 的数据一起画出来， 见图 13.1。 仔细看看这张图， 我们发现两个频率分布有很多类似的特征。 两者都有一些出现频率较高的字母。 英文报纸上出现最多的字母从左向右依次是A、E、H、I、N、O、R、S、T， 而加密信息里出现最多的字母依次是D、H、K、L、O、 示)， 那么这 9 个高频率字母就完全重合。 这使我们推论， 加密的信息极可能是英文， 而且加密方法是把字母做了表 13.3 给出的对应关系。
图 13.1 英文报纸中的字母频率分布 (蓝色) 和加密文字的频率分布(橙色)的比较。
。 如果我们把橙色的密码信息的频率分布向左移动 3 位 (如红色箭头所
表 13.3 根据图 13.1 猜测的加密信息中的字母对应正常英文字母的关系
| 英文 字母 | A | B | C | D | E | F | G | H | I | JK | L | M | $\mathrm{N}$ | 0 | P | Q | R | S | T | U | V | W | X | Y | Z |
| 密码 字母 | D | E | F | G | H | I | J | K | L | M$\mathrm{N}$ | 0 | P | Q | R | S | T | U | V | W | X | Y | 乙 | A | B | C |
我们可以尝试破译这个简单的加密方式: 从密码字母顺序中跳过 3 个字母， 选择第 4 个字母 D 作为起点， 这就是英文字母 A。 其余的按照英文字母顺序， 依次类推。 密码的Z用英文字母W来表示， 最前面跳过去的A、B、C则用X、Y、Z来表示。
那么这个猜测是否正确呢? 让我们对上面的加密信息做我们猜测的这种字母变换， 于是得到下面的文字 (为了便于阅读， 我们改变了全是大写的表示方法， 标点符号也加上去了):
Call me Ishmael. Some years ago - never mind how long precisely - having little or no money in my purse， and nothing particular to interest me on shore， I thought I would sail about a little and see the watery part of the world. It is a way I have of driving off the spleen and regulating the circulation. Whenever I find myself growing grim about the mouth; whenever it is a damp， drizzly November in my soul; whenever I find myself involuntarily pausing before coffin warehouses， and bringing up the rear of every funeral I meet; and especially whenever my hypos get such an upper hand of me， that it requires a strong moral principle to prevent me from deliberately stepping into the street， and methodically knocking people’s hats off - then， I account it high time to get to sea as soon as I can. This is my substitute for pistol and ball. With a philosophical flourish Cato throws himself upon his sword; I quietly take to the ship. There is nothing surprising in this. If they but knew it， almost all men in their degree， some time or other， cherish very nearly the same feelings towards the ocean with me …
就叫我以实玛利吧。 很多年以前——多久以前无所谓了， 那时我的钱包干瘪， 陆地上看来没什么好混的了， 干脆下海吧， 到这个世界上全是水的地方去看看吧。 这是我唯一的去处了。 每当我心烦气躁、肝火上升；每当我心情阴郁、灵魂进入十一月的愁云惨雾；每当我身不由己， 站在棺材铺前， 跟随在每一个碰到的送葬队伍的末尾；每当我忍无可忍， 马上就要到街上如野兽般横冲直撞， 我都得赶紧去出海！只有出海才能代替手枪和炮弹！伽图带着哲学的狂热将自己扑向利剑， 而我只能悄悄地走上船去。 没什么让人惊奇的。 不论是谁， 在某一个特定的时刻， 他都会对大海产生类似的感情。
这是美国作家赫尔曼·梅尔维尔(Herman Melville， 1819-1891)的名著《莫比・迪克》(Moby Dick；又译作《大白鲸》)的开篇段落。 首句 Call me Ishmael(“就叫我以实玛利吧”)， 是世界文学史上公认的名句。
这种加密方法在密码学里被称为替换式加密法或取代加密法 (substitution cipher)。 它的历史非常悠久， 在古罗马的时候就被广泛采用了。 事实上， 表 13.3 的加密方式正是两千年前恺撒大帝最喜欢使用的。
你也许会问， 要是密码根本不按照字母表的顺序安排， 你这个解密办法就不能用了吧? 对这个问题， 有一位古老的学者早就回答了， 他说:
如果已知密码的母语， 一个解密的方法是找到一份用同种语言写成的一段不加密的文字。 文字至少要有一页纸那么长， 我们先对出现的字母计数， 把出现最多的字母称为 “第一号字母”， 第二多的字母为 “第二号字母”， 等等， 依此类推。 一直做下去， 直到把所有的字母都数过来。 然后对加密的文字做同样的工作， 找到其中的 “第一号”、“第二号” 等字母， 直到把所有的字母都数过来。 …… 有时加密的信息太短， 不包含母语所有的字母。 在这种情况下， 字母出现次数的高低就很可能不正确了; 字母次数的高低只有在足够长的信息中才可能是正确的。 ……在后种情况下， 必须采用其他方法。
也就是说， 不管密码是怎么构成的， 只要密码同母语字母有一一对应的关系， 我们都可以通过字母出现的频率找到这种对应关系， 前提是必须知道母语是什么， 而且加密的文字足够长。 显然， 给出答案的人已经知道这个方法的统计学特性: 文字越长， 字母出现的规律越可靠， 破译的把握就越大。
为什么呢? 因为每个使用字母的语言都有这个特征， 那就是字母使用的频率不均衡。 替代字母的符号不论看上去多么复杂， 一旦有了足够的文字， 字母使用频率的规律就显现出来了。 就拿英文来说， 字母 出现的频率最高， 其次是 和 ， 等等。 只要密码传递的信息是英文的， 这个规律就是不可改变的。 当然， 编制密码的人可以加一下花样， 比如前一章图 12.4 中使用的空字符、双字符、短语的代码等等。
第一个发现这个现象的人一定具有非同寻常的观察能力。
我们上面所引的话， 来自阿布·优素福·肯迪(Abu Yusuf Al-Kindi， 801-873)。 他在公元841年写了一部手稿， 名字就叫《关于破译加密信息的手稿》(A Manuscript on Deciphering Cryptographic Messages)。 这部手稿埋没了一千多年， 直到 1979 年才在土耳其伊斯坦布尔的苏里曼档案馆里发现。
肯迪这个名字来自一个古老的游牧王国肯达 (Kindah)， 这个部落最早在今天的也门一带生活， 后来逐渐转移到阿拉伯半岛的中部。 肯迪的家族世代都是部落领袖， 先祖卡伊斯 (Al-Ash’ath ibn Qays， ?—661) 和伊斯兰教创始人穆罕默德 (Muhammad， 约 570-632) 是同时代人。 肯达部落一直到公元 6 世纪都信奉多神论， 在 5 世纪还有不少人转信犹太教。 也许由于这样的背景， 肯达人在转信伊斯兰教的过程中有点儿三心二意。 卡伊斯起初追随穆罕默德， 但后者去世以后， 他又离开了伊斯兰教。 当时伊斯兰教的势力已经非常强大， 卡伊斯因为叛教遭到逮捕。 表示悔改以后， 他被重新启用， 并率领自己的部落参与了伊斯兰征服美索不达米亚和波斯的战争， 最后在库法 (Kufa) 驻扎并安顿下来。 肯迪就出生在这个距离巴格达一百多公里的小城里。
公元9世纪的远东， 大唐王朝刚刚经过 8 年的安史之乱 (755-763)， 精疲力竭， 气息奄奄。 西方， 欧洲的加洛林王朝兴盛不久又陷于内战和分裂， 它一面要应付东罗马帝国的挑战， 一面又要面对北方崛起的维京人 (Vikings)， 于是阿拉伯诸国崛起。 846 年， 一万多名撒拉森人 (也就是阿拉伯人) 和 500 名骑兵居然攻到了罗马城外， 对城郊的基督教神庙大肆破坏， 包括圣保罗大教堂。
巴格达是当时世界文化的中心。 阿拔斯王朝 (Abbasid， 中国古代称之为黑衣大食)的第七代哈里发迈蒙(Abū‘Abbūs‘Abd-Allah al-Ma’mūn， 786-833)开启了历史上著名的 “百年翻译运动”， 使阿拔斯文化和整个阿拉伯伊斯兰文化进入了鼎盛时期。 迈蒙把他父亲在巴格达建立的图书馆加以扩充， 命名为智慧之宫， 鼓励官员与朝臣从事古代文献的研究和翻译。 这些文献主要是古希腊学术和文化著作， 但也包括古波斯、古印度、亚述、希伯来、拉丁语及其他许多语言的文献。 这些举措挽救了大量珍贵的古代文献， 后来到了欧洲的文艺复兴时代， 许多古希腊文献就是从阿拉伯文翻译过来的。
肯迪在巴格达接受了良好的教育， 并且崭露头角， 于是迈蒙指派他为智慧之宫的主要负责人之一。 另外几位负责人， 包括开创代数学的花剌子米 (Al-Khwarizmi， 约 780一约 850， 见《几何与代数卷》)， 还有穆萨三兄弟 (Banu Musa Brothers)。 肯迪在许多领域都有建树， 其中以哲学为最， 被认为是阿拉伯哲学之父。 迈蒙是一位开明的哈里发， 肯迪得以阐发他的不大合乎伊斯兰原教旨的哲学观点。 他在天文学、光学、医学、化学、数学上也有重要建树。 据说， 他一生出过 290 本著作。 他研究密码学的主要原因是为了翻译。 智慧之宫遇到很多死掉的、无名的和加密语言的文本。 为了读懂这些文字， 必须研究解密和句法。 有人甚至认为， 在他的时代， 古埃及文字也已经被阿拉伯人破译了。 读者也许还记得上篇里的卡当诺吧? 肯迪是卡当诺最佩服的世界十二位思想家之一。
833 年迈蒙去世， 他的弟弟穆塔西姆 (al-Mu’tasim bi-‘llah， 794-842) 即位， 肯迪继续得到重用， 并为新哈里发的太子充当教师。 这时阿拔斯王朝以呼罗珊人为主力的常备军已经欲振乏力， 而阿拉伯人与波斯人的冲突不断。 穆塔西姆想了一个办法， 用自己的突厥奴隶组成禁卫军。 我们在第七章的纸牌故事中， 曾经介绍过马木留克这个国家。 马木留克的兴起就是源自穆塔西姆。 伊斯兰世界在控制了阿拉伯半岛以后， 向伊朗高原和北非扩张， 各地的领主纷纷从中亚购买或招聘游牧民族的勇士看家护院。 他们是被人花钱买来的， 属于私人财产， 背景单纯， 忠心耿耿。 这就是所谓 “白人奴隶”(马木留克)军团的起源。 实际上， 穆塔西姆自己的生母就是突厥女奴。 在二三百年的时间里， 马木留克军人从奴隶开始， 由于骁勇善战， 渐渐成为骑士阶层， 最终反 “客”为主， 成为埃及的统治者， 那是后话。
穆塔西姆统治期间， 马木留克军团与正规军之间的冲突不断发生， 于是穆塔西姆于 836 年亲率马木留克军团迁都， 搬到了底格里斯河上游一百公里处的萨迈拉 (Samarra)。 从这一年起， 阿拔斯王朝以萨迈拉为都长达 56 年， 其间换了 7 位哈里发。 842 年穆塔西姆去世， 后来的哈里发们开始对肯迪越来越不满了。
847年， 穆塔瓦基勒(al-Mutawakkil， 822-861)登基， 开始对非穆斯林宗教大加迫害， 摧毁了巴格达的基督教教堂和犹太教会堂， 肯迪的“自由派” 表现也受到压制。 这时穆萨三兄弟乘机进谗言， 致使穆塔瓦基勒下令鞭笞年迈的肯迪， 并强迫将其藏书全部送给穆萨兄弟。 公元873年， 贫困交迫的肯迪孤零零地死在巴格达。
一直到今天， 肯迪留下的解密分析方法都非常重要。 因为无论多么先进的加密方法， 都脱离不了语言本身的特征， 解密到了最后一步， 必须查看字母使用的频率是否同该语言的一般特征相符合。
本章主要参考文献
Broemeling， L. D. An account of early statistical inference in Arab cryptology. The American Statistician， 2011， 65: 255-257.
Al-Kadit， I. A. Origins of cryptology: the Arab contributions. Cryptologia， 1992， 16: 97-126.