04 密码学 素数的秘密生活（第1页）

04密码学：素数的秘密生活

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

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

化身为数的秘密

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

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

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

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

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

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

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

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

密钥和密钥交换

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

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

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

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

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

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

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

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

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

回忆一下，我们把每条明文信息都看作一个单独的数，我们自然努力想用其他数来掩盖它。最常用的方法是用所谓的RSA（Rivest-Shamir-Adleman）加密过程，这是由它的创始人罗纳德·李维斯特（Ro）、阿迪·萨莫尔（AdiShamir）和莱昂纳德·艾德曼（LeonardAdleman）在1978年发表的。在RSA中，每个人的私有密钥由三个数p，q，d组成，p和q是（非常大的）素数，而第三个数d是爱丽丝保密的解密数（degnumber），我们到下面合适的时候再解释它。爱丽丝公开给大家的是两个秘密素数之积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]（BooksofEuclid）中发表的欧几里得算法，求解这个方程是很容易的，这并不困难。麻烦的地方在于，除非你知道p和q中至少一个，否则不可能准确地找到那个要解的方程。这便是挡在伊芙道路上的障碍。

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

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

同时，因为74末尾两位是01，所以接下来四个幂的末尾依次是07，49，43，接着又是01。因此，随着我们挨个计算幂次，末尾两位的数字只会一遍又一遍地重复这个长度为4的循环。回到我们手上的问题，由于39=4×9＋3，我们会经历这个循环9次，然后还需要三步来计算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，我们说这些数是互素（e）的，那么总存在一个指数t，使得幂at等于1模n——也就是说被n除时余1。从这个角度说，连续次幂的余数会构成周期为t的循环。但是，预测t的值很难。不过人们知道t总等于一个特殊的数或是它的某个因数。这个数传统上被写φ（n），代表欧拉φ函数（Eulerphifun）的值。

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

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

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

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

回到欧几里得算法。这个算法是通过推广以下的观察结果得到的，即对于两个数a〉b，可以通过连续的相减来找到最大公因数（highestonfactor）。最大公因数也叫作最大公约数（greatestondivisor）。我们注意到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，我们现在面对的是跟之前一样的问题，不过是相对于两个更小的数。重复应用这个方法，最终会得到一对数，它们的最大公因数可以一眼看出。（实际上，最后手中的两个数会变成相等的，因为如果不是这样，我们可以继续多做一步。这对数共同的值就是我们找的那个数。）