版权信息

如果你不知道读什么书或者想获得更多免费电子书请加小编QQ：2338856113 小编也和结交一些喜欢读书的朋友 或者关注小编个人微信公众号名称：幸福的味道 获得上百个书单 为了方便书友朋友找书和看书，小编自己做了一个电子书下载网站，网址：http://www.ireadweek.com 如于某种原因，经常换网址 如果打不开，可以qq联系我

书名:数学家、间谍与黑客：密码与解码（万物皆数学）

作者:（西）琼·戈麦斯

译者:于秀秀

ISBN:9787521722345

中信出版集团制作发行

版权所有•侵权必究

送给我的儿子维森斯（Vicenç）

前言

童年时期我们可能都玩过这样一种游戏：几名小伙伴先商定一套暗号，然后用这套暗号互相收发秘密信息。有些孩子会幻想自己是特工，进而在这类编解码游戏上倾注热情，但不会真的窃听传输中的信息，对第三方造成威胁。但是，在成年人的世界中，这种讨人厌的窃取信息的行为屡见不鲜，因此对我们来说，保证通信工具的保密性至关重要。

暗号和密码曾经只应用于政治领域和精英的社交活动中，而信息时代的到来使它们成为整个社会平稳运行的关键。本书旨在介绍密码学的历史，所选的角度乃是探索密码世界的最佳向导——数学。

密码学是用暗码书写的艺术，与书写同时出现。虽然最早埃及人和美索不达米亚人使用过加密文字，但第一个充分利用密码的是古希腊人和古罗马人，因为这两个民族都有好战的文化，通信保密是战争胜利的关键因素。这样的保密催生了新的对垒双方——宣称自己是秘密保护者的加密者和希望揭开秘密的密码破译者，也叫解密者。这场发生在台面之下的战争始终战况焦灼，随着时间的流逝，或许一方会暂时领先，超越对手，但始终没有哪边能收获决定性的胜利。比如9世纪时，阿拉伯哲人肯迪（Al-Kindi）发明了一种密码破解方法，叫作频率分析，在当时看来，任何用密码书写信息的人在它面前都会败下阵来，但接下来，加密者花了几百年的时间创造出了多表加密法，又扳回一城。同样，多表加密法看似也是一件致命武器，后来出现了由一位英国天才所创的更强大的密码破译系统（后人研究他的个人文件时才发现这个秘密），再一次扭转了局势。从那以后，加密和解密双方各自使用的主要武器就成了数学，从统计学到模运算，还曾取道数论。

这场编解码大战后来迎来了一个转折点：第一台加密机的出现，以及不久之后出现的解码机。第一台可编程数字计算机由英国人发明，名为“巨人”，其目的就是破解纳粹德国的恩尼格玛密码机。

随着计算能力的大爆炸，代码取代了传统的保密方法，成为加密信息传输的主流。现代社会的通用语言既不是字母也不是表意文字，而是0和1两个数字，这就是二进制代码。

随着新技术的到来，到底哪一方获利更多，是加密者还是解密者？在这个计算机病毒、数据窃取和超级计算机满天飞的时代，还有可能保密吗？对于第二个问题的回答是肯定的，而我们要再次感谢数学，这次要感谢的是质数和质数的特性。但这次加密者的暂时优势能够持续多久呢？要回答这个问题，我们需要求助当代科学最前沿的阵地——量子力学。了解过量子力学中令人感到自相矛盾却又震惊不已的理论之后，我们这场事关安全与保密的激动人心的数学之旅也将画上句号。

本书最后还提供了参考书目，希望对想要进一步探索加密和密码学世界的你有所帮助。

如果你不知道读什么书，

就关注这个微信公众号号。

微信公众号名称：幸福的味道

加小编QQ一起读书，并免费提供找书服务

QQ号：2338856113

【幸福的味道】已提供200个不同类型的书单

1、 历届茅盾文学奖获奖作品

2、 每年豆瓣，当当，亚马逊年度图书销售排行榜

3、 25岁前一定要读的25本书

4、 有生之年，你一定要看的25部外国纯文学名著

5、 有生之年，你一定要看的20部中国现当代名著

6、 美国亚马逊编辑推荐的一生必读书单100本

7、 30个领域30本不容错过的入门书

8、 这20本书，是各领域的巅峰之作

9、 这7本书，教你如何高效读书

10、 80万书虫力荐的“给五星都不够”的30本书

关注“幸福的味道”微信公众号，即可查看对应书单和得到电子书

更多书单，请关注微信公众号：一种思路

每日新出版的读书分享，请关注公众号：周读读书

第一章 信息真的安全吗？

密码学：用代码或密码书写的艺术或实践。

《牛津英语词典》

可以说，自有文字以来，人类就希望创造出一种只有收发双方能够读懂而其他人无法理解的特殊文字。其实，世界上存在一些有着4 500多年历史的“非标准”象形文字，但现在的人们已无法确定它们存在的目的到底是隐藏信息，还是在某种仪式中扮演什么角色。有一块可追溯到约公元前2 500年的巴比伦泥板，上面的单词都被去掉了第一个辅音，还使用一些不常见的变异字符。研究发现，这段文字描述的是一种制作涂釉陶瓷的方法，由此我们可以推断，这块泥板是由商人或陶工雕刻的，这么做的目的是保护商业秘密，不让竞争者知晓。

随着书写和贸易的传播，伟大的帝国也随之诞生，而帝国转而又会卷入频繁的边界争端中。于是，密码学和信息的安全传播成为统治者及商人的头等大事。迈入信息时代后，保护通信完整性、合理维护隐私，相比以前要重要得多。所有信息的流通几乎都要首先经过编码将原始信息转换为代码。使用代码是为了更加简便地传播，比如，把文本转换成电脑能够识别的二进制语言（一种只用0和1的数字系统）。编码后，为了保护信息的大部分内容不被非法截获的人看到，需要对代码进行加密，而信息接收者必须要有译解信息的能力。编码、加密和译解是“信息之舞”中的基本步骤，每时每刻、每分每秒都会重复数百万次之多，而“舞蹈”的背景音乐中的音符自然非数学莫属了。

代码、密码和密钥

密码学者对术语“编码”的理解与普通人稍有不同。对他们来说，编码是用代码书写的一种方法，例如用一个单词替换另一个单词，或者使用加密术或密码替换字母或其他单个字符。随着时间的流逝，替换字母这种形式越来越普遍，变成了“用代码书写”的同义词。不过，如果从更学术的角度解释，这种方法的正确术语应该是“加密”，反向过程则叫“译解”。

假设我们要发送一条机密信息“ATTACK”（攻击），可以用两种基本方法：替换单词（代码）或替换这个单词的某几个或所有字母（密码）。编码一个单词，最简单的做法是把它翻译成潜在的窃听者听不懂的一种语言。不过那也意味着发出和接收信息的人得掌握一门独特的语言。为了降低收发密码人员素质的要求，大多数机密信息采用的是加密术，比如把单词中的每一个字母用字母表中的其他字母替换。无论是哪种方法，信息接收者都必须知道信息编码或加密的过程，否则这条加密信息就无法被译解。如果已经与接收者商量好使用其中一个方法，比如翻译成另一种语言或把每一个字母都用其他字母替换，我们就需要把目标语言或替换字母在字母表中的对应序号告知对方。例如，“ATTACK”加密后，接收者收到信息“CVVCEM”，只要知道发送者是把原单词每一个字母都按字母表顺序往后推了两个位置，接收者就能通过反向操作，轻松译解这条信息。

二进制代码

计算机在理解和处理信息的过程中，必须要把信息的书面语言翻译成所谓的二进制语言。二进制语言仅包括两个数字：0和1。十进制的0-10对应的二进制表达如右方表格所示。

十进制数9780用二进制代码表达就是10011000110100。

对于译解加密信息的人来说，加密规则（应用的系统）和加密参数（针对每条信息或一组信息的变数指令）都大有用处，潜在的间谍只有同时掌握这两点才能解密信息。掌握加密规则，间谍就知道译解手上的信息需要将词中的每一个字母按字母表顺序往前推x位，找到对应字母，然后将单词中的每一个字母替换掉即可。然而，如果他不知道加密参数，即x是多少，就必须尝试所有可能的数字，再根据每个x译解的结果猜测正确的译解。在这个例子中，密码相对简单，即便把所有可能都试一遍，即大家熟知的“暴力破解”，也不会太费力气。不过，这类密码破解或密码分析手段在面对加密技术足够复杂的信息时肯定会力不从心，暴力破解无论如何也行不通。而且，一般来说，对信息的窃听和译解都有时间限制，间谍必须赶在信息无效或被许多人获知之前，获取并理解它。

翻译或译解？

用一套未知的字符集语言编写文本时，就好像在译解一套密码。翻译可以看作把未知的文本转换成了我们使用的语言，而加密算法就是源语言的语法规则和句法。翻译和译解使用的两种技术有很多相似之处，两者都需要满足相同的条件：收发双方至少必须要有一门共同语言。这就是为什么对失传的语言（如古埃及象形文字或古希腊线形文字B）写就的文本，除非在已知语言中找到对应的表达，否则无法翻译出来。对于上述两种失传的语言，这个对应的已知语言就是古希腊语。下图中的石碑发现于克里特岛，上面的信息就是由希腊线形文字B书写的。

加密规则通常叫作“加密算法”，而用来给信息加密或编码的具体参数叫作“密钥”。前文“ATTACK”例子中，其密钥为2，即每一个原始字母在字母表中往后推两位，用所对应的字母替换掉即可。显而易见，每个加密算法都有许许多多的密钥，所以，仅仅知道加密算法是没用的，还需同时知道所有加密密钥。由于密钥的改变和传播通常比较容易，因此要想保证加密系统的安全，重点保护密钥免遭泄露也就在情理之中了。这个原则由19世纪的荷兰语言学家奥古斯特·柯克霍夫·冯·纽文霍夫（Auguste Kerckhofs von Nieuwenhof）提出，因此也称柯克霍夫原则。

需要多少个密钥？

对于拥有两个用户的系统来说，需要多少个密钥才能确保安全呢？三个？四个？对于秘密交流信息的两个用户来说，一套密码或密钥就够了。如果是三个用户，那么A与B之间的交流需要一个，A与C需要一个，B与C又需要一个，一共三个。同样，四个用户需要六个密钥。以此类推，n个用户时需要计算出有多少个成对的组合，然后确定密钥的数量，公式如下：

因此，在一个相对较小的系统中，如果有10 000个相互联系的用户，就需要49 995 000个密钥。如果是全世界的60亿人口，密钥总数会大到令人眼晕，即17 999 999 997 000 000 000个。

让我们对前面所讲的内容稍做总结，一个加密的通用体系，所需要素如下：

也就是说，过程中包含一个信息发送者和一个信息接收者，一个加密算法和一个确定的密钥，而这个密钥是发送者加密信息和接收者解密信息时使用的。之后我们会发现，在当代，由于密钥的属性和功能发生了改变，这个图表自然也将进行修改，但目前我们还是暂时使用这个图表。

私人密钥和公开密钥

根据柯克霍夫原则，密钥是左右所有密码系统安全的基本元素。近代以前，在所有可行的密码系统中，信息收发双方的密钥都得一致，或者至少要对称，也就是说，密钥既能用来加密，也能用来解密。由于密钥是收发双方共享的秘密，因此密码系统的两端都易受到攻击。这种收发双方共享一个密钥的密码学，人们称为“私人密钥”，简称“私钥”。

统一收发双方的密钥似乎是理所当然的，自有记录以来，人类发明的所有密码系统，不论使用何种算法，有多复杂，都有这样的特点。毕竟，如果一个人用一个密码规则加密信息，另一个人用另一个密码规则解密，怎么可能顺利传达正确的信息呢？几千年来，人们一直把这种想法看作是荒诞不经的。不过，稍后我们会细说此事，因为就在50多年前，这种荒唐想法竟成真了，而且现在已经成了加密学中无处不在的一部分。

当今时代，交流中使用的大部分加密算法至少包括两种密钥：一种是保密的私钥，这是为人熟知的一种；另一种是公开透明的密钥，简称“公钥”。使用私钥的传输机制是这样的：发送者从接收者那里拿到发送信息的公钥，然后用它来加密信息。接收者用自己的私钥解译收到的信息。而且，这种系统具有一个举足轻重的额外优势：收发双方不需要提前聚在一起商量确定密钥问题，这样一来，系统的安全性就比以前高出很多。人们把这种革命性的加密形式称为“公钥”，这种形式构成了当今通信网络安全的基础。

还需要多少个密钥呢？

我们在前面已经介绍过，经典密码学需要大量的密钥。但是，在公共加密系统中，任意两个交换信息的用户仅需要4个密钥，即各自的公钥和私钥。这种情况下，n个用户只需要2n个密钥。

数学就是这种革命性技术的根本，我们稍后会详细解释。实际上，现代密码学建立在两大基础之上。第一个是模运算，第二个是数论，尤其是数论中对质数的研究。

齐默尔曼电报

密码学是应用数学的一个领域。在应用数学中，基本理论简洁明了，但应用效果却很模糊，两者形成了鲜明对比。毕竟，有时信息传递安全与否决定着整个国家的命运。密码学改变历史进程的事件比比皆是，发生于20世纪的齐默尔曼电报事件就是最引人注目的例子之一。

在大半个欧洲都被卷入的血腥的第一次世界大战之中，1915年5月7日，一艘德国U型潜艇发射鱼雷袭击了横跨大西洋的客轮“路西塔尼亚号”，当时这艘插着英国国旗的客轮正航行在爱尔兰海岸附近。这是历史上最臭名昭著的屠杀之一，1 198名平民因此而丧生，其中124人是美国籍。新闻不胫而走，在美国激起了民愤，时任美国总统伍德罗·威尔逊向德国方面发出警告，如果德方再有此类行径，美方会立即加入协约国阵营，向德国宣战。另外，威尔逊总统要求德国潜艇浮出水面，不再发动任何攻击，防止再次发生民用船只被击沉事件。于是，德国U型潜艇的战略优势因此项让步威势大减。

《纽约时报》对“路西塔尼亚号”沉没事件的报道。

亚瑟·齐默尔曼（Arthur Zimmermann）在外交界的声誉很高，1916年11月，德国政府委任他为新一任外交部长。美国新闻界对此表示赞许，认为齐默尔曼的上任对德美两国关系而言是好兆头。

1917年1月，距离“路西塔尼亚号”悲剧还不到两年，在战争的高潮时，德国驻美国大使约翰·冯·伯恩斯托夫（Johann von Bernstorf）收到一封来自齐默尔曼的加密电报，指示大使将此电报秘密交给德国驻墨西哥大使海因里希·冯·埃卡特（Heinrich von Eckardt），内容为：

我方欲于2月1日发动无限制潜艇战，务必尽一切努力使美国保持中立。

一旦形势有变，我方将寻求与墨西哥结盟，以如下条件为基础：一同开战，一同求和，经济上倾囊相助，以及我方对墨西哥意欲收复得克萨斯州、新墨西哥州和亚利桑那州失地诉求的理解。协议细节由你（冯·埃卡特）确定。

一旦与美国开战，请尽快以绝密形式将上述内容告知墨西哥总统，并建议他主动邀请日本追随我方，同时担任日方与我方的中间人。

可告知墨总统，我方已经做好充足准备，随时可进行无限制潜艇战，有望迫使英国在几个月内求和。

可想而知，如果这篇电报被公布于众，德国和美国必定爆发战争。虽然德国皇帝威廉二世清楚潜艇在水下发动攻击就等于向美方宣战，但他希望英国迅速投降，美国也就没什么战争可参与了。此外，如果墨西哥对美国南部边界造成威胁，势必也能阻止美国参与远方的战争。但是，墨西哥需要一定的时间组织自己的军事力量。因此，保密时长是关键，德国的目的是尽量延长保密时间，保证潜艇战能够按照德方的意愿扭转战局。

40号房间开始工作

然而，英国政府有别的计划，战争开始后不久，英国政府就切断了德国直通西半球的海底通信电缆。这样一来，英国就能截获所有通过电缆传输的通信。另一方面，美国有意通过协商终止战争，所以一直允许德方继续传递外交信息，向德国驻华盛顿大使馆保证其能够不受干扰地收到德国发来的信息。

英国政府截获这份加密电报后，把信息发给了密码分析部门，这个部门就是40号房间。

德方使用的是外交部的一般加密算法，还使用了一个叫作0075的密码，而40号房间之前已经在一定程度上将其破解。这种加密算法包括替换单词（编码）和字母（加密），类似于德国当时使用的另外一个加密工具ADFGVX密码，稍后我们会做详细介绍。

破解这份电报没有花费多长时间，但英方在要不要立即告知美方的问题上犹豫不决。原因有二：首先，美方有承诺在先，德国与驻美使馆间的通信受到外交庇护，英方告知美方这一消息也就意味着暴露了英方无视美方对德方的承诺；其次，如果将电报公布于众，德国政府会立即意识到其诸多密码已经被破解，随后会更改加密系统。最终，英国采取了一个折中的办法，决定告知美国截获并解密的电报是德国驻美大使发给驻墨西哥大使的那份，保全了美方的外交声誉，也以此让德方认为电报是在墨西哥被截获并解密的。

德国驻华盛顿大使约翰·冯·伯恩斯托夫将齐默尔曼的电报（上）译解后（下），传给驻墨西哥大使。

英国译解的齐默尔曼电报（部分）。从中可以看出，德方对单词“Arizona”（亚利桑那）没有使用代码，而是将一个词分成了AR、IZ、ON和A。

2月底，美国威尔逊政府将电报内容泄露给新闻界。起初，一些媒体对此持怀疑态度，尤其是赫斯特报团旗下持反战观点，同情德国的报纸。然而，3月中旬，齐默尔曼公开承认发过这份颇有争议的电报。两周后，即1917年4月6日，美国国会决议向德国宣战，这个决定对欧洲和整个世界来说都产生了深远的影响。

虽然在当时轰动一时，但在密码学扮演关键角色的历史上，齐默尔曼电报事件只是诸多里程碑中的一个，本书还有很多散布在历史长河和各种文化当中的其他事例。虽如此说，但有一点我们非常清楚，很多至关重要的历史事件必定至今还无人知晓，因为就其实质而言，密码学的历史是一个秘密的历史。

第二章 19世纪之前的密码学

在前文中我们说过，密码学是一门古老的学科，或许与文字交流本身一样古老。但是，它不是唯一秘密传送信息的方法。毕竟，所有文本都必须要有传播媒介，如果能让这个媒介只对接收者可见，就算达到了隐藏信息的目的。隐藏信息存在的技术叫作“隐写术”，与密码学兴起于大约同一时期，也有着同样的起因和使命。

隐写术

古希腊学者希罗多德（Herodotus）是公认的世界上最伟大的历史学家之一，其著作《历史》记述了公元前5世纪希腊和波斯之间的战争，其中提到两个隐写术的实例，展现了人类无穷的智慧。第一个实例在《历史》第三卷中，米利都僭主希斯提亚埃乌斯（Histiaeus）在波斯宫廷时命令仆人把头发剃干净，然后把准备里应外合反抗波斯的信息写在这个人的头皮上，等仆人的头发长出来后再把他派往留守米利都的阿里斯塔格拉斯（Aristagoras）的营帐。安全抵达后，这个送信人给阿里斯塔格拉斯解释了个中玄机，然后把头发剃净，露出了等待已久的信息。第二个例子具有非常重要的历史意义，流亡波斯的斯巴达国王狄马拉图斯用这种方式给他的国民发出警告信息，说波斯国王薛西斯（Xerxes）即将统率部队入侵本国，不过其真实性有待考证。希罗多德在《历史》第七卷中提到了此事：

狄马拉图斯不能那样直接警告国民，于是他想了一个办法。他拿来两块涂了蜡的书写板，刮掉上面的蜡，把波斯人的进攻计划刻在木板上，最后再把熔化的蜡涂在表面，从而隐藏了信息。

如此一来，书写板看上去什么字都没有，即使有卫兵盘查，也不会招来麻烦。书写板最终抵达拉栖第梦（斯巴达的旧称）时，拉栖第梦人不明就里，戈尔戈女王看出了端倪，命人把书写板上的蜡刮去，众人才发现蜡下面的木头上刻的信息。

