RSA加密

RSA加密算法是一种非对称加密算法，所谓非对称，就是指该算法加密和解密使用不同的密钥，即使用加密密钥进行加密、解密密钥进行解密。在RSA算法中，加密密钥（即公开密钥）PK是公开信息，而解密密钥（即秘密密钥）SK是需要保密的。加密算法E和解密算法D也都是公开的。虽然解密密钥SK是由公开密钥PK决定的，由于无法计算出大数n的欧拉函数phi(N)，所以不能根据PK计算出SK。

也就是说，对极大整数做因数分解的难度决定了RSA算法的可靠性。理论上，只要其钥匙的长度n足够长，用RSA加密的信息实际上是不能被解破的

加密过程

RSA的加密过程可以使用一个通式来表达：

也就是说RSA加密是对明文的E次方后除以N后求余数的过程。从通式可知，只要知道E和N任何人都可以进行RSA加密了，所以说E、N是RSA加密的密钥，也就是说E和N的组合就是公钥，我们用(E,N)来表示

解密过程

RSA的解密同样可以使用一个通式来表达：

也就是说对密文进行D次方后除以N的余数就是明文，这就是RSA解密过程。知道D和N就能进行解密密文了，所以D和N的组合就是私钥，我们用(D,N)来表示

密钥生成

公钥是（E，N），私钥是（D，N），所以密钥对即为（E，D，N）

密钥生成分为以下几个步骤

1、求N

准备两个互质数p，q。这两个数不能太小，太小则会容易破解，将p乘以q就是N

如果互质数p和q足够大，那么根据目前的计算机技术和其他工具，至今也没能从N分解出p和q。换句话说，只要密钥长度N足够大（一般1024足矣），基本上不可能从公钥信息推出私钥信息

N = p * q

2、求L

L 是 p－1 和 q－1的最小公倍数，可用如下表达式表示

L = lcm（p－1，q－1）

3、求E

E必须满足两个条件：E是一个比1大比L小的数，E和L的最大公约数为1(即E和L互质)

用gcd(X,Y)来表示X，Y的最大公约数则E条件如下：

1 < E < L

gcd（E，L）=1

之所以需要E和L的最大公约数为1，是为了保证一定存在解密时需要使用的数D。现在我们已经求出了E和N也就是说我们已经生成了密钥对中的公钥了

4、求D

数D是由数E计算出来的，数D必须保证足够大。D、E和L之间必须满足以下关系：

1 < D < L

E＊D mod L ＝ 1

其他需要考虑的

质数的选择

要使用概率算法来验证随机产生的大的整数是否是质数，这样的算法比较快而且可以消除掉大多数非质数。。假如有一个数通过了这个测试的话，那么要使用一个精确的测试来保证它的确是一个质数。除此之外这样找到的p和q还要满足一定的要求，首先它们不能太靠近，此外p-1或q-1的因子不能太小，否则的话N也可以被很快地分解

寻找质数的算法不能给攻击者任何信息，要求是随机和不可预测

加密的系统不要具备解密的功能

公钥加密，私钥解密。加密的系统和解密的系统分开部署，加密的系统不应该同时具备解密的功能，这样即使黑客攻破了加密系统，他拿到的也只是一堆无法破解的密文数据。否则的话，你就要考虑你的场景是否有必要用 RSA 了

密钥的长度

密钥长度越大，生成密文的长度也就越大，加密的速度也就越慢，而密文也就越难被破解掉。我们必须通过定义密钥的长度在"安全"和"加解密效率"之间做出一个平衡的选择

生成密文的长度和明文长度无关，但明文长度不能超过密钥长度

RSA加密算法的缺点

（1）产生密钥很麻烦，受到质数产生技术的限制，因而难以做到一次一密；

（2）运算速度慢：由于进行的都是大数计算，使得RSA最快的情况也比DES慢上好几倍，无论是软件还是硬件实现，速度一直是RSA的缺陷，所以一般只用于少量数据的加密。RSA的速度是对应同样安全级别的对称密码算法的1/1000左右 一般使用对称算法来加密数据，然后用RSA来加密对称密钥，然后将用RSA加密的对称密钥和用对称算法加密的消息发送出去。这样一来对随机数的要求就更高了，尤其对产生对称密码的要求非常高，因为否则的话可以越过RSA来直接攻击对称密码