牛易疯先森的开发记录
0%

浅谈 RSA

发表于 分类于

上篇文章中讲到了密码学的相关知识，今天来简单谈谈 RSA。之前有提到过，对称密码通过将明文转换为复杂的形式来保证其机密性的，而公钥密码则是基于数学上困难的问题来保证机密性的。 RSA 就是利用了大整数的质因数分解问题的困难度。在谈它之前，我们先来谈谈时钟（只有指向小时的一根指针）运算。

时钟运算

我们来想想指针的转动，运用加、减、乘、除、乘法、对数处理一下。

加法

假设现在时钟的指针指向 0，往右转一个刻度就是 1，再转一个刻度就是 2，以此类推，当转到 10、11 之后，就会回到 0，这样指针就转了整整一圈。如果现在指针指向 8，向右转动 20 个刻度是多少呢？按照常识可知，不是指向 28，而是 4，因为每隔 12 就会回到 0，所以为 4，计算方法为：(8+20) / 12 = 28 / 12 = 2 余 4。上面的例子就是求余数，只要求得除以 12 的余数，无论时钟转了多少刻度，我们就能算出它最终指向哪个位置。在数学中，除数求余数的运算有个一个运算符： mod 。 所以上面的例子可以写成：28 mod 12 = 4， 28 除以 12 的余数。在数学上，也称28 与 4 以 12 为模同余。

减法

减法可以看做是时钟向左转动。我们先规定指针不能左转，只能右转。那么(8+x) mod = 0， 8 加上多少除以 12 的余数为 0 ？ 因为 x 只能为 0,1,2...11，不可能为 -7，我们将候选值一个一个的试，可以知道x = 5，5 这个数字，在时钟运算中和 -7 是等价的。这里我们将减法转换为加法了，将指针向左转动 X 个刻度和将指针向右转动 Y 个刻度这两个操作是等价的。

乘法

乘法其实相当于加法的多次运算：8 * 4 mod 12 = 32 mod 12 = 8。

除法

减法是加法的逆运算，除法是乘法的逆运算。先看看：7 * x mod 12 = 1，我们将 0,1,2...11 一个一个代入 x 可知，x = 7。也就是：7 * 7 mod 12 = 1，也就是在 mod 12 的世界中， 7 * 7 = 1，也就是 1 / 7 = 7。再来看看这个算是：x * y mod 12 = 1，在 mod 12 的世界中， x 与 y 互为倒数。那么在 0,1,2...11 中，是不是每一个数都存在相对应的倒数呢？实际上，时钟运算中某个数是否存在倒数这个问题，与 RSA 中一个公钥是否存在相对应的私钥这个问题是直接相关的。我们来看看 0,1,2...11 中的情况

1
2
3
4
5
6
7
8
9
10
11
12
 0 * x mod 12 = 1, 不存在，不管 x 为多少都为 0。
 1 * x mod 12 = 1, 不存在，注意 x 也只能为 `0,1,2...11` 中的数
 2 * x mod 12 = 1, 不存在
 3 * x mod 12 = 1, 不存在
 4 * x mod 12 = 1, 不存在
 5 * x mod 12 = 1, x =  5
 6 * x mod 12 = 1, 不存在
 7 * x mod 12 = 1, x =  7
 8 * x mod 12 = 1, 不存在
 9 * x mod 12 = 1, 不存在 
10 * x mod 12 = 1, 不存在
11 * x mod 12 = 1, x = 11

我们上面的关系，我们推断出：在 mod 12 的世界中，存在倒数的数，它们和 12 之间的最大公约数是 1。所以，某个数是否存在倒数，可以通过这个数和 12 的最大公约数是否为 1 这个条件来进行判断。和 12 的最大公约数为 1 的数（5、7、11），在数学上称为和 12 互质的数，也可以理解为相对于 12 的质数。

乘方

指数运算。举个例子吧：

1
2
3
4
5
6
7^4 mod 12 
= ( 7 * 7 * 7 * 7 )mod 12 
= (7 * 7 mod 12) * (7 * 7 mod 12) mod 12 
= (49 mod 12) * (49 mod 12) mod 12 
= (1 * 1) mod 12 
= 1

这里中间步骤求 mod 的方法，可以避免计算大整数的乘积，RSA 中加密和解密也是用的这种方法。

对数