真正经得住时间考验的隐写工具是隐形墨水。涉及隐形墨水的小说和电影数以千计，使用的材料也多种多样，一般有柠檬汁、植物汁液，甚至人类尿液。隐形墨水主要是一些含碳量比较高的有机化合物，所以一旦暴露在高温下，如蜡烛火焰，墨水覆盖过的地方色彩就会变暗。

隐写术的实用性是毋庸置疑的，但如果涉及大量的信息交流，它就难以胜任了。而且，这种方法有一个明显的弊端：一旦信息的载体被截获，内容就无法传达，甚至可能暴露。正因如此，隐写术主要用作密码的补充，是一种加强绝密信息传递安全性的手段。

从这些实例当中，我们也能总结出一点：武装冲突大大推动了信息安全传递的发展。既然如此，把战斗民族，比如斯巴达人列为密码学发展的先驱也就不足为奇了。如果希罗多德纪事不虚的话，古希腊的斯巴达人已然是隐写术方面的专家。

换位加密术

斯巴达和雅典在争夺伯罗奔尼撒半岛控制权的战争中频繁使用过一种加密方法：把长长的纸条缠在一根木棒上，即大家熟知的密码棒，然后把信息写在缠起来的纸上。即便截获了信息，敌方也知道加密的方法（也就是加密算法），但如果不知道所用密码棒的精确尺寸，解密起来也会相当困难。事实上，密码棒的粗细和长度就是加密系统的密钥，而纸条展开时，信息是完全无法辨认的。

蝇头小字

美苏“冷战”期间，有关间谍的电影总是颇具戏剧性，电影的主角通常借助一种肉眼无法辨认的媒介——缩微胶卷发送大量的信息。这一技术诞生的时间不长，“二战”期间，德国特工使用了一种叫作缩微影印的隐写技术。缩微影印包含一张印有简短文本的照片，把照片压缩到句号大小，然后把这个“句号”当成一个标点符号，插入无关紧要的文本中。

下方插图中，要传送的信息（M）为“A message encodedwith a scytale”，但纸条展开后显示的却是令人摸不着头脑的乱码（C）“anh mca eos sdc sey adt gwa eil ete”。

使用密码棒的加密方法叫作换位加密术，就是将信息的字母重新排序。要了解这种方法的原理，不妨先考虑一个简单的例子，只给三个字母换位：A、O和R。不用计算，通过快速试验，大家可以发现重新排列这三个字母最多有6种方式：AOR、ARO、OAR、ORA、ROA和RAO。

用抽象的术语表达，过程如下：有三个字母时，先确定其中一个字母的位置，会有三种不同的排列方式，剩余两个字母，会有两种不同的排列方式，总数为3×2=6。如果信息稍长一点，比如十个字母，排列的情况是：10×9×8×7×6×5×4×3×2×1。这样的运算用数学符号“10！”表示，一共有3 628 800个不同的排列方式。通常，n个字母有n！个不同的排列方式。所以，如果一条信息中含有40个字母，就会产生超多的不同排列方式，纯手工解密几乎是不可能完成的。那是否可以说，我们已经找到了完美的加密方式呢？

女性必读

古印度典籍《爱经》是一部专为女性而作的冗长手册，书中探讨了如何让女人成为一个好妻子，当然还有其他内容。这本书的内容得自公元前4世纪左右的古文稿，作者是婆蹉衍那，书中推荐了64种不同的技能，包括音乐、烹饪和象棋。第45项提到的密写（mlecchita-vikalpa）的艺术尤其令我感兴趣。《爱经》的作者博学多识，推荐了几种方法，比如将字母表分成两部分，然后随机配对。在这个系统中，每个字母的配对代表一把“密钥”。如下表所示：

要写秘密信息，就必须要把原文中的A用E代替，P用C代替，J用W代替，等等，反之亦可。

并非如此。实际上，虽然随机换位算法安全性更高，但解密的密钥不方便使用，加密和译解过程中的“随机”既是优势也是劣势。此时需要另外一种加密方法，密钥简单又好记，还方便传递，也不用牺牲大量的安全性。于是乎，人们就开始搜寻完美的算法，首位成功者是一名罗马独裁者。

恺撒的归恺撒

我来，我见，我征服。

——尤里乌斯·恺撒

替换加密是和换位加密同时发展起来的。与换位加密不同，严格的替换加密是用另外一个字母或任意符号替换原字母。与换位加密也不同，替换加密不仅涉及信息中出现的字母。在换位加密中，字母改变它的位置，但字母本身不变，原始信息与解密后的信息中，字母都是一样的，而在替换加密中，字母虽保持位置不动，但样子却变了，即原始信息与解密后的信息中，相同字母或符号代表的意义各不相同。波里比阿密码是以古希腊历史学家波里比阿（约前203-约前120）命名的，是已知最早的替换算法之一，这位历史学家给我们留下了相关记载，本书附录中也详细记录了他的方法。

盖乌斯·尤里乌斯·恺撒（前100-前44）

恺撒，政治家，军事家，独断专行，终结了罗马共和制。他曾任职西班牙行省的地方长官，之后与当时另外两个手握大权的人物庞培和克拉苏强强联合（恺撒把女儿尤利娅嫁给了庞培），形成了一个三人执政团，史称“前三头政治”。三人瓜分了罗马帝国。克拉苏管理东部行省，庞培依然控制罗马，恺撒则用军事控制了高卢地区，宣布自己为山南高卢的总督。当时，正值罗马向高卢开战，战争持续了8年，最终罗马胜利，高卢被征服。战后，恺撒带着大胜的军团进军帝国首都，宣布自己为唯一的独裁者。

公元前1世纪，大约在波里比阿密码出现50年后，另一种替换加密法出现了。它有个通用名称——恺撒密码，因为尤里乌斯·恺撒是它最著名的使用者之一。恺撒密码是密码学领域被研究最多的密码，它的实用性非常强，因为它阐明了模运算的原则，而模运算是加密文本的数学基础之一。

恺撒密码用字母表中每个字母下方对应的固定位数的字母进行替换。伟大的历史学家苏维托尼乌斯（Suetonius）在他的著作《罗马十二帝王传》（The Twelve Caesars）中提到，尤里乌斯·恺撒用一种替换算法给自己的私人信件加密，方法是这样的：把原信息中的每一个字母在字母表中向后推三个位置，用所对应的字母替换，如字母A用D替换，B用E替换，以此类推，W用Z代替，X、Y和Z对应的分别是A、B和C。

如下图所示，信息的加密和解密非常简单：

现在我们来详细探讨一下这个过程。下图中，两行各有26个字母，第一行是原始字母表，第二行是恺撒密码字母表，即把原始字母表向后推三个位置，与第一行对应的字母就是加密字母。

电影中的密码

经典科幻电影《2001太空漫游》是1968年由斯坦利·库布里克执导的作品。电影改编自亚瑟·C.克拉克的小说，主人公是一艘宇宙飞船的超级计算机，代号HAL 9000，被赋予意识，后来精神失常，企图谋杀人类船员。现在我们把“HAL”当作一条信息，用恺撒密码的方法加密，密钥为B，往后推一位。字母H对应I，A对应B，L对应M，也就是说，原信息“HAL”对应的加密信息就是“IBM”。IBM是当时世界上最大的电脑制造商。影片中这样安排，是在评论人工智能的危险或不受监管的商业力量的危害吗？还是只是个巧合？

电影《2001太空漫游》中HAL 9000的全视之眼。

把原始（也叫明文）字母表和加密字母表以这种方式排列好，解密信息就简单多了，只需替换对应的字母即可。密码对应的密钥就是原始字母表中的字母A对应的字母，即加密值。假设密钥为D，那么那句经典的“AVE CAESAR”（恺撒万岁）加密后的表达就是“DYH FDHVDU”。反过来，如果加密信息是“WUHH”，那么解密后的信息或明文信息就是“TREE”。假设一个密码破译者截获了使用恺撒密码加密的信息，而且知道使用了什么样的加密算法，但并不知道密钥，那他就必须要把所有可能的重新排序都试一遍，直到找到一条能够说得通的信息为止。要解密信息，就必须得挨个儿试，最坏的情况下，要把字母表中的所有字母都试一遍，也就是替换一遍。如果字母表中有n个字母，n种可能的替换就会产生n个密码。

16=4，模运算和恺撒密码中的数学

16=4？2=14？这可不是计算错误，也不是什么奇怪的编号系统。恺撒密码的运算，甚至是密码学中的运算，都可以用数学中常见的公式来表达，那就是“模运算”，有时也称“时钟算术”。这一技术源于古希腊数学家欧几里得（前325-前265）的著作，同时它还是现代情报安全的基石。本节我们就来介绍与这类算法相关的数学概念。

以经典的指针式钟表为例，把它与电子表做对比。指针式钟表把圆形表盘分为12个部分，每个部分代表一个小时，写作：0、1、2、3、4、5、6、7、8、9、10、11。从上表中，我们可以看出指针式钟表表盘上的数字和电子表显示的数字对午后的12小时的对应关系。

分析加密之父

《几何原本》是欧几里得的主要著作，共13卷，内容涉及平面几何、比例、数字的性质、无理数和空间几何。尽管大多数内容都与最后这个领域相关，但古希腊数学家的著作与数的有限集合或系数，构成了现代密码学的基石之一。虽然欧几里得几何在阿拉伯学者之间广为流传，备受推崇，但是直到1482年，第一部现代欧洲版的欧几里得著作才出现在威尼斯。如此看来，阿拉伯人和威尼斯人都精通密码术也就不是巧合了。

比如，说到现在“14:00”整，同样也是在说现在是下午2点。角度的计算运用同样的原则。一个大小为370°的角等于大小为10°的角，因为一个完整的360°过后，要再从头开始计算。注意370=(1×360)+10，同样的，10也是370减去360的得数。那么750°对应的角度是多少呢？完全旋转两圈后，发现750°的角就等于30°的角。由此我们可以总结出：750=2×360+30，而30是750除以360之后的余数。数学表达为：

750≡30(mod.360)

其中≡表示“被界定为”，读作“750对模360同余的数字为30”。切换回钟表，公式写作：14≡2(mod.12)。

同样，我们也可以想象一块有“负数”的钟表。当时针指向-7时，是几点呢？或者换句话说，与-7对模12同余的数字是多少？计算时，我们应记住，在分成12个部分的表盘上，0对应的值等于12：

同余运算

如何用计算器计算出与231对模17同余的数字？

首先计算231除以17，得出13.5882352。

然后算出乘积，即13·17=221，这样就去掉了所有的小数。

最后再做减法，即231-221=10，得出除法运算后的余数。

231对模17同余的数字就是10，写作：231≡10（mod.17)。

-7=-7+0≡-7+12=5

分为12个部分的指针式钟表的数学计算叫作对模12的运算。一般来说，数字a、b和m都是整数，如果a和m相除的余数是b，那么就可以说a≡b(mod.m)，b等于a除以m所得的余数。下面的表达式意义相同：

a≡b(mod.m)

b≡a(mod.m)

a-b≡0(mod.m)

a-b等于m的倍数

“指针式钟表上19时是几点？”用数学术语表达，即“与19对模12同余的数字是什么？”回答这个问题，我们就必须要解出这个方程：

19≡x(mod.12)

19除以12，商为1，余数为7，因此：

19≡7(mod.12)

那么127时又是几点呢？127除以12，商为10，余数为7，所以：

127≡7(mod.12)

把刚刚学的内容巩固一下，如果模为7，我们来检查一下下面的运算：

（1）3+3≡6

（2）3+14≡3

（3）3·3=9≡2

（4）5·4=20≡6

（5）7≡0

（6）35≡0

（7）-44=-44+0≡-44+7·7≡5

（8）-33=-33+0≡-33+5·7≡2

（1）6小于模，因此不变

（2）3+14=17；17:7=2……3

（3）3·3=9；9:7=1……2

（4）5·4=20；20:7=2……6

（5）7=7；7:7=1……0

（6）35=35；35:7=5……0

（7）-44=-44+0；-44+(7·7)=5

（8）-33=-33+0；-33+(5·7)=2

用Excel运算模为5的乘法表

模为5的乘法表如下：

　 0 1 2 3 4

0 0 0 0 0 0

1 0 1 2 3 4

2 0 2 4 1 3

3 0 3 1 4 2

4 0 4 3 2 1

如果你对Excel的操作稍微有点了解，运算模为5的乘法表以及类似的表格都会易如反掌。在我们的例子中，计算机上的Excel表达式（即所在行和列的位置）如下表所示。“被5整除后的余数”用Excel语言表达是“=remainder(number；5)”。计算模为5的4乘以3乘积的有效指令为“=remainder(4×3；5)”，运算得出答案为2。这样的表格在进行模运算计算时会有很大帮助。

那么模运算与恺撒密码之间有怎样的关系呢？回答这个问题，我们需要准备一个常规字母表和一个位移三个字母后的字母表，然后给字母表加上对应的序号。

我们发现，加密字母表中序号为x的字母就是明文中序号为x+3的字母。因此，关键就是找出明文中每个字母对应的序号和加密规则（位移三个之后）对应的序号之间的转换规律，即计算模为26的结果。注意密钥是3，因此它的函数表达式为：

C(x)=x+3(mod.26)

x为未加密的序号，C（x）是加密后的序号。也就是说，替换序号对应的字母，再进行转换就够了。以信息“PLAY”为例，我们给它加密：

P的明文序号为15，C(15)=15+3≡18（mod.26)，对应的加密字母为S。

L的明文序号为11，C(11)=11+3≡14（mod.26），对应的加密字母为O。

A的明文序号为0，C(0)=0+3≡3(mod.26)，对应的加密字母为D。

Y的明文序号为24，C(24)=24+3=27≡1(mod.26)，对应的加密字母为B。

那么，密钥为3，信息“PLAY”加密后即“SODB”。

通常，如果x代表我们要加密字母的位置（0对A，1对B,等），C(x)表示加密后字母的位置，那么公式为：

C(x)=(x+k)(mod. n)

其中n=字母表的长度（如英文中为26个字母），k=密钥，转换加密信息时就根据k的值。

对这样一条信息进行解密就是逆向操作加密过程。还以刚才的为例，解密即运用加密公式的逆向公式：

C⁻¹(x)=(x-k) (mod.n)

以用恺撒密码加密的信息“SODB”为例，英文字母表中密钥为3，即k=3，n=26，因此：

C⁻¹(x)=(x-3) (mod.26)

过程如下：

通过x=18，C⁻¹(18)=18-3≡15(mod.26)，计算得出，S的对应字母是P。

通过x=14，C⁻¹(14)=14-3≡11(mod.26)，计算得出，O的对应字母是L。

通过x=3，C⁻¹(3)=3-3≡0(mod.26)，计算得出，D的对应字母是A。

通过x=1，C⁻¹(1)=-2+26≡24(mod.26)，计算得出，B的对应字母是Y。

用恺撒密码加密，密钥为3的信息“SODB”，解密后的明文，就是“PLAY”。

我们刚刚初试了密码学中的数学，总结起来就是：可以创建一种新的转换模式，人们称之为仿射密码，广义上说就是恺撒密码，用公式表达是：

C(a,b)(x)=(ax+b)(mod.n)

n表示字母表中的字母数，a和b都是小于n的整数。a和n之间的最大公约数是1[gcd(a,n)=1]，因为在其他情况下，加密时有可能出现相同字母具有不同的表达，这点我们稍后会细说。加密的密钥由数字对（a,b）确定。因此，密钥为3的恺撒密码，即为a=1、b=3的仿射密码。

像这样的仿射密码比传统的恺撒密码安全性高吗？我们已经知道，仿射密码的密钥是数字对（a,b），那么如果信息是由26个字母写成并用仿射密码加密，那么a和b就可以取介于0和25之间的任意值。因此，像这样由26个字母编写的信息，其加密系统的密钥数为：25·25=625。根据观察，由n个字母编写的信息，其密钥数比恺撒密码的密钥数大n倍。尽管密钥数增长很多，但如果暴力破解的话，依然不是什么难事。

最大公约数（GCD）

两个数字的最大公约数可以用欧几里得算法（简称“欧式算法”）求出。欧式算法即辗转相除，先将两个数字相除，如余数不为0，则继续用除数和得出的余数相除，直到余数为0。余数为0时，最后一次相除的除数就是两数的最大公约数。例如：

gcd(48，30)？

48÷30=1……18

30÷18=1……12

18÷12=1……6

12÷6=2……0

此次计算得到的结果为：

gcd(48，30)=6

如果gcd(a,n)=1，那么就可以说a和n为互质数。

裴蜀定理在密码学中有着十分重要的意义，该定理的内容是对于大于0的两个整数a和n，存在整数k和q，满足gcd(a,n)=ka+nq。

间谍游戏

无论是信息接收者还是发送者，在什么条件下，才能破解一条用仿射密码加密的信息呢？举个简单的例子来说明这个问题，加密一条用6个字母写成的信息：

文本用仿射密码加密：C(x)=2x+1 (mod.6)。

根据C(0)=2×0+1≡1(mod.6)，字母A对应的加密字母为B。

根据C(1)=2×1+1≡3(mod.6)，字母B对应的加密字母为D。

根据C(2)=2×2+1≡5(mod.6)，字母C对应的加密字母为F。

根据C(3)=2×3+1=7≡1(mod.6)，字母D对应的加密字母为B。

根据C(4)=2×4+1=9≡3(mod.6)，字母E对应的加密字母为D。

根据C(5)=2×5+1=11≡5(mod.6)，字母F对应的加密字母为F。

可是，如果用同样的仿射密码对信息“ABC”和“DEF”加密再译解后，得出的却不是原信息，这是怎么回事？

如果加密表达式为C(a,b)(x)=(ax+b)(mod.n)，那么只有gcd(a,n)=1时，才能明确译解信息。在上例中，gcd(2,6)=2，就不符合这个限制条件。

解密的数学运算过程就相当于在已知数值y，模为n的条件下，求出未知数x：

C(a,b)(x)=(ax+b)=y(mod.n)

(ax+b)=y( mod.n)

ax=y-b(mod.n)

换句话说，我们要求出a⁻¹（a的倒数）的值，即满足a⁻¹a=1的条件：

a⁻¹ax=a⁻¹(y-b)(mod.n)

x=a⁻¹(y-b)(mod.n)

接下来，要想成功译解，就必须计算数字a对模n的倒数，为了不浪费时间，需要提前知道是否真的存在这样一个倒数。仿射密码C(a,b)(x)=(ax+b)(mod.n)，只有在满足gcd(a,n)=1的条件下，才有一个倒数。

以仿射密码C(x)=2x+1(mod.6)为例，我们想知道数字a（此处为2）是否有一个倒数。也就是说，是否有一个小于6的整数n满足公式2·n≡1(mod.6)。要想解决这个问题，我们要把所有可能的数值都试一遍，即0、1、2、3、4、5：

2·0=0，2·1=2，2·2=4，2·3=6≡0，2·4=8≡2，2·5=10≡4

可见没有符合条件的值，从这点可以得出，2没有满足条件的倒数。实际上，这点是我们已知的，因为gcd(2,6)≠1。

现在假设我们已经截获了一条加密信息“YSFMG”。我们知道这条信息已经按照仿射密码以C(x)=2x+3的方式加密，而且原文是西班牙文，有27个字母（包括字母N之后的Ñ）。那原信息是什么呢？首先计算出gcd(2,27)，结果为1。这说明能够破解出原信息！要想破解，我们必须求出C(x)=2x+3对模27的反函数：

y=2x+3

2x=y-3

要分离出x，就必须在方程等号两边乘以2的倒数。对模27时，2的倒数是一个整数n，符合2·n≡1(mod.27)，求出结果为14，就此确认：

14·2=28≡1

因此：

x=14(y-3)

接下来，我们就可以破解信息了：

字母Y占据第25位，解密它的过程是14(25-3)=308≡11(mod.27)。

字母表上的第11位为L，所以Y对应的解密字母是L。

同理，S：14(19-3)=224≡8(mod.27)，对应的解密字母是I。

F：14(5-3)=28≡1(mod.27)，对应的解密字母是B。

M：14(12-3)=126≡18(mod.27)，对应的解密字母是R。

G：14(6-3)=42≡15(mod.27)，对应的解密字母是O。

破解后的信息为西班牙单词“LIBRO”（书）。

超越仿射密码

