五二小说网

手机浏览器扫描二维码访问

04 密码学 素数的秘密生活 Cryptography the Secret Life of Primes（第4页）

在这个方法中，每个人发布他们自己的公开密钥，要发送给一个人的信息都用他的公开密钥来加密。

但是，每个人还有一份私人密钥。

如果没有私人密钥，使用对应的公开密钥加密的信息就没法解读。

如果接着用挂锁比喻的话，爱丽丝提供给鲍勃一个盒子用来装他的明文信息，外加一只开着的锁（她的公开密钥），而只有她自己手里握着钥匙（她的私人密钥）。

看起来，建立一个实用的公开密钥系统需要满足太多条件，因为安全性和易用性这两个要求密不可分，但似乎又互相矛盾。

不过，快速、安全的加密方法已经在互联网上广为应用了，即便大家很少意识到它的存在和它为人们提供的保护。

让这一切得以实现的，说到底都是数，尤其是素数。

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

回忆一下，我们把每条明文信息都看作一个单独的数，我们自然努力想用其他数来掩盖它。

最常用的方法是用所谓的RSA（Rivest-Shamir-Adleman）加密过程，这是由它的创始人罗纳德·李维斯特（Ro）、阿迪·萨莫尔（AdiShamir）和莱昂纳德·艾德曼（LeonardAdleman）在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]（BooksofEuclid）中发表的欧几里得算法，求解这个方程是很容易的。

这不是困难之处。