乘法的逆运算称为对数。时钟运算中的对数称为离散对数。我们来求下：7^x mod 13 = 8，我们将 0,1,2...12 代入 x 中算一下：

1
2
3
4
5
6
7
8
9
10
7^0 mod 13 = 1
7^1 mod 13 = 7
7^2 mod 13 = 10
7^3 mod 13 = 5
7^4 mod 13 = 9
7^5 mod 13 = 11
7^6 mod 13 = 12
7^7 mod 13 = 6
7^8 mod 13 = 3
7^9 mod 13 = 8

当数字很大时，求离散对数非常困难，也非常耗时。能快速求出离散对数的算法到现在还没发现，RSA 就是利用了这一点。 Diffie-Hellman 密钥交换协议（下篇博文会简单介绍）和 ElGamal 公钥算法中也用到了离散对数。

RSA

RSA 的加密公式为：密文 = 明文^E mod N。解密公式为：明文 = 密文^D mod N。其中 E 是加密(Encryption)的首字母，D 是解密(Decryption)的首字母，N 是数字(Number)的首字母。E 和 N 的组合就是公钥，当然 E 和 N 不是什么随便的数字，它们是经过严密计算得到的。D 和 N 的组合就是私钥，加密和解密中的 N 是相同的，并且 D 也不是什么随便的数字，它和 E 有着相当紧密的关系，否则用 E 加密的结果用 D 来解密是无法实现的。

生成密钥对

我们只要求出 E、D 和 N 就能生成密钥对。它的步骤如下：

  • 求 N
    我们先得准备两个很大的质数 p 和 q。如果 p 和 q 太小的话，密码会很容易被破译，太大的话计算时间又会变得很长。例如，假设 p 和 q 都是 512 比特，它们相对于 155 为的十进制（2^512 约等于 10^155）。 
    1
    N = p * q
  • 求 L（L 仅在生成密钥对的过程中使用）
    L 是 p-1 和 q-1 的最小公倍数(least common multiple, lcm)。 
    1
    L = lcm(p-1,q-1)
  • 求 E
    E 是一个比 1 大、比 L 小的数，此外， E 和 L 的最大公约数(greatest common divisor, gcd)必须为 1，这里是为了保证一定存在解密时需要使用的 D，之前在讲时钟运算减法的时候有提到。 
    1
    2
    1 < E < L
    gcd(E,L) = 1
  • 求 D
    D 需要满足以下条件
    1
    2
    1 < D < L
    E * D mod L = 1
    其中 p、q、E 都需要用伪随机数生成器生成。

实践

我们用具体的较小的数实践一下一下吧

  • p = 17, q = 19, 两个都是质数
  • N = 17 * 19 = 323
  • L = lcm(p-1,q-1) = lcm(16,18) = 144
  • 求 E，gcd(E,L) = 1，满足条件的有5，7，11，13，17，19，23，25，29，31，... 这些数称为和 L “互质的数”，也就是相对于 L 是质数，所以 25 也是可以的。我们选择 5 为 E 吧，公钥就是 (E,N)=(5,323)，它是公开的。
  • 求 D，E * D mod L = 1, 5 * 29 mod 144 = 145 mod 144 = 1，那么就取 29 为 D 吧，私钥就是 (D,N)=(29,323)，它必须要妥善保管，不能告诉任何人。

加密

注意，要加密的密文必须是小于 N 的数，这是因为在加密和解密过程中都需要执行mod N操作，而mod N的结果必然小于 N，所以如果明文本身大于 N，那么解密后就无法得到正确的明文。我们就取明文为 123 吧，根据加密公式：密文 = 明文^E mod N 。 123^5 mod 323 = 225，因此密文是 225。

1
2
3
4
5
6
= ((123 mod 323) * (123 mod 323) * (123 mod 323) * (123 mod 323) * (123 mod 323)) mod 323
= (123 * 123 * 123 * 123 * 123) mod 322 (wtf?没有变化，再来)
= ((123^2 mod 323) * (123^2 mod 323) * (123 mod 323)) mod 323
= (271 * 271 * 123) mod 323
= 9033243 mode 323
= 225

我们发现123 323 271都是质数，质数A mod 质数B = 质数A，质数真的是个有意思的东西。

解密

明文 = 密文^D mod N = 225^29 mod 323 = 123。

对 RSA 的攻击

