π导航  

模算术催生了密码学的一项重要发展：公开密钥加密。所有密码都有赖于密钥，它们所面临的最大风险也在于密钥被泄露。如果敌人（比如通过间谍）得到了一份你的一次性密码本的副本，那你的麻烦就大了。但也有可能这并不要紧。通常的暗含假设是，一旦有人知道了密钥，他应该就能很容易地解码加密讯息。毕竟，这正是接收者预期要做的事情，所以把它弄得很难无疑是愚蠢的。但在1977年，罗恩·里韦斯特(Ron Rivest)、阿迪·沙米尔(Adi Shamir)和伦纳德·阿德尔曼(Leonard Adleman)发现，事情并没有这么简单。事实上， 有可能公开将讯息加密的密钥，而不用担心加密讯息会被破解。同时，合法的接收者可以借助另一个相关的密钥解码该讯息，而这个密钥是保密的。

这类方法有赖于一个有趣的数学事实：逆推一个计算，从答案推算出问题，有时会比做这个计算本身难得多——即便这个过程在原理上是可逆的。如果真是这样的话，即便知道这个过程的原理，也无从算得具体的内容。不过，单靠这个事实并没什么用处，还需要有某种秘密捷径，使得合法的接收者可以轻松地解码。而这正是高斯的奇异发明、可使2+2=0的模算术大显身手的地方。

RSA加密算法（得名自上面提到的三位发明者的姓氏首字母缩写）基于欧拉证明的一个定理。这个定理推广了皮埃尔·德·费马发现并证明的一个较简单的定理，后者被称为费马小定理，以区别于费马大定理（参见《数学万花筒（修订版）》第49页）。

费马小定理说，如果以质数 p 为模数，则对于任意整数a，都有a^(p−1)≡1。例如，以5为模数，我们应该会发现1^4≡1，2^4≡1，3^4≡1，4^4≡1。情况也的确如此。比如，

3^4≡3×3×3×3≡81≡1(mod 5)

因为81−1=80，而80可被5整除。其他整数也是如此。

为了应用RSA加密算法，你先得将讯息转换成数。例如，将每个包含100个字母、空格及其他字符的块表示成一个200位的数，其中每对相邻数字根据如下规则编码字符：A=01, B=02, …, Z=26, 空格=27, ?=28， 等等。然后将一条讯息分解成一系列100位数。令 N 是其中的一个数。我们的任务是把 N 加密，通过一种使用模算术的数学方法。

下面我举一个例子，其中用到的数要比实际应用中的数小得多。 爱丽丝使用两个特别的数：77和13，这两个数是可以公开的。假设她的讯息是 N=20，则她计算2013(mod77)，得到69，并发送给鲍勃。鲍勃知道秘密捷径是数37，通过它可以逆推爱丽丝使用13所作的计算。因此，他解码了爱丽丝的讯息：

6937≡20 (mod 77)

这对于爱丽丝可能发送的任何讯息都有效，因为

(N^13)^37≡N(mod77)

但这些数是如何而来的呢？

爱丽丝所选的数77是两个质数的积，7×11。可求得(7−1)×(11−1)，即60，并可知存在一个数d，使得13d≡1(mod 60)，以及根据欧拉定理，对于任意讯息N，(N13)d≡N(mod77)。这个数 d 只有鲍勃知道，在这里 d=37。要使这种方法切实可用，我们需要用大得多的质数替换7和11——通常是100位左右的数。编码密钥（这里是13）和解码密钥（这里是37）可从这些质数计算得出。只有编码密钥、两个质数的积以及一个200位的数需要公开。只有鲍勃需要知道解码密钥。

这涉及找到非常大的质数，而事实证明这比我们可能预想的要更容易：存在许多有效的方法去检验一个数是否为质数，而无须将其因数分解。当然，你需要利用计算机来求这些乘积。注意到这里的宠物门效应： 爱丽丝不需要知道如何解码讯息，她只需知道如何编码讯息即可。数学家普遍认为（但还不能证明），计算出一个非常大的数的质因数是极其困难的——难到在实践中做不到，而无论你的计算机多大多快。找到大质数则要容易得多，把它们相乘也是如此。

宠物门: 我有时喜欢把这类过程比喻成宠物门。我们的宠物猫埃勒坎知道通过推门从里面出来，但大部分时候它以为从外面回去的方式应该是逆转这个过程，所以常常会坐在外面试图拉门。即便它把这个逻辑推向极端，试图让尾巴先进来，我也不会觉得奇怪。但它忘了秘密捷径。我们躺在床上听着它折腾，心里暗暗着急：“埃勒坎！你倒是推啊！”

当然，我的例子使用的是不实用的小数，所以找到解码密钥37很容易。爱丽丝能算出来，任何试图破解讯息的人也可以。但若是100位的质数，如果你只知道两个质数的乘积，要算出解码密钥几乎是不可能的。另一方面，如果你确实知道这些质数，那么求解码密钥是相当简单的。这正是这个系统得以建立的基础。

像RSA这样的加密算法非常适合互联网，因为在网上每个用户都必须“知道”如何发送加密讯息（比如信用卡号）。也就是说，加密这条讯息的方法必须存储在他们的计算机上。这样的话，程序员有可能找到它。但只有银行需要知道解码密钥。因此，在罪犯分子找到大数的质因数分解的有效方法之前，你的钱都是安全的——假定银行是可靠的，不过这突然变得成问题起来了……

在实际应用中，还有其他要点需要注意，这种方法并没有这样简单。

参见：en.wikipedia.org/wiki/RSA_(cryptosystem)

还值得注意一点，在实践中，RSA主要用于发送加密后的密钥给其他更简单的加密系统，通过后者发送讯息，而非通过自己发送讯息。毕竟通过RSA发送常规讯息，所需的计算时间就有点太多了。

这个故事的最后还有一段有趣的历史花絮。1973年，英国情报部门的一位数学家克利福德·科克斯提出了同样的方法，但在当时被认为不切实际。由于保密的缘故，在1997年之前，没人知道他在RSA系统上所做的工作。