下文中 我整理了 RSA 的推导方法。 https://juejin.cn/post/6968115250461671437/
首先想确认下 RSA 对 pq 的要求是互质,而不是要求其都是质数?
我看很多资料中 p 和 q 选的都是质数。然后 pq 肯定互质
我的问题是 为什么要选 2 个质数呢?比如 15 和 32,我让 p 和 q 都不是质数,这样求出的 n=q*p 岂不是更难分解?
1
iBugOne 2021-06-05 22:00:37 +08:00 1
RSA 的安全性可不是因为 pq 互质,而是由公钥指数 e 计算密钥指数 d 需要用到模数 n 的欧拉函数值 ϕ(n),这个值在 pq 都是质数时等于 (p-1)*(q-1),并且目前没有已知的比分解 n 更好的方法来计算 ϕ(n)。
如果你的 pq 是两个合数的话,把所有质因数都分解出来然后 ϕ(n) = (p1-1)*(p2-1)*...*(pn-1) 就行了,你的私钥就 GG 了 |
2
bing1178 OP @iBugOne 非常感谢大神的回复。 不过我需要时间理解下
没有已知的比分解 n 更好的方法来计算 ϕ(n)。 这句话解释了网上说的:RSA 安全的原因是“因数分解困难”。 但您的重点在于找 欧拉 n e 和 d 有个计算上的关系 (欧拉 n * x) + 1 = e * d 这在数轴上是个直线,知道了 欧拉 n 就知道了 e,d 的对应关系 这个值在 pq 都是质数时等于 (p-1)*(q-1) 这个我之前没注意,不过我验证了是确实由您所言。 我选了 2 个互质的合数,其欧拉 n 并不等于 (p-1)*(q-1) 这块我需要再研究下欧拉的特性。。 如果你的 pq 是两个合数的话,把所有质因数都分解出来然后 ϕ(n) = (p1-1)*(p2-1)*...*(pn-1) 就行了 这句几乎没理解。。我再想想。。 虽然 pq 是合数。但是是做 质因数分解。而不是因数分解。 “把所有质因数都分解出来然后” 如果 p,q 是合数 n=p*q 对 n 做质因数分解就简单 ? 还有就是 假设 p,q 都是质数,那么 n 的因数分解只有 1 种组合 就是 p*q,不会有第 2 种(除了 1 )? 再次感谢~ 我再理解下 |
3
iBugOne 2021-06-05 23:19:35 +08:00
没错,RSA 安全的原因是 “大质数分解是困难的”,这并不是直接的原因,而是经过了以下几个已知的命题
1. 由 e 求解 d 需要知道 ϕ(n)(需要的额外知识) 2. 对于 n=pq (两质数乘积),ϕ(n) = (p-1)*(q-1)(即分解得到 p 和 q 是一种破解方式) 3. 没有已知的更好的求 ϕ(n) 的方式 因为有了 3,我们才能认为 RSA 的安全性依赖于大质数难以分解。 对于任何非对称加密,其安全性的直接保证都是 “由公钥计算私钥是困难的”,只不过对于 RSA 可以推导到质数分解。 当 pq 都是质数时,对于 m 位长度的模 n,求出 pq 之一的期望复杂度是 2^(m/2)(例如,对 256 位的 n,分解质数的期望复杂度就是 2^128 )。如果 pq 是合数的话,这个期望复杂度会直接下降,例如当 p 和 q 各有 3 个质因数时,期望复杂度就只剩下 2^(m/6) 了。显然没有人会在相同长度 n 的情况下选用安全性更差的方案。 其中欧拉函数 ϕ(n) 表示 1 到 n 之间与 n 互质的整数个数,参见维基百科: https://en.wikipedia.org/wiki/Euler's_totient_function |
4
iBugOne 2021-06-05 23:29:03 +08:00
如果 pq 都是合数的话,那么质因数在 pq 中怎么分配是无关紧要的,例如 p=12, q=14 和 p=8, q=21 会得到完全一样的结果。这是因为 ϕ(n) 是关于 n 的函数,与 pq 没有直接关联。
另外上面那个算式有点偏差,应该是 ϕ(n) = n*(1-1/p1)*(1-1/p2)*...*(1-1/pn),这样就可以看出它与各个质因数的顺序没有关联了 > 如果 p,q 是合数 n=p*q 对 n 做质因数分解就简单 ? 这是因为如果 n 有 6 个质因数,那么其中最小的那个肯定不会超过 6√n,这里 6 可以换成其他数字。当 n 的大小确定时,显然质因数越多,每个质因数就会越小,从而分解(找到其中的一个或多个质因数)也会更容易。 > 还有就是 假设 p,q 都是质数,那么 n 的因数分解只有 1 种组合 就是 p*q,不会有第 2 种(除了 1 )? 这个问得我一时无语凝噎……回去补补整除和同余相关的数论吧 |
5
bing1178 OP @iBugOne 感谢感谢。
“其中欧拉函数 ϕ(n) 表示 1 到 n 之间与 n 互质的整数个数” 那么 我有这个疑问的原因是:我觉得:因数多了,会有同比例的 欧拉 n 出现,我依然要验证哪个 欧拉 n 是对的。 而实际 如您所回答,它们 2 个 比例并不一致, 而且是指数关系 |
6
iBugOne 2021-06-05 23:47:28 +08:00 1
> 因数多了,会有同比例的 欧拉 n 出现,我依然要验证哪个 欧拉 n 是对的
ϕ(n) 是一个确定的函数,对于任何正整数 n,ϕ(n) 都有唯一确定的值。只要将 n 的全部质因数找出来,就可以算出这个唯一确定的值,这里有什么问题吗? |