读者朋友现在应该能够体会，从很早开始，自然数的集合就已经被看作谜语和秘密的源泉，产出了很多直到今天都没能解决的问题。对我们中的不少人来说，这已经是继续进行关于数本身严肃研究足够的理由。不过其他人可能会有不同的态度：虽然这些难题可能耐人寻味、充满挑战，但是也可以想象，它们对人类文明的其他方面影响甚微。然而，这样的想法是个错误。

过去的几十年里，人们逐渐意识到，我们时不时会有保密的需求，某些普通信息构成的秘密可以被编码成关于数的秘密。现在，密码学已经得到了全面的应用。我们最为珍贵的秘密，无论是商业的、军事的、个人的、财务的、一般政治性的还是彻头彻尾丑闻性质的，都可以在互联网上被保护起来——用有关普通自然数的秘密。

化身为数的秘密

这一切都是怎么做到的呢？任何信息，无论是一首诗还是一份银行账单，一张武器设计图还是一套计算机程序，都可以用词语来描述。当然，我们可能需要拓展用来表示词语的字母表，使它不仅限于含有普通的字母。我们或许会加上数字符号和标点符号，包括代表词语之间空格的特殊符号。即便如此，我们希望传输的所有信息(包括生成相片和图表的指令)总可以由一张字母表来表达。让我们假设这张表包含的符号不超过一千个。我们可以数一数这些符号，然后用一个独一无二的数来表示每个符号。因为数的成本低廉，取之不尽。为了我们的目的，或许使用位数相同的数会比较方便。比如，每个符号都被一个独一无二的4位个体识别码(personal identification number， PIN)表示。我们可以将这些符号按顺序串连起来，从而得到一个很大很长的数，里面包含故事的全部。我们要是愿意，甚至可以在二进制下做这件事。这样我们可以设计一个方法将信息转译成一长串0和1。于是，我们想要发送的每条信息都可以编码为一个二进制字符串，然后在接收端由具有相应程序的计算机解码，再被编译为我们都可以理解的普通语言。这就是我们的第一层领悟：要传递信息，从理论和实用两方面来说，能从一个人向另一个发送数字就足够了。

但是将信息变成数并不是关键的思想。明确一点说，将所有信息数字化的具体过程可以被藏起来，不被大众知晓，但这并不能形成有效的保护、免遭窃听。的确，从密码学的观点来看，我们可以将任何信息——所谓的明文(plaintext)——与代表它的数等同看待，于是便可以把数看作明文本身。这是因为我们假定，任何人都有办法掌握这两者互相转换的途径。只有当我们用别的数掩盖明文数码的时候，信息才真正具有了保密性。

密码学便是关于密码(ciphers)(机密的代码)的学问。让我向你介绍一些虚拟角色吧，他们经常出现在密码学所考虑的各类情境中。我们设想爱丽丝(Alice)和鲍勃(Bob)想互相通信，但不想让窃听者伊芙(Eve)听见[1]。我们也许会本能地同情爱丽丝和鲍勃，而将伊芙想象成坏人。但是这可能与真相相反，伊芙或许代表了正义的警方，努力保护着我们免受鲍勃和爱丽丝的邪恶计划的伤害。

无论参与者的道德立场如何，爱丽丝和鲍勃都可以运用一个古老的方法，来将伊芙排除在对话内容之外，哪怕伊芙截取了他们之间传递的信息。方法就是用密钥(cipher key)来加密数据，而这个密钥只有爱丽丝和鲍勃自己知道。他们可以预定在一个安全的环境会面，交换一个秘密数字(比方说57)，然后各自回家。当时机到来时，爱丽丝想要发送一条信息给鲍勃。这里为了叙述方便，我们假设信息可以用一个1～9之间的数字来表示。在那个重大的日子，爱丽丝想将信息“8”发给鲍勃。她取出信息，加入秘密数字。也就是说，她通过加上57把真实的数值掩藏了起来，然后将信息8+57 = 65通过一个未经保护的渠道发给鲍勃。鲍勃收到这条信息，减去秘密数字，从而获取爱丽丝的明文65-57 = 8。

