巴贝奇对维吉尼亚密码

19世纪密码分析界最引人瞩目的人物是查理·巴贝奇(Charles Babbage)，这位英国怪才最闻名的成就是研发了现代计算机的先驱。他出生于1791年，是富有的伦敦银行家班杰明·巴贝奇(Benjamin Babbage)的儿子。查理的婚事未得到他父亲的赞同，因而与巴贝奇的财产绝缘，但他仍有足够的金钱，不至于有财务问题。他喜欢过流浪学者的生涯，把心思用在任何能激发他奇想的问题上。他的发明包括速度计和捉牛器。捉牛器是一种固定在蒸气火车头上的装置，用于驱除铁轨上的牛只。若讲到科学性的突破，他是第一位发现树的年轮宽度跟气候有关的人，并进而推论，研究古树可以推断出以前的气候。他对统计学也很有兴趣，消遣之际画出一套死亡率统计表，是现今保险业的基本工具。

巴贝奇不自限于处理科学和工程的问题。以往邮资是依信件的运送距离来计费的，巴贝奇却指出，计算每封信的价格所需的人力成本比邮资成本还高。因此，他提议了这套我们今日仍在使用的系统——所有信件不论收信地址在国内何处，都收取相同的邮资。他也对政治、社会问题有兴趣，晚年时发起清除在伦敦游荡的手风琴手和街头音乐家的运动。他抱怨这些音乐“时常使得破破烂烂的顽童，有时甚至使得半醉的男人跳起舞来，那些醉汉偶尔还用他们不和谐的声音来应和这些噪音。另一个大力支持街头音乐的阶级，是那些道德标准伸缩自如且有四海一家主义倾向的淑女们，这些音乐提供她们一个体面的借口，得以敞开窗户，展示她们的魅力”。结果，这些音乐家反倒在他家门前聚集了大批人群，尽其所能地大声演奏，以示反击。

巴贝奇的科学生涯在1821年出现了转折点，当时他和天文学家约翰·赫谢尔(John Herschel)检查一组数学表格，那种用于天文学、工程和航海计算的表格。这些表格有很多错误，让这两个人不胜其烦，因为这些错误会使一些重要的计算产生误差。其中一张“在海上确定纬度和经度的航海星象表”（Nautical Ephemeris for Finding Latitude and Longitude at Sea)，有一千个以上的错误。很多船难和工程灾难的确得归咎于表格的数据错误。

这些数学表格是用手计算出来的，这些错误纯粹是人为错误。巴贝奇因而大叫：“老天，我真希望这些计算是利用蒸气执行的！”他随之投注下大把的心力，矢志建立一台可以无误地计算出高精度数字的机器。1823年，巴贝奇设计出“差分机一号”（Difference Engine No.1)，一部包含两万五千个精密零件、很是壮观的计算器，这部机器将由政府出资制造。巴贝奇是才气纵横的创新者，却不是个挺好的实践家。辛勤工作十年后，他放弃“差分机一号”，重新提出一份全新的设计，开始着手制造“差分机二号”（Difference Engine No.2)。

巴贝奇放弃他的第一台机器时，政府对他失去信心，决定从这项计划抽身，以减少损失——这计划已经花掉17,470英镑，足以建造两艘战舰了。大概就是这撤回资助的举动让巴贝奇后来发出如下的牢骚：“向英国人提议一项原理或一套仪器，不管有多宏伟，你都会发现他们的心思全放在找出它的困难、缺陷或不可能性。如果你跟他谈削马铃薯机，他会说那是不可能的。你在他面前用这机器削颗马铃薯给他看，他又会说这个玩意没啥用处，因为它不能切菠萝。”

没有政府的资助，巴贝奇也就没能完成差分机二号。这实在是科学界的一大悲剧。巴贝奇的机器已具备程序设计的特征。成功的话，差分机二号不仅能计算一些特定的表格，还能根据指令解决各种数学问题。事实上，差分机二号提供了一套现代计算机的蓝本。他的设计包括一个“仓库”（内存)和“磨坊”（处理器），让它可以做决策及重复执行指令，相当于现代程序语言的“if...then...”和“loop”指令。

