RSA加密
一、密钥对的产生
1、选取两个素数p和q，
2、计算n=p*q。及n的欧拉函数值φ(n)=（p-1）*（q-1）
3、随机选取整数e，（1<e<φ(n)),且e和φ(n)的最大公约数为1。
4、求d。e*d=1modφ(n)。（下文有求d的一种简单算法）
5、形成密钥对。公钥{e,n},私钥{d,n}。
二、加密
加密使用公钥，c=m^e(mod n),m是明文、c是就是密文。
三、解密
解密使用私钥，m=c^d(mod n)，m就是明文，c是密文。
案例详解
1、选取两个素数p和q，
本次选取p和q分别为11,13。
2、计算n=p*q。及n的欧拉函数值φ(n)=（p-1）*（q-1）
n=11*13=143。φ(n)=10*12=120。
3、随机选取整数e，（1<e<φ(n)),且e和φ(n)的最大公约数为1。
e选取17，
4、求d。e*d=1modφ(n)。
e*d=1modφ(n)。经过等式变换e*d - k *φ(n)=1。
将e和φ(n)带入等式。比较d和k系数哪个大，大数除小数取余，并且代替大数，再次进行判断、取余，直至其中一个系数为1。结束循环进入下一步
若是d的系数为1，令k=0，求d然后替代上一个等式的d值求k，然后逐步向上替代直至求出第一个等式的d。
若是k的系数为1，令d=1，求k替代上一个等式的k值求d，然后逐步向上替代，直至求出第一个等式的d。
具体算法如下图所示
本方式分为两种情况，
5、形成密钥对。公钥{e,n},私钥{d,n}。
公钥{17,143},私钥{113,143}。
1、对明文进行加密
明文 m=24
c=m^e=24^17=7(mod 143)
2、密文进行解密
密文 c=7
m=c^d=7^113=24(mod 143)
小结
在RSA加解密算法中，有两个难点，第一就是d值的计算，我们需要找到合适方法进行快速计算出d值。其二就是在加解密中次方的值是非常大，我们同样需要找到合适方法进行快速计算。在计算过程中保证不出错。公钥加密，私钥解密，加解密的时候不要用错。