五二小说网

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

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

为了满足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卷。