介绍：本篇文章主要介绍RSA密码算法的流程、基本定理及其实现难点说明。
一.RSA密码算法
1.安全基础
RSA公钥密码体制的理论基础是数论中的大整数因子分解的困难性，即求两个大素数的乘积，在计算机上很容易实现，但是，要将一个大整数分解成两个大素数的乘积，在计算机上很难实现。
2.算法流程
注：由于现代计算机计算性能的提高，要求n的比特长度不低于512，现在使用的RSA算法中一般使用的长度一般为512/1024/2048.每次加密过程中要求明文m小于n。
3.算法证明
4.欧拉定理
5.RSA实例
二.重难点说明
1.大素数选择
在RSA算法中，p、q是两个大素数，这样就涉及到选取大素数的问题。特别的，例如在1024位的RSA算法中，我们可以设计这两个大素数分别为512位（因为两个512bit长度数的乘积为2013或1024bit，而我们需要的是1024bit，故在设计p和q时可将最高的几位固定为1，这样乘积就为1024bit了）。可以通过下面的定理证明一个整数是否为素数，
2.公私钥产生
1）公钥产生
我们生成公钥e时，要求e与n的欧拉函数φ（n）互素，我们可以通过欧几里得算法验证互素与否。也可以通过构造一个一个素数e，因为e与非倍点的任何数都是互素的，故是符合要求的。
while(b!=0)
{r = a % b;a = b;b = r;
}
//最终的a即为原a,b最大公约数
2）私钥产生
私钥d符合要求d = e^(-1)modφ(n)，求逆可以通过拓展欧几里得算法求得。
int exGcd(int a,int b,int &x,int &y)
{if(b==0){x = 1;y = 0;return a;}int r = exGcd(b,a%b,x,y);t = x; x = y;y = t-a/b*y;return r;
}
3.加解密
1）加密
在加密过程中，加密者是不知道n的分解因子p、q，故无法使用中国剩余定理，只能通过常规的模幂运算。
2）解密
方法1：和加密流程一样，使用常规的模幂运算求解。
方法2：基于中国剩余定理（CRT）求解
m = c^d mod n，n = pq，这样就可以通过中国剩余定理将其变换为求解m，使得m = c^d mod p,且m = c^d mod q，这样就可以通过中国剩余 定理来求解。
中国剩余定理
通俗写法
拓展：拓展中国剩余定理
注：本文档部分参考自别的博客，侵删。