任何密码总有一天会被破解的，只是时间问题而已。那来谈谈怎么破解 RSA，密码破译者知道的信息有：密文、E、N，不知道的有：明文、D、p、q、L。

通过密文来求得明文

RSA 的加密过程为：密文 = 明文^E mod N。既然密文、E、N都知道了，那有没有一种方法能够求出密文呢？如果没有 mod N 即密文 = 明文^E的话，这就是个求对数的问题，难道不大。加上 mod N 后，就变成了求离散对数的问题了，这是非常困难的，目前还没发现求离散对数的高效算法。PS：至于更深入的问题讨论，不是搞数学的就没啥必要去深究了，攻城狮还有很多事情要做。

通过暴力破解找出 D

当 D 足够长时，是不可能在现实的时间内通过暴力破解找出 D 的。现在，RSA 中所使用的 p 和 q 都是 1024 长度以上，那么 N 的长度为 2048 以上，E 和 D 的长度和 N 差不多，所以要找出 D，就需要进行 2048 以上的暴力破解(2^2048 = 10 ^x，自己算是 x 是多少吧)。

通过 E 和 N 找出 D

E 和 D 的关系：E * D mod L = 1，而 L 为：lcm(p-1,q-1)，所以通过 E 计算 D 需要求出 p 和 q，所以质数 p 和 q 不能被密码破译者知道。当然密码破译者也可以通过下面的方法来求出 p 和 q。

  • 对 N 进行质因数分解。所以一旦发现了对大整数进行质因数分解的高效算法，那么 RSA 就能够被破解。而问题是现在还没发现，而且也尚未证明质因数分解是否真的是非常困难的问题，甚至也不知道是否存在一种质因数分解的简单方法。
  • 通过推测 p 和 q 进行攻击。由于 p 和 q 是通过伪随机数生成器产生的，如果伪随机数生成器的算法很差的话，那么就有可能推测出 p 和 q 来。

中间人攻击

中间人攻击(man-in-the-middle attack)，就是攻击者混入发送者和接收者之间，对发送者伪装成接收者，对接收者伪装成发送者的攻击方式。这种攻击不仅针对于 RSA ，而是可以针对任何公钥密码，这个需要证书防御。

对 RSA 的 Q&A

下面来说说关于 RSA 的一些比较重要的问题。

RSA 与质数

Q: 越来越多的人生成 RSA 密钥对，质数会不会用光？
A: 这个不需要担心，来看看一组数据吧。512 比特能够容纳的质数的数量大约为 10 的 150 次方(2^512 约等于 10^150)，这个数量比整个宇宙中原子的数量还要多。我们现在来做个假设吧，如果现在地球上 100 亿人，每个人每秒中生成 100 亿个密钥对，那么经过 100 亿年会生成多少对呢？

1
2
3
4
5
6
7
1 年最多 365 天，也就是 366 * 24 * 60 * 60 = 31622400 秒

100 亿人 * 100 亿个 * 31622400 秒 * 100 亿年 
= 31624400*(100*100000000)^3 
= 31624400 * (10^10)^3 
= 31624400 * 10^30 
= 3.16244 * 10^37

3.16244 * 10^37 比 10^150 差远了，所以不用担心，当然，质数组合偶然碰撞的可能性还是存在的，不过事实上也可以忽略咯。

RSA 的长度

Q: 要抵御质因数分解，N 的长度需要达到多少比特？
A: N 无论有多长，总有一天都能够被质因数分解，现在的问题是，在现实的时间内 N 是否能够被质因数分解。当然，随着计算机性能的提高，分解的时间会进一步缩短。目前能够分解的长度为 1024 比特的整数，目前 RSA-2048（617位）的整数应该是不大可能被分解的。

1
2
3
4
5
6
7
计算方法为 2^RSA长度 = 10^位
RSA-512		155
RSA-640		193
RSA-768		232
RSA-1024	309
RSA-1536	463
RSA-2048 	617

这里有趣的现象叫做密码劣势：随着计算机技术的进步等，以前被认为是安全的密码会被破译。

总结

这里只简单地讲述了 RSA 的加密功能，它可以用来数字签名，相信你会看到过RSASHA1吧，下次有机会再谈。

**转载请注明出处！http://joakimliu.github.io/2017/08/17/浅谈-RSA/ 谢谢！ **