跨越千年的RSA算法

     个人心得：
     核心定律为费马定律：当 n = p · q（p，q为质数） ， m = (p - 1)(q - 1) ，a为小于n任意自然数，则a1+m mod n = a mod n = a
     RSA扩展：当e 乘以 d 的结果除以 m 余 1时，ae*d mod n = a mod n，即ae*d mod n = a，应用于运算e算为公钥给外界，外界加密时使用数据ae mod n = y，将原文a加密为y。私钥持有者将(y）d  mod n 即为a。
     举例：p：3，q：5，n=15，m=8，e=3（公钥），d=11（私钥）
     原文：7，公钥加密：13（Excel: =MOD(7^3,15)），解密：7（Excel：=MOD(13^11,15)）

     转载自：http://www.matrix67.com/blog/archives/5100
     数论，数学中的皇冠，最纯粹的数学。早在古希腊时代，人们就开始痴迷地研究数字，沉浸于这个几乎没有任何实用价值的思维游戏中。直到计算机诞生之后，几千年来的数论研究成果突然有了实际的应用，这个过程可以说是最为激动人心的数学话题之一。 
    ......
     首先，找两个质数，比如说 13 和 17 。实际使用时，我们会选取大得多的质数。把它们乘在一起，得 221 。再计算出 (13 - 1) × (17 - 1) = 192。根据前面的结论，任选一个数 a ，它的 i 次方除以 221 的余数将会呈现长度为 192 的周期（虽然可能存在更短的周期）。换句话说，对于任意的一个 a，a, a193, a385, a577, ... 除以 221 都拥有相同的余数。注意到， 385 可以写成 11 × 35 ……嘿嘿，这下我们就又能变数学小魔术了。叫一个人随便想一个不超过 221 的数，比如 123 。算出 123 的 11 次方除以 221 的余数，把结果告诉你。如果他的计算是正确的，你将会得到 115 这个数。看上去，我们似乎很难把 115 还原回去，但实际上，你只需要计算 115 的 35 次方，它除以 221 的余数就会变回 123 。这是因为，对方把他所想的数 123 连乘了 11 次，得到了一个数 X ；你再把这个 X 乘以自身 35 次，这相当于你们合作把 123 连乘了 385 次，根据周期性现象，它除以 221 的余数仍然是 123 。然而，计算 35 个 X 连乘时，反正我们要取乘积除以 221 的余数，因此我们不必完整地获知 X 的值，只需要知道 X 除以 221 的余数就够了。因而，让对方只告诉你 X 取余后的结果，不会造成信息的丢失。
    不过这一次，只知道加密方法后，构造解密方法就难了。容易看出， 35 之所以能作为解密的钥匙，是因为 11 乘以 35 的结果在数列 193, 385, 577, ... 当中，它除以 192 的余数正好是 1 。因此，攻击者可以求解 11x mod 192 = 1 ，找出满足要求的密钥 x 。但关键是，他怎么知道 192 这个数？要想得到 192 这个数，我们需要把 221 分解成 13 和 17 的乘积。当最初所选的质数非常非常大时，这一点是很难办到的。
    根据这个原理，我们可以选择两个充分大的质数 p 和 q ，并算出 n = p · q 。接下来，算出 m = (p - 1)(q - 1) 。最后，找出两个数 e 和 d ，使得 e 乘以 d 的结果除以 m 余 1 。怎么找到这样的一对 e 和 d 呢？很简单。首先，随便找一个和 m 互质的数（这是可以做到的，比方说，可以不断生成小于 m 的质数，直到找到一个不能整除 m 的为止），把它用作我们的 e 。然后，求解关于 d 的方程 e · d mod m = 1（就像刚才攻击者想要做的那样，只不过我们有 m 的值而他没有）。 Bézout 定理将保证这样的 d 一定存在。
    好了，现在， e 和 n 就可以作为加密钥匙公之于众， d 和 n 则是只有自己知道的解密钥匙。因而，加密钥匙有时也被称作公钥，解密钥匙有时也被称作私钥。任何知道公钥的人都可以利用公式 c = ae mod n 把原始数据 a 加密成一个新的数 c ；私钥的持有者则可以计算 cd mod n ，恢复出原始数据 a 来。不过这里还有个大问题： e 和 d 都是上百位的大数，怎么才能算出一个数的 e 次方或者一个数的 d 次方呢？显然不能老老实实地算那么多次乘法，不然效率实在太低了。好在，“反复平方”可以帮我们快速计算出一个数的乘方。比方说，计算 a35 相当于计算 a34 · a ，也即 (a17)2 · a ，也即 (a16 · a)2 · a，也即 ((a8)2 · a)2 · a……最终简化为 ((((a2)2)2)2 · a)2 · a ，因而 7 次乘法操作就够了。在简化的过程中， a 的指数以成半的速度递减，因而在最后的式子当中，所需的乘法次数也是对数级别的，计算机完全能够承受。不过，减少了运算的次数，并没有减小数的大小。 a 已经是一个数十位上百位的大数了，再拿 a 和它自己多乘几次，很快就会变成一个计算机内存无法容纳的超级大数。怎么办呢？别忘了，“反正最后都要对乘积取余，相乘之前事先对乘数取余不会对结果造成影响”，因此我们可以在运算过程中边算边取余，每做一次乘法都只取乘积除以 n 的余数。这样一来，我们的每次乘法都是两个 n 以内的数相乘了。利用这些小窍门，计算机才能在足够短的时间里完成 RSA 加密解密的过程。
    RSA 算法实施起来速度较慢，因此在运算速度上的任何一点优化都是有益的。利用中国剩余定理，我们还能进一步加快运算速度。我们想要求的是 a35 除以 n 的余数，而 n 是两个质数 p 和 q 的乘积。由于 p 和 q 都是质数，它们显然也就互质了。因而，如果我们知道 a35 分别除以 p 和 q 的余数，也就能够反推出它除以 n 的余数了。因此，在反复平方的过程中，我们只需要保留所得的结果除以 p 的余数和除以 q 的余数即可，运算时的数字规模进一步降低到了 p 和 q 所在的数量级上。到最后，我们再借助“今有物，不知其数”的求解思路，把这两条余数信息恢复成一个 n 以内的数。更神的是，别忘了， ai 除以 p 的余数是以 p - 1 为周期的，因此为了计算 a35 mod p ，我们只需要计算 a35 mod (p-1) mod p 就可以了。类似地，由于余数的周期性现象，计算 a35 mod q 就相当于计算 a35 mod (q-1) mod q 。这样一来，连指数的数量级也减小到了和 p 、 q 相同的水平， RSA 运算的速度会有明显的提升。
     ......