RSA算法原理（三）：补充知识
# 60.RSA算法原理（三）：补充知识
补充下关于RSA的更多细节
# RSA算法：公钥指数的选取
我们回顾下公私玥的生成
- 首先，Alice选择一对不相等且足够大的质数，记为p和q
- 计算pq的乘积，记为n，也就是 p × q = n
- 计算n的欧拉函数，φ(n) = φ(p×q) = φ(p) × φ(q) = (p -1 ) × (q - 1)
- 随机选取一个与 φ(n) 互质的数e，并且 1 < e < φ(n)
- 计算出一个 e 对于φ(n)的模反元素 d，也就是说 ed mod φ(n) = 1
公钥：（n，e） 私钥：（d，n）
加密公式： m^e^ mod n = c
解密公式：c^d^ mod n = m
关于e ：
第4步，e到底是怎么选取呢？其实，是可以随机的，但是为了提高RSA的加密速度实际使用中公钥指数最长用的三个值是3、17、65537（65536 = 2^16^ +1）。这样选取主要是为了性能，将公钥指数选小一点，这样计算密文就方便一点；
但是这样会导致解密会麻烦一点。因为正常使用中都是用公钥加密，所以需要节约大部分人的时间。而极少部分人也会选用私钥解密，那么就只能少数服从多数了。
在选用公钥指数时，人们普遍会认为3和17没有65537安全。然而这种想法并没有合理的依据。实际上采用这三个值中的任何一个都不存在安全问题。前提是使用正确的填充方案。
关于d是怎么计算出来的：
- 我们知道ed mod φ(n) = 1
- 那么也就是说，存在一个整数k，使得 ed ÷ φ(n) = k....1 （商为k，余数为1）
- 也就是 ed - 1 = kφ(n)， 变化一下就是 ed + kφ(n) = 1.
- 我们已知e和φ(n)的值，d和k的值未知。其实，以上公式就是对这个二元一次方程求解：ex + φ(n)y = 1
- 这个方程可以用扩展欧几里得算法 (opens new window)求解，此处省略具体过程
# RSA算法的一个例子
我们来举个例子，具体演示下算法的运作过程。本例子用到的数字都特别小，实际应用中，一般会成百上千位的数字进行计算。
第一步，选取 p = 61， q=53
第二步，计算pq乘积：n = pq = 3233。 n的长度就是密钥长度。3233写成二进制是110010100001，一共有12位，所以这个密钥就是12位。实际应用中，RSA密钥一般是1024位，重要场合则为2048位。
第三步：计算n的欧拉函数：φ(n) = (p-1)(q-1) = 3120
第四步：随机选取一个整数e，这里选择17
第五步：计算e对于φ(n)的模反元素d，使得ed mod φ(n) = 1. 上一小节我们说过 ed + kφ(n) = 1，代入e和φ(n)，也就是17d + 3120k = 1，可以根据扩展欧几里得算法 (opens new window)算得一组整数d = 2753， k=-15。
因此，公钥就是（3233，17），私钥就是（3233,2753）
假设我们要加密字符 ‘A’，其ASCII码为65； 根据加密公式可得 65^17^ mod 3233 = 2790，因此密文c就是2790
解密：通过解密公式c^d^ ≡ m (mod n)，可得2790^2753^ mod 3233 = 65。
至此，"加密--解密"的整个过程全部完成。
# RSA的一个漏洞
Rambus公司曾发现了RSA的一个小漏洞：如果N的两个质数p和q很接近，那么很可能被硬猜出来！其实这个方法是大数学家费马之前就发现过的：如果两个数很接近，意味着他们的差很小，因此可能破解出来。
具体怎么破解呢？首先，假设质数p和q是用来生成公钥的，我们设a，b为两个整数，并且a = （p+q）/2， b = （p-q）/ 2
那么就有p = a + b， q = a - b
则有n = （pq） = （a+b）（a-b） = a^2^ - b^2^ （初中的平方差公式）
因此a^2 ^= n +b^2^。 我们可以知道，任何数的平方都是正数，因此 a^2 ^= n +b > n。而费马说过，如果两个数很接近，意味着他们的差很小，而b是作为他们的差的一半，即使算上了平方，也还是很小的！那么 a^2 ^应该就约等于n。
又因为p和q是质数（也是奇数），所以a 和 b 必定是整数（奇数加减后是偶数，除以2，是能被整除的，所以a和b不是小数），然后我们就可以从 n 的平方根开始，一个个试，总有可能试出来。
举个粒子：
假设有个公钥n = 27263 = a^2^ - b^2^
我们将n开平方，并用a表示：a ≈ $\sqrt{27263}$ ，也就是 a ≈ 165.12
假设a = 166，则b^2^ = 293，则b不是整数，pass❌
假设a = 167，则b^2^ = 626，则b不是整数，pass❌
假设a = 168，则b^2^ = 961，则b=31☑
因此，就破解出了a和b，然后就可以计算出p=a+b=199，q=a-b=137，因此可以破解出密钥d。
当然，现实生活中会极力避免出现这样的情况的，并且这个漏洞已经上报公开了，目前RSA算法还是很安全的。
数学家们认为，判断RSA算法密钥是否安全的标准为：| p - q | < $\sqrt[4]n$ ，也就是p-q的绝对值，是否小于 n的四次方根。
# 公钥的传输
其实，使用公钥传输还是有一个问题：万一用户收到的是攻击者的公钥怎么办？
假设Bob要和Alice通信，需要Alice的公钥，那么Alice将公钥发送给了Bob；但如果在发送公钥的过程中，Peter截胡了，将自己生成的公钥发给了Bob！
然后Bob收到公钥后，加密数据，并发送给Alice，但不幸的是，也被Peter截胡了，然后Peter就可以解密了。。。
最后，我们还是回到最初的问题：密钥怎么发送给使用者？其实我们电脑（准确来说是操作系统）一开始就装了很多证书。
以Windows为例，在 cmd 命令行中执行 certmgr.msc 命令，可以查看操作系统已经安装的证书列表。
# 量子计算机
1994年，美国数学家秀儿（Peter Shor），曾经提出了一种逆天的量子计算算法，对于一般的计算机而言，RSA算法的公钥N位数每增加一位，破解RSA的难度都会呈指数上升；而这个逆天算法可以把“指数上升”的难度，降低到跟N位数的平方成正比！
图片来自麻省理工学院官网 (opens new window)
量子算法是厉害，但现在的量子计算机性能实在太渣。2001年IBM曾经在自己的量子计算机上，用秀儿算法搞了次因数分解，成功把15分解成了3×5；2019年的时候BM想用自己最新的量子计算机，尝试分解35，但失败了.....
图片来自：Quantum computing- 维基百科 (opens new window)
目前的密钥长度基本都是成百上千的，要想分解，至少需要600个量子比特的量子计算机。然而谷歌最新的量子计算机，也不过53个量子比特。因此在可见的未来里。RSA加密都会继续保持安全。
# 总结
本文作为RSA原理系列的最后一篇，相信大家通过之前的讲解，对于RSA都有一定的认知了。
RSA从提出到现在，这么多年过去了，经历了各种攻击的考验，注解为人们接受，普遍认为是目前最优秀的公钥方案之一。
本文参考了非常多的博客和文章，非常感谢他们：
深入理解RSA算法 - 简书 (opens new window)
RSA中 底数m和模数 n 不互素是仍然成立_rsa的m_Zetaa的博客-CSDN博客 (opens new window)
密码学笔记 - 阮一峰的网络日志 (opens new window)
RSA算法原理（一） - 阮一峰的网络日志 (opens new window)
RSA算法原理（二） - 阮一峰的网络日志 (opens new window)
密钥交换算法 - 廖雪峰的官方网站 (opens new window)
五年级数学“分解质因数”难题详解 (opens new window)
为什么大整数分解质因数很困难？ - 知乎 (opens new window)
质因数分解与量子计算机 - 知乎 (opens new window)
欧拉函数 - 天殇梦璃 - 博客园 (opens new window)
Diffie-Hellman密钥交换算法| 公钥加密| DH算法| 密码学| 信息安全_哔哩哔哩_bilibili (opens new window)
【不懂数学没关系】DH算法 | 迪菲-赫尔曼Diffie–Hellman 密钥交换_哔哩哔哩_bilibili (opens new window)
用小学数学，看懂支付宝微信都在用的“最强加密”_哔哩哔哩_bilibili (opens new window)
【RSA加密算法】| RSA加密过程详解 | 公钥加密| 密码学| 信息安全|_哔哩哔哩_bilibili (opens new window)