不过，不怀好意的伊芙很清楚这两个人在干些什么，并且她也确实截获了加密过的信息65。但是她能对它做什么呢？她可能像我们一样，知道爱丽丝发送给鲍勃九种可能的信息1，2，3，…，9中的一个，也知道她通过将信息加上一个数进行了加密，这个加密数一定在65-9 = 56到65-1 = 64之间。然而，因为她不知道这九个数字中的哪一个被使用了(她被排除在这个秘密之外)，她没法进一步搞清楚爱丽丝给鲍勃发送的明文信息。九种信息中的每一种都有相同的可能性。她知道的全部就是爱丽丝给鲍勃发送了一条信息，但是不知道信息的内容。

看起来爱丽丝和鲍勃对伊芙的邪恶渗透已经防得滴水不漏，他们似乎可以使用这个奇妙的数57来掩藏所有想说的内容，从而不受限制地通信。但是，实际却非如此。他们最好换一换这个数，实际上每次都使用一个新的密码会更好。不然这套系统就会开始泄露线索给伊芙。比如说，在未来某一周爱丽丝想向鲍勃传送一条相同的信息8。每件事都会与之前一样，再一次伊芙从电波中截获了神秘的数65，但这次会让她读出一些东西。伊芙会知道，无论这条信息是什么，这和爱丽丝第一周发给鲍勃的是一样的——而这类事情正是爱丽丝和鲍勃所不希望伊芙知道的。

当然，对于爱丽丝和鲍勃来说，这看起来也不是什么大问题。当他们第一次见面“互换密钥”时，爱丽丝可以不只是约定一个密码，而是提供给鲍勃一张长长的有顺序的列表，里面有上千个密码。他们可以依次使用这些密码，从而避免了在公开通信中出现有意义重复的可能性。

我们确实也是这样操作的。这种密码系统在业内被称为一次性密码本(one-time pad)。发送者和接收者从密码本中找到一个一次性的数，用以掩藏他们的明文。当信息被发送和解密后，密码本中的那一页会被发送者和接收者一起撕掉。一次性密码本代表了一种彻底安全的系统，因为在公共领域传输的不安全文本不含有任何关于明文内容的信息。为了解码，拦截者需要拿到密码本才能获得加密/解密的钥匙。

密钥和密钥交换

一次性密码本似乎完全解决了安全通信的问题。某种角度上说确实如此。但是，参与者必须交换一份密钥，才能使用一次性密码本，类似的密码都有这样的问题。在实践中，交换密钥很麻烦。对于高层通信，比如在白宫和克里姆林宫之间，钱不是问题，所以必要的信息交流会在最高安全级别下开展。另一方面，在日常生活中，各类人和机构都需要以保密的方式互相沟通。参与者负担不起安全交换密钥所需的时间和精力，即使通过受信任的第三方来安排，加密可能依然价格不菲。

所有使用了几千年的密码——直到20世纪70年代——都有一个共同的缺点：它们都是对称密码(symmetric ciphers)，就是说加密和解密的钥匙在本质上是一样的。无论是尤利乌斯·恺撒(Julius Caesar)的简单的字母位移式密码，还是第二次世界大战中的复杂的英格玛密码(Enigma Cipher)，它们都摆脱不掉共同的弱点，即一旦对手知悉你是如何编码信息的，他们就能与你一样顺利地解码。为了使用对称密码，通信双方需要一种安全的密钥交换方式。

一直以来，我们似乎默认加密代码有不可避免的原则——要运用一套密码，双方需要用某种方式交换相应的密钥，并对敌人保密。的确，有人可能把它当作了数学常识。

这种假设恰恰会令一个数学家心生疑惑。本质上，我们面对的是一个数学问题，因而人们会预期这样一条“原理”有着坚实的基础，甚至表达成某种形式的数学定理。然而，并没有这种定理。之所以没有，是因为这条原则根本就是不对的。下面这个思想实验可以证明。