在几百年的时间里，很多信息安全系统都是基于恺撒密码，以及恺撒密码的一般形式仿射密码开发的。今天，凡是将原始信息的每个字母由另一个相距一定位次的字母代替（不一定非得是3个）的加密方式，都被称作恺撒密码。

一个好的加密算法，最大的优点之一就是能够产生大量的密钥。无论是恺撒密码还是仿射密码，在密码分析面前都很脆弱，因为两者的最大密钥数都很低。

如果我们对加密字母表的字母顺序不设任何限制的话，密钥数就会大规模增加。含有26个字母（顺序不限）的标准字母表，可用的密钥数为26!=403 291 461 126 605 635 584 000 000，也就是403×10²⁴个密钥。假如破译者每秒钟破译一个密钥，那也要穷尽宇宙生命总长度的10亿倍才能把所有的密钥破译完。

常见的替换算法，密码如下：

（1）明文字母表；（2）加密字母表。

加密字母表的顺序，从前6个字母中可见端倪：QWERTY，它与标准电脑键盘上的字母顺序相对应。用QWERTY加密恺撒的那句名言“VENI VIDI VICI”（“我来，我见，我征服”）时，可在对应的加密字母表中找出对应字母，如下所示：

加密后即为：

CTFO CORO COEO

这种方法能够产生几乎无穷尽的密码，要想轻松记住，倒是有个简单方法。收发双方只要商定好“密钥单词”（也可能是个词组）就够了：把密钥单词置于加密字母表的前头，然后把它的最后一个字母作为起始点，后面按照常规字母表顺序将加密字母表补充完整，注意任何字母都不要出现重复。以“JANUARY CIPHER”（一月密码）为例。首先我们去掉空格和重复字母，得到密钥单词“JNUYCIPHE”。那么加密字母表就如下表所示：

信息“VENI VIDI VICI”加密后为“XCME XEYEXEUE”。使用这种代码生成系统加密，收发双方都不容易出错，而且易于更新。在刚才举的这个例子中，一个月更换一次代码足矣。从JANUARY CIPHER（一月密码）到FEBRUARYCIPHER（二月密码），再到MARCH CIPHER（三月密码），等等。一旦密码建立，收发双方就用不着再互通密钥了。

密钥单词替换算法稳定可靠，简便易用，几百年来一直是人们的首选加密系统。在那个时代，人们有个普遍的共识，那就是：在加密者和密码破译者之间，加密者占了上风。

加密上帝之语

中世纪的密码破译者认为，他们在《圣经·旧约》中发现了密码，而且他们确实没有搞错。《圣经》中有好几个片段用一种叫作“阿特巴希”（atbash）的替换加密算法加密过。阿特巴希密码就是将字母表中的任意字母（用n表示）替换成n在字母表中位置与之对称的字母。比如，英文字母表中，A由Z代替，B由Y代替，等等。《圣经·旧约》原文用的希伯来字母表进行替换。因此，在《耶利米书》25章26节中，“Babel”（巴别塔）一词加密后为“Sheshakh”（示沙克）。

18世纪初的《希伯来圣经》。

频率分析

《古兰经》共30卷，114章，每一章都对应先知穆罕默德得到的一个启示。这些启示都成文于先知归真之前，由先知的多个追随者执笔，后由第一任哈里发阿布·伯克尔整理，第二任和第三任哈里发，即奥马尔和奥斯曼依次编纂完成。由于原稿是断断续续写完的，因此兴起了神学的一门新学科，专门研究不同启示诞生的准确日期。古兰经学者运用当时的年代测定技术，汇编了某些词语出现的频率，认为它们是在编书时期创造的新词。如果一个启示中包含这些新词，就足以合理地得出结论，这篇启示出现得相对较晚。

这项研究后来促成了第一代密码分析工具的发明：频率分析。记录这一革新技术的第一人是哲学家肯迪，他于801年出生于巴格达。虽然他有多个头衔——天文学家、医生、数学家和语言学家——但历来为人熟知的却是密码破译者。即使肯迪不是史上第一位密码破译者，那他至少是最重要的一位。

14世纪的手抄本《古兰经》。

肯迪的开创地位直到近些年才渐为人知。1987年，以他的名字署名的专著《论解密加密信息》（On Deciphering Cryptographic Messages）在伊斯坦布尔的一家档案馆浮出水面。书中对于这项独创的技术有一段简要摘录：

对于一条加密信息，如果我们懂得它的语言，那么其中一个解密方法就是找出一份用相同语言书写的足够长的明文，然后数出每个字母出现的次数。频率最高的字母，我们称之为“第一”，其次为“第二”……诸如此类，直到把明文中出现的所有字母都囊括为止。接着观察要解密的加密文本，用同样的方法给文本中的符号分类。对出现频率最高的符号，我们用文本中的“第一”个字母替换，然后是“第二”个，如此，直到把解密的所有密码符号都覆盖为止。

在书的前几页中，他提到替换加密法让原文中的每个字母“位置不变，但样子改变”，正是因为这一成不变的“位置不变”，使得它在频率分析面前不堪一击。肯迪的天才之处就在于反转了加密者和解密者之间的力量天平，至少在一段时期内，天平倾斜向了解密者。

一个详例

英文字母表中，使用频率从高到低依次为：E T A O I N SH R D L C U M W F G Y P B V K J X Q Z，每个字母出现的百分比如下表所示：

假如一条信息用我们之前讨论过的替换算法加密，那么根据原始信息中字母出现的相对频率就可以破解。数一下加密信息中每个字母出现的次数，与所使用语言的频率表对比一下就行了。因此，如果一个字母在加密信息中出现的频率最高，假设这个加密字母是J，那么它对应的原始信息中的字母很可能就是E。同理，频率第二的字母若是Z，那么它对应的字母很可能是T。对加密信息中的所有字母重复同样的过程，这样一来，密码分析就完成了。

很明显，频率方法通常无法像这样直接应用。前面表格中的频率也只是以平均计。比如，信息“Visit the zoo kiosk for quiz tickets”很短，字母的出现频率与整个语言的平均频率特点是不同的。

密码破译者：夏洛克·福尔摩斯

频率分析解密技术颇具戏剧效果，吸引了众多作家的注意。或许，在以密码分析为蓝本写作的小说中，最著名的就是1843年埃德加·爱伦·坡（19世纪美国诗人、小说家和文学评论家）创作的《金甲虫》。爱伦·坡在书末附录中详细记述了一条自己虚构的加密信息，利用频率分析破解，过程天衣无缝。儒勒·凡尔纳（法国作家，被誉为“科幻小说之父”）及阿瑟·柯南·道尔为增加悬疑气氛，在创作故事主线中也用了同样的手法。在《小舞人探案》（The Adventure of the Dancing Men）中，柯南·道尔让主人公夏洛克·福尔摩斯碰到了一道替换加密的难题，迫使这位侦探研究起频率分析。可见肯迪的天才之作，即便在时过境迁1 000多年后，依然能够让市井百姓痴迷不已。

《小舞人探案》中夏洛克·福尔摩斯必须要破解的第一条加密信息，在这里我们就不详述解密过程了，以免给想读这本书的读者透露了故事情节。只消说一点：小舞人手中挥动的小旗是密码构成的一个重要因素。

实际上，这种简单的分析在破译少于100字符的信息时很少用得上。不过，频率分析并不局限于对字母本身的研究。在一条短信息中，使用频率最高的字母通常不可能是E，尽管我们同意这种说法，但我们可以更确定地说，在不知道字母对应的前提下，使用频率最高的前五个字母为A、E、I、O和T。英语中，A和I从不以成对的方式出现，但其他字母会。而且，同样可能的是，无论信息多短，元音字母通常出现在其他字母集合的前后，而辅音字母则与元音字母或少数字母组合在一起。这样一来，我们或许能够将T与A、E、I、O区别开来。由于我们成功破解了一些字母，因此只需要再解密一到两个字符，单词就可以拼写出来了，这将允许我们对那些字母的身份做出假设。破解的字母越多，破解的速度就越快。

多表加密法

1587年2月8日，苏格兰女王玛丽因叛国罪在佛斯林费堡被斩首。之所以最终判处得如此决绝，是因在司法调查中发现玛丽与以年轻人安东尼·巴宾顿为首的几个天主教贵族勾结，意图谋杀英格兰女王伊丽莎白一世，以期缔造囊括英格兰和苏格兰在内的天主教王国，并奉玛丽为女王。证据确凿无疑，而关键证据就是伊丽莎白手下的反间谍中心发现的，反间谍中心的领头人是沃尔辛厄姆勋爵。证据包括玛丽和巴宾顿的一系列往来书信，明确表明这位年轻的苏格兰女王对于这项谋杀计划不但知晓，而且赞同。信件是用密码和代码结合的算法加密的，也就是说，不只是用其他字符交换字母，还运用了特定的符号指代某些常用的单词。玛丽的加密字母表如下所示：

玛丽的加密字母表使用符号替代字母，除此之外，与世界各地的加密者几百年来使用的方法并无二致。年轻的女王和她的同谋确信密码安全无虞，但是对她来说不幸的是，伊丽莎白手下最优秀的密码破译者托马斯·菲利普斯刚好精通频率分析，不费吹灰之力就破解了玛丽的信件。后人称此事件为“巴宾顿阴谋”，令人感到挫败的是，这个事件给了全欧洲的政府和间谍当头一棒：传统的替换算法已不再安全。在新的解密工具的威势面前，加密者不堪一击。

苏格兰女王玛丽写给同谋安东尼·巴宾顿的信，最终她被判死刑，图为信件残片。

阿尔伯蒂的贡献

不过，频率分析摆出的难题，早在玛丽的头颅落地前一百多年前就已经找到了应对办法。全新密码大厦的建筑师当数多才多艺的文艺复兴学者莱昂·巴蒂斯塔·阿尔伯蒂（LeonBattista Alberti）。阿尔伯蒂以建筑师和数学家著称于世，在透视学研究领域也取得了跨越性的进步。1460年，他创造了一套加密系统，在第一个加密字母表基础上添加第二个加密字母表，如下图所示：

第一行：明文字母表；第二行：加密字母表1；第三行：加密字母表2。

阿尔伯蒂提出，加密任何信息，都可以交替使用两套加密字母表。以单词“SHEEP”（绵羊）为例，第一个字母在字母表1中找对应者，即V，而第二个字母在字母表2中找到，即L，第三个字母再回到表1，其余以此类推。那么，“SHEEP”就可以加密为“VLHCS”。与之前的加密算法相比，多字母表加密算法（简称“多表加密法”）的优势即刻跃然纸上——明文中的两个E，以不同的方式加密为H和C。而且，相同的加密字母在明文中代表两个不同的字母，这令密码破译者更加迷惑。这样一来，频率分析就大大失去了优势。阿尔伯蒂从未以专著的形式正式论述过他的想法，后来这种加密方法经由同时代的两位学者各自独立发展。这两位分别是德国的约翰尼斯·特里特米乌斯（Johannes Trithemius）和法国的布莱兹·德·维吉尼亚（Blaise de Vigenère）。

德·维吉尼亚方阵

恺撒密码使用的是单字母表加密法，即一个加密字母表对应一个明文字母表，这样一来，相同的加密字母总是对应相同的明文字母。经典恺撒密码中，D总是对应A，E总是对应B，其余依次类推。

但是，在多表加密法中，信息中的某个字母在加密字母表中可以对应很多字母。要破解一篇密文，每破解一个加密字母（在明文字母表中找到对应字母），要在不同的字母表之间往复。维吉尼亚是一位出生于1523年的法国外交官。在罗马进行为期两年的外交任务时，维吉尼亚获得了阿尔伯蒂的作品。最初，维吉尼亚对密码学的兴趣纯粹是实用的，与他的外交工作相关，但在39岁时，他放弃了自己的职业生涯，投身于一生的研究，其结果是创造了一种新的、更强大的密码。德·维吉尼亚方阵是第一个也是最著名的多表加密系统。阿尔伯蒂的密码使用两套加密字母表，然而，维吉尼亚密码使用了26种不同的加密字母表！

他的字母表包括一个由n个字母构成的明文字母表，下方会出现n个加密字母表，每个字母表以前一个字母表的第二个字母为首，依次循环。也就是说，它是一个纵横各26的方阵，如下页图所示。注意观察字母对应的对称性。字母对（A,R）=（R,A），这个关系符合所有的字母。

我们马上就能发现德·维吉尼亚方阵包括一个由n个字母构成的明文字母表，每个字母都能根据参数递增的规律转换。因此，运用恺撒密码参数，第一个加密字母表为a=1，b=2；第二个加密字母表刚好符合恺撒密码，即b=3，此后依次类推。德·维吉尼亚方阵的密钥包括知晓信息的哪些字母是加密的，以及对应的加密字母需要往下数到第几行。最简单的密钥是原始信息的所有字母往下移动一行。

圆盘游戏

多表加密有一种使用方法，那就是使用一种叫作阿尔伯蒂加密圆盘的仪器。这些密码仪方便携带，包括两个同轴圆盘，一个固定不动，上面刻有通用字母表，另一个可以转动，刻有另外一组字母表。信息发送者通过转动圆盘，把明文字母表与加密字母表匹配，匹配的最大数量与当前所用字母表的字母数相等。从阿尔伯蒂圆盘上获取的密码，不容易被频率分析破解。要想解密信息，信息接收者只需转动圆盘，转动次数与发送者一致即可。这种加密的安全性，通常与密码的秘密性息息相关，也就是可转动圆盘字母表的布置及转动的次数。一个刻有常规字母表的阿尔伯蒂圆盘，如果只有一个可转动的圆环，那么每转动一圈，就形成一个恺撒密码。美国内战中也用到了类似的仪器，今天在孩子们玩特工游戏用的玩具上也可以见到。

美国内战中南部同盟使用的阿尔伯蒂圆盘。

以此为密钥，那句经典“VENI VIDI VICI”的加密过程如下所示：

加密第一个字母V，在第二行中找到对应字母为：W。

加密第二个字母E，在第三行中找到对应字母为：G。

加密第三个字母N，在第四行中找到对应字母为：Q。

以此类推，I对应第五行：M。

V对应第六行：A。

I对应第七行：O。

D对应第八行：K。

I对应第九行：Q。

V对应第十行：E。

I对应第十一行：S。

C对应第十二行：N。

I对应第十三行：U。

外交官和密码专家

1523年，布莱兹·德·维吉尼亚出生在法国。1549年，法国政府派遣他出使罗马，在那里他开始对密码学和加密信息产生浓厚兴趣。1585年，他编写了一本开创性的专著《密码论》（Traicté des Chiffres），书中所载的加密系统令他名声大起。这套密码系统在近两百年内所向披靡，无人能解，直到1854年，英国人查尔斯·巴布奇（Charles Babbage）才将其成功破解。但奇就奇在，这一事迹直到20世纪，一组学者在研究巴布奇的个人笔记和计算时，才渐为人知。

原文加密后就是“WGQM AOKQ ESNU”。各位读者很容易就能发现，原文中本来重复的字母不再重复了。但是，所有密码专家都关心一点，那就是密码要容易识记、方便传递和易更新。破解信息的过程中，要找出密钥单词，它的字母数会等于或少于待破解信息的字母数，越短越方便使用德·维吉尼亚方阵。密钥单词的每个字母构成了字母表中每一行的首字母，之后按常规字母表顺序排列。加密时把密钥单词写在明文下方，重复排列直到明文结尾。接着，接收者以每个明文字符为横坐标，下方的密钥单词的字母为纵坐标，就能在方阵中找到对应的加密后的字母。

举例来说，如果要加密信息“BUY MILK TODAY”（今天买牛奶），密钥单词是“JACKSON”，那么：

加密后的信息就是“KUAWAZXCOFKQ”。

依据密钥单词“JACKSON”，从德·维吉尼亚方阵中提取出来的对应行。

与所有经典加密系统一样，使用德·维吉尼亚方阵解密信息与加密信息是对称的。以加密信息“WZPKGIMQHQ”为例，密钥单词是“WINDY”，则有：

先看第一行。假如(?,W)=W，我们要弄明白未知的“？”是什么。找到前面的德·维吉尼亚方阵，顺着W行找到W对应的字母A。接下来，要寻找满足条件(?,I)=Z的“?”，答案为R。其他同理。破解后的原始信息就是“ARCHIMEDES”（阿基米德）。

德·维吉尼亚方阵之所以具有历史意义，就在于它不易被频率分析破解，与之比肩的还有一种多表加密法，即格伦斯菲尔德（Gronsfeld）密码（两者在同一时期被创造，附录中有详述）。如果同一个字母可以加密成两个及以上的字母，那什么样的密码分析才能破解它呢？这个问题要等300年才能回答。

加密字母表的分野

虽然等了近乎8个世纪，但以德·维吉尼亚方阵为首的多表加密法最终以智取胜，打败了频率分析。说来奇怪，虽然单表系统脆弱易攻，但自身也有优势，那就是好部署。密码专家呕心沥血，不断完善这个过程，在算法中加入巧妙的方法，但从根本上说，理念都与最简单的加密方法相同。

密码专家：太阳王路易十四

路易十四执政时期，虽然坊间对安托万（Antoine）和博纳旺蒂尔·罗西尼奥尔（Bonaventure Rossignol）兄弟知之甚少，但他们却是17世纪欧洲大地上最令人闻风丧胆的人物。作为密码专家，他们不仅在破解法国敌方（也是国王的仇人）信息方面能力卓越，创造性也同样突出。他们创造了“伟大密码”（Grande Chiffre），用一套复杂的音节替换算法加密国王最重要的信息。不过，两兄弟死后这种加密法就失传了，从此无人能破解。1890年，一位密码专家，退伍军人艾蒂安·巴泽里耶斯（Étienne Bazeries）踏上了破解这些加密文件的艰难征程，几年的勤勉时光，让他成为破解太阳王密信的无可争议的专家。

单表系统中最成功的一个范例就是“同音异字替代加密”，这么做是为了防止对方使用数据分析破解，毕竟按照字母出现的最大频率就能推导出替换率。因此，在一篇任意语言写成的文本中，如果字母E占10%，使用同音异字替换加密法用10个其他字符替换E，就能改变这个频率。18世纪之前，这种方法一直备受青睐。

然而，时光继续流转，伟大的民族和国家涌现出来，国家之间的外交对保密通信的要求越来越高。随着新的通信技术的出现，这一趋势进一步增强，比如电报，它大大提高了通信量。欧洲国家建立了俗称“黑屋”的通信活动神经中枢，在那里，专家加密那些最需谨慎处理的通信，并破解截获的敌方信息。很快，黑屋的专家使得任何形式的单表替换加密法无论如何改进，统统都不再安全。慢慢地，这场信息交流比赛中的伟大玩家开始选择多表加密法。在加密者的努力下，破译者失去了最有力的武器——频率分析，再次处于下风。

默默无闻的破译者

英国数学家查尔斯·巴布奇（1791-1871）是19世纪最耀眼的科学家之一。他发明了一台早期机械计算机，叫作“差分机”，走在了时代的前沿。他对当时的数学和技术都有着浓厚的兴趣。巴布奇决定用自己的智慧破解多表加密法，而德·维吉尼亚方阵就是他的主要目标。他把注意力集中在这种加密法的特点上。此时我们需要回想一点：在德·维吉尼亚加密法中，选中的密钥单词长度决定了使用的加密密码表的数量。因此，如果密钥单词是“WALK”（步行），原始信息的每个字母最多可以用四种方式加密。对于句子来说同样是如此。巴布奇开始攀登多表加密法这个悬崖峭壁，而这点正是他的踏足点。我们来看一个例子，下面是一条用德·维吉尼亚方阵加密的信息：

大家马上就能注意到，原始信息中的两个“BY”与加密信息中两个“XY”同时重复了。这是因为第一个“BY”在8个字符后，又出现一次，而8是密钥单词WALK字母数4的倍数。有了这条信息，再加上足够长的原始信息，就有可能猜到密钥单词的长度了。过程如下：把所有重复的字符列出来，观察隔了多少字符出现了重复。然后，计算这些数字的整数除数。其公约数有可能就是密钥单词的长度。

假设出现次数最多的公约数是5，那5就最有可能是密钥单词的字母数。接下来，我们必须要猜出密钥单词中的5个字母的对应字母各是什么。回想加密过程，密钥单词的每个字母在德·维吉尼亚方阵中都是一个与原始信息中字母对应的单表加密。我们假设的包含5个字母的密钥单词（C1, C2, C3, C4,C5）的第一个字母与第六个字母（C6）使用的加密字母表相同，第七个（C7）与C2相同，以下同理。因此，破译者实际上处理的是5个独立的单表加密，而单表加密在传统的密码分析面前都不堪一击。

