1970年左右科学家们开始思考公钥加密系统的可能性。经过科学家多年的研究，终于在1977年时，来自MIT的Ron Rivest，AdiShamir和Leonard Adlemn三个人合写了一篇论文，给出了至今仍然安全的公钥加密算法，即以三个人姓氏的首字母命名的RSA算法。

RSA的过程步骤如下：

1)       找两个大质素p和q

2)       设n=p·q 算出m=(p-1)(q-1)

3)       找出e和d，使得 e·d mod = 1 （随便找出一个与m互质的数e，求解方程e·dmod = 1）

4)       把e，n作为公钥，d，n作为私钥

5)       设X为原始报文，Y为密文

则  Y=X^e mod n

X=Y ^dmod n

即某个人用公钥e和n加密后，只有拥有私钥d和n的另一个人才能进行解密。

       看以上的算法步骤你会产生很多疑问，如为什么要找两个大质素p、q；为什么需要按照(p-1) ·(q-1)算出m，然后根据e·d mod m= 1这个公式找出e和d，…等等。

RSA背后所依赖的数学定理已经存在300年以上，但是根据这么古老的定理创造RSA算法却是最近几十年的事，主要原因是随着计算机运算速度的提升以及网络的建立带来安全通讯的需求，因此开始了研究公钥算法的可行性，并终于在1977年时由MIT的三位教授发明了RSA公钥加密算法。

       由数学定理找出RSA公钥算法是一条异常曲折的道路，但是对RSA算法扩展然后用数学定理证明似乎就平坦多了。因此本文对RSA算法的详解从结果开始，然后提出疑问逐步反推并用数学定理证明，最后再回头看是如何用现存的数学定理找出RSA算法。

       我们根据RSA算法的步骤，首先列出疑问

1.     为什么X=Y ^dmod n，而Y=X^e mod n，也就是X的e次方除以n取余的值的d次方再除以n的取余又等于X了呢？

1.1    因为X^e除以n的余数（X^e mod n）的d次方再模n，相当于X^e·dmodn，证明如下：

(1)     Y=X^emod n   即是算X的e次方除以n的余，

(2)     换成公式：X^e= nx + Y    x为n的倍数

(3)     则Y= X^e – nx

(4)      Y ^dmodn = (X^e – nx)^d mod n

(5)      (X^e –nx)^d 是一个多项式，展开后除了第一项为X^e·d外，其余项都携带n，因此其余项都能被n除尽，(X^e –nx)^d mod n可以简化为X^e·dmodn

1.2   由1.1可知Y ^dmodn = (X^e – nx)^d mod n = X^e·dmodn，而为什么X^e·dmodn = X呢？

1.2.1       如果某个整数n等于两个质数p,q的乘积，那么对于任意一个整数a，写出aⁱ 依次除以n所得的余数序列，那么p-1 和 q-1的最小公倍数将成为该序列的一个周期，这是一个费马小定理的扩展。为什么p-1 和 q-1的最小公倍数将成为该序列的一个周期呢？具体证明见2节，先记住这个结论，继续往下分析。

1.2.2       m就是(p-1)和（q-1）的乘积，因此该序列的周期是m，a mod n 、a^1+mmod n 、a^1+2m mod n 和a^1+3m modn的余数都相等。

1.2.3       所以计算e·d = 1 + m、e ·d = 1 + 2m或 e ·d = 1 + 3m等的任何一个值即能保证a mod n = a^e·dmod n

1.2.4       计算e·d = 1 + m 即计算e·d mod m = 1，随便找一个与m互质的数e，然后求方程e·d mod m =1。由于e与m互质，那么e·d mod m = 1、e·d mod m = 2、e·d mod m = 3等都有解，并且在这个解的基础上加减n的倍数即为所有的解。因此对n来说，必然存在一个与e对应的解d。为什么e与m互质，就必然存在一个解d呢？具体证明见3节。