从爱丽丝那里传送一条机密信息给鲍勃，这本身并不一定需要交换一份密钥，因为他们可以按下面的程序来操作。爱丽丝写好她要给鲍勃的明文信息，然后将它放进一个盒子里，再挂上她自己的锁，只有爱丽丝有锁的钥匙。她接着将盒子寄给了鲍勃。当然，鲍勃没法打开它，不过他可以给盒子加上第二把锁，而只有他一个人有这把锁的钥匙。接下来，盒子被寄还给爱丽丝，她会打开自己的锁，第二次把盒子寄给鲍勃。这次，鲍勃便可以打开盒子，读到爱丽丝的信息。寄送过程中，我们知道伊芙即使想从中作梗，也没办法看到内容，因此信息是安全的。这样，一条机密信息便可以通过不安全的渠道安全地传送，却从不需要爱丽丝和鲍勃交换密钥。这个假想的情境说明，在密信的传递过程中，没有定律规定密钥必须转手。在真实系统中，爱丽丝和鲍勃的“锁”可能是他们各自对信息的编码，而不是一个分隔潜在窃听者和明文的实体设备。爱丽丝和鲍勃可以利用这个初始的交换来建立一套普通的对称密码，接下来这套密码便可以掩藏未来的所有通信。

其实在真实世界中，安全的通信渠道经常是这样建立起来的。不过，用个人代码代替实体的锁并不是那么容易。解读(即解锁)的过程需要爱丽丝在先，鲍勃在后。不像普通的锁，爱丽丝和鲍勃的编码可能会相互干扰，从而导致这一过程无法进行。但是，1976年，惠特菲尔德·迪菲(Whitfield Diffie)和马丁·赫尔曼(Martin Hellman)首次公开证明了这个方法是有效的。

另一种相关的方法是不对称(asymmetric)或者说公开密钥加密(public key cryptography)的思想。在这个方法中，每个人发布他们自己的公开密钥，要发送给一个人的信息都用他的公开密钥来加密。但是，每个人还有一份私人密钥。如果没有私人密钥，使用对应的公开密钥加密的信息就没法解读。如果接着用挂锁比喻的话，爱丽丝提供给鲍勃一个盒子用来装他的明文信息，外加一只开着的锁(她的公开密钥)，而只有她自己手里握着钥匙(她的私人密钥)。

看起来，建立一个实用的公开密钥系统需要满足太多条件，因为安全性和易用性这两个要求密不可分，但似乎又互相矛盾。不过，快速、安全的加密方法已经在互联网上广为应用了，即便大家很少意识到它的存在和它为人们提供的保护。让这一切得以实现的，说到底都是数，尤其是素数。

用素数的秘密守护我们的秘密

回忆一下，我们把每条明文信息都看作一个单独的数，我们自然努力想用其他数来掩盖它。最常用的方法是用所谓的RSA(Rivest-Shamir-Adleman)加密过程，这是由它的创始人罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和莱昂纳德·艾德曼(Leonard Adleman)在1978年发表的。在RSA中，每个人的私有密钥由三个数p，q，d组成，p和q是(非常大的)素数，而第三个数d是爱丽丝保密的解密数，我们到下面合适的时候再解释它。爱丽丝公开给大家的是两个秘密素数之积n =pq，以及一个加密数e(这是一个普通的整数，与第2章中提到的特殊常数e没有任何关系)。

为了说明RSA如何发挥作用，我们举一个简单的例子。假设爱丽丝的素数是p= 5和q= 13，于是n = 5×13 = 65。如果爱丽丝把她的加密数设为e = 11，那么她的公开密钥就是(n， e) = (65， 11)。为了加密信息m，鲍勃只需要n和e。然而，要想解码鲍勃发送给爱丽丝的经过加密的信息E(m)，就需要有解码数d。在这个例子中，可以推知d= 35，这个我们待会儿就来证明。计算出d的数学方法需要知道素数p和q。在这个简单的例子里面，给定n = 65，任何人都会很快发现p = 5而q = 13。然而，如果素数p和q极其地大(通常它们有几百位数字那么长)，在实际操作上，至少是在较短的时间(比如说两到三周内)，几乎没有任何计算机系统能完成这项任务。总的来说，RSA加密系统是基于一个经验事实，即找到一个很大很大的数n的素因数极为困难，困难到在实际操作中无法实现。这个方法设计得真正聪明的地方，在于代表信息的数m可以只用公开的数n和e来加密，但在实际操作中，解密需要知晓n的素因数。在这章剩下的部分里，我们就来详细解释这一点。

