天才一秒记住【狂风中文网】地址：https://www.kfzw.net
应用欧几里得算法于φ（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卷。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！