Question

RSA加解密原理以及三种填充模式

Answer 1

如果需要理解RSA的加密原理，需要理解以下理论：

​ 等同于求一元二次方程 23 * d + 192 * y = 1

​ 可以求得其中一解为（d=167，y=-20）

​ 至此就完成了所有的计算

​ 对于上述例子的到公钥（221，23）和私钥（221，167）

在上述的计算过程中一共用到了

上面用到的数中只有公钥部分是公开的，即（221，23）。那么我们是否可以通过公钥来推到出私钥部分，即已知n和e，推到出d？

（1）ed 1(mod (n))，只有知道 (n)才能解出d

（2） (n)= (p) (q)= (p-1) (q-1)，只有知道p和q才能得到 (n)

（3）n=p q，就需要对n进行因式分解

那么如果可以对n因式分解就可以求出d，也就意味着私匙被破解

那么RSA加密的可靠性就在于对n因式分解的难度，而现在对一个整数n做因式分解并没有巧妙的算法，只有通过暴力破解计算。在实际应用中的n取值通常在1024位以上，而公开已知的可因式分解的最大数为768位。所以现阶段来说RSA加密是可靠的。

现在我们就可以进行加密和解密了

我们使用上面生成的公钥（221，23）来加密。如果我们需要加密的信息是m（ m必须为整数并且m要小于n ），m取56，可以用以下公式求出加密串c：

​ c (mod n)

​ 10 (mod 221)

可以求出加密后的结果c为10

密钥为（221，167），加密结果c=10，可以使用以下公式求出被加密的信息

​ m (mod n) 即加密结果的d次方除以n的余数为m

​ 56 (mod 221)

RSA加密属于块加密算法，总是在一个固定长度的块上进行操作。如果被加密的字符串过长，则需要对字符串进行切割，如果字符串过短则需要进行填充。

以下主介绍一下RSA_PKCS1_PADDING填充模式以及RSA_NO_PADDING模式

此填充模式是最常用的填充模式，在此填充模式下输入的长度受加密钥的长度限制，输入的最大长度为加密钥的位数k-11。如果公钥的长度为1024位即128字节，那么输入的长度最多为128-11=117字节。如果长度小于117就需要填充。如果输入T的长度为55字节，填充后的块为EM，则EM格式如下：

EM= 0x00 || BT || PS || 0x00 || T

在此填充模式下，输入的长度最多和RSA公钥长度一样长，如果小于公钥长度则会在前面填充0x00。如果公钥长度是128字节，输入T的长度为55字节，填充后的块为EM，则EM格式如下：

EM=P || T

参考：
http://www.ruanyifeng.com/blog/2013/06/rsa_algorithm_part_one.html
http://www.ruanyifeng.com/blog/2013/07/rsa_algorithm_part_two.html
https://my.oschina.net/3pgp/blog/749195