参考文献：
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
两种加密方式：对称加密和非对称加密
一.对称加密：加密解密使用同种规则（“密钥”）。
二.非对称加密：加密和解密可以使用不同的规则，只要这两种规则之间存在某种对应关系即可。
RSA算法前奏：
1.互质：两个正整数，除了1以外，没有其他公因子；
2.欧拉函数（用φ(n)表示）：任意给定正整数n，计算小于等于n的正整数之中与n构成互质关系的个数；
关于计算φ(n)：
a.如果n=1，则 φ(1) = 1 。因为1与任何数（包括自身）都构成互质关系;
b.如果n是质数，则 φ(n)=n-1 。因为质数与小于它的每一个数，都构成互质关系;
c.如果n是质数的某一个次方，即 n = pk (p为质数，k为大于等于1的整数)，则φ(pk)=pk-pk-1=pk(1-1/p);
d.如果n可以分解成两个互质的整数之积，n=p1p2,则φ(n)=φ(p1p2)=φ(p1)φ(p2);
e.因为任意一个大于1的正整数，都可以写成一系列质数的积,n=p1k1p2k2...prkr,根据d得到：φ(n)=φ(p1k1)φ(p2k2)...(prkr),再根据c得到：φ(n)=p1k1p2k2...prkr(1-1/p1)(1-1/p2)...(1-1/pr),也就等于：φ(n)=n(1-1/p1)(1-1/p2)...(1-1/pr)。
3.欧拉定理（RSA算法的核心）：如果两个正整数a和n互质，则n的欧拉函数 φ(n) 可以让下面的等式成立
aφ(n)Ξ1(mod n)
注：假设正整数a与质数p互质，因为质数p的φ(p)等于p-1，则欧拉定理可以写成
ap-1Ξ1(mod p) ......费马小定理
4.模反元素：如果两个正整数a和n互质，那么一定可以找到整数b，使得 ab-1 被n整除，或者说ab被n除的余数是1
abΞ1(mod n) ......b叫做a的模反元素,b+kn都是a的模反元素
欧拉定理证明模反元素
aφ(n)Ξ1(mod n)=aaφ(n)-1
可以看到，a的 φ(n)-1 次方，就是a的模反元素。
密钥生成步骤：
1.随机选择两个不想等的质数p和q；
2.质数相乘得n；
3.计算n的欧拉函数φ(n)，根据欧拉函数第二、四点
φ(n)=φ(pq)=φ(p)φ(q)=(p-1)(q-1);
4.随机选择一个整数e，条件是1< e < φ(n)，且e与φ(n) 互质,通常情况选65537；
5.计算e对于φ(n)的模反元素d
ed ≡ 1 (mod φ(n))
等价于
ed - 1 = kφ(n)
令d=x,k=y,可得
ex + φ(n)y = 1
已知e和φ(n),采用扩展欧几里得算法可求得一组解，即d；
6.将n和e封装成公钥，n和d封装成私钥，公钥（n,e），私钥（n,d）。
RSA算法的可靠性：密钥生成过程总共产生了6个数，分别是：p、q、n、φ(n)、e、d。公钥用到（n,e）,私钥用到（n,d），所以d是解密的关键
不妨反推：根据已知公钥的n和e，由ed ≡ 1 (mod φ(n))，要想得到d，必须得到φ(n)，又由φ(n)=(p-1)(q-1)知，要求的φ(n)，就需要知道p和q，而pq=n，所以需要将n因式分解才能得到p和q。n分解的难道决定算法的难度。
加密解密：
1.加密过程，加密用公钥（n,e）,对m进行加密
me ≡ c (mod n) ......c就是加密之后的m，m信息以c的形式传递
注：m必须是整数（字符串可以取ascii值或unicode值），且m必须小于n。
2.解密过程，解密用私钥（n,d）,对c进行解密
cd ≡ m (mod n) ......m就是解密之后的c
私密解密证明：
cd ≡ m (mod n)
根据加密规则ｍe ≡ c (mod n)，所以c = me - kn
将c代入cd ≡ m (mod n)，则
(me - kn)d ≡ m (mod n)
等同于
med ≡ m (mod n)
又由于ed ≡ 1 (mod φ(n))，所以ed = hφ(n)+1
将ed带入med ≡ m (mod n)，则
mhφ(n)+1 ≡ m (mod n)
若m和n互质
根据欧拉定理
mφ(n) ≡ 1 (mod n)
得到
(mφ(n))h × m ≡ m (mod n)
若m和n不是互质关系
由于n等于质数p和q的乘积，所以m必然等于kp或kq，根据欧拉定理，下式成立
(kp)q-1 ≡ 1 (mod q)
进一步得到
[(kp)q-1]h(p-1) × kp ≡ kp (mod q)
即
(kp)ed ≡ kp (mod q)
改写如下
(kp)ed = tq + kp
这时t必然能被p整除，即 t=t'p
(kp)ed = t'pq + kp
因为 m=kp，n=pq，所以
med ≡ m (mod n)