1991年，根据发明家巴布奇留下的方案制造的差分机。这台仪器能够计算对数函数和三角函数的近似值，因此也就能计算天文表。可惜巴布奇有生之年没有见到它被制造出来。

因此我们得出结论，可以根据加密信息中的每个用密钥单词中的相同字母（C1, C6, C11,…与C2, C7, C12,…）加密的字母设计出一个频率表，然后你会得出五组构成全部信息的字母。最后借助明文信息使用语言的频率表，解密密钥单词。如果两组数据不能吻合，那就再试长度的可能性位居第二的密钥单词。这次我们至少能够确定一个可能的密钥单词，剩下的就是解密信息了，这个方法攻破了多表加密法。

尽管如此，巴布奇于1854年前后完成的这项令人震惊的试验仍将默默无闻。这位性情古怪的英国学者从未向世人公布他的发现，直到近期对他的笔记进行研究时，才发现原来他是破解多表密钥单词的先驱。令全世界的密码破译者感到庆幸的是，在巴布奇发明他的解密方法几年后，也就是在1863年，普鲁士军官弗里德里希·卡西斯基（Friedrich Kasiski）向世人公布了一个类似的方法。

无论谁是破解多表加密法的第一人，总之，它不再那样牢不可破。从那时起，加密强度不再单纯依靠加密算法上的革新，而是越来越多地依靠增加潜在的加密字母表数量，数量越多，频率分析和它的变式就越不可能实现。而对垒的另一方的目标，就是想方设法加快密码分析的速度。两方遥相呼应，研究方向指向了同样的目标，共同促成了一个进程的诞生：计算机浪潮。

第三章 编码机

19世纪，编码不断普及，其用途不再局限于发送秘密信息。19世纪上半叶，电报的发展，以及随后托马斯·爱迪生的双向电报的发展，革新了全世界的信息通信。由于电报靠电脉冲驱动，就必须运用一套系统，将信息内容翻译为机器能够表达的语言，并发送出去。换句话说，需要用代码表示自然语言。在众多创意当中，美国艺术家和发明家塞缪尔·莫尔斯（Samuel Morse）发明的点线系统（即莫尔斯电码）脱颖而出。人们把莫尔斯电码看作编码的前身，几十年之后，我们间接使用它们给计算机输入数据，并读懂从计算机输出的数据。

莫尔斯电码

莫尔斯电码用点、线、空格组合表示字母表中的字母、数字和其他符号。这样一来，它就把字母表翻译为能够用光、声音或电的简单符号表达的内容。点表示一个时间单位，大约为1/25秒；线表示三个时间单位（等于三个点）。字母之间的空格也是三个时间单位，单词之间的空格用五个时间单位表示。

非语言的交流

托马斯·爱迪生（1847—1931）因患有听力障碍，就与妻子玛丽·史迪威以莫尔斯电码的方式交流。两人恋爱期间，爱迪生用手轻拍电码向玛丽求婚，玛丽也以同样的方式回应他。后来，电码就成了这对夫妻常用的交流方式，甚至去剧院看戏，爱迪生都会把玛丽的手放到自己的膝盖上，这样她就能把演员的对白“发报”给他了。

最初，莫尔斯没能在美国和欧洲申请到电码的专利权。1843年，他终于获得了政府的财政支持，在华盛顿（特区）和巴尔的摩之间铺设了一条电报线路。1844年，第一条编码传输完成，不久之后一家公司成立了，专门负责整个北美洲的电报线路覆盖。1860年，拿破仑三世授予莫尔斯法国荣誉军团勋章，此时，他的电报线已经纵横交错在美国和欧洲大地上。1872年莫尔斯去世时，美国已经铺设了长达30万千米的电缆。

这台起初由莫尔斯在1844年发明的简单仪器，此时已开始用来发送和接收电报信息。这台设备包括一个电报发报键——用来连接和断开电流，还有一个电磁体——用来接收输入信号。发报员每次按下发报键（通常会用食指或中指），就会产生电接触。按动发报键，间歇性脉冲就通过由两根铜线组成的电缆传送出去。这些线由高高的木制“电线杆”支撑，连接国内不同的电报站，通常能不间断延伸数百千米。

1844年塞缪尔·莫尔斯发明的第一台电报机。

V大调交响曲

说起与电报结缘的聋人，贝多芬也是一位，不过没那么直接。他的天才之作《第五交响曲》最著名、最振奋人心的前四个和弦让人们不禁会联想起一条莫尔斯电码信息“dot dot dot dash”（点点点线）。

在莫尔斯电码中，“dot dot dot dash”对应的字母是V，也就是单词“victory”（胜利）的首字母。为此，“二战”期间，英国广播公司（BBC）将贝多芬的《第五交响曲》作为向欧洲占领区播送的节目的开场曲。

输入信号接收器包括一个由铜线圈缠绕铁芯构成的电磁体。当铜线圈接收到与点线相符的电流时，铁芯磁化，并吸引一块也由铁构成的活动部件。这个部件击打磁体时，会产生与众不同的声音。接收到一个点，就发出短促的“咔嗒”声，如果是一条线，声音就长些。最初，借助这种仪器发送一封电报，需要一位操作员在一边敲打出信息的编码版本，另一个人在一边接收并译解出来。

莫尔斯电码的通用字符的翻译如下表所示：

所以，信息“I love you”（我爱你）编码后就是：

从一定程度上说，莫尔斯电码是后来数字通信系统的前身。为了证明这一点，我们可以把莫尔斯代码转换成数字，1表示点，0表示线。由1和0构成的字符串在后面的章节中会经常出现。

在20世纪，无线电的发明催生了无线通信，取代了传统的电报。不久之前的电报员摇身一变，成了无线电报员。这项新技术意味着信息能够以更快的速度和更大的容量传递。然而，通过电磁波发送的信息比较容易被截获。这不仅给密码破译者提供了大量加密的材料去破解，也有利于巩固他们在与加密者的对抗中的主导地位，鉴于多数密码都是政府和私人机构使用的，因此即便是最敏感的信息，也都基于已知的算法。以普莱费尔密码为例，它是由英国莱昂·普莱费尔（Lyon Playfair）男爵和查尔斯·惠特斯通爵士（Sir CharlesWheatstone）创造的。普莱费尔密码是对波里比阿密码的独创性变式，但最终也只是一种变式——附录中有详细说明。

虽然对这些密码的创造者而言，新密码是相当大的创新，但破译这些循环密码只是时间和计算能力的问题。“一战”中的密码史完美阐释了这一点。在齐默尔曼电报事件中，我们已经了解了德国外交加密中的弱点。还有一个名为“ADFGVX”的常用密码用来加密前线最敏感的信息，本以为这种密码无懈可击，却同样也被敌方破解了。“一战”中，德国在密码方面的双重失败使得各方都意识到，必须提高加密信息的安全性。要想达到这个目的，就要增加密码分析的难度。

拯救我们的灵魂（Soul）、船只（Ship）或任何以“S”开头的事物

莫尔斯电码中最有名的信号当数“SOS”了。由于它简单且易于传递（三点、三线、三点）——没有任何实际意义，所以几个欧洲国家共同确立其为求救信号。但是，人们很快就给这个信号赋予了其他含义。这些“情形缩略语”中最常见的就是“Save Our Souls”（拯救我们的灵魂）。后来，这个信号在海上使用频繁，“SOS”也变成了“Save Our Ship”（拯救我们的船只）。

距离巴黎80千米

1918年6月，德国军队准备袭击法国首都。协约国抵抗的关键就在于能否截获德军信息并弄清他们的进攻计划。德军发往前线的信息是用ADFGVX密码加密的，在德军看来，它牢不可破。

关于这个密码，令我们感兴趣的地方就在于它结合了替换和换位算法。这是传统加密法中最精密的方法之一。1918年德国采用了这个密码，而在法国尚未注意到它的存在时，德国就已经铺天盖地般地用它来加密和解密信息了。幸运的是，天赋异禀的密码破译者乔治斯·潘万（Georges Painvin）当时正在法国中央密码局工作。他夜以继日地研究这个密码。1918年6月2日晚间，潘万成功破解了第一条信息，内容令人感觉不妙，那是对前线发出的命令：“Rush munitions。Even by dayif not seen。”（军火急速前进。白天也要隐秘前进。）技术分析显示，德军这条密电是从巴黎北部大约80千米的地方发出的，位置应在蒙迪迪耶和贡比涅之间。潘万成功破解的信息揭露了以德国为首的同盟国的进攻意图，使得协约国军队能够挫败此次攻击，最终赢得战争。法国把此事称为“电报大捷”。

前面提到，ADFGVX密码包括两部分：替换和换位。首先是替换，我们列一张7×7的表格，第一行和第一列都包括字母ADFGVX。其余表格内随机填上36个字符：26个字母和从0到9的十个数字。字符的排列构成了密码的密钥，很明显，信息接收者有密钥才能理解信息的内容。

我们就用下方的基表来试试：

加密过程是，用ADFGVX表示坐标，把信息中的每个字母翻译为坐标的形式。坐标中第一个字符对应行，第二个对应列。比如，我们要把4加密，就写为“DV”。信息“Target isParis”（目标是巴黎）加密情况如下表所示：

讲到这儿，我们就知道这个密码用的是简单替换，使用频率分析就足以破解。

但是，密码还包括第二道程序：换位。收发双方商量好一个密钥单词，换位就依据它进行。过程如下：首先，创建一个表格，列数等于密钥单词的字母数，每个格内填上加密文本。将密钥单词的字母填入表格的顶行。以密钥单词“BETA”为例。创建一个新表格，顶行填入密钥单词，其余行填入替换加密信息的字母。所有空格内填入数字0，我们知道0用“AG”表示。

然后对信息“Target is Paris”进行第二次加密。首先回忆一下替换加密后的信息：

再应用密钥单词“BETA”生成一个新表：

接下来，再用换位加密法改变每列的位置，密钥字母按照字母表顺序排列，如下图所示：

把表格中的字母组合起来，就产生了加密信息，最终得到的加密信息是：

AAXFAXGGFGVAFVXVVXDVFFDGVFVA

我们可以发现，信息是由ADFGVX几个字母随机组合而成的。德国之所以选择这六个字母，是因为它们在莫尔斯电码中发音区别性非常大，这可以帮助接收者轻易判断出可能存在的传递错误。再者，因为它只包括六个字母，电报传递简单易行，所以经验不足的操作员也容易操作。

现在我们把目光转回本章开头的莫尔斯电码表，发现ADFGVX密码中每个字母对应的莫尔斯电码分别为：

A=·–

D=–··

F=··–·

G=––·

V=···–

X=–··–

接收者只需要随机分布的字母和基表上的数字，以及第二个换位密钥，就能译解这条信息了。

战壕代码

战争中，使用像ADFGVX这样的复杂密码非常不易。比如，在西班牙内战（1936—1939）中，有很多较为简单的替换算法，如：

可以发现，有几个字母的加密方式不止一个。例如R可以用28或54替换。单词“GUERRA”（战争）加密之后就是：167427285453。这些代码是主要的替换代码，叫作“战壕代码”，有专门用途。

图中的“紫色密钥”（Clave Violeta）是共和军104旅415营使用的密钥，被国民军截获。内容为：“密码必须用字母表示。用（1）标注的列（行）对应字母表，用（2）标注的列对应相应的代码。”

为了提高信息保密性，以佛朗哥为首的国民军部署了另一种武器——纳粹盟军提供的30台恩尼格玛密码机。这或许是军事史上第一次大规模使用加密仪器，德国在“二战”中也使用过。西班牙内战期间，英国曾试图破解该密码系统，但没有成功。

1936年10月27日发给共和西班牙长枪党法西斯分子在加那利群岛截获军的电报：“昨天你们加密的电的共和军编码信息。报……经证明无法破解。”

恩尼格玛密码机

1919年，德国工程师亚瑟·谢尔比乌斯（Arthur Scherbius）为他发明的机器申请了专利，这台机器可以产生完全保密的通信，机器的名字就是“恩尼格码”（Enigma，意为“谜”），后成为“军事秘密”的代名词。恩尼格玛精密复杂，有目共睹，但实际上，它只是阿尔伯蒂圆盘的改进版，往下看大家就明白了。

因它使用起来相对方便，因加密过程复杂，“二战”期间，德国政府用恩尼格玛密码机加密了大量的军事通信。

因此，破解恩尼格玛，成为各国政府对抗纳粹德国的头等大事。事实证明，最终盟军情报机构成功破解的信息成为战争取得胜利的关键。破解恩尼格玛基本上是由波兰和英国的情报部门完成的，过程精彩纷呈，引人入胜，其中的主角就包括数学天才阿兰·图灵，后人把他誉为现代计算机之父。成功破解恩尼格玛，也孕育出史上第一台数字计算机，在漫长多彩的军事密码破译史上，书写了最壮丽的篇章。

“二战”战场上，德国士兵在抄录恩尼格玛加密的信息。

四转子恩尼格玛密码机复制品。

恩尼格玛密码机本质上是一种电磁设备，外表与打字机相似。它的特别之处在于，它的机器构件能够改变每次按键的位置，所以即便是同一个明文字母连续打出来，每次的编码几乎也都各不相同。

加密的实际过程相对简单。首先，发送者会根据当时有效的代码本（代码本定期更新）确定一个起始点，设置机器的插件和转子。接着，他打出明文的第一个字母，机器会自动产生一个替代字母并出现在照明盘（最原始的显示器）上，于是就产生了加密信息的第一个字母。

转动第一个转子，将其定位在26个可能位置中的一个。转子的新位置生成字母的新密码，接着信号操作员打出第二个字母，依次类推。要解码这条信息，只需把第二台恩尼格玛密码机的起始参数设置为加密时的参数，然后键入加密字符就可以了。

借助下一页的插图，我们把恩尼格玛的加密机制用简化图的方式呈现出来。在简化图中，转子的字母表只有三个。因此，每个转子只有三个可能的位置，当然真实情况中是26个。

可以看出，恩尼格玛密码机的转子在起始位置时，除了A保持不变外，原始信息中的每个字母都被其他字母替换掉了。加密第一个字母后，转子转动三分之一。此时在新位置，替换的字母相比第一次发生了改变。最后是第三个字母，转子转回起始位置，密码序列出现重复。

标准恩尼格玛密码机的每个转子有26个位置，与26个字母一一对应。也就是说，一个转子能够产生26个不同的密码。所以，转子的起始位置就是密钥。为了增加可能的密钥的数量，恩尼格玛密码机设计了三个转子，彼此机械地连接。

当第一个转子转动后，相邻的转子就会启动另一个，直到所有转子都转完，可能的密码总数为26·26·26=17 576。此外，谢尔比乌斯的设计允许更改转换器的顺序，这样就能进一步增加密码的数量，稍后我们会一窥究竟。

三个转子的恩尼格玛密码机，打开前部可以看到它的连接板。

除了三个转子外，恩尼格玛还有一个连接板，位于第一个转子和键盘之间。连接板使得成对字母在连接转子前就可相互转换，这样又大大增加了加密密码的数量。标准设计的恩尼格玛密码机有6根线，最多能够交换6对字母。下页图演示了连接板的交换操作，同样以简化的方式，只保留三个字母和三根线：

这样，a与C交换，b与A交换，c与B交换。加上连接板，具有三个字母的简化版恩尼格玛密码机的运行过程如下图所示：

看似只增加了一个连接板，但额外能够产生多少密码呢？我们必须要思考从26个字母中选出的6对字母可产生的连接方式的数量。有N个字符的字母表，其中n对字母的转换数量由这个方程计算可得：

在我们的例子中，N=26，n= 6，即能够提供100 391 791 500个组合。

结论是，如果一台恩尼格玛密码机具有三个带有26个字母的转子和一块有6根线的连接板，那么它能提供的密码总数为：

1.参考转子的转数，26³=26·26·26=17 576种组合。

2.同理，三个转子（1, 2, 3）彼此交换，能够产生的位置有1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2, 3-2-1；这又增加了6种可能的组合。

3.最终，我们计算出，配备6根线的连接板增加了100 391 791 500个额外的密码。

不同的具体组合数的乘积就是可获得密码的总数：6·17 576·100 391 791 500=10 586 916 764 424 000。因此，恩尼格玛密码机加密一条信息能够产生一万万亿种不同的组合。纳粹德国坚信其安全，因为有最高安全指数的通信。可是，这是一个很大的错误。

破解恩尼格玛

任何一个恩尼格玛的密钥首先要确定连接板上的配置，也就是6个可能性的字母交换，比如，B/Z、F/Y、R/C、T/H、E/O和L/J，即第一组连接交换的字母是B和Z，其他同理。其次，密钥透露了转子的顺序，如2-3-1。最后，密钥包括转子的起始方向（如R、V、B，表明了哪个字母位于起点，也叫索引标志）。这些设置都收录在密码本中，而密码本本身也以加密的方式传递，一两天或者接到命令的时候都会更新，比如，特定的密钥是专为特定类型的信息保留的。

有时一天会发送上千条密电，为了避免在一整天内重复使用相同的密码，恩尼格玛操作员在传递密码时会使用一些小技巧，这样他们无须替换共享代码的整个密码本，就可以发送新密码。例如，操作员发送6个字母的信息，根据当天的密码进行编码，实际上就是一组新的转子索引标志，比如T-Y-J。（为增加安全性，发送者对这三个指令编码时执行两遍，因此是6个字母。）接下来，他要根据新设置，对真正的信息进行编码。接收者收到信息后，无法直接用当天的密码解译，但他知道前6个字母实际是设置转子位置的指令。接收者会保持连接板和转子顺序不变，然后就能准确解码信息了。

1931年，盟军情报人员从德国间谍施密特手中取得了第一条关于恩尼格玛的珍贵情报。情报中包含多个关于该机器的使用手册。法国情报机构与施密特进行了接触，随后将情报发给波兰情报机构。波兰密码分析部门——密码局，集中研究施密特带来的情报，并从德方手中偷来多台恩尼格玛密码机。

波兰破译团队会集了大量数学家，这在当时非同寻常。团队中有一位天赋异禀、腼腆、内省的23岁年轻人——马里安·雷耶夫斯基（Marian Rejewski），他注意到德方每天的通信信息中，很多都是以6个字母的密码开头的，于是将注意力集中在这点上。雷耶夫斯基总结出一个理论：密码的后三个字母是前三个字母的新密码，因此，知道第四个、第五个和第六个字母就能找到转子转动的线索。

这个发现看起来微不足道，但雷耶夫斯基就此建立了一套特殊的推理网络，最终破解了恩尼格玛系统。这个过程非常复杂，此处我们不便详细说明，不过事实摆在那儿。几个月后，雷耶夫斯基将需要破解的可能密码的数量从10万亿减少到105 456，这是由转换器的顺序组合和不同的转动方式导致的。为了破解密码，雷耶夫斯基创造了一个仪器，取名为“邦贝”（Bombe），它与恩尼格玛的操作方法一样，在搜索当日密码时，能够模拟三个转子的所有可能性位置。1934年初，波兰密码局破解了恩尼格玛，并能在24小时之内破解任何信息。

不同版本的恩尼格玛密码机。

虽然德国人不知道波兰人已经攻破了恩尼格玛的安全系统，但他们还是对这个已经运行了十多年的系统进行了改进。1938年，恩尼格玛操作员收到两个新转子，加到标准的三个转子机器上，不久后，新型机器又安装了十个连线板。

突然之间，可能的密码数量增加到约159×1018个。单是增加两个转子，就把转子的旋转次数组合从6增加到60，即处于首位的五个转子的任意一个（5个选项）乘以第二位的剩余四个转子的任意一个（4个选项）乘以第三位的剩余三个转子的任意一个（3个选项）=5×4×3=60。虽然波兰密码局的工作人员知道如何破解这种密码，但无法分析十倍于它的新转子配置。

英方接手

