这是一个创建于 1265 天前的主题，其中的信息可能已经有所发展或是发生改变。
下文中 我整理了 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 的全部质因数找出来，就可以算出这个唯一确定的值，这里有什么问题吗？ |
Select Language