1 RSA 算法概述
1．1 RSA的实现
RSA 算法，也就是加密解密的过程比较容易理解：
1.1.1 公钥密钥对的生成
a 生成两个大素数 p 和 q.
b 令 n = p * q and f(n) = (p-1) (q-1)
c 选择 b (1< b < f(n)) 使得 gcd(b, f(n))=1, 即b与f(n)互质
d 找到 a = b^(-1) mod f(n),即 a*b=1 (mod f(n))
e 结果：(n,b)为公钥对； (p,q,a) 为密钥对.
举例说明: Ⅰ. 我们选择 p=11 q=13, 则有：
n = 11*13=143
f(n)=(p-1)(q-1)=10*12=120;
Ⅱ. 选择b=37 , (我们有gcd(37,120)=1)
我们可以计算出 a=13, (有a*b=481=1 mod 120)
Ⅲ. 于是有(143,37)为公钥对；(11,13,13)为密钥对.
1.1.2 加密解密
对于任意 x,yÎZn（自然数）,依习惯, x为原文,y为密文. E( x)为加密, D(y) 为解密.
我们有E(x) = x^b (mod n) D(y) = y^a (mod n)
举例说明： 由上例，我们有原文 x=2
加密：y= x^b mod n=2^37 mod 143 = 12.
解密：x= D(y) = y^a mod n = 12^13 mod 143 =2.
显然, 实际应用时是不可能这么简单的。从公钥对 (n,b), 得到 a, p,q或是f(n) 在计算上应该是不可行的。
1.2 RSA 成立的证明
根据前面的例子，我们可以看到对于任意的x<n (实际应用中，我们把原文分成许多长度位u位的小段, 有2^u<=n, 使得x<n) , 通过加密再解密的过程都可以得到原文x, 下面给出一般性的证明：
由上，我们有： x= D(y) = D(x^b) = (x^b)^a = x^ab (mod n)
也就是说我们需要证明上式成立，即：
x ^ ab mod n = x (1)
a.首先我们有恒等式: X^(p-1) (mod p) =1, 其中p是素数，X是非零整数。
譬如有 X=3, p=7, 则有3^6 mod 7 = 729 mod 7 =1
(这个等式来自费马定理，不要再试图让我给出这个定理的证明哦！据说这个定理到现在还没有人能够完全证明.汗!对数论感兴趣的同学可以去参考[1]或是去Google搜索fermat theorem)
b. 于是我们有X^(p-1)(q-1) mod p = (X^(p-1))^(q-1) mod p = 1^(q-1) mod p=1
即 X^(p-1)(q-1) mod p=1
c. 同样对于任意整数k, 有X^k(p-1)(q-1) mod p=1
d. 上等式两端同时乘X,则有 X^(k(p-1)(q-1)+1) mod p = X
e. 即X^(kf(n)+1) mod p = X
f. 因为ab mod f(n)=1， 我们可以写成 ab = k’f(n)+1
g. 因为k和k’可以是任意整数，所以由e,f可以的到：
X^ab mod p = X
h. 同样的，我们有 X^ab mod q = X
i. 因为p,q都是素数，我们有 X^ab mod n = X. 即（1）式