天才一秒记住【狂风中文网】地址：https://www.kfzw.net
为了说明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）中发表的欧几里得算法，求解这个方程是很容易的，这并不困难。
麻烦的地方在于，除非你知道p和q中至少一个，否则不可能准确地找到那个要解的方程。
这便是挡在伊芙道路上的障碍。
我们可以再进一步解释，以上涉及的数如何在这个系统中各司其职。
首先，很明显鲍勃一开始就面临着一个大问题，m很大，n更是可怕（在200位数字这个量级上）。
即便e的值不那样夸张，me也是极其大的。
计算出它之后，我们还得将me除以n来得到余数r，这代表了被加密的文本。
这些计算太过繁杂，以至于看起来也许并不可行。
我们需要意识到，即使现代计算机异常强大，它们还是有能力极限。
当计算涉及很高次的幂，就可能会超过任何计算机处理能力的极限。
我们不能假设电脑可以在短时间内完成任何我们交给它们的计算任务。
鲍勃有根救命稻草——他完全可以不做很长的除法就找到要求的余数r。
实际上，余数仅仅取决于余数。
这里我们举一个例子来说明：739的最后两位是多少？（换句话说，当这个数被100除后余多少？）为了回答这个问题，我们可以从计算7的前几次幂开始：71=7，72=49，73=343，74=2401，75=16807，…。
不过很快我们就发现，离739还远着的时候，这些数已经变得相当大，我们都处理不过来了。
另外，随着我们算出一个又一个幂次，一个关键的规律出现了。
当计算连续的幂次时，结果的最后两位数字仅依赖于前一个数的最后两位。
这是因为我们做乘法时，百位及以上的数字并不会影响到结果在个位和十位上的数字。
本章未完，请点击下一章继续阅读！若浏览器显示没有新章节了，请尝试点击右上角↗️或右下角↘️的菜单，退出阅读模式即可，谢谢！