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)