一个世纪后，在第二次世界大战期间，第一代实现巴贝奇设计的电子设备对密码分析学有深切的影响。事实上，巴贝奇在他有生之年，对破解密码的知识也有着同等重要的贡献：他成功破解了维吉尼亚密码，这是自9世纪的阿拉伯学者发明频率分析法破解单套字母密码法以来，密码分析学上最伟大的突破。巴贝奇的杰作不需要机械的计算或复杂的运算。他所用到的，不过是那颗灵活的脑袋。

巴贝奇年纪轻轻时，就对密码产生兴趣。他后来回忆道，童年时的嗜好常给他惹上麻烦：“那些大男孩造了一些密码。通常我只要得到几个，就能找出钥匙。展现这巧妙本领的后果有时并不好受：有些密码的主人会揍我一顿，尽管这该怪他们自己太蠢。”这些痛打并未使他退却，巴贝奇依旧对分析密码非常着迷。他在自传里写道：“我认为，解译密码是最迷人的技艺之一。”

他那密码分析家的名声，很快就在伦敦的社交界建立起来，人人都知道他乐于对付任何加密信息，常有陌生人带着各种问题来找他。例如有位传记作家无法判读英国第一任皇家天文学家约翰·弗兰斯蒂德(John Flamsteed)的速记笔记，绝望之际，获得巴贝奇的协助。他也协助了一位历史学者破解查理一世(Charles I)的妻子亨丽叶塔·玛丽亚(Henrietta Maria)的密码。1854年，他和一位律师合作，利用密码分析法揭出一件诉讼案的关键证据。长年下来，巴贝奇收集了一大沓厚厚的密码文件，打算以此为基础，写一本堪称密码分析学权威的书籍，标题拟为《密码解译的哲学》（ The Philosophy of Decyphering )。他计划在此书为每一种密码法列举两个例子，一个由他来示范破解方法，另一个则留给读者练习解译。可惜，就如他许多其他宏伟的计划，这本书从未完成。

正当大部分的密码分析家已经放弃破解维吉尼亚密码法的希望时，巴贝奇却在跟约翰·霍尔·布洛克·斯维特斯(John Hall Brock Thwaites)信件往来之际，兴起尝试破解它的念头。斯维特斯是来自布里斯托尔(Bristol)的牙医，对密码术的发展相当无知。1854年，他宣称发明了一种新的密码法，其实正是维吉尼亚密码法。他显然不知道自己晚了好几个世纪，还去信《技术学会期刊》( Journal of the Society of Arts )，要为他的主意申请专利。巴贝奇写信给这个学会，指出：“这个密码法……历史非常悠久了，大多数书籍都有提到它。” 斯维特斯不认错，并挑战巴贝奇破解他的密码。它能否被破解，跟它是不是新的密码法，当然是两回事。不过，巴贝奇倒真的被勾起好奇心，开始着手寻找维吉尼亚密码法的弱点。

破解困难的密码，犹如攀爬一面峭立的断崖。密码分析家会寻找任何能让他攀抓的角落或裂缝。在单套字母密码法里，密码分析家紧紧抓住字母的频率，因为最常用的字母，如e、t、a，不管怎么掩饰，都会突显出来。使用多套字母集的维吉尼亚密码法，把这些频率掩饰得均衡多了，因为它使用钥匙单词在数套密码字母之间轮换。所以乍看之下，这片岩面光滑无比，根本没有可以攀附或落脚的地方。

别忘了，维吉尼亚密码法之所以难以破解是因为同一个字母有数种加密方法。举例来说，如果钥匙单词是KING，那么明文的每个字母就都有四种可能的加密方式，因为这个钥匙单词含有四个字母，而每个字母都代表维吉尼亚方格内的一列密码字母，如表7所示。标示出方格里e这一直栏后，你可以看到，仅仅考虑轮到以钥匙单词的哪个字母来指定密码字母集，e有以下四种加密可能性：

如果用KING的K来加密e，就会产生密码字母O。

如果用KING的I来加密e，就会产生密码字母M。

如果用KING的N来加密e，就会产生密码字母R。

如果用KING的G来加密e，就会产生密码字母K。