1.2.5       通过以上步骤可以看出Y ^dmod n =(X^e– nx)^d mod n = X^e·dmodn = X mod n，而X mod n等于X，因此Y^dmodn也等于X，换句话说密文Y用私钥d，n解密出原始报文X。

2       为什么n存在两个质数p和q的乘积，aⁱ 依次除以n所得的余数序列，存在为 p-1 乘以q-1的最小公倍数的一个周期

2.1   n是一个质数的话，那么对于任意一个数a，随着i的增加，a的i次方除以n的余数将会出现一个n-1的周期。具体证明见第4节。

2.2   如果n不是一个质数，而是两个质数的乘积，比如35是5和7的乘积，根据中国剩余定理(附录A)，一个数除以35的余数就可以唯一的由它除以两个乘数5和7的余数确定出来。

2.3   所以根据2.1， aⁱmod p有一个p-1的周期，aⁱ mod q有一个q-1的周期，再根据2.2，aⁱmod n的周期由n的两个质数p和q确定，因此aⁱmod p存在一个(p-1) ·(q-1)=m的周期。

3       为什么e与m互质，就必然存在一个d，使得e·d mod m = 1？

3.1   a · x mod n = b 的解，相当于寻找一个 a 的倍数使得它除以 n 余 b ，或者说是寻找一个数 M 同时满足 M mod a =0 且 M mod n = b 。

3.2   如果 a 和 n 是互质的，那么根据中国剩余定理(附录A)，这样的 M 一定存在，并且找到一个这样的 M 之后，在它的基础上加减 a · n 的整倍数，可以得到所有满足要求的 M 。

3.3   因此，为了解出方程 a · x mod n = b 的所有解，我们也只需要解出方程的某个特解就行了。假如我们找到了方程 a · x modn = b 中 x 的一个解，在这个解的基础上加上或减去 n 的倍数（相当于在整个被除数 a · x 的基础上加上或者减去 a · n 的倍数，这里的 a · x 就是前面所说的 M ），就能得到所有的解了。

(更妙的是，我们其实只需要考虑形如 a · x modn = 1 的方程。因为，如果能解出这样的方程， a · x mod n = 2 、 a · x mod n = 3 也都自动地获解了。假如 a · x modn = 1 有一个解 x = 100 ，由于 100 个 a 除以 n 余 1 ，自然 200 个 a 除以 n 就余 2 ， 300 个 a 除以 n 就余 3 ，等等，等式右边余数不为 1 的方程也都解开了。)

4       为什么n是一个质数的话，那么对于任意一个数a，随着i的增加，a的i次方除以n的余数将会出现一个n-1的周期？

4.1    1640 年，法国业余数学家 Pierre de Fermat （通常译作“费马”）发现，如果 n 是一个质数的话，那么对于任意一个数 a ， a 的 n 次方减去 a 之后都将是 n 的倍数。

4.2    4.1的费马小定理（见附录B）描述为 aⁿ-a mod n = 0；那么存在aⁿ mod n = a mod n

4.3    由于aⁱ mod n = a^i-1 · a mod n

而a^i-1 = nx + y  设x为n倍数，y为aⁱ mod n的余数

则y = a^i-1 – nx

则aⁱ = a^i-1· a = （nx + y）· a

则 aⁱ mod n = （nx + y）· a mod n

          = （anx + ay）mod n

由于anx是an的倍数，anx mod n必然等于0，所以aⁱ mod n的余数只需要求ay mod n即可，而y为a^i-1 mod n的余数。也即是aⁱmod n的余数等于a^i-1 mod n的余数乘以a再除以n的余数，换句话说aⁱ mod n的值是由a^i-1 mod n的值决定。

4.4    由4.2和4.3结合起来可知aⁱ的余数存在1到n-1的周期

附录A 中国剩余定理