恩尼格玛系统的更新不是随性之举，当时德国已然开始在欧洲的侵略扩张，吞并捷克斯洛伐克和奥地利后，正意图入侵波兰。1939年，欧洲腹地战火四起，波兰沦陷，波兰人把所有的恩尼格玛密码机转移给英国盟军，并告知使用方法。同年8月，英国决定把之前已解散的密码分析部门重新组织起来，位置选在了伦敦郊区的一处名为“布莱切利庄园”的地方。一位密码破译新贵也加入布莱切利庄园，他就是年轻的剑桥数学家阿兰·图灵。图灵在计算机领域享有盛誉，不过当时计算机还处于萌芽阶段，并朝着革命性的全新发展方向敞开了大门。破译改进后的恩尼格玛密码机，后来被证明是朝计算机大踏步迈进的推动力。

布莱切利庄园内忙碌的专家，恩尼格玛系统在此被破解。

布莱切利庄园的专家将注意力集中在加密文本的片段和疑似对应的明文片段上。比如，多亏身在现场的间谍，他们才得知德国人习惯在每天下午6点左右，将前线各地的天气情况编码发送出去。因此他们就有理由确定，那个时间点过后不久截获的信息中，一定包含明文为weather（天气）和rain（雨）等的加密信息。图灵发明了一个电子系统，能够复制三个转子的因顺序和位置不同产生的所有可能的组合，而且在5个小时内就能把1 054 650个可能组合全部复制出来。该系统根据字符长度和其他线索，会输入疑似对应明文片段的密文单词，比如前面提到的weather和rain。

假设他们怀疑密文“FGRTY”是加密后的“BREAD”（面包），密码输入系统后，如果转子的组合刚好给出“BREAD”，那么密码破解员就知道了这个代码对应的转子的配置。接下来，操作员根据代码设置转子，将密文输入真的恩尼格玛密码机中。如果机器显示译解后的文本，比如说是“DREAB”，就能确认与连接板的线相关的位置包括字母D和B的换位。这样，他们就获知了整个代码。恩尼格玛的秘密最终大白于天下。在发展并完善上述分析系统的过程中，布莱切利庄园团队创造了史上首台数字可编程计算机，将其命名为“巨人”（Colossus）。

位于布莱切利庄园的“巨人”，现代计算机的前身。图片摄于1943年，从中可以看出这台复杂设备的控制面板。

“二战”中的其他密码机

日本自主发明了两种编码系统，分别是：“紫色”（Purple）和JN-25。第一个为外交通信专用，第二个用来发送军事信息。两种密码机都是通过机械装置驱动的。拿JN-25来说，其构成是替换算法，将日语的书写字符（最大限度为30 000字符）转换为数字，数字则是通过五个数组表任意指定的。虽然日本早有防备，但英国和美国还是破译了“紫色”和JN-25。情报部门将破译了“紫色”和JN-25的密码所截获的情报用“Magic”（魔术）这一代号来命名，这在太平洋战争的关键战役中，尤其对1942年的珊瑚海海战和中途岛战役具有巨大的影响。Magic的情报同样还用来制订战略计划，比如指导盟军1943年击落日本军事指挥官山本五十六的座机的行动。

纳瓦霍人密码员

美国截获了敌军在太平洋战场作战计划的情报，充分利用这份情报的同时，美国对自己的军事通信也用了几种加密方式，将加密算法直接置于语言的自然属性层面。这些密码就是乔克托、科曼奇、麦斯奎基，以及人数最多的纳瓦霍（均为北美印第安部族）等族的语言，既没有明确编写成复杂的手册，也未经明智的加密部门筹划，它们只是北美印第安各族的语言。

旷世天才

1912年，阿兰·图灵生于英国。少年时代，他就在数学和物理方面展现出极高的天赋。1931年，他考入剑桥大学，在那里，逻辑学家库尔特·哥德尔（Kurt Gödel）的研究吸引了他的兴趣。哥德尔研究的是所有逻辑体系的固有不完整性的一般性问题。三年前，他就构建某种机器的理论可能性发表了一篇论文，这种机器能够运算诸如加法、乘法等不同算法。受哥德尔研究的启发，1937年，图灵将有限的证明和计算向前推动了一步，并构建了“通用机器”的原理，这台机器能够执行所有可能的算法，现代信息理论的支柱之一就此诞生。在此之前的两年，图灵曾与伟大的匈牙利数学家亚诺什·冯·诺依曼（János von Neumann）有过接触，当时冯·诺依曼住在美国，大家都叫他约翰。人们把冯·诺依曼称为“另一位计算机之父”，他给图灵在普林斯顿提供了一份薪水和地位都很高的工作，但图灵拒绝了，他更喜欢剑桥波希米亚式（不拘于传统）的氛围。1939年，战争爆发，他加入位于布莱切利庄园的英国密码分析团队。图灵在战争期间的突出贡献为他赢得了大英帝国勋章，但他是同性恋，这在当时是非法的。1952年图灵被判有罪，无法继续承担政府的保密工作。1954年6月8日，因提起的反诉被驳回而心生绝望，阿兰·图灵吞下氰化钾自杀身亡。

美军在这些印第安人中挑选出无线电操作员，分组安排在前线，用各自的语言传递信息，这样一来，不光是日本人不懂，除了这些印第安无线电操作员，其他美军士兵也不懂。这些加密信息中还叠加了一套基本密码，以防士兵被捕后被敌方强行逼供将信息翻译出来。朝鲜战争之前，这些“密码员”一直在美军服役。

1943年，布干维尔岛战役中的两名纳瓦霍人“密码员”。

创新：希尔密码

看到这里，我们已经明白，以某种提前设定好的方式替换字符的加密方法，通常很容易被破译者破解。

1929年，美国数学家莱斯特·S.希尔（Lester S. Hill）结合模运算和线性代数发明了一套新的加密系统，申请专利后意欲销售，但未成功。

接下来我们可以看到，在加密信息时，矩阵是一个非常有效的工具，可以把文本编为一个个字母对，每个字母都有对应数值。

我们用矩阵加密一条信息：

限制条件是行列式为1，即ad-bc=1。使用逆矩阵解密这条信息：

对行列式的值的限制条件确定后，逆矩阵就可以作为解译工具进行运算了。通常，含有n个字符的字母表，其gcd（A,n的行列式）=1。如果对应结果正确，那么模运算可以逆向就不能确定了。

简单了解线性代数

矩阵是指先排列“行”再排列“列”的数字表格。比如，2×2矩阵的形式为：

2×1矩阵的形式为：

两个矩阵相乘得到一个新的2×1矩阵，叫作列向量：

在2×2矩阵中，ad-bc的值叫作矩阵的行列式。

继续看刚才的例子，取26个字母的字母表，加上一个代表“空格”的字符（方便起见，我们在此用@表示“空格”）。每个字母都赋予一个数值，如下所示：

计算0和26之间的值，要用模27进行运算。

加密和解密文本的过程如下页所示：首先确定行列式为1的加密矩阵A。

比如，

解密矩阵就是逆矩阵

因此，A就是加密密钥，而A⁻¹是译解密钥。

下面，我们以信息“BOY”（男孩）为例。信息中的字母成对分为：BOY@。在表中对应的数字也以成对的方式列出来，即（1,14）和（24,26）。接下来，每对数字均乘以矩阵A：

根据表格，所得结果对应的字母为（Q,T）；

根据表格，所得结果对应的字母为（V,O）。

最终，信息“BOY”加密为“QTVO”。

译解时，使用矩阵进行逆向运算：

得到字母对（Q,T），在表格中对应的数值为：(16,19)，然后乘以A⁻¹，得到：

(mod. 27),对应字母对(B, O)；

同理，第二组字母对（V,O）对应的数字为（21,14），得到：

(mod.27),对应(Y, @)。

以上便是译解密钥的过程。

在这个例子中，我们用的是两个字符对。如果把字母分为三个一组甚至四个一组时，保密性会大大增强。在这些情况中，计算时各自使用3×3矩阵和4×4矩阵，如果手动计算的话，是极为费时耗力的。不过，借助现代计算机，计算大型矩阵及相应的逆矩阵已成为可能。

但是希尔密码有很大的弱点：信息接收者拿到明文的一个小片段，就有可能破解整个信息。显然探索完美密码的征程远未结束。

第四章 用数字0和1的通信

“巨人”计算机的诞生和恩尼格玛的破解打开了人类通往有史以来最伟大的信息革命的大门。这一巨大进步基于一种加密系统的发展，这种加密系统能够横贯巨大的网络，保证通信安全、有效、快速，而这只需要两个基本的参与者：计算机和用户——你和我。我们今天再提到security（安全），不仅仅是指密码学和保密，同时还有一个更加宽泛的含义，包括可靠性和效率的概念。

二进制构成了这次科技革新的基础。这种超级简单的代码由两个字符构成：0和1，在计算体系中，这种代码能够表示计算机中电子电路的交互作用，即电路打开（有脉冲）用1表示，电路断开（脉冲间隔）用0表示。每个0和每个1用“比特”［bit，二进制位（binary digit）的缩写，也可称为“位”］表示。

美国信息交换标准代码（ASCII）

二进制应用广泛，其中一个应用方式就是用它表示一组具体的字符集，每个字符包括8比特，即一个字节。这些字符是由字母和数字混合编制的，代表传统通信中的基本符号。人们把这些字符称为ASCII代码，即美国信息交换标准代码。每组0和1的排列种数为：2⁸=256。

内存字节

一台计算机的内存和存储容量是以字节的倍数计量的：

千字节（kB）：1 024字节

十亿字节（GB）：1 073 741 824字节

兆字节（MB）：1 048 576字节

太字节（TB）：1 099 511 627 776字节

借助ASCII代码，用户就可以将文本输入计算机。我们打出一个字母数字的字符时，计算机就把它转换为一个字节的数据，即长度为8比特的一串数字。比如，我们打出字母“A”，计算机就把它转为“0100 0001”。

二进制ASCII数值表表示所有常用的字符——26个大写字母、26个小写字母、10个数字、7个标点符号和一些特殊字符。所有字符见后页表，表分字符、二进制数字、十进制数字三列：

（续表）

用BASIC编程语言输入短语“GOTO 2”时，计算机就会把这些字符翻译为相应的二进制序列：

计算机就会按下列序列执行：

010001110100111101010100010011110010000000110010

十六进制

十六进制是计算机使用的另外一种常用编码。它是一种数字系统，使用16个特殊的数位，因此叫十六进制，区别于常用的十进制系统。可以说十六进制是仅次于二进制的第二大计算机语言。为何是16数位系统呢？还记得计算机的基本运算单位吧，也就是字节，由8比特组成，0和1最多产生2⁸=256种不同的组合。但是2⁸=2⁴×2⁴=16×16，也就是说，两个十六进制数字加起来等于一个字节。

十六进制中的16个数位由传统的0、1、2、3、4、5、6、7、8、9和六个规定好的大写字母——A、B、C、D、E、F组成。用十六进制表示时，如下所示：

从0到15：0、1、2、3、4、5、6、7、8、9、A、B、C、D、E、F。

从16到31：10、11、12、13、14、15、16、17、18、19、1A、1B、1C、1D、1E、1F。

32以后：20、21、22、23、24、25、26、27、28、29、2A、2B、2C……

这些文件都是计算机自动生成的，文件的名字看似奇怪，其实都是十六进制数字。

十六进制数字的字母大小写没有区别（1E与1e相同）。下表是前16个二进制数字和它们对应的十六进制数字：

想要从二进制向十六进制转换，我们需要从右起把所有“比特”（位）分为四个一组，根据上面的表格完成转换。如果二进制数字的位数不是4的倍数，就在左侧补充0。从十六进制向二进制转换时，我们把每个十六进制数字转换为对应的二进制数字。请看下面的例子：

9F2₁₆是十六进制数字（下标“16”表明这个数字是十六进制数字）的形式标志。记住它们对应的二进制数字是：

因此9F2₁₆=100111110010₂（下标“2”表明这个数字是二进制数字）。

现在我们把过程反过来：1110100110₂有十个数位。四个数位一组，最后需要在左侧补充两个0，成为12个数位。

转换为：

1110100110₂=0011 1010 0110₂=3A6₁₆

十六进制字符与ASCII码之间是什么关系呢？每个ASCII码都包括8比特（1字节）的信息，所以5个ASCII字符包含40比特（5字节），而且因为十六进制包含4比特，所以可以说5个ASCII字符就是10个十六进制字符。

举个例子，我们把一个词语用十六进制编码。以名称“NotRealCo Ltd”（非真实有限公司）为例，步骤如下：

1.用标准ASCII码把“NotRealCo Ltd”译为二进制数字。

2.将数字分为四个一组，如果数位的长度不是4的倍数，在左侧补0。

3.参照二进制和十六进制转换表，继续译。

因此，短语“NotRealCo Ltd”用十六进制编码后为：

4E 6F 74 52 65 61 6C 43 6F 20 4C 74 64

数系和基变换

n个数字的数系也可以叫作基n。人类的手有十根手指，这或许是发明十进制的原因，毕竟最原始的计数是用手指头进行的。一个十进制数，如7392代表七千三百九十二个单位。千、百和十，都是基数的乘方，此处是10的乘方，10就是基数。因此，7392可以表示为：

7392=7×10³+3×10²+9×10¹+2×10⁰

但是，此处默许为只写出系数（7、3、9和2）。除了十进制，还有很多数系（实际上有无数种）。在本书中，我们特别讲解两种数系：以2为基数的二进制和以16为基数的十六进制。在二进制中，系数只有两个数值：0和1。二进制数字是2的乘方的系数。因此，数字11011₂也可以写为：

11011₂=1×2⁴+1×2³+0×2²+1×2¹+1×2⁰

如果计算等号右边，得到的结果是27，就是二进制数11011的十进制表达。过程反过来，我们把十进制数接连除以2（二进制的基数），把余数记下来，直到得到的系数为1。二进制数最后的系数就是它的第一个数位，后面是从后往前的所有余数。为了方便读者理解，我们把数字76转换成二进制，过程如下：

76÷2=38……0

38÷2=19……0

19÷2=9……1

9÷2=4……1

4÷2=2……0

2÷2=1……0

因此，数字76的二进制表达为1001100₂。这个结果大家可以在前面的ASCII表格中确认（别忘了，在对应的代码的前面，我们需要补充0，使其长度成为四个数位的倍数，所以最终结果为“01001100₂”）。把一个数系的数字转换为其他数系的过程叫作基变换。

检测传输错误的代码

因为有了上述代码，计算机与计算机之间、程序与程序之间以及用户与用户之间的有效保密通信成为可能。但这种线上语言是以信息的统一理论为基础的，理论本身就以通信过程为基础。制定这个理论的第一步如此基础，有时容易被忽视，那就是如何度量信息。

像“2kB attachment”这样简单的短语是基于一系列聪明的直觉，这些直觉都始于1948年美国工程师克劳德·香农（Claude E. Shannon）在《贝尔系统技术杂志》上发表的一篇题为“通信的数学原理”的文章，之后，他的灵感一个接一个涌出。这篇文章影响巨大，香农在文中提出，度量信息大小的单位叫作比特。引领香农走向研究之路的一般问题，对于现代读者来说并不陌生。加密信息以防止在传输过程中损坏的最佳方法是什么？香农得出结论：不可能编出一套总能避免信息丢失的代码。换句话说，只要有信息传递，错误就不可避免。不过，这个结论并没有中断编码标准的确立，即便不能防止信息被损毁，但至少能保证具有最高的可靠性。

在信息的数字传输中，信息一旦经由发送者产生（由非人类，如计算机或其他设备代理此事简单易行），则该信息用二进制加密，进入收发双方各自的计算机以及连接本身在内的通信通道——可以是有线，也可以是无线（如无线电波、红外波等）。通道中的传输过程最为敏感，因为信息会受到各种干涉，包括与其他信号混杂、物理媒介温度的不利影响、在媒介中传播时信号减弱等。人们把这些干涉的源头称为“干扰”（noise）。

为了使干扰影响最小化，不仅需要保护连接线路，还必须创建一种探测并纠正错误的方法。

其中一种方法叫作“冗余”——按照规定的标准，重复信息的某些特点。为厘清这个过程，请看下面这个例子。想象存在一份文本，其中每个单词都由4比特构成，总单词数为16（2⁴=16），每个单词的样式均为（a₁ a₂ a₃ a₄）。在发送信息之前，我们在单词上添加3个多余的比特（c₁ c₂ c₃），这样通过通信通道的编码信息形式为（a₁ a₂ a₃ a₄ c₁ c₂ c₃）。c₁ c₂ c₃会确保信息的安全——被称为“奇偶检验码”——其产生如下所示：

我们把下列奇偶检验码指定给信息0111：

因为0+1+1=2为偶数，所以数字c₁=0

因为0+1+1=2为偶数，所以数字c₂=0

因为1+1+1=3为奇数，所以数字c₃=1

结果，信息0111发送时为0111001。下列16个“单词”发送版如下表所示：

未获奖的天才

克劳德·香农（1916—2001）是20世纪最伟大的科学家之一。他曾就读于密歇根大学和麻省理工学院，专业是电气工程，后以数学家的身份在贝尔实验室工作，研究密码学和通信理论。他对信息论的贡献足以让他位列发明家名录的前茅，但由于他的研究介于数学和信息论之间，因此与所有科学家梦寐以求的诺贝尔奖失之交臂。

假设在传输的末端，即接收系统收到的信息是1010110。注意，如果这个二进制数字避开了所有可能的信息，那就必然出现了传输错误。若要纠正这个错误，将系统使用所有可能信息的数字与接收信息的每个数字进行比较，查找可能性较高的选择。为此，它检查了数字可能出现错误的数量，具体如下页表所示：

错误的1010110与1000110只有一个数字之差。鉴于这个误差最小，系统会给接收者提供第二个，也就是纠正后的版本。这个原理类似于文字处理软件中的“拼写检查”，一旦检查到一个词语与它的内部词典不符，就会给出一些接近的选项。人们把信息看作字符序列，一条信息区别于另一条信息的位置数叫作“两个序列之间的距离”。这个误差检测和误差校正的具体机制是与克劳德·香农同时代的美国人理查德·W.海明（Richard W. Hamming，1915-1998）提出的。

如同在其他领域一样，在信息领域检测可能的错误是一回事，而校正这些错误又是另一回事。在加密中，比如上一个例子，如果最小距离只有一个备选，那问题就简单多了。如果我们把1出现在序列中最小次数定为t（数列全为0的情况除外），可以确定：

假如t为奇数，可以校正的错误

假如t为偶数，可以校正的错误

如果我们只是检测错误，那么能够检测到的最小数量为t-1。前面我们已经详述过十六进制的语言，如果t=3，那么这个机制就能检测出3-1=2个错误，并纠正(3-1):2=1个错误。

第三代加密术

1997年，为使无线网络信息安全传输，引入了名为WEP（有线等效保密）的协议。此协议包括名为RC4的加密算法，它有两种编码方式，各由5个和13个ASCII字符构成。因此，我们也可以说编码由40或104比特构成，或者由10或26个十六进制字符构成：

5个字母或数字的字符=40比特=10个十六进制字符

13个字母或数字的字符=104比特=26个十六进制字符

连接提供者提供编码，但用户一般可以更改。建立连接之前，计算机会请求密钥。下页对话框中，可以看到弹出一条错误信息，请求WEP密钥，明确说明了比特、ASCII字符及十六进制字符的长度：

实际上，真正的密钥还要更长。从用户提供的密钥开始，RC4算法产生更多比特的新密钥，而这个密钥是用来加密传输的。这是一种公钥密码学，在本书第五章中会有详细解释。想更改密钥的用户会发现，相比5个字母或数字字符的密钥，记忆10个十六进制字符的密钥保密性更高，且更好记，虽然两者比特大小相同。当然，同样确定的是，“james”与它对应的十六进制表达“6A616D6573”相比，也更方便识记。

其他代码：工业和商业标准

与加密术或二进制数学相比，银行、超市及其他大型商业机构的标准代码虽然逊色不少，而且，虽然它们无处不在，却常被人们忽视。不过其的确是支撑现代社会的支柱之一。说到这些代码，其首要作用是保证诸如银行卡、书籍或苹果等产品身份的独一无二和精确性。下面我们来详细探讨这些代码。

信用卡

大型银行会为顾客办理借记卡或信用卡，卡主要通过设定好的数字集合来识别，并用同样的算法和验证系统进行计算，这一切都基于我们的老朋友：模运算。大部分卡片上都有16位数字，由0到9十个数字组成。这些数字每四位分为一组，方便读取。为了方便讲解，我们用ABCD EFGH IJKL MNOP表示卡号。