RSA是这样起作用的：鲍勃通过网络发送的不是m本身，而是me除以n所得的余数(remainder)。然后爱丽丝拿到这个余数r，计算rd除以n得到的余数，就能重新得到m。这背后的数学保证了爱丽丝得到的结果正是原始的信息m，爱丽丝的计算机可以进一步将它解码为普通明文。当然，对于任何真实生活中的“爱丽丝”和“鲍勃”，这一过程都是在幕后无缝衔接地完成的。

这么看来伊芙所缺的唯一重要的东西是解密数d。倘若伊芙知道d，那她也能像爱丽丝一样完美地解码信息。事实上，存在着一个特殊的方程，d恰好是它的一个解。从计算的角度来讲，借助于公元前300年的《几何原本》[2](Books of Euclid)中发表的欧几里得算法，求解这个方程是很容易的。这不是困难之处。麻烦的地方在于，除非你知道p和q中至少一个，否则不可能准确地找到那个要解的方程。这便是挡在伊芙道路上的障碍。

我们可以再进一步解释，以上涉及的数如何在这个系统中各司其职。首先，很明显鲍勃一开始就面临着一个大问题，m很大，n更是可怕(在200位数字这个量级上)。即便e的值不像那样夸张，me也是极其大的。计算出它之后，我们还得将me除以n来得到余数r，这代表了被加密的文本。这些计算太过繁杂，以至于看起来也许并不可行。我们需要意识到，即使现代计算机异常强大，它们还是有能力极限。当计算涉及很高次的幂，就可能会超过任何计算机处理能力的极限。我们不能假设电脑可以在短时间内完成任何我们交给它们的计算任务。

鲍勃有根救命稻草是，他完全可以不做很长的除法就找到要求的余数r。实际上，余数仅仅取决于余数。这里我们举一个例子来说明，739的最后两位是多少？(换句话说，当这个数被100除后余多少？)为了回答这个问题，我们可以从计算7的前几次幂开始：71 = 7， 72 = 49， 73 = 343， 74 = 2401，75 = 16 807，…。不过很快我们就清楚地发现，离739还远着的时候，这些数已经变得相当大，我们都处理不过来了。另一方面，随着我们算出一个又一个幂次，一个关键的规律出现了。当计算连续的幂次时，结果的最后两位数字仅依赖于前一个数的最后两位。这是因为我们做乘法时，百位及以上的数字并不会影响到结果在个位和十位上的数字。

同时，因为74末尾两位是01，所以接下来四个幂的末尾依次是07， 49， 43，接着又是01。因此，随着我们挨个计算幂次，末尾两位的数字只会一遍又一遍地重复这个长度为4的循环。回到我们手上的问题，由于39 = 4×9+3，我们会经历这个循环九次，然后还需要三步来计算739的最后两位数，因此结果一定是43。

这样的技巧是相当普适的。比方说，为了找到某个幂次ab除以n所得的余数，我们只需要取a除以n所得的余数r，并追踪r的各次幂除以n之后的余数。余数r一定是大于或等于0、小于或等于n-1之间的一个数。在我们只关心r的时候，数学家们说我们是在求模(modulo)n。我们舍弃了所有n的整数倍，因为它们除以n余0，所以不会对最终的余数r有任何贡献。

你可能还是在怀疑，我是不是通过选择特殊的例子操纵了证据，这个例子里一个很小的幂次就给出了余数1——这里74比100的某个整数倍大1。然而，你怀疑的情况只在部分程度上成立。事实上，如果我们取任意两个数，a和n，它们的最大公因数为1，我们说这些数是互素的(coprime)，那么总存在一个指数t，使得幂at等于1模n——也就是说被n除时余1。从这个角度说，连续次幂的余数会构成周期为t的循环。但是，预测t的值却很难。不过人们知道t总等于一个特殊的数或是它的某个因数。这个数传统上被写作φ(n)，代表欧拉φ函数(phi function)的值。

这跟我们直接从定义得到的结果是一样的。使用这个方法，你可以自己验证φ(100)=40。因此，可以推出740同余于1模100。当然，就像我们已经看到的，余1的7的最小幂次不是40，而是它的因数4。

