千米小说网

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

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

比如，要找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能帮助爱丽丝解密信息，其原因可以归结为模算术（modulararithmetic）的特性，以及当de除以k=φ（n）时余1这一事实。爱丽丝计算（me）d=mde模n。现在de具有1+kr的形式，这里r是某个整数。正如之前解释的那样，mk除以n余1，这通常被称为欧拉定理（Euler’sTheorem），而这对于（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加密背后的关于数的理论保证了系统的可靠性。当然，要保证系统的完整，还需要遵守很多这里没有解释的协议。可能出现的问题包括身份验证（authenti）（假如伊芙伪装成鲍勃联系爱丽丝怎么办？）、不可抵赖性（ion）（假如鲍勃装作伊芙发送了信息给爱丽丝怎么办？）以及身份欺诈（identityfraud）（假如爱丽丝滥用鲍勃发给她的保密的身份信息，试图在网上假扮他怎么办？）。另外，当可预测的或者重复的信息大量出现，这个系统的其他弱点也可能会暴露。不过，这些困难在任何公开密钥加密系统中都可能出现。它们是可以被克服的，并且总体来说与背后的数学技术没有太大关系，而那些数学技术才是保证加密的高质量和稳定性的因素。

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

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

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

[2]　一般称为TheElementsofEuclid，共有13卷。