中国剩余定理：给出 m 个两两互质的整数，它们的乘积为 P ；假设有一个未知数 M ，如果我们已知 M 分别除以这 m 个数所得的余数，那么在 0 到 P - 1 的范围内，我们可以唯一地确定这个 M 。这可以看作是 M 的一个特解。其他所有满足要求的 M ，则正好是那些除以 P 之后余数等于这个特解的数。注意，除数互质的条件是必需的，否则结论就不成立了。比如说，在 0 到 7 的范围内，除以 4 余 1 并且除以 2 也余 1 的数有 2 个，除以 4 余 1 并且除以 2 余 0 的数则一个也没有。

       从某种角度来说，中国剩余定理几乎是显然的。让我们以两个除数的情况为例，来说明中国剩余定理背后的直觉吧。假设两个除数分别是 4 和 7 。下表显示的就是各自然数除以 4 和除以 7 的余数情况，其中 x mod y 表示 x 除以 y 的余数，这个记号后面还会用到。

i mod 4 的值显然是以 4 为周期在循环， i mod 7 的值显然是以 7 为周期在循环。由于 4 和 7 是互质的，它们的最小公倍数是 4 × 7 = 28 ，因而 (i mod 4, i mod 7) 的循环周期是 28 ，不会更短。因此，当 i 从 0 增加到 27 时， (i mod 4, i mod 7) 的值始终没有出现重复。但是，(i mod 4, i mod 7) 也就只有 4 × 7 = 28 种不同的取值，因而它们正好既无重复又无遗漏地分给了 0 到 27 之间的数。这说明，每个特定的余数组合都在前 28 项中出现过，并且都只出现过一次。在此之后，余数组合将产生长度为 28 的循环，于是每个特定的余数组合都将会以 28 为周期重复出现。这正是中国剩余定理的内容。

附录 B 费马小定理

    费马小定理：如果 n 是一个质数的话，那么对于任意一个数 a ， a 的 n 次方减去 a 之后都将是 n 的倍数。

Fermat 小定理有一个非常精彩的证明。我们不妨以“ 37- 3 能被 7 整除”为例进行说明，稍后你会发现，对于其他的情况，道理是一样的。首先，让我来解释一下“循环移位”的意思。想象一个由若干字符所组成的字符串，在一块大小刚好合适的 LED 屏幕上滚动显示。比方说， HELLOWORLD 就是一个 10 位的字符串，而我们的 LED 屏幕不多不少正好容纳 10 个字符。刚开始，屏幕上显示 HELLOWORLD 。下一刻，屏幕上的字母 H 将会移出屏幕，但又会从屏幕右边移进来，于是屏幕变成了 ELLOWORLDH 。下一刻，屏幕变成了 LLOWORLDHE ，再下一刻又变成了LOWORLDHEL 。移动到第 10 次，屏幕又会回到 HELLOWORLD 。在此过程中，屏幕上曾经显示过的ELLOWORLDH, LLOWORLDHE, LOWORLDHEL, ... ，都是由初始的字符串 HELLOWORLD 通过“循环移位”得来的。现在，考虑所有仅由 A 、 B 、 C 三个字符组成的长度为 7 的字符串，它们一共有 37个。如果某个字符串循环移位后可以得到另一个字符串，我们就认为这两个字符串属于同一组字符串。比如说， ABBCCCC 和 CCCABBC 就属于同一组字符串，并且该组内还有其他 5 个字符串。于是，在所有 37个字符串当中，除了 AAAAAAA 、 BBBBBBB 、 CCCCCCC 这三个特殊的字符串以外，其他所有的字符串正好都是每 7 个一组。这说明， 37- 3 能被 7 整除。

       在这个证明过程中，“ 7 是质数”这个条件用到哪里去了？仔细想想你会发现，正因为 7 是质数，所以每一组里才恰好有 7 个字符串。如果字符串的长度不是 7 而是 15 的话，有些组里将会只含 3 个或者 5 个字符串。比方说， ABCABCABCABCABC 所在的组里就只有 3 个字符串，循环移动 3 个字符后，字符串将会和原来重合。

附录C SSH中的diffie-hellman公钥交换算法，以RSA公钥举例：

RSA公钥算法详解