同样地，单词本身也会有不同的加密可能性。例如，the这个单词就可能加密成DPR、BUK、GNO或ZRM，仅仅考虑它跟这个钥匙单词的相对位置而定。这会使密码分析工作变得很困难，但并非绝不可能成功。需注意的重点是，如果the这个单词只有四种加密可能性，而且原始文件用了数次the这个单词，这四个加密可能性的其中几个可能会在密码文里重复出现。例如，假设我们用维吉尼亚密码法，以KING当钥匙单词，加密The Sun and the Man in the Moon(太阳及月亮上的人）这一行单词，结果如下：

the这个单词第一次被加密成DPR，第二次和第三次则都加密成BUK。BUK之所以会重复，是因为从第二个the前缀算起，一直到第三个the出现以前，共有八个字母，而八是这个钥匙单词长度（四）的倍数。换句话说，第二个the是根据钥匙单词中的ING三个字母来选择密码字母集，当我们加密到第三个the时，这个钥匙单词刚好循环了两次，于是和第二个the—样，仍是根据ING来选择密码字母集，所以得到的密码也就相同了。

巴贝奇发现，这种重复性正是他征服维吉尼亚密码所需的立足点。他定出一些相当简单的步骤，让任何密码分析家只要依循这些要领，即可破解这个到当时为止仍“无法破解的密码”。我们且试着依巴贝奇的方法来解译如图13所示的密码文，便能了解他高超的技巧。现在，我们只知道它是用维吉尼亚密码法加密的，但不知道它的钥匙单词是什么。

巴贝奇分析法的第一步骤是寻找出现两次以上的字符串。有两种情况可能出现重复的密码文字符串。最可能的情况是，同样的明文字符串用了钥匙单词的相同部分加密。另一种可能性颇低的情况是，不同的明文字符串用了钥匙单词的不同部分加密，却巧合地产生一模一样的密码文字符串。我们若把寻找目标限定于较长的字符串，第二种可能性的出现就会大打折扣。在本例，我们只考虑四个字母以上的字符串。表8记录了这类重复的字符串以及重复字符串之间的间隔值。例如，字符串E-F-I-Q先是出现在这段密码文的第一行，后来又出现在第五行，向前挪动了95位。

钥匙单词既定义明文加密的程序，也是收信人把密码文还原成明文的依据。因此只要能判定出钥匙单词，这段文字很容易就能解译出来了。在这个阶段，我们的信息还不足以解出钥匙单词，不过表8提供了很有用的线索，让我们可以判断钥匙单词的长度。表8的左边两栏列出重复出现的字符串和重复的间隔值，右边各栏列出这些间隔值的因子，亦即可以整除这些间隔值的数字。例如，字串W-C-X-Y-M在20个字母后再度出现，它的因子就是1、2、4、5、10和20，因为这些数字可以整除20，而不留下余数。这些因子提示出六种可能性：

1.这把钥匙的长度是1个字母，在第一个W-C-X-Y-M字符串和第二个W-C-X-Y-M之间循环了20次。

2.这把钥匙的长度是2个字母，在两段字符串间循环了10次。

3.这把钥匙的长度是4个字母，在两段字符串间循环了5次。

4.这把钥匙的长度是5个字母，在两段字符串间循环了4次。

5.这把钥匙的长度是10个字母，在两段字符串间循环了2次。

6.这把钥匙的长度是20个字母，在两段字符串间循环了1次。

第一个可能性可以马上排除，因为使用一把长度只有1个字母的钥匙形同使用单套字母密码法——整个加密过程只用到维吉尼亚方格中的某一列密码字母，从头到尾都不更换密码字母。编码者不太可能做这种事。在表8中，我们在适当字段加上v记号，以标出每种可能的钥匙长度。

欲判定钥匙长度是2、4、5、10或20个字母，我们必须检视所有其他间隔值的因子。因为钥匙字长度似乎小于20个字母，所以表8只列出每个间隔值介于1到20之间的因子。我们看到，这些间隔值倾向为5的倍数。事实上，每个间隔值都可以被5整除。我们可以将第一个重复字符串E-F-I-Q的重复情形解释成，一个长度为5个字母的钥匙单词，在第一次和第二次加密这个字符串之间循环了19次。第二个重复字符串P-S-D-L-P可以解释成，长度为5的钥匙单词，在第一次和第二次之间只循环了1次。第三个重复字符串W-C-X-Y-M可以解释成，长度为5的钥匙单词，在第一次和第二次之间循环了4次。第四个重复字符串E-T-R-L可以解释成，长度为5的钥匙单词，在第一次和第二次之间循环了24次。简而言之，钥匙字长度为5个字母的假设，可以符合所有情形。

假定这个钥匙单词的长度真的是五个字母，下一个步骤即是找出这个钥匙单词的组成分子。我们暂且把这个钥匙单词称为L1-L2-L3- L4-L5，L1代表第一个字母，L2代表第二个字母，以此类推。加密信息时，第一步一定是根据钥匙单词的第一个字母L1来加密明文的第一个字母。字母L1指定了某一行维吉尼亚方格的密码字母，相当于以单套字母替代法加密明文的第一个字母。当加密第二个明文字母时，编码者则是以字母L2来指定另一行维吉尼亚方格的密码字母，相当于用另一套密码字母来进行单套字母替代法的加密。同理，明文的第三个字母会根据L3来加密，第四个根据L4，第五个根据L5。钥匙字的每个字母都指定一套互异的密码字母集。然而，明文的第六个字母则又根据L1来加密，明文的第七个字母又再根据L2，如此一直循环下去。换句话说，这一个多套字母密码法是由五个单套字母密码法所组成，每一个单套字母密码法分别负责加密整则信息的五分之一，而更重要的是，我们已经知道如何破解单套字母密码法了。

我们继续进行如下的分析。我们知道，由L1所指定的某一行维吉尼亚方格的密码字母，是被用来加密明文的第1、6、11、16、……个字母。因此，如果检视密码文的第1、6、11、16、……个字母，就可以运用老式的频率分析法来找出这一套密码字母集。图14是密码文的第1、6、11、16……个字母（亦即W、I、R、E、……)的出现频率分布图。在此，别忘了，维吉尼亚方格的每一套密码字母集都只是标准字母集挪移了1至26位罢了。所以，图14的频率分布图形，除了平移一段距离外，应该会跟标准字母集的频率分布图形很相似。比较L1的分布图与标准字母集的分布图，应该可以判定出挪移位数。图15是一段英文明文的标准字母频率分布图。

