RSA 中 pq 互质是比 pq 都是质数更安全？

[bing1178]

下文中 我整理了 RSA 的推导方法。 https://juejin.cn/post/6968115250461671437/

首先想确认下 RSA 对 pq 的要求是互质，而不是要求其都是质数？

我看很多资料中 p 和 q 选的都是质数。然后 pq 肯定互质

我的问题是 为什么要选 2 个质数呢？比如 15 和 32，我让 p 和 q 都不是质数，这样求出的 n=q*p 岂不是更难分解？

[iBugOne]

RSA 的安全性可不是因为 pq 互质，而是由公钥指数 e 计算密钥指数 d 需要用到模数 n 的欧拉函数值 ϕ(n)，这个值在 pq 都是质数时等于 (p-1)*(q-1)，并且目前没有已知的比分解 n 更好的方法来计算 ϕ(n)。

如果你的 pq 是两个合数的话，把所有质因数都分解出来然后 ϕ(n) = (p1-1)*(p2-1)*...*(pn-1) 就行了，你的私钥就 GG 了

[bing1178]

@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 ）？

再次感谢~ 我再理解下

[iBugOne]

没错，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

[iBugOne]

如果 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 ）？

这个问得我一时无语凝噎……回去补补整除和同余相关的数论吧

[bing1178]

@iBugOne 感谢感谢。

“其中欧拉函数 ϕ(n) 表示 1 到 n 之间与 n 互质的整数个数”

那么
我有这个疑问的原因是：我觉得：因数多了，会有同比例的 欧拉 n 出现，我依然要验证哪个 欧拉 n 是对的。
而实际 如您所回答，它们 2 个 比例并不一致， 而且是指数关系

[iBugOne]

> 因数多了，会有同比例的 欧拉 n 出现，我依然要验证哪个 欧拉 n 是对的

ϕ(n) 是一个确定的函数，对于任何正整数 n，ϕ(n) 都有唯一确定的值。只要将 n 的全部质因数找出来，就可以算出这个唯一确定的值，这里有什么问题吗？

[bing1178]

@iBugOne 没问题没问题。 我刚才验算卡在之前的认知里。 用合数 （ p-1 ）*（ q-1 ） 求欧拉 n 了。。