每组数字都代表某些信息：第一组（ABCD）表示银行身份信息（或任何提供服务的机构）。每家银行的ID号码都不一样，根据大洲的不同而不同，同样也与银行卡的商标和条件相关。以维萨（VISA）和某些大银行为例，前四个数字如下所示：

第五个数字（E）代表卡片类型，表示管理该账户的金融机构：

可以看出，这并不是一条铁则，维萨和万事达卡都可以用“0”代表。

其余10个数字（FGH IJKL MNO）是每张卡独一无二的标识符。这个身份信息不仅提供每个客户账号的参考号码，还与这张卡的品牌设计（经典卡、金卡、铂金卡等）、相关信用额度、结算类型的利率以及截止时间相关。

最后还有一个控制数字（P），根据卢恩算法［由德国工程师汉斯·彼得·卢恩（Hans Peter Luhn）开发，并以他的名字命名］，它与之前的数字相关。对于16位数字的银行卡，卢恩算法如下所示：

（1）从左边第一个数开始，每个奇数位上的数字乘以2，计算出一个新数字。如果结果大于9，就把个位和十位上的数字再次相加（或减去9，两种方式会得到相同的结果）。比如，假如结果为18，则1+8=9，或18-9=9。

（2）我们把所有结果加起来计算得出一个和，同时计算得出卡号中偶数位数字（包括最后的控制数字）的和，最后把得出的两个结果加在一起。

（3）如果总数为10的倍数（也就是说，它对于模10为0），那么卡上的数字则是有效的。注意，是最后一位的控制数字使得最终结果为10的倍数。

大来信用卡

大来信用卡是第一批获得广泛认可的信用卡之一。它是由美国人弗兰克·麦克纳马拉（Frank McNamara）创立的。1950年，他努力说服几家饭店接受信用卡支付，这种信用卡是麦克纳马拉给他的最佳客户量身定做的担保卡。最初十几年中，信用卡最常见的用途是给美国旅行推销员支付旅途中的餐费。

以下列卡号为例：

1234 5678 9012 3452

根据卢恩算法：

1×2=2

3×2=6

5×2=10=>1+0=1

7×2=14=>1+4=5（或14-9=5）

9×2=18=>1+8=9

1×2=2

3×2=6

5×2=10=>1+0=1

2+6+1+5+9+2+6+1=32

2+4+6+8+0+2+4+2=28

32+28=60

结果是60，是10的倍数。因此，这张卡的号码是有效的。

还有另一种运用卢恩算法的方法：如果奇数位数字之和的两倍加偶数位数字之和再加卡号中奇数位上的数值大于4的数字的个数，总和是10的倍数，那么卡号ABCD EFGH IJKLMNOP则为正确。说这么多，不如用公式来表达，即2(A+C+E+G+I+K+M+O)+(B+D+F+H+J+L+N+P)+卡号中奇数位上的数值大于4的数字的个数≡0(mod.10)。

计算信用卡号中控制数字的Excel应用

信用卡包括15位数加一个控制数字。卡号四个一组，共分四组。控制数字（简写为C.D.）按照以下算法计算：

还是之前的例子，运用第二种算法：

1234 5678 9012 3452

2×(1+3+5+7+9+1+3+5)+(2+4+6+8+0+2+4+2)+4

=100≡0(mod.10)

我们再一次证明这张卡的卡号有效，同时证明了看似随机的银行卡代码其实遵循严格的数学标准。

如果卡号中的一位数字遗失了，能否找回来呢？只要这张卡是有效卡，是可以找回来的。让我们来找回4539 4512 03X8 7356中的X。

奇数位的每个数字（4、3、4、1、0、X、7、5）乘以2，将它们变为个位数。

4×2=8

3×2=6

4×2=8

1×2=2

0×2=0

X2=2X

7×2=14，14-9=5

5×2=10，10-9=1

把偶数位的数字之和和上述奇数位计算出的结果之和相加：

30+41+2X=71+2X

我们知道，结果一定是10的倍数。

如果X大于4（且小于10），则2X是介于10与18之间的数字。把2X变为个位数：2X-9，因此之前的总和为71+2X-9。如果结果为10的倍数，那么X只有一个值，也就是9；反之，如果X小于或等于4，71+2X不可能为10的倍数。

因此，遗失的数字是9，这张信用卡的完整卡号为：4539 4512 0398 7356。

条形码

1952年10月7日，美国人诺曼·伍德兰德（Norman Woodland）和伯纳德·西尔弗（Bernard Silver）申请了第一个条形码系统的专利。早期的条形码与今天差异很大。伍德兰德和西尔弗用的不是我们熟悉的条形码，而是同心圆。1974年，俄亥俄州特洛伊市的一家商店首次正式使用条形码。

现代条形码由一系列黑条（二进制系统中编码为1）和黑条之间的空白（编码为0）构成。条形码被用来识别物体。一般条形码印在标签上，由光学设备读取。这种设备类似于扫描器，测量反射光，然后将明暗条纹转换为字母数字的密钥，再发送给计算机。条形码的标准有很多：编码128、编码39、库德巴码、EAN码（出现于1976年，有8数位和13数位两种）和UPC（通用产品编码，主要在美国使用，有12数位和8数位两种）。最常用的是13数位的标准版EAN码。虽然标准有很多，但条形码可快速识别世界各地的产品，且没有很大的误差。

条形码中，条和空白的宽度与二进制数字对应。

EAN-13条形码

现代条形码出现之前，伍德兰德和西尔弗申请的同心圆专利体系。

计算EAN-13条形码控制数字的Excel应用

EAN-13条形码由12位数字和1个控制数字（C.D.）组成。13位数分为四组：

算法包括以下步骤：

使用Excel，算法的写法如下：

1976年，EAN条形码创立，最初EAN是“欧洲商品编号”（European Article Number）的缩略语，现在是“国际商品编号”（International Article Number）的代称。它是接受度最高的条形码标准，全世界通用。EAN条形码通常包括13位数，用黑条和空白表示，同时还包括二进制代码，方便读取。EAN-13条形码用30个黑条和空白表示这13位数。数字分为三部分：第一部分，包括两个或三个数字，是国家代码；第二部分，包括九个或十个数字，代表公司和产品；第三部分，只有一个数字，就是控制数字。以代码ABCDEFGHIJKLM为例，可以按如下方式分为：

·前两位（AB）是构成产品的原产地代码。

·接下来的五位（CDEFG）代表生产产品的公司。

·再后五位（HIJKL）是产品代码，由生产公司赋值。

·最后一位（M）是控制数字。若要计算控制数字，必须从左开始，将奇数位的数字相加，控制数字不包括在内。然后将偶数位数字之和乘以3，两个结果相加。最后用大于此结果的最小的10倍数减去此结果，就是控制数字的值。可以看出，条形码控制体系与前面信用卡中应用的控制体系相当接近。

下面我们来验证一下这个条形码是否有效：

8413871003049

8+1+8+1+0+0+3(4+3+7+0+3+4)=18+3(21)=18+63=81

正确的控制数字应为90-81=9。

这个算法的数学模型基于模运算(mod.10)，如下所示：

编码ABCDEFGHIJKLM，我们用N表示结果

A+C+E+G+I+K+3(B+D+F+H+J+L)=N

n是N关于模10的数值。控制数字M的表达公式为：M=10-n。此例中，我们得出81≡1(mod.10)，因此控制数字其实是10-1=9。

之前的算法可以使用计算中的控制数字，同样也能表达出来。下面这个方法，能使我们在不需要首先计算控制数字的前提下验证它是否有效：

A+C+E+G+I+K+3(B+D+F+H+J+L)+M≡0(mod.10)

以下面这个代码为例：

5701263900544

5+0+2+3+0+5+3(7+1+6+9+0+4)+4=100

100≡0(mod.10)

因此，此代码有效。

出于好奇心，我们会试着求出条形码中丢失的数字。以下面的代码为例，用X表示丢失的数字：

401332003X497

根据算法，我们列出这个公式：

4+1+3+0+3+4+3(0+3+2+0+X+9)+7=64+3X≡0(mod.10)

对于模10，我们得到下列方程：

4+3X≡0(mod.10)

3X≡-4+0≡-4+10·1=6(mod.10)

注意3有倒数，因为gcd(3,10)=1。

因此，我们得出，X必须为2，有效代码是：

4013320032497

二维码

1994年，日本Denso-Wave公司开发了一种图形加密系统，用以验证装配线上汽车的部件是否正确。这种系统通过特制的机械能够快速读取，因此简称QR（quick response，快速反应，也称“二维码”），后来用途日渐广泛，不再局限于汽车工厂。仅仅几年内，日本大多数手机已能快速读取二维码中包含的信息。二维码是一种矩阵代码，由不同数量的黑白方块组成，依次排列成一个更大的方块形状。黑白方块分别代表的是二进制数值0或1，因此，二维码与条形码的操作非常相似，不过由于加入了第二维度，所以二维码的存储容量要大很多。

日本大阪大学的二维码，行列数为37×37。

第五章 公开的秘密：公钥密码学

在计算机技术迅速发展的背后，密码学一直如影随形。使用计算机对信息进行加密的过程与不使用计算机加密一条信息的过程大体上是相同的，但存在三种基本差异。首先，计算机可以通过编程来模仿传统加密机器的运作，比如，不需实际制作设备就可以有1 000个转子。其次，计算机只用二进制数工作，因此，所有加密都处于同一水平（即使数字信息后来再次被译解为文本）。最后，计算机可以快速地加密和译解信息。

20世纪70年代，利用计算机优势设计出来的首批密码横空出世，其中就包括路西法密码。这种密码将文本分为64位的区块，通过复杂替换对部分加密，然后再次分为新的64位加密区块，并重复此过程。这套密码系统要求收发双方在计算机上安装同样的加密程序，并共享一个数字密钥。1976年，名为DES的56位路西法密码出现。DES是“数据加密标准”（Data Encryption Standard）的缩写，虽然在1999年曾被破解，但今天仍在使用，2002年被大幅替换为128位AES（高级加密标准）密码。

无疑，这种加密法将计算机的处理能力推向顶端，但与它们1 000多年前的祖先一样，如果未授权的接收者获取了密码，那么他在知道加密算法的情况下就可以解译信息，使得计算机加密依然脆弱。每个“经典”的加密系统都有基本的薄弱点，人们称之为“密钥分配问题”。

密钥分配问题

人们普遍认同，为维护密码的安全性，保护密钥应先于保护算法。那么问题就产生了：如何分配密钥才安全？即便是最简单易用的加密方式，大规模使用时也会出现问题，比如如何在庞大的军队中分派数千本密码本，或者如何把它们分派给处于极端条件下（比如在深海执行秘密任务或与敌方激战正酣）的部队。经典加密系统无论有多精密，它们的密钥都易被截取。

迪菲-赫尔曼密钥交换算法

安全地交换密钥，这种说法听起来就自相矛盾：你如何把密钥作为一份已经加密的信息发送，而密钥先前就已经按常规方法交换过了？不过，如果交换方式为复式通信交换，那么大家就可以想象出解决问题的方法了——至少在理论层面是行得通的。

算法背后的人

1944年，贝利·惠特菲尔德·迪菲(Bailey Whitfield Diffie)生于美国。于麻省理工学院取得数学学位后，他2002年至2009年间在总部位于加利福尼亚的太阳微系统公司工作，担任首席安全官和副总裁。马丁·赫尔曼（Martin Hellmann）是工程师，出生于1945年，曾在IBM和麻省理工学院工作，在麻省理工学院期间，他与迪菲开始合作。

现在我们假设发送者叫詹姆斯（James），他用密钥加密了一条信息，并发送给接收者彼得（Peter）。彼得用自己的密钥把加密信息再次加密后，发回给詹姆斯。詹姆斯用他的密钥译解信息后发送了这份新信息，此时只有彼得的密钥能够译解。如此一来，多年来安全交换密钥的问题突然一下就解决了。这真的行得通吗？可惜不行。对于任何复杂的加密算法来说，密钥应用的顺序都很严格，我们已经发现，在上述理论的例子中，詹姆斯必须译解一条已经用另外一个密钥加密过的信息，如果他不先用彼得的密钥再用自己的密钥译解，那结果自然是乱码。上述情形虽然不能解决密钥安全的问题，但却是解决这个问题的一盏明灯。1976年，两个年轻的美国科学家贝利·惠特菲尔德·迪菲和马丁·赫尔曼发现一个方法，让两个人在不必交换任何密钥的前提下交换加密信息。这种方法运用了模运算和质数的性质。方法如下：

1.詹姆斯选取一个保密数字，我们把它设为NJ1。

2.彼得随机选取另一个保密数字，我们把它设为NP1。

3.然后，詹姆斯和彼得各自把数字套入函数公式f(x)=axmod.p，p为质数，且二人都知道是什么。

·通过方程运算，詹姆斯得出一个新数字NJ2，并将其发送给彼得。

·同样，彼得也得出一个新数字NP2，并将其发送给詹姆斯。

4.詹姆斯解出方程(mod.p)，得出新数字CJ。

5.彼得解出方程(mod.p)，得出新数字CP。

虽然看似不可能，但CJ和CP是相同的，由此我们求出了密钥。注意，詹姆斯和彼得交换信息的前提是两人商定好使用函数方程f(x)=axmod.p，并给对方发送NJ2和NP2。这样一来，无论是密钥还是信息被截取，都不会对加密系统的安全构成威胁。这种系统的密钥通常是这种形式：

同样重要的还有一点，就是要考虑原函数具有不可逆的特点，也就是说，即便知道函数以及运用到变量x上的结果，也不可能（至少很难）获取原变量x。

下面，为了强调重点，我们用具体的数值再讲一下这个过程。应用的函数是：

f(x)≡7x(mod.11)

1.詹姆斯选取一个数字NJ1，以3为例，计算f(x)≡7x(mod.11)，得出f(3)=7³≡2 (mod.11)。

2.彼得选取一个数字NP1，以6为例，计算f(x)≡7x(mod.11)，得出f(6)=7⁶≡4(mod.11)。

3.詹姆斯将结果2发给彼得，同样，彼得把结果4发给詹姆斯。

4.詹姆斯计算4³≡9(mod.11)。

5.彼得计算2⁶≡9(mod.11)。

因此，9就是密钥。

詹姆斯和彼得已经交换的是函数f(x)和数字2、4。对于窃听者来说，这条信息有用吗？假设未授权的接收者知道方程和数字。他的问题是要解决关于模11的NJ1和NP1，NJ1和NP1是詹姆斯和彼得的保密数字——甚至两人也互相保密。如果间谍试图发现它们，他只有求解关于模p的密钥。顺便说一句，解决这个问题在数学上叫作“离散对数”。举个例子：

f(x)≡3x(mod.17)

可以发现3x≡15(mod.17)，再试试x的其他值，求得x=6。

直至20世纪90年代初，这种算法和离散对数的问题才备受重视，而且直到近些年，才得以发展完善。在上述例子中，我们说6是15以3为底、对模17的离散对数。

前面已经提过，这种方程的特别之处，就是很难进行逆向计算——它们是非对称的。因此，对于大于300的p和大于100的a，破解密钥难度相当大。

病毒和“后门”

即便是最安全的公钥加密也依赖于保密的私钥。因此，如果病毒侵入并常驻在计算机内，还传输私钥，就能大规模地破坏加密系统。1998年，人们发现瑞士一家生产和销售加密产品的龙头公司在产品中嵌入了“后门”，能够检测用户的私钥并将数据发回公司。这些信息有一部分被移交给了美国政府，从而使其能够监控遭病毒感染的计算机之间的通信。

这种算法是现代加密术的基础。美国全国计算机会议期间，迪菲和赫尔曼在一次研讨会上提交了一篇名为“密码学的新方向”的论文，将他们的想法呈现给世人，开创了一个密码学的新时代。

迪菲-赫尔曼算法证明了创建一个不需要交换密钥的加密方法的可能性，但矛盾的是，该过程的一部分却要依靠公开通信——借此来传播确定密钥的初始数字对。

换句话说，它使得安全加密系统的收发双方无须会面，也无须私底下达成密钥。不过，还是存在某些问题：如果詹姆斯想给彼得发送信息，而此时彼得正在睡觉，或在干别的，那詹姆斯就必须得等彼得醒后计算出密钥，才能完成传输。

在尝试发现更有效的新算法的过程中，迪菲建立了一套理论，其中加密密钥不同于译解密钥，这样，两个密钥决不可能根据对方推导出来。在这个理论体系中，发送者有两个密钥：加密密钥和译解密钥。两个密钥中，发送者只能公开第一个，这样无论谁想给他发送信息，都能根据密钥加密。收到信息后，发送者使用译解密钥译解信息，而此时，很明显，译解密钥依然是保密的。这样的加密系统实用吗？

前来拯救的主力军：RSA算法

1977年8月，美国著名科学作家马丁·加德纳（MartinGardner）在《科学美国人》杂志的趣味数学专栏中发表了一篇文章，题目是“一种需数百万年才能破解的新型密码”。文中，他首先解释了公钥系统的原理，然后列出了加密信息以及用来创建该密码的公钥N：

N= 114.381.625.757.888.867.669.235.779.976.146. 612.010.218.296.721.242.362.562.561.842.935.706.935.245.733. 897.830.597.123.563.958.705.058.989.075.147.599.290.026.879.543.541

加德纳向他的读者发起挑战，甚至还提供了一条线索——要想破解，需要把N分解为它的主要组件p和q。当时，李维斯特、沙米尔和阿德尔曼预测，需要40万亿年的时间才能知道RSA-129。除此之外，加德纳还承诺，谁先解答出正确答案，就奖励他100美元（在当时算是一笔巨款了）。加德纳提出，如果有人想了解密码的更多信息，可以写信咨询密码的创始人、麻省理工实验室的罗恩·李维斯特、阿迪·沙米尔和伦恩·阿德尔曼。

一晃17年过去了，加德纳才收到正确答案，而且是600多人合作才求出来的。求出的密钥是p=32.769.132.993.266.709.549.961.988.190.834.461.413.177.642.967.992. 942.539.798.288.533和q=3.490.529.510.847.650.949.147.849.619.903.898.133.417.764.638.493.387.843.990.820.577，加密的信息是“Themagic words are squeamish ossifrage”（咒语是易受惊的鱼鹰）。

人们把加德纳提出的算法称为RSA算法，RSA是李维斯特、沙米尔和阿德尔曼三人姓氏的首字母。这是迪菲假定提出的公钥模型的第一例实际应用，今天人们仍经常使用。RSA几乎可以说是完全安全的，原因就在于解译过程虽说不无可能，但也绝对是难于登天一般。下面，我们简单了解一下这个系统的基础。

RSA算法的详细步骤

RSA算法基于质数的某种特性，有兴趣的读者可以参考附录。此处限于篇幅，我们只介绍它背后的基本假设：

·小于n并与n互为质数的数的数目叫作欧拉函数，用φ(n)表示。

·假设p和q是质数，且n=pq，则φ(n)=(p-1)(q-1)。

·根据费马小定理，如果p是质数，a是pn［即如果gcd(a,p)=1］的整数倍数，则满足方程ap⁻¹≡1(mod.p)。

·根据欧拉定理，如果gcd(n,a)=1，则aφ(n)≡1(mod.1)。

上面提到，任何人只要有兴趣传输信息，都可以拿到加密密钥，因此人们把这套系统称为“公钥”。每个接收者都有自己的公钥。信息通常译为数字，如ASCII密码或其他系统，然后发送。

首先，詹姆斯根据两个质数p和q的乘积得到n（n=p·q），我们给e选择一个数值，满足gcd(φ(n) , e)=1。记住φ(n)=(p-1)(q-1)。公开的数据是n和e的值（任何情况下都不公开p和q）。(n,e)就是该系统的公钥，而p和q被称为RSA数字。同样，詹姆斯计算出d对于模φ(n)的唯一值，满足d·e≡1(mod.φ(n))，就是e对于模φ(n)的倒数。我们知道，倒数之所以存在，是因为gcd(φ(n),e)=1。这个值是该系统的私钥。彼得用公钥（n,e）通过M≡me(mod.n)加密信息m。收到信息后，詹姆斯进行Md≡(me)d(mod.n)的运算，这个表达式等于Md=(me)d≡m(mod.n)，证明信息能被解译。