标准分布图会有高峰、平原和山谷，拿来跟L1的分布图比对时，我们要寻找最明显的地貌。例如，标准分布图(图15)中由R-S-T三个直条所形成的山峰，和接下来U到Z六个字母所形成的一大片洼地，构成非常独特的地貌。在L1的分布图(图14)，唯一较相近的地形是V-W-X这三个高高的直条以及随后从Y到D伸展了六个字母长的洼地。这表示，根据L1所加密的所有字母可能都向后移了四位，也就是说，L1所指定的密码字母集是E、F、G、H……反推回来，钥匙单词的第一个字母L1很可能是E。要检验这个假设，我们可以把L1的分布图向前平移四位，再来跟标准分布图比较。图16并列这两张分布图以供比较。两张图的主要高峰非常相符，表示我们的假设很可靠，钥匙单词的第一个字母应该就是E。

归纳一下要点：我们首先寻找密码文里的重复字符串，以判定钥匙单词的长度——得到的答案是五个字母长。根据这个答案，我们把密码文分成五组，每一组都是根据钥匙单词其中某个字母所指定的单套字母密码法加密的。分析根据钥匙单词第一个字母所加密的密码文片段后，我们推论出字母L1很可能是E。我们必须重复这个步骤，以判定钥匙单词的第二个字母。图17所绘出的，是密码文的第2、7、12、17……个字母的频率分布图，将与标准分布图比对，以推定它的平移位数。

这个分布图比较难分析。它没有明显的三个相邻高峰来对应R-S-T。不过从G延展到L的洼地非常明显，很可能可以对应到标准分布图中从U到Z的洼地。若是如此，R-S-T高峰应该会出现在D、E、F，可是E却不是高峰。我们可以暂且假设这个少掉的高峰是统计瑕疵，跟随初步反应，推定G到L这个凹陷区域是可供辨识平移位数的特征。这表示，根据L2所加密的字母可能都向后挪了12位，也就是说，L2所指定的密码字母集是M、N、O、P……而钥匙单词的第二个字母L2很可能就是M。为了检验这个假设，我们可以再次把L2的分布图往前平移12位，来跟标准分布图比较。图18并列这两张分布图以供比较。两张图的主要高峰非常相符，表示我们的假设很可靠，钥匙单词的第二个字母应该就是M。

