简介：不羁将在本文中介绍RSA的原理，但与其他的讲解不同的是，本文是循着发明者的思路，一步步来得出RSA算法的。这种方式更有助于理解。
朋友勿笑，亦勿怒。
这里的标题用了“重新发明”这个词，其实代表的是，假设我们回到了上世纪70年代，在RSA非对称加密算法被发明之前，我们该怎么思考才能发明出RSA算法呢？当然了，现在RSA已经被发明出来了，我们这里不免还是会受到它的影响，但我们这里将试图循着发明人的思路，一点点推导出RSA算法。
我学习一样东西，比较喜欢这种从未知到探索出一个解决方案的过程；可惜目前国内的学习资料，不管是哪个方面的(特别是教材里面的知识)，都是先告诉你个结果，然后去证明这个结果，少了很多在摸索中思考的乐趣。
好了，言归正传。
目标
我们先从思考如何实现一个非对称加密算法开始。我们希望的达到的目的是，我们有一对公钥和私钥，公钥是可以公开出去，私钥是保密的，别人要发给我一段不想让外人窃取的信息的时候，可以先用我的公钥加密，我们把加密后的消息称为密文，然后我收到密文之后，用我的私钥解密，即可变为明文；而且要保证无法从公钥推导出私钥，这样，即便密文消息即便被黑客截获了，因为Ta没有私钥，就无从得到明文，从而起到保密的作用。
初步方案
我们给出的方案需要满足如下特性：
- 无法从密文得出明文
- 私钥可以解密密文得到明文
- 无法从公钥得出私钥
也就是说，我们先从第一个特性开始，假设我们密文是m, f是加密函数，c代表密文，e代表公钥，那么我们需要一个这样的f，满足:
f(m, e) = c，并且通过m,e很容易得到c, 而无法通过c得到m。
也就是说，f必须是一个单向函数，正向求解容易，而反向求解很难。
那么什么样的f才能满足这个要求呢？
这时，突然灵光一闪，有这么一个求余的函数出现了:
m^e = c (mod\ N)，N是一个正整数常量。
这个函数的意思是m^e除以N得到的余数与c除以N得到的余数相同。我们发现，当给定m,e,N的时候，比较容易得到c，但如果给定c,e,N，则很难得到m，因为要做到这一点，我们只能使用穷举法一个个去试，当N和e都很大的时候，穷举法的计算量就大的惊人了，当N,e大到一定程度的时候，也就是从c得到m需要的运算时间很长很长的时候，我们就可以认为不可能从c得到m。
第一个特性解决了，那么如何满足第二个特性（私钥可以解密密文得到明文）呢？
如何从密文得到明文呢？我们用d表示私钥，那么要满足第二个特性，如果利用同样的函数，也就是要满足：
c^d = m (mod\ N)，我们把c = m^e (mod\ N)，带入进去，从而得到:
(m^e)^d = m (mod\ N)，也就是：
m^{ed} = m(mod\ N)，这个式子又等价于：
m^{ed-1} = 1(mod\ N)
注意，上面的推导中，我们用到了如下数学事实：
m^e = c (mod\ N) 等价于 c = m^e (mod\ N)
再来看下我们得到的结果:
m^{ed-1} = 1(mod\ N)
于是，只要我们能在e和d之间建立联系，使得上面的式子成立，那么我们就可以用(e,N)作为公钥，(d,N)作为私钥。如此别人用(e,N)对明文m加密之后得到密文c，我们就可以用私钥d做这个操作c^d(mod\ N)进行解密了。
那么我们该如何使得m^{ed-1} = 1(mod\ N)成立并且满足特性三(无法从公钥e得出私钥d)的要求呢？
救星：欧拉公式
先看如何满足m^{ed-1} = 1(mod\ N)，最简单的情况是让ed=1，但是这样的话，要么e=d=1或者-1，要么其中一个是小数；前者将导致起不到加密的作用，后者将会面临小数运算误差的问题。
看来让ed=1是行不通的。
再一次灵光闪，这个形式和欧拉公式特像，看下欧拉公式：
m^{\phi(N)} = 1 (mod\ N)
是不是仿佛看到了救星。
我们从欧拉公式开始：
m^{\phi(N)} = 1 (mod\ N) 等价于 (m^{\phi(N)})^k = 1^k (mod\ N)，k是任意的整数
也就是:
m^{k*\phi(N)} = 1 (mod\ N)
也就是说我们只需要让ed满足ed -1 = k*\phi(N)即可， 这样就可以计算d了：
d = (k*\phi(N) + 1)/e。
那么\phi(N)是什么呢？怎么求呢？根据欧拉定理中对\phi(N)的定义，它代表1~N中，所有与N互质的数的数量。所谓互质，是指两个数除了1之外没有其他公因子，比如9和4互质，7和6互质等。很容易得出，对于质数X而言，\phi(X) = X - 1，因为任何一个比它小数都和它互质。
又遇拦路虎
然而，欧拉定理有一个前置条件，即：m必须与N互质。可是，m代表的是消息，我不能对m做任何限定，所以我们只能从N入手。
先来个最简单的，让N为质数，这样的话，无论m是什么，m和N都互质了，如此\phi(N)也简单了，等于N-1，可这就有问题了：
别人根据我们的公钥(e,N)很容易就能计算出\phi(N)，于是很容易就能得到我们的私钥d了。看来这个方案不行。
看来既要满足m和N互质，还要满足难以计算出\phi(N)才行，不容易啊
柳暗花明
我们再试试其他方法。嗯，N是质数，会使得\phi(N)太容易计算，那我们只能允许m和N不互质了，只要不互质的概率比较小就行。于是，我们不让N单独作为一个质数了，我们把N表示成两个质数p和q的乘积，这样，除非m=hp或者m=hq，否则m与N仍是互质的；而当m=hp或者m=hq时，即便欧拉定理不满足了，我们也可以重新选择p和q，这个计算量不大。因为N=p*q，而且p,q都是质数，所以：
\phi(N) = \phi(p) * \phi(q)
这个式子根据\phi(N)的定义，也是可以想到的，这里就不再证明了。考虑p,q都是质数，所以\phi(p) = p-1, \phi(q) = q -1，所以\phi(N) = (p-1)*(q-1)
好，那我们看看这个时候，黑客如何通过公钥(e,N)计算\phi(N)，他有两种办法：
- 把N进行质数分解
- 从1~N中，依次检查是否与N互质
当N很大的时候，这两种方案的计算量都会大的惊人。
因而这个方案是安全的。
自此，我们已经得出了RSA的方案了，还差一点需要确认：
当m=hp或者m=hq的时候，m^{ed-1} = 1(mod\ N)还成立吗？
如果成立，就太好了，我们就不用根据m的取值来调整p和q的取值了。
我们来分析一下：
假设m= hp，因为p和q是质数，所以h和p也必然互质，所以由欧拉定理知：
(hp)^{q-1} = 1 (mod\ q)
进一步得到：
[(hp)^{q-1}]^{k(p-1)} × hp ≡ hp (mod\ q)
即：
(hp)^{ed} ≡ hp (mod\ q)
将它改写成下面的等式:
(hp)^{ed} = tq + hp
因为p互质，这时t必然能被p整除，因而t = t'p，因而：
(hp)^{ed} = t'pq + hp
因为 m=hp，n=pq，所以
m^{ed} = m (mod\ n)
等价于
m^{ed-1} = 1 (mod\ n)
所以，当m=hp或者m=hq的时候，m^{ed-1} = 1(mod\ N)依然成立。
完美结局。
自此我们就得到的RSA加密算法了。其实不难，对吧？
总结
总结上面得出的RSA过程如下：
选取两个正的大质数p, q，然后计算出N，以及\phi(N) = (p-1)*(q-1)，然后随机选取一个正整数e, 然后在计算出
d = (k*\phi(N) + 1)/e
由此得出公钥(e, N)和私钥(d, N)，p和q就可以丢弃掉了，但不能泄漏出去。
从明文m到密文c(也即加密)的过程：
c = m^e(mod\ N)
从密文c到明文m(也即解密)的过程：
m=c^d(mod\ N)
