RSA算法原理介绍

前置知识

质数

质数又称素数，指在大于1的自然数中，除了1和该数自身外，无法被其他自然数整除的数（也可定义为只有1与该数本身两个正因数的数）。大于1的自然数若不是素数，则称之为合数（也称为合成数）。最小的质数为2。

互质关系

如果两个正整数，除了1以外，没有其他公因子，我们就称这两个数是互质关系（coprime）。比如，15和32没有公因子，所以它们是互质关系。这说明，不是质数也可以构成互质关系。

关于互质关系，不难得到以下结论：

1. 任意两个质数构成互质关系，比如13和61。important

2. 一个数是质数，另一个数只要不是前者的倍数，两者就构成互质关系，比如3和10。

3. 如果两个数之中，较大的那个数是质数，则两者构成互质关系，比如97和57。

4. 1和任意一个自然数是都是互质关系，比如1和99。

5. p是大于1的整数，则p和p-1构成互质关系，比如57和56。 important

6. p是大于1的奇数，则p和p-2构成互质关系，比如17和15。

生成RSA密钥对，即公钥和私钥

1：随机找两个质数 p 和 q ,p 与 q 越大，越安全。

比如 p = 3 ，q = 11。这里为了方便后面计算，选了2个很小的质数，实际应用需要选择两个非常大的质数。

2：计算p和q的乘积n。

计算他们的乘积 n = 3 * 11 = 33 ，转化为二进制 10 0001，该加密算法即为 6 位，实际算法是 1024 位或 2048 位，位数越长，算法越难被破解。

3：计算 n 的欧拉函数 φ(n)。

φ(n) 表示在小于等于 n 的正整数之中，与 n 构成互质关系的数的个数。例如：在 1 到 8 之中，与 8 形成互质关系的是1、3、5、7，所以 φ(n) = 4。如果 n = p q，p 与 q 均为质数，则 φ(n) = φ(p q)= φ(p - 1)φ(q - 1) = (p - 1)(q - 1) 。本例中 φ(3 11) = 2 * 10 = 20。

4：随机选择一个整数 e，条件是1< e < φ(n)，且 e 与 φ(n) 互质。

这里我们随机选择 e = 7 请注意不要选择19 (即φ(n) - 1)这样的边界值，容易被人破解。实际应用中，常常选择65537。

5：计算e对于φ(n)的模反元素d。

所谓“模反元素”就是指有一个整数d，可以使得e * d除以φ(n)的余数为1。

即：

1	e * d ≡ 1 (mod φ(n))

等价于：

1	e * d - 1 = kφ(n)

于是，找到模反元素d，实质上就是对下面这个二元一次方程求解。

1	ex + φ(n)y = 1

已知 e=7, φ(n)=20，

1	7x + 20y = 1

这个方程可以用“扩展欧几里得算法”求解，此处省略具体过程。总之，算出一组整数解为 (x,y)=(3,-1)，即 d=3。不同的 e 生成不同的 d，因此可以生成多个密钥对。

至此所有计算完成。

6：将n和e封装成公钥，n和d封装成私钥。

在爱丽丝的例子中，n = 33，e = 7，d = 3，所以公钥（n，e）就是 (33, 7），私钥（n，d）就是（33, 3）。

实际应用中，公钥和私钥的数据都采用ASN.1格式表达（实例）。

总结一下：

随机选择两个非常大的质数p,q—->计算p,q的乘积n——>计算φ(n)—->选择一个与φ(n)互质的整数 e——>计算e对于φ(n)的模反元素d。

得到公钥：（n，e）,私钥：（n，d）。

加密明文

公钥加密公式

　　m^e ≡ c (mod n)

也可以写为

　　c = m^e mod n

私钥解密公式

　　c^d ≡ m (mod n)

也可以写为

　　m = c^d mod n

参数说明：

m: 明文
c: 密文
n: 模数，两个很大的质数的乘积
e: 公钥指数
d: 私钥指数
(n,e) 是公钥
(n,d) 是私钥
d是e对于φ(n)的模反元素

注1：从上面的公式可以看出一个数模n，那么这个数肯定不能大于等于n，否则结果会无意义。比如n=13,那么13模上13结果为0，解密结果还是0，得不到原来的整数了。

注2：也可以使用私钥加密，公钥解密，这一过程通常称为签名。因为只有本人才有私钥，所以使用私钥加密得到的密文可以作为本人的签名。如果公钥能解开代表确实是由本人操作。

举个例子：对[6, 14, 7, 32]进行加密。应用上面的加密公式得到：

6^7 % 33 = 30

14^7 % 33 = 20

7^7 % 33 = 28

32^7 % 33 = 32

即[6, 14, 7, 32]加密后得到密文[30, 20, 28, 32]，如果没有私钥 d ,神仙也无法从密文[30, 20, 28, 32]中恢复出明文[6, 14, 7, 32]。

解密密文

应用上面的解密公式

1	m = c^d mod n

得到：

30^3 % 33 = 6

20^3 % 33 = 14

28^3 % 33 = 7

32^3 % 33 = 32

即[30, 20, 28, 32]解密后得到明文[6, 14, 7, 32]。

RSA应用

上面我们知道要想用RSA加密，需要满足两个条件：

被加密的明文必须是整数
该整数必须大于0且小于 n。这意味着一次加密的明文不能太多。所以RSA是块加密。如果要加密的明文很长则必须分块加密。

因此我们的明文需要转化为整数才能使用RSA加密，如果明文就是数字那就不用转化，如果是英文或者中文该怎么办呢？简单：各种编码方式，比如utf-8，gb2312。所以我们需要先将明文使用某种编码方式编码为数字，然后使用RSA加密。

怎么保证该整数一定小于 n呢？这个也很简单，只要明文长度小于n的长度即可。

Padding

padding就是通过一些填充方式保证明文c的位数，且不能使c大于n.

padding可以让RSA对同一明文加密的结果每次都不一样，提高安全性，因为RSA加密是确定的，即给定一个密钥，特定明文总会映射到特定的密文。攻击者可以根据密文中统计信息获取明文的一些信息。

相同的明文在不管加密多少次，它的密文都是一样的。这在密码学中是一个大忌，很容易被破解者猜到内容。对称加密算法也有这个问题，需要用添加随机初始化向量IV，以实现相同的加密请求，每一次出来的结果都要不同。所以加密系统都会采取一定的手段确保每次加密结果都不一样。

Padding填充方式：

填充方式	输入	输出
RSA_PKCS1_PADDING	必须比 RSA 钥模长(modulus) 短至少11个字节, 也就是　RSA_size(rsa) – 11	和modulus一样长
RSA_PKCS1_OAEP_PADDING	RSA_size(rsa) – 41	和modulus一样长
RSA_NO_PADDING	可以和RSA钥模长一样长，如果输入的明文过长，必须切割，然后填充	和modulus一样长

感兴趣的可以研究下padding是如何让rsa的加密结果变得随机的。简单来讲就是padding+明文组成新的明文再加密。

00 02 xx xx xx xx xx xx xx xx 00 --->padding
yy yy yy yy yy yy yy yy yy yy yy --->原始明文
yy yy yy yy yy yy yy yy yy yy yy
yy yy yy yy yy yy yy yy yy yy yy
yy yy yy yy yy yy yy yy yy yy yy
...

假如n为1024位，则一个块就是128字节，由于最高位是00，所以明文的大小肯定小于n。加密后得到密文也是128字节（不足的最高位补0），解密后根据填充规则去掉开头的11个字节得到原始明文。