现在我们用具体的数值重复这个过程：

·如果p=3，q=11，则n=33。φ(33)=(3-1)·(11-1)=20。詹姆斯选择e的数值与20没有公约数，如e=7。詹姆斯的公钥是（33,7）。

·同时，詹姆斯已经计算出私钥d是7对模20的倒数，也就是7·3≡1 (mod.20)，因此d =3。

·彼得获取了公钥，想给我们发送信息“9”。他用詹姆斯的公钥给信息加密，即：

9⁷=4 782 969≡15(mod.33)

·加密后的信息是15。在公共领域发出“15”这条信息。

·詹姆斯收到信息15，并开始译解它：

15³=3 375≡9(mod.33)

最终信息被正确译解。

如果选择较大的质数p、q，应用RSA算法的难度系数就会暴增，此时就得求助计算机了。比如，如果p=23、q=17，则n=391。对e=3的公钥是（391,3）。结果是：d=235。如果明文信息是34，那么译解运算公式为：

204²³⁵≡34(mod.391)

请注意这个数量级，并想象找到这个解决方案所需的巨大计算能力。

我们为什么能信赖RSA算法？

间谍知道n和e的值，因为它们是公开的。但要译解信息，他还需要d的值，也就是私钥。在前面的例子中，我们展示了根据n和e计算得出d的过程。那么安全性从何而来呢？回忆一下，要想求得d，就必须知道φ(n)=(p-1)(q-1)，尤其p和q。为此，把n作为两个质数p和q的乘积分解就够了。间谍面临的问题是，两个质数的乘积很大，分解起来费时又费力。如果n足够大（大约有100多个数位），那么在一定时间内就没法求出p和q。今天，用来加密信息的质数，难度最大的已经超过了200个数位。

合情合理的隐私

RSA算法消耗大量的计算时间，需要高性能处理器。20世纪80年代之前，只有政府、军队和大型企业拥有能够运算RSA的高性能计算机，结果它们垄断了有效的加密术。1991年夏季，美国物理学家，同时也是倡导隐私保护的积极分子——菲利普·齐默尔曼（Philip Zimmermann）免费开放了PGP（Pretty Good Privacy，良好隐私）系统，它是一种在家用电脑上就能计算的加密算法。PGP用的是经典对称编码——在家用电脑上可以提高运算速度——但加密用的却是非对称RSA密钥。

齐默尔曼写了一封公开信解释这一做法，在这儿我们应该重温一下，至少重温一部分，因为这些内容预言了20多年后人们的生活、工作和交流的方式：

这是私人的，这是隐私的，与别人无关，但与你自己有关。或许你在筹划一次政治竞选、讨论税务问题或者不想为人所知的浪漫情话。又或许你在做一些自己感觉并不违法，但其实是违法的事。无论怎样，你都不想让自己的私人电子邮件或保密文件被他人偷窥。总之，维护自己的隐私是没错的，隐私就像《宪法》一样理所应当得到保护。

面向所有人的加密技术

菲利普·齐默尔曼出生于1954年，是美国物理学家和软件工程师，曾倡导人人都能享用现代加密技术的运动。除了推出PGP系统，他还在2006年创建了Zfone，Zfone是通过互联网进行安全音频通信的软件程序。同时，他也是开放PGP联盟的总裁，该联盟是主张开放代码软件的游说组织。

我们正朝着未来迈进，那时美国大地上将遍布大容量的光纤数据网络，把日益随处可见的个人电脑连接起来。今天电子邮件还是个新奇事物，而到那时将人人都用，很普遍。政府会用官方设计的加密协议保护人们的电子邮件。或许多数人会默许同意，但或许有人更愿意用自己的保密方法……如果保护隐私是犯罪的话，那世上就只有罪犯有隐私了。

情报机构有权限使用优良的加密技术，大型机构和毒枭也可以，还有国防承包商、石油公司以及其他企业巨头。但对于大多数平民百姓和基层政治组织来说，其负担不起军事级别的公钥加密技术。不过，现在可以了。

PGP让人们的隐私自由掌握在自己手中，社会对它的需求也在逐渐增加。这也是我在本书中提到它的原因。

从齐默尔曼的想法中，我们可以看出，信息时代的生存代价就是我们传统的关于隐私的观念受到了威胁。因此，对围绕在我们身边的编码和加密机制有很好的理解，不仅能让我们更加明智，今后在保护我们的宝贵东西时，也会有很大的实用价值。

PGP自诞生以来，用户就在不断增加，而且它是当今可用的最重要的个人加密工具。

信息和密钥的验证

不同的公钥加密系统——或如PGP这样公钥和私钥的融合——确保信息传递具有较高的机密性。但是，像互联网这样的复杂通信系统，其安全就不仅仅在于机密性一条。

早在现代通信技术出现之前，大多数情况下，我们都是从认识的人那里获取信息，比如家人、朋友或因工作认识的人。但在今天，每个人面前都有多如牛毛的信息来源。仅仅通过阅读验证这些信息的真实性是不可能的，所有问题也因此而产生。比如，如何阻止某些人伪造电子邮件的源地址？

迪菲和赫尔曼提出了一种独创性的方法，使用公钥加密来确定信息来源。在这种加密系统中，发送者用接收者的公钥加密一条信息，接收者再用自己的私钥解译这条信息。迪菲和赫尔曼发现，RSA和其他类似的算法都体现出对称性。这一点很有意思，也就是说私钥也能用来加密信息，公钥也能用来解译信息。这种操作一点安全性都没有——所有人都能轻易获取公钥——但它能明确发送者的身份，也就是私钥的所有者。验证一条信息发送者的身份，从理论上说，在正常的加密过程中再添加一条就够了，步骤如下：

第一步，发送者用接收者的公钥加密一条信息。第一步确保机密性。

第二步，发送者再次加密信息，这次用的是私钥。这样，信息就已认证或“签名”了。

第三步，接收者用发送者的公钥撤销第二步的加密。这样就验证了信息源。

第四步，现在接收者再用私钥撤销第一步的加密。

哈希函数

从理论框架来看上述问题，其中一个问题是公钥加密需要大量的计算能力，而且重复验证每条信息同样耗费大量的时间。这就是在实际运用中，信息的签名是用数学资源执行的原因，这种数学资源叫作“哈希函数”。从原始信息开始，这些算法就产生一个简单的“比特链”（通常是160位）——“哈希”，运算时，不同信息与相同哈希产生关联的概率几乎为零。同样，实际上也不可能撤销过程和仅从它的哈希开始获取原始信息。任何信息的哈希都是由发送者用其私钥加密的，而且私钥的发送用的也是传统方法，即与加密信息一起发送。接收者解码包含哈希和发送者公钥的信息。接下来，如果他知道发送者使用的哈希函数，就把此函数应用在信息上，并对比两组哈希。如果匹配，发送者的身份就得到了验证，而且还能确认一点，没有人动过原始信息。

信息内容发生微小的变化，就会产生完全不同的“哈希”，这样，接收者就能确定文本有没有被人动过手脚。

公钥证书

然而，人们发现，公钥加密系统中最重要的问题不是信息的验证，而是公钥本身。收发双方如何知道对方的公钥是有效的？假设间谍从发送者那儿骗取公钥，同时让他相信这就是接收者的密钥，成功截获了信息后，间谍就可以用他的私钥破译信息了。为了不被发现，间谍使用接收者的公钥重新译解信息，并发送至初始目的地。

数字密写

新技术的发展催生了隐写术的复兴，这貌似有点矛盾。常见的音频文件由以44.1kHz复制的16位（比特）构成。信息发送者很容易用16位中的一部分传递秘密信息，而让收听者又完全察觉不出。另外，图像文件也可以用来传递隐藏信息。

数字密写举例：π数值的四个小数位以小碎片的形式隐藏在大图像中。左图看起来很正常，右图的部分像素中隐藏着数字3.1415。

这就是为什么有些公共的和私人的机构致力于独立验证公钥。除了相应密钥，证书中还包含接收者信息和截止时间。这类密钥的持有者都公开他们的证书，此时可以应用和交换，具有一定的安全性。

在互联网上购物到底安不安全？

大多数网上间谍和黑客对于普通大众交流的信息没什么兴趣，但有个例外，那就是信用卡号。能够保护像这类敏感信息块（用信息科学术语说是“信息层”）传递的密码系统叫作TLS（“传输层安全”）。它是由美国网景公司于1994年开发的，两年后被采纳为全球标准。

TLS协议包括公钥和对称密钥，加密过程相当复杂，此处只做简要介绍。首先，网上买家的浏览器验证网上卖家是否具有有效的公钥证书。如果有，就用这个公钥译解第二个密钥，这个是对称密钥，并将其发给卖家。卖家用他的私钥解译信息得到对称密钥，而这个密钥可以用来加密所有正在处理的信息。这样一来，要想获取网上交易中的信用卡号，必须得破解两个加密系统，而不是一个，大大提高了网上交易的安全性。

第六章 量子化的未来

根据菲利普·齐默尔曼在西蒙·辛格（Simen Singh）的《密码故事》（The Code Book）中的说法，“在现代密码学中，有可能创造出所有密码分析手段都破解不了的密码”。前面我们说过，即便是性能最强大的计算机，其计算能力也无法暴力破解像RSA或DES那样的加密算法，甚至连PGP那样的混合加密系统也不太可能被暴力破解。那么有没有可能存在某种数学捷径，能够降低密码破解的复杂性呢？虽然不能完全否认这种可能性，但也没人特别看好这种可能。

齐默尔曼说的话对吗？加密者和解密者之间持续1 000多年的爱恨对决已经结束了吗？

量子计算

答案是不一定。在20世纪的最后10年中，量子计算机，这种在设计和操作方式上发生了革命性改变的计算机横空出世。尽管目前仍处于理论阶段，但经过不断摸索，量子计算机的计算能力有希望破解今天的加密算法。有朝一日，密码分析学会重回竞技场。

尼尔斯·玻尔（左）和马克斯·普朗克，量子力学的两位奠基人，照片摄于1930年。

这场刚刚萌芽的技术革命基于量子力学。量子力学是20世纪初，由包括丹麦人尼尔斯·玻尔（1885-1962）、英国人保罗·狄拉克（1902-1984）、德国人马克斯·普朗克（1858-1947）、维恩·海森伯（1901-1976）和埃尔文·薛定谔（1887-1961）在内的诸多科学家构建的一座理论大厦。量子力学提出的宇宙观违反常识，爱因斯坦持反对态度，曾因此说过一句名言：“上帝不掷骰子。”与爱因斯坦的保守形成对比的是，量子力学理论已经被成功验证了无数次，现在，它的正确性已毋庸置疑。整个科学界认为，从宏观层面上——由恒星、建筑、分子组成的宇宙——宇宙遵循经典物理学的规律。但是在量子世界——由夸克、光子、电子等亚原子粒子组成的小到不能再小的王国——则需要另外一套规则，通向令人惊奇的悖论。没有量子理论，就不会有核反应堆，不会有激光扫码器，也无法解释太阳的灿烂光辉或者DNA的功能。

既死又活的猫

1958年，在量子力学的研讨会上，玻尔就一位发言人的观点提出了以下见解：“我们都同意他的理论是疯狂的，但在关于这个理论正确与否的问题上，我们分成了两个阵营，无论它有多疯狂，都有50%的概率是对的。”量子力学到底有多疯狂？举个例子，就拿状态叠加的原理来说。当一个粒子同时占据两个以上位置或同时具有不同的能量时，我们就可以说它呈现出一种叠加状态。但当观察者测量这个粒子时，它总是只选择一个位置或具有某个具体的能量。薛定谔设计了一个思想实验，名为“薛定谔的猫”，用以阐释这个明显荒谬的概念。想象一只猫，把它放进一个不透明的密封箱子中，箱子中还放有一个烧瓶，烧瓶内装有有毒气体，通过某种设备把烧瓶和一个放射性粒子连接起来，如果粒子发生衰变，烧瓶就会被打破，放出毒气，猫将中毒而死。但问题是粒子在一定时间内衰变的概率是50%。整套设备，取决于一个粒子的行为，而这个粒子遵循量子物理的规律。

薛定谔的猫是一个思想实验，用以说明量子理论中叠加状态的概念。

假设已经到了既定的时间，猫会是死的还是活的？或者，用量子力学的行话来说，箱子-猫-系统处于什么状态？只有当观察者打开箱子，“观测”了系统的状态，察知粒子是否衰变，之后才能回答这个问题。因此，存在系统的叠加状态：严格来说，猫既不活着也没死去，而是既活又死。

有人认为叠加状态是一种难以置信的假设，但这些人要注意了，令人尊敬的物理学家已经提出了“多世界诠释”。比如，“多世界诠释”理论认为，叠加状态的概念是一种不可证实的论点，而实际上，对于每一个可能的状态，一个粒子都有它可能的位置、能量等；还存在另外一个宇宙，在那里，粒子具有某个具体的状态。换句话说，在一个宇宙中，猫是活的；在另外一个宇宙中，猫是死的。当观察者打开箱子，确定这只猫科动物实际活着时，他在另外一个可能的宇宙中也这样做了，而这两者是一个整体。在另外一个平行宇宙中，有它自己的恒星、行星、火车站和蚂蚁以及这位观察者，他也正看着箱子的内部，满面忧伤，因为那个宇宙中的猫已经被毒死了。多世界诠释的支持者仍不确定这些宇宙彼此会不会相互作用。即便如此，理论说明的是对量子现实为何以这种方式作为行为的诠释，而不是行为本身，这点已经在无数实验中被证实了。

从“比特”到“量子比特”

话说回来，粒子的叠加状态和计算之间有什么关系吗？密码学又跟粒子的叠加状态有什么关系？1984年之前，尚无人思考这两个领域之间的关系。大约那时，英国物理学家大卫·多伊奇（David Deutsch）开始抛出一种革命性的观点：如果计算机不再遵循经典物理学，而是量子力学的定律，它们会是什么样呢？粒子的叠加状态如何促进计算呢？

回想一下，传统的计算机处理信息的最小单位——比特，能够采用对应的数值：0和1。另一方面，量子计算机处理信息的最小单位是粒子，而一个粒子具有两个可能的状态。比如，电子自旋只能有两个方向中的一个——向上或向下——代表数值0（下旋）或1（上旋）。但这个粒子具有神奇的属性，通过叠加的自旋状态，它可以同时表示两个数值。这种信息的新单位叫作“量子比特”，英文写作“qubit”，即“quantumbit”（量子比特）的缩写，这种处理能够打开通往超强计算机的大门。

传统计算机的计算是循序渐进的。下面以32位的数字信息为例。用32位数字，我们可以把从0到4 292 967 295的数字译成密码。传统计算机如果必须在这个范围内查找一个具体的数字，那它必须一点一点地进行。

但量子计算机执行这个任务速度要快得多。请想象，把32个电子放进一个特制的容器，并让它们进入叠加状态。那么，通过应用足够强的电子脉冲改变电子自旋的方向，从上旋变为下旋，这32个电子——量子计算机的量子比特——能够同时表现出所有上旋（1）和下旋（0）的可能组合。这样一来，查找想要的数字，就可以同时执行每一个可能的选择。如果增加量子比特的数量，比如250，同时运算的数量会有大约10⁷⁵个，这个数字比我们宇宙包含的原子数还要多一点。

多伊奇的研究证明，量子计算机从理论上是可能的。终有一天它会成为现实，这是全世界众多高校和科研机构的目标。不过，迄今为止，科学家还未能克服建造一台可行的量子计算机所面临的技术难题。有些专家认为还要花费15~25年的时间，有些专家则怀疑这个想法根本行不通。

21世纪的“终结者”

众所周知，建造一台可行的量子计算机意义重大，不仅意味着密码学的坍塌——如此强大的计算能力服务于任何机构，无论是公共的还是个人的，都会转变世界强国的平衡。研发出这样一种技术，就相当于赢得了这场战役的胜利，能够轻而易举地赢得下一场技术竞争，就像20世纪下半叶的太空和军备竞赛一样。在这个领域处于领先地位具有决定性的作用，把它列为国家安全的最高机密一点也不为过。或许在世界的某个地方有个冷藏的地下隧道，隧道中存在一台量子计算机，它正等待着火力全开，永远改变人类的生活呢。

密码学的末日？

众所周知，量子计算会宣判密码学的死刑，我们以现代加密算法的名角RSA为例。前面提到，任何人想暴力破解RSA密码都必须要成功分解两个非常大的质数的乘积。这个运算过程相当耗时费力，目前尚未发现有数学捷径可走。那么分解RSA密码使用的超大质数，量子计算机能够挑战成功吗？1994年，美国计算机科学家彼得·肖尔（Peter Shor）肯定地回答了这个问题。肖尔设计了一款量子计算机可执行的算法，能够分解无限大的数字，用时比更加强大的传统计算机短许多。

如果这个震撼人心的设备有一天被创造出来，那么肖尔的算法就会把围绕在RSA身边的强大的加密基础设施一片一片地拆掉，而这个星球上最高机密的信息也会在一夜之间大白于天下，当代所有的加密系统会面临同样的命运。用马克·吐温的名言改述一下：关于密码分析已死的报道真实不虚，只不过把日期提前了一些。

永别了，DES，永别吧！

肖尔证明量子计算机能够终结RSA密码，两年后，另一位美国人鲁弗·格鲁弗（Lov Grover）也提出了同样的观点，量子计算机能够终结现代密码学的另一个支柱DES算法。格鲁弗设计了一个程序，能使量子计算机在一定时间内，从一系列可能的数值中查找出正确的数值，所用时间是传统计算机所用时间的平方根。还有一个常用的算法同样也会受到量子计算机发明的影响，那就是RC5，现在是微软浏览器使用的标准。

量子力学带走了什么，也将带来什么

量子力学的其中一座基石是海森伯于1927年提出的“不确定性原理”。虽然它的公式表达非常专业，但它的创造者却大胆地用如下的话简要总结了这个原理：“原则上说，我们无法知晓当下的所有细节。”更具体地说，在任何给定的时刻都不可能准确地确定一个粒子的某些互补属性。我们以光子为例。偏振是它们的基本特点之一，这是个专业术语，是指电磁波的振荡或振动。［虽然光子朝各个方向振动，但为了简要论述，我们假设它朝四个方向振动：垂直（）、水平（）、向左呈对角线倾斜（）、向右呈对角线倾斜（）。］海森伯的原理表明，确认一个特定光子的偏振，唯一的方法是让它通过一个滤波器或“狭缝”，其方向依次为水平、垂直、左斜和右斜。水平偏振的光子穿过水平滤波器保持不变，而垂直偏振的光子被挡住。对于倾斜偏振的光子，其中一半的偏振方向变为水平，穿过滤波器，而另一半反弹回来，完全是随机的。而且，一旦光子从滤波器中发射出来，是不可能准确知道它的原始偏振方向的。

那么光子偏振与密码学有什么关系呢？关系非常大，我们下面就讲这一点。一开始，我们假设一个研究员想了解一组光子的偏振。要做到这点，他别无选择，只能选择一个方向固定滤波器，如水平方向。假设一个光子穿过了滤波器，研究者从中得到了什么信息呢？当然，他可以假设光子的原始偏振方向不是垂直的。他还能做出其他假设吗？不能。起初，人们可能想光子的原始方向中为水平的可能性要比倾斜大得多，因为倾斜的光子中，有一半无法穿过滤波器。但是，倾斜光子的数量同样是水平数量的两倍。需要重点强调一点：检测一个光子的偏振难度之大，并非技术或理论短板造成的，未来也无法修正，因为这是亚原子的天性使然。如果适当地开发利用，这一属性可以用来构建一个完全无法破解的密码，以此达成密码学的最高成就。

一组不同偏振方向的光子穿过一个水平滤波器，可以发现，一半倾斜的光子偏振方向变为水平，穿过了滤波器。

无法破译的密码

1984年，美国人查尔斯·贝内特（Charles Bennett）和加拿大人吉勒斯·布拉萨德（Gilles Brassard）基于偏振光子的传输构思出一种加密系统。第一步是收发双方约定一个方法，把0或1分别指定为一种偏振。在这个例子中，0和1被分派为两个图标或偏振基数的函数：第一个基叫作直线模式，由符号+表示，将1映射为偏振，0映射为偏振；第二个基叫作对角模式，由符号×表示，把1映射为偏振，0映射为偏振。