我不再累述后面的分析过程，直接说明结论：分析第3、8、13、18、……等字母的结果暗示，钥匙单词的第三个字母是I；分析第4、9、14、19、……等字母的结果暗示，钥匙单词的第四个字母是L;分析第5、10、15、20、……等字母的结果暗示，钥匙单词的第五个字母是Y。这个钥匙单词是EMILY。现在，我们可以逆向运用维吉尼亚密码法，完成这项分析工作。密码文的第一个字母是w，它是根据钥匙单词的第一个字母E加密的。反推回去，到维吉尼亚方格以E开头的那一行找到W，再往上查看这一直栏最上面的字母是什么。它是s，所以本篇文字的第一个字母就是s。重复这个步骤，即可得出如下的明文：sittheedownandhavenoshamecheekbyjowl……插入适当的空格与标点符号，最终得到：

Sit thee down, and have no shame,

Cheek by jowl, and knee by knee:

What care I for any name?

What for order or degree?

Let me screw thee up a peg:

Let me loose thy tongue with wine:

Callest thou that thing a leg ？

Which is thinnest？ thine or mine ？

Thou shalt not be saved by works:

Thou hast been a sinner too:

Ruined trunks on withered forks,

Empty scarecrows, I and you!

Fill the cup, and fill the can:

Have a rouse before the mom:

Every moment dies a man,

Every moment one is bom.

这是阿尔弗雷德·丁尼生(Alfred Tennyson,1809年～1892年)标题为《罪恶狂想曲》( The Vision of Sin )的诗句。钥匙单词正是丁尼生的妻子爱米莉·塞伍德(Emily Sellwood)的名字。我摘取这首诗来当密码分析的例子，是因为巴贝奇和这位大诗人对这首诗有一段古怪有趣的讨论。身为敏锐的统计学者，又是死亡率统计表的编纂者，巴贝奇对原文的最后两行“Every moment dies a man,Every moment one is born”（每当一人逝去，同时亦有一人诞生）颇有微词。他建议丁尼生修正一下这首“否则，倒是很漂亮”的诗：

很明显地，若真如此，这个世界的人口数就会静止不变了……我想建议你，这首诗再版时，把它改成”Every moment dies a man, Every moment 1 1/16 is born……确实数值太长，一行放不进去，不过我相信1 又1/16这个数值对诗作而言够精确了。

查理·巴贝奇 敬上

巴贝奇大概是在1854年，跟斯维特斯发生争论不久后，就成功地破解维吉尼亚密码法的，但因为他从未发表结果，所以大家对他的发现毫无所知。这项发现，是20世纪的学者检视巴贝奇大量的笔记才得见天日的。在这同时，一位普鲁士退休军官弗里德里奇·卡西斯基(Friedrich Wilhelm Kasiski)也发现了这个技巧。1863年，他在《秘密书写与解密艺术》（ Die Geheimschriften und die dechiffrir-kunst )中发表他在密码分析学上的突破，这项技术从此被称为卡西斯基测试(Kasiski Test)，巴贝奇的贡献则几乎完全被忽略。

巴贝奇怎么会没公开他破解了这么重要的密码技术呢？他的确是有不把计划做完，以及不发表他的发现的坏习惯，这可能只是他懒散态度的另一个例子。不过，还有另一种可能性。他是在克里米亚战争爆发不久后发现这个方法的，根据某些人的推测，这个方法可以提供给英国对抗俄罗斯的明显优势。很有可能是英国的情报当局要求巴贝奇将这项成就保密，让他们遥遥领先世界其他国家9年。若真是如此，这倒很符合为了国家安全而对密码解译成就噤声不语的悠久传统——一项直到20世纪仍然存在的传统。 l35r4Y11dRypFFd82imqOan8kQ+jklT6Hx4nhKHev29B8ggVdTqs86rd+TSwjOna