以上这些都是为了表明，鲍勃确实可以求出发送给爱丽丝的数，me模n，同时不需要鲍勃的计算机做出太多努力。不过，在实际操作中涉及的数依然大到可怕，因此我们有必要进一步说明如何处理它们。计算me所涉及的高次幂可以分阶段进行，这个过程叫作快速求幂(fast exponentiation)。简而言之，这一方法运用连续求平方以及幂的相乘来得出me模n，我们可以用二进制形式的e引导算法，从而在相对少的步数里快速找到想要的余数。

欧几里得教爱丽丝找到她的解密数

为了找到d，爱丽丝的电脑可以利用一个代数工具——欧几里得算法，这一工具已经有2300多岁了。稍后我们就来介绍它。如果伊芙的计算机知道去解哪个方程，那它当然也能做到同样的事情。然而，因为p和q是爱丽丝私有的，(p-1)(q-1)也是，因此伊芙并不知道从哪里着手。

加密数(公开的)e需要满足一个温和的限制条件，才能保证d的存在。爱丽丝必须确保e与φ(n)没有公因数。这很容易做到，爱丽丝可以检验用不同的素数除φ(n)的结果，从而保证既不泄露p和q的值也让e满足限制条件。实际应用中，e的值常常使用第四个所谓的费马素数(Fermat prime)e=65 537=216+1。这个值，224+1，具有一个尤其稀有的性质，即可以用直尺和圆规(straightedge and compass)作出一个有e条边的正多边形。不过，它在密码学中的用处在于它是一个很大的(恰好比某个2的幂大1的)素数，这非常适合运用之前提到的快速求幂过程。

回到欧几里得算法。这个算法是通过推广以下的观察结果得到的，即对于两个数a＞b，可以通过连续的相减来找到最大公因数(highest common factor)，最大公因数也叫作最大公约数(greatest common divisor)。我们注意到r = a-b有一项性质：a，b，r中任意两者的公因数也是第三个数的因数。例如，如果c是a和b的公因数，于是a = ca1并且b = cb1，我们看到r=a-b=ca1-cb1=c(a1-b1)，这就得出了r包含c的一个因数分解。于是，a和b的最大公因数等于b和r的最大公因数。因为这两个数都小于a，我们现在面对的是跟之前一样的问题，不过是相对于两个更小的数。重复应用这个方法，最终会得到一对数，它们的最大公因数可以一眼看出。(实际上，最后手中的两个数会变成相等的，因为如果不是这样，我们可以继续多做一步。这对数共同的值就是我们找的那个数。)

比如，要找a = 558和b = 396的最大公因数，第一次减法后我们得到r = 558-396 = 162，因此新数对是396和162。由于396-162 = 234，所以我们的第三对数是234和162。随着我们继续下去，完整的数对依次是：

(558，396)→(396，162)→(234，162)→(162，72)→(90，72)→(72，18)→(54，18)→(36，18)→(18，18) .

因此558和396的最大公因数是18。

还可以根据待考察的数对各自的素因数分解来写出它们的最大公因数。在这个例子里，558=2×32×31，而396=22×32×11；取两个分解中各个素数的共同次幂，我们得最大公因数为2×32=18。然而，对于大数而言，使用欧几里得算法需要的工作量少得多，因为一般执行减法运算比寻找素因数分解更简单。

欧几里得算法的另一项优点是总可以倒着做，这样便可以将最大公因数用原始的两个数来表示。为了更好地看清楚这是怎么做到的，我们在刚才这个例子里将计算压缩。在依次相减的过程中，同样的数重复出现了好几次，我们可以把它们表达在一个方程里。这样我们就得到以下几个等式：

558 = 396+162；

396 = 2×162+72；

162 = 2×72+18；

72 = 4×18 .

从第二行开始到最后一行，我们可以用各个等式逐个消去中间余数。在这个例子中，先利用倒数

第二个等式，然后是它上面的那个，我们得到：

18=162-2×72=162-2×(396-2×162)

=5×162-2×396.

最后再用第一个等式，我们可以把第一个中间余数162也消去：

5×162-2×396=5×(558-396)-2×396=

=5×558-7×396=18.