比如，信息0100101011可按如下方式传输。

如果传输过程中信息被间谍用一个×方向的滤波器截获，则间谍只能得出下表的信息：

可以看出，如果间谍不知道原始基，无论如何都无法从检测到的偏振方向中获取相应的信息。即便知道收发双方分派0和1的方式，但如果发送者随机改变基，那么间谍搞错的概率大约为三分之一，表中显示的是根据描述的条件分解出的所有收发的可能性组合。但是，这里存在一个非常明显的问题：接收者在译解密码时其实会跟间谍面临一样的问题。

说到这一点，收发双方可以通过某种保密媒介，如用RSA加密，给对方发送基序列解决这个问题。但这时，密码的安全性就会受到那些据推测存在的量子计算机的威胁。

为解决最后这个难题，布拉萨德和贝内特在原来的方法上又做了些精细的改进。请大家回想一下，德·维吉尼亚方阵加密家族中，多表加密法是使用简短、重复的密钥，密码因此呈现出规律性，给密码破译者创造了很小但很宝贵的可乘之机。但是，如果密钥用一连串比信息还要长的随机字符，又会怎样呢？而且，如果为了提高保密性，虽然漏洞明显，但是每条信息都用不同的密钥加密呢？答案是，我们将拥有一个无法破解的密码。

提出使用唯一密钥进行多表加密的第一人是约瑟夫·莫博涅（Joseph Mauborgne）。“一战”结束后不久，莫博涅当时担任美国密码破译中心的首席信息官，他设计了一个密钥本，每个密钥由100多个字符随机构成，收发双方每次根据指令破解密钥，然后再进行下一步的操作。这个系统叫作“一次性密码本”，就像我们之前所说的，它是无法破解的，从数学上可以证明这一点。实际上，国家高层领导人之间的机密通信用的都是这种方法。

既然一次性密码本的保密性如此之高，为什么没有普及呢？我们为什么还担心量子计算机的超能力，更别提什么光子操纵了？

随机创造数千个与信息量等量的一次性密钥，困难我们先不说，一次性密码本与其他经典加密算法存在一样的致命点：密钥分配，这也是现代密码学亟待解决的问题。

但是，用偏振光子传递信息是使用单独密钥而没有危险的绝佳途径。想做到这点，需要在发送信息前做三步：

第一，发送方借助不同的、随机的滤波器，分派垂直（）、水平（）和对角线（或）符号，给接收者发送一个由1和0组成的随机数列。

第二，接收者通过随机转换直线模式基（＋）和对角模式基（×）继续测量收到光子的偏振方向。由于接收者不知道发送者使用滤波器的顺序，因此0和1的大部分序列同样也会是错误的。

第三，收发双方用两个人都倾向的方式取得联系（不用担心联系渠道是否安全），然后双方交换如下信息：发送者解释用的什么基，是直线模式还是对角模式，只有这样才能正确读取每一个光子，而不会泄露光子的偏振（也就是使用的滤波器）。接收者告诉发送者在什么情况下他获取的基是正确的。在前面的表格中我们已经看出，如果收发双方各自得到正确的基，就能确定0和1序列的传输是完全正确的。最后，在私底下，双方各自丢弃与光子对应的比特，也就是接收者用错误基确定后的比特。

巴别塔的信息

阿根廷作家博尔赫斯曾在他的短篇小说《巴别塔图书馆》中设想了一座超大型图书馆，馆内收藏着所有可能的书：每一部小说、每一首诗、每一篇论文，以及对它们的评论文章和对评论文章的评论，无穷无尽。而一位密码破译者反复试验、不断摸索，想要破解一条用一次性密码加密的信息，就像在构筑这样一座图书馆。由于密码是完全随机的，可能的译解包含所有相同长度的文本，包含真正的信息、对信息的验证，以及所有专有名词用别的词替代后的相同长度的信息，无穷无尽。

这个过程的结果是，收发双方现在共享一个完全随机生成的、由1和0组成的序列：发送者对偏振滤波器的选择是随机的，接收者对基的选择也是随机的。以一个不大的12比特的信息为例，按照上述过程进行，如下图所示。

请注意，最终保留的比特，即便是正确译解，有一些也会丢弃不用。之所以这样，是因为接收者无法确定究竟是检测正确，还是用了错误的基。如果最初传递的是包含足够数量的光子，1和0的序列长度就足够形成一个一次性密码本，能够加密正常长度的信息。

现在，我们设想自己是间谍，已经截获了收发双方的光子和公开的对话。前面讲过，如果不能准确知道信息发送者使用的偏振滤波器，就不可能确定我们已经检测到了正确的偏振。获取收发双方交换的信息也无济于事，因为他们从不以具体的偏振传输信息。

令间谍更觉沮丧的是，如果没有获取正确的基，就相当于改变了光子的偏振，而他的侵入就此暴露——为了不被发现，他什么都不能做。对于收发双方来说，确保密钥中有足够长的一部分，能够保证一旦有窃听者对光子的偏振进行操作，他们就能检测到，这就够了。

为了达到这个目的，收发双方要达成一个非常简单的验证协议。完成了上述的三步，保留了足够多的比特，收发双方再次通过某种常见的媒介取得联系，然后从总数中随机选取一组比特（比如100比特）进行检查。如果这100个比特匹配，收发双方可以完全确定没有间谍窥探过此次传输，也就可以把这组序列看成是较好的一次性密码。否则，双方需要从头再来一次。

绝密的32厘米

布拉萨德和贝内特的方法从理论角度来讲是完美的，但当理论应用到实际中时，就会面临大量的问题。1989年，努力一年之后，贝内特优化了一套包含两台计算机的系统，这两台计算机之间相距32厘米，一台担任发送角色，另一台担任接收角色。几小时的尝试和调整后，实验取得了成功，收发双方完成了所有步骤，甚至还能验证彼此的密码，可见量子加密是可能实现的。

贝内特的实验具有历史性意义，不过却有明显的缺陷，收发双方只能在一小步的距离内发送秘密，事实上和两人耳语的保密效果差不多。不过，在未来几年内，其他研究团队增大了传输的距离。1995年，日内瓦大学的研究人员用光线发送信息，距离长达23千米。2006年，美国洛斯阿拉莫斯国家实验室的一个研究团队用同样的步骤，把信息发送距离增加到107千米。虽然与常规通信相比，它的信息发送距离还不够长，但足以胜任在绝密信息为重中之重的小范围地区内的工作，比如政府大楼、公司总部等地。

先不考虑发送信息的实际限制，单就传输的信息不被损坏这点来说，即便是在量子层面，也是不可能的。量子密码象征着“秘密”在“泄密”面前、加密者在解密者面前的最后一次狂欢。现在，我们必须得为自己考虑的是，如何应用这个强大的工具，谁又会从中受益，这和我们所有人的未来息息相关。

如果你不知道读什么书或者想获得更多免费电子书请加小编QQ：2338856113 小编也和结交一些喜欢读书的朋友 或者关注小编个人微信公众号名称：幸福的味道 获得上百个书单 为了方便书友朋友找书和看书，小编自己做了一个电子书下载网站，网址：http://www.ireadweek.com 如于某种原因，经常换网址 如果打不开，可以qq联系我

附录

多样的经典密码和隐藏的秘宝

下面我们讲解几种在前面的章节中曾经提到，但并没有展开详述的经典加密术。每种密码都是不同加密技巧的典型代表，大家也可以作为消遣来读。我们选取了一些经典密码，最后是美国作家埃德加·爱伦·坡的虚拟解密故事，故事完美阐释了频率分析。

波里比阿密码

这个密码是有详细记载的最古老的密码之一，先画一个5×5的表格，从字母表中选取5个字母，并以这5个字母作为表格横和纵的表头，然后在表格中填入字母。这套密码的构成方式是，每个字母对应表格中行和列中的字母对。起初，希腊字母只有24个，而英文字母有26个，因此字母I和J通常算作一个。为简明起见，此处用字母A-E作为表头。表中填充字母的顺序要由收发双方达成一致。我们以下页表为例进行解释：

注意加密字母有25（即5×5）个。加密字母表也可以按照数值（如1、2、3、4、5）为表头加密。这样，表格如下所示：

我们分别用两个版本的加密密码来认识波里比阿密码。明文信息是“BLANKS”（空白）。按照第一个以字母为表头的密码表加密如下：

B由字母对AB代替。

L由字母对CA代替。

A由字母对AA代替。

N由字母对CC代替。

K由字母对BE代替。

S由字母对DC代替。

信息加密之后为：“ABCAAACCBEDC”。如果用数值加密，步骤同上，得到的加密信息是：123111332543。

格伦斯菲尔德密码

这个密码由荷兰人约斯特·马克西米利安·布龙克霍斯特（Jost Maximilian Bronckhorst）发明，他是格伦斯菲尔德地区的伯爵，密码因此得名，于17世纪在欧洲使用。它是一种多表加密法，类似于德·维吉尼亚方阵，但使用难度稍小，保密性也略差。我们根据下表加密一条信息：

首先，从0—9随机选择一个数字代替要加密的信息中的每个字母。如果明文是“MATHEMATICAL”（数学的），就随机选择12个数字，如：1、2、3、4、5、6、7、8、9、0、1、2。这一串数字就是密钥。然后参照上页表，把信息中的每个字母用表中对应数字行的字母替换：

M加密为P，其他同理。整个信息加密之后是“PFASRDTQKEDQ”。信息中的三个A分别加密为F、T和D。一般来说，暴力破解和频率分析都无法破解多表加密法，这套加密系统同样如此。对于26个字母的字母表来说，格伦斯菲尔德的密钥数为26!×10=4.03×1026个。

普莱费尔密码

该密码由莱昂·普莱费尔男爵和查尔斯·惠特斯通爵士（他同时是电报的发明者）创造。两人亦邻亦友，都爱好密码学。这种方法是它杰出“前辈”——波里比阿密码的翻版，也用了五行五列的表格。第一步，根据五个不同的字母，将明文中的每个字符替换为字母对。此处以密码“JAMES”为例。如果是26个字符的字母表，会生成如下加密表：

然后，将明文信息分为字母对或“双字母组合”。所有字母对的两个字母必须不同，而且如果出现重复，我们就用字母x替代。如果末尾字母落单，也用x补充，组成一个字母对。

比如，明文信息为“TRILL”（颤音），分为字母对为：

TR IL Lx

单词“TOY”（玩具）分为：

TO Yx

把明文信息分为字母对的形式后，就可以开始加密了，要考虑三种情况：

第一种情况，字母对的两个字母在同一行。

第二种情况，字母对的两个字母在同一列。

第三种情况，上述都不符合。

如果是第一种情况，字母对中的字符就由每个字母右侧的字母代替（即依照字母表顺序的“下一个”）。这样，字母对JE加密为AS：

如果是第二种情况，字母对中的字符就由该字母表中正下方的字母代替。以字母对ET为例，加密为FY，TY加密为YE：

如果是第三种情况，加密字母对中的第一个字母时，要观察它所在的行，直到找到包含第二个字母的列为止；明文的密码在行列相交处查找。加密第二个字母，要观察它所在的行，直到找到第一个字母所在的列为止；同样，明文的密码在相交处查找。

以字母对CO为例，C加密为G，O则为I或K。

用密钥JAMES加密信息“TEA”（茶），步骤如下：

将其分为字母对：TE Ax。

T加密为Y。

E加密为F。

A加密为M。

x加密为W。

加密后，信息为“YFMW”。

金甲虫密码

埃德加·爱伦·坡的小说《金甲虫》的主人公威廉·罗格朗破解了一个写在羊皮纸上的密码，由此发现了传说中的宝藏。罗格朗破解密码的步骤用的是一种统计方法，以英文文本中字母出现的频率为基础。加密信息如图所示：

罗格朗一开始假设原始信息是用英文写成的。英文中出现频率最高的字母是e。然后，字母按出现频率从高到低排列为：a,o,i,d,h,n,r,s,t,u,y,c,f,g,l,m,w,b,k,p,q,x,z。

我们的主人公根据密文列出了一个表格。第一行是加密信息的字符，第二行是每个字符出现的频率：

因此，8很有可能就是字母e。接着，他按照出现频率，将常见单词the翻译为字符“;”、“4”和“8”。

这样一来，他就知道术语“; (88”表示的是“t(ee”，经过推测得知，“(”可能为r，毕竟tree是词典中最有可能的单词。最终，他用同样机智的解密技巧，再加上耐心，得出了部分加密字母表：

虽然不多，但足够译解信息了，译解后的信息为：

A good glass in the bishop's hostel in the devil's seat.

forty-one degrees and thirteen minutes northeast and by north.

main branch seventh limb east side shoot from the left eye of the death's-head.

a bee line from the tree through the shot fifty feet out.

质数和质数在密码学中的价值

“真正的数学不会影响战争的结果。至今，还没有数学理论曾为战争服务过。”

戈弗雷·H.哈代，《一个数学家的自白》（1940）

为译解一条信息，密码能够逆向操作至关重要。前文讲仿射密码时，我们已经知道，有一个方法能够保证这一点，那就是质数模。而且，质数乘积构成了一个不可逆的函数。也就是说，一旦相乘，若再想求出原始因数就会非常困难。

这一特点使得这种运算成为基于对称密钥的加密系统（如RSA算法）的有效工具，转而构成了公钥密码学的基础。让我们更为详细地认识一下质数与密码学的交集，并通过学习RSA正常的数学运算，对此进行证明。

质数和“其他”费马定理

质数是自然数的子集，是指所有大于1的只能被自己和1整除的自然数。数学的一个基本定理确定，所有大于1的自然数通常都可以用质数幂相乘的方式表示，而且这种表示（分解）是独一无二的。例如：

20=2²×5

63=3²×7

1 050=2×3×5²×7

除了2之外所有质数都是奇数，唯一两个连续的质数是2和3。两个相邻的奇数，即相差2的质数（如17和19）叫作“孪生质数”。梅森质数和费马质数同样也很有趣。

有一类质数叫作梅森质数，它加1之后，结果是2的幂。例如7就属于梅森质数，因为7+1=8=2³。

前8个梅森质数如下：

3；7；31；127；8 191；131 071；524 287；2 147 483 647

时至今日，我们只知道40个左右的梅森质数。最大的是个超大数字：243 112 609-1，发现于2008年。通过比较，整个宇宙中的元素粒子数大约小于2³⁰⁰。

费马质数形式如下：

Fn=2²n+1，其中n是自然数

我们只知道5个费马质数：3(n=0)、5(n=1)、17(n=2)、257(n=3)和65 537(n=4)。

费马质数是以它的发现者、著名的法国法学家和数学家皮埃尔·德·费马（Pierre de Fermat，1601-1665）的名字命名的。这位法国数学家在质数相关方面有大量额外发现，具有重要意义。费马小定理就是比较出名的一个，定义如下：

如果p是质数，那么对于任何整数都符合ap≡a(mod.p)

后面将会说到，这个结论对于现代密码学有重要意义。

从欧拉到RSA

与模运算紧密相关的另一个成果叫作“裴蜀定理”。按照裴蜀定理，如果a和b是正整数，且gcd(a,b)=k，则两个整数p和q满足：

pa+qb=k

在gcd(a,b)=1的特殊情况下，可以断言整数p和q符合

pa+qb=1

如果用模n计算，可以确定，若gcd(a,n)=1，则一定存在符合公式pa+qn=1的整数p和q。从模n推测，我们得出qn=0，根据这些，可以总结出存在符合pa=1的p，也就是说a关于模n存在倒数，就是p。

那么，对模n具有倒数的质数数量就等于满足gcd(a,n)=1且小于n的自然数a的数量。这样的数叫作欧拉函数，用φ(n)表示。

如果在质数中对n的分解满足，则：

假设n=1600=2⁶5²，就能得出：

再稍微调整一下，如果条件是n为质数，则a的任何值都满足gcd(a,n)=1，因此，a的任何值都有对模n的倒数，因此φ(n)=n-1。

我们花点时间，回想一下目前得出的最重要的结论：

1.φ(n)叫作欧拉函数，表明小于n的数字主要取决于n。

2.如果p和q都是质数，且符合n=pq，那么：

φ(n)=(p-1)(q-1)

3.根据费马小定理，我们知道如果a是大于0的整数，且p是质数，就能得出关系式ap≡a(mod.p)，同样可以得出ap-¹≡1(mod.p)。

剩下的就是根据欧拉公式增加最后的部分。欧拉断言：

4.如果gcd(a,n)=1，那么我们就能确定公式aφ(n)≡1(mod.n)。

为什么RSA算法能够成功？

有了以上知识，现在可以给大家介绍RSA算法加密过程背后的数学论点了。

设RSA算法用数值表示的信息为m，且p和q是质数，满足n=p·q。e为满足gcd(e,φ(n))=1的任意值，d是对模φ(n)的n的倒数[因为gcd(e, φ(n))=l，所以我们知道d存在]。因此：

d·e≡1(mod.φ(n))

加密信息M根据M≡me(mod.n)加密。该算法假定原始信息m根据m=Md≡(me)d(mod.n)获取。验证了这个方程，就相当于证明了RSA的有效性。为验证这点，我们把欧拉公式与费马小定理进行结合。

考虑两种情况：

1.根据欧拉公式，如果gcd (m, n)=1，则mφ(n)≡1(mod.n)。

我们从等同于e·d-1≡0(mod φ(n))关系式开始，存在一个整数k，符合e·d-1=k·φ(n)，也就是e·d=k·φ(n)+1。有了这个公式，运用欧拉公式，我们得出公式

(me)d=me·d=mk·φ(n⁾⁺¹=mk·φ(n)·m=(mφ(n))k·m=1km(mod.n)==m(mod.n)

这就是我们要求的结果。

2.如果gcd(m,n)↑1，且n=p·q，则m只有一个因数，仅为p，仅为q，或两者同时。

在第一种情况中：

a）m是p的倍数，也就是说，存在一个整数r满足m=r·p。因此mde≡0(mod.p)，且最后：mde≡m(mod.p)，换句话说，存在满足下列条件的A：

mde-m=Ap　表达式一

在第二种情况中：

b）我们得出公式：

(me)d=me·d=mk·φ(n)+¹=mk·φ(n)·m=(mφ(n)) k·m≡≡(m(q-1))k(p-1)·m(mod.n)=m

gcd(m,n)=p，(m,q)=1，根据费马小定理m(q-1)≡1(mod.q)

应用到初始方程：

(me)d=me·d=mk·φ(n)+¹=mk·φ(n)·m=(mφ(n)) k·m≡≡(m(q-1))k(p-1)·m(mod.n) =1k(p-1)m≡m(mod.q)

从中我们得出结论，存在数值B满足

mde-m=Bq　表达式二

从表达式一和二中，我们可以确定p·q=n除尽mde-m，因此mde-m≡0(mod.n)。

考虑q的过程是类似的。如果m同时是p和q的倍数，这种情况下，结果就简单了：

(me)d≡m(mod.n)

这就是RSA算法加密法。

参考书目

Gómez, J., De La Enseñanza Al Aprendizaje De Las Matemáticas,Barcelona, Paidós, 2002.

Kahn, D., The Codebreakers:The Story of Secret Writing, New York, Scribner, 1996.

Singh, S., The Code Book: The Secret History of Codes and Code breaking, London,Fourth Estate, 2002.

Tocci, R., Digital Systems:Principles and Applications, Essex,Pearson Education Ltd., 2013.

如果你不知道读什么书，

就关注这个微信公众号号。

微信公众号名称：幸福的味道

加小编QQ一起读书，并免费提供找书服务

QQ号：2338856113

【幸福的味道】已提供200个不同类型的书单

1、 历届茅盾文学奖获奖作品

2、 每年豆瓣，当当，亚马逊年度图书销售排行榜

3、 25岁前一定要读的25本书

4、 有生之年，你一定要看的25部外国纯文学名著

5、 有生之年，你一定要看的20部中国现当代名著

6、 美国亚马逊编辑推荐的一生必读书单100本

7、 30个领域30本不容错过的入门书

8、 这20本书，是各领域的巅峰之作

9、 这7本书，教你如何高效读书

10、 80万书虫力荐的“给五星都不够”的30本书

关注“幸福的味道”微信公众号，即可查看对应书单和得到电子书

更多书单，请关注微信公众号：一种思路

每日新出版的读书分享，请关注公众号：周读读书