RSA加密算法是利用大整数分解耗时非常大来保证加密算法不被破译。
密钥的计算过程为：首先选择两个质数p和q，令n=p*q。
令k为n的欧拉函数，k=?(n)=(p−1)(q−1)
选择任意整数a，保证其与k互质
取整数b，使得a*b ≡1mod k
令公匙为a和n。私匙为p，q，b。
加密时算法为：
例如所发数位x，则所发过去的数据为 o = x^a mod n
解码时将可以得到x = o^b
正确性证明（1）：?(n)=(p−1)(q−1) 成立的正确性
?(n)表示小于n且与n互质数的个数
则小于等于n且与n非互质的数的个数为，n-?(n) = n - (p-1)*(q-1) = n - (pq-q-p+1) = n-n+p+q-1 = p+q-1
所以只要证明小于等于n且与n非互质的数的个数为p+q-1即能证明?(n)=(p−1)(q−1) ：
这点很容易证明，由于n只有两个素因子p，q。则所有与n非互质的数都可以写成p*x或q*x，对于p*x来讲，x的取值范围为1<=x<=q，对q*x来讲x的取值范围为1<=x<=p，p*x与q*x的唯一交集为p*q，所以结论成立。
加密解密算法的正确性即能保证x = (x^a)^b
了解此部分正确性首先要了解群论
由a，b的描述可知b为a在模n乘法群当中的逆元，模n乘法群的规模为?(n)，x^imodn形成一个模n乘法群的循环子群，一个群的子群的规模必为该群的约数（证明见拉格朗日定理）
原文：http://www.cnblogs.com/icodefive/p/5459655.html