一. RSA算法
首先，找到三个数，p，q，r，
其中，q是两个不同的素数，r是(p-1 ) ) ) q-1 )和q-1 )互为素数
p，q，r的3个数为private key
接着，找到m以使RM==1mod(p-1 ) ) q-1 )
这个m一定存在。 r与(p-1 ) ) ) q-1 )互质，因此可以通过辗转相除得到
然后计算n=pq
m、n这两个数是公共密钥
在数据为a的情况下，编码过程将其视为大整数，假设a‘n’
a ) )=n，则a为s进制表示(s(=n，通常为s=2^t )，
各位将小于n，并进行分段
然后计算b==a^m mod n，(0(=b ) n )，
b是编码数据
解码的过程包括计算c==b^rmodpq(0(=c ) pq )，
因此，解码完成后，证明c和a实际上相等：)
如果第三者进行窃听，他会得到一些数。 m、n(=pq )、b
如果他要解码，就必须想办法得到r
所以，他必须先对n进行质因数分解
防止他分解的最有效的方法是找到两个非常大的素数p，q
让第三者进行因数分解很难
《定理》
在p、q为不同素数的情况下，RM==1mod(p-1 ) ) q-1 )，
a是任意正整数，b==a^m mod pq，c==b^r mod pq，
c==a mod pq
证明的过程，利用费马小定理，叙述如下。
m是任意素数，n是任意整数，n^m==n mod m
(换句话说，如果n和m互为素，则n^(m-1 )==1 mod m ) )。
运用一些基本的群论知识，可以很容易地证明费马小定理
《证明》
RM==1mod(p-1 ) ) q-1 )，因此RM=k ) p-1 ) ) q-1 )。 这里，k是整数
因为在modulo中是preserve乘法
(x==y mod z and u==v mod z=) xu==yv mod z )，
因此，c==b^r==(a^m ) r==a^ ) RM )==a^ ) k(p-1 ) ) q-1 )1) mod pq
1.A既不是p的倍数也不是q的倍数时，
a^(p-1 )==1 mod p )费马定理((a^ ) k ) p-1 ) (q-1 )==1 mod p
a^(q-1 )==1 mod q )费马定理((a^ ) k ) p-1 ) (q-1 ) )==1 mod q
因此，p、q都可以被a^(k(p-1 ) (q-1 ) ) (pq|a ^ (k (p-1 ) (q-1 ) ) ) )1)整除
即，a^(k ) p-1 (q-1 ) )==1 mod pq
=c==a^(k(p-1 ) ) q-1 )1)==a mod pq
2 .如果a是p的倍数，不是q的倍数，则为、
那么a^(q-1 )==1 mod q )费马小定理() ) ) )。
=’a ^ (k (p-1 ) q-1 ) )==1 mod q
=c==a^(k(p-1 ) ) q-1 )1)==a mod q
q | c - a
原因p | a
=c==a^(k(p-1 ) ) q-1 )1)==0 mod p
p | c - a
因此，pq|c-a=’c==amod pq
3 .如果a是q的倍数但不是p的倍数，则证明同上
4 .如果a同时为p和q的倍数，则、
那么pq | a
=c==a^(k(p-1 ) ) q-1 )1)==0 mod pq
pq | c - a
=) c==a mod pq
首先是密钥对的生成。
)1)选择两个大素数p和q )现在，两个数的长度都接近512bit是安全的)。
)2)计算乘积n=p*q，(n )=(p-1 ) q-1 )。 在此，) n是n的欧拉函数) )因为两个素数之积的欧拉函数等于两个数分别减去1的积)。
)3)随机选择整数e(1) e“”n )作为公钥d，要求e和) n的最大公约数为1，即满足两者为素数
(4)用Euclid扩展算法计算私钥d，满足d*e1 ) mod(n ) )即de^(-1 ) mod(n ) )。 e和n是公钥，d是私钥
注意： e和n必须公开。 两个素数p和q不再需要，可以丢弃，但不能遗漏。