无论是对于实践还是理论，可以倒过来执行这一程序都是很重要的。特别是在解密里，为了找出爱丽丝的解密数d，我们想要d满足de除以φ(n)余1的条件。为了简洁，我们用一个单独的符号k来代表φ(n)。现在就可以看出我们坚持要e和k互素的原因了。因为如果它们的最大公因数是1，当我们对e和k执行欧几里得算法时，最终出现的余数自然是1。倒过来执行这一算法，我们就能最终把1表示成e和k的组合。特别地，我们会找到整数c和d，它们满足ck+de = 1，或者换句话说de=1-ck。因此de除以k会余1。

这个相对简单的过程将给出爱丽丝的解密数d：直接从方程里得出的d的值可能不在1到k的范围内；倘若不在，通过加上或减去合适的k的倍数，我们最终可以找到那个d，在给定范围内，它是唯一具有de除以k余1这个神奇性质的数。(我们可以轻松证明d的唯一性，不过这里还是不要离题太远了。)这便是如何计算解密数d的方法。我们可以回到前面的例子来说明，这里p=5，q=13，于是n=pg=5×13=65。我们有φ(n)=(p-1)(q-1)=4×12=48。爱丽丝设定e=11，由于11与48互素，这在游戏规则所允许的范围内。应用欧几里得算法于φ(n)=k=48和11，可得：

48 = 4×11+4；

11 = 2×4+3；

4 = 1×3+1 .

这显示k和e的最大公因数确实是1。将算法反转，我们得到：

1=4-3=4-(11-2×4)=3×4-11

=3(48-4×11)-11=3×48-13×11.

为了满足11d除以48余1的条件，我们解出d的初步值-13。为了得到一个在要求范围内的正的d的值，我们在这个数的基础上加上48，于是d=48-13=35。

d能帮助爱丽丝解密信息，其原因可以归结为模算术(modular arithmetic)的特性，以及当de除以k=φ(n)时余1这一事实。爱丽丝计算(me)d=mde模n。现在de具有1+kr的形式，这里r是某个整数。正如之前解释的那样，mk除以n余1，这通常被称为欧拉定理(Euler’s Theorem)，而这对于(mk)r=mkr也是对的。因此，m1+kr=m×mkr，它除以n余m。(详细的验证需要一点代数运算，不过结果的确是这样的。)通过这个方法，爱丽丝得到了鲍勃的信息——m。

顺便指出，我们在证明素因数分解唯一性的时候缺少了一环，欧几里得算法恰好提供了这缺失的环节。因为它使得我们能够验证欧几里得性质，即如果素数p是乘积ab的一个因数，比方说ab=pc，那么p是a和b之中至少一个的因数。如果p不是a的一个因数，那么由于p是素数，a和p的最大公因数是1。应用欧几里得算法于a和p这对数，并将其反转，我们可以找到整数r和s，使得ra+sp=1。这已经足够证明p是b的一个因数了，由于ab=pc，我们有：

b=b×1=b(ra+sp)=r(ab)+psb:

=r(pc)+psb=p(rc+sb).

这便是想要找的b的分解，它显示p正是一个因数。

总而言之，RSA加密背后的关于数的理论保证了系统的可靠性。当然，要保证系统的完整，还需要遵守很多这里没有解释的协议。可能出现的问题包括身份验证(authentication)(假如伊芙伪装成鲍勃联系爱丽丝怎么办？)、不可抵赖性(nonrepudiation)(假如鲍勃装作伊芙发送了信息给爱丽丝怎么办？)以及身份欺诈(identity fraud)(假如爱丽丝滥用鲍勃发给她的保密的身份信息，试图在网上假扮他怎么办？)。另外，当可预测的或者重复的信息大量出现，这个系统的其他弱点也可能会暴露。不过，这些困难在任何公开密钥加密系统中都可能出现。它们是可以被克服的，并且总体来说与背后的数学技术没有太大关系，而那些数学技术才是保证加密的高质量和稳定性的因素。

这一章展示了素数以及整除性和余数理论的一项主要应用。我们不仅从广义的原理上，还在细节层面对此进行了解释，这都要感谢欧几里得的古代数学和欧拉在18世纪的贡献。

我们这本书的第一部分会在第5章告一段落，该章里我们将要介绍一些特殊类型的整数，它们与某些自然呈现的分组现象有关。

[1]　“窃听者”的英语单词为eavesdropper，因此虚拟的窃听者常用名字Eve来代表。

[2]　一般称为The Elements of Euclid，共有13卷。