V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
bing1178
V2EX  ›  问与答

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

  •  
  •   bing1178 · 2021-06-05 21:53:06 +08:00 · 1485 次点击
    这是一个创建于 1266 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

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

    iBugOne
        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 了
    bing1178
        2
    bing1178  
    OP
       2021-06-05 22:53:03 +08:00
    @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
        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
    iBugOne
        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 )?

    这个问得我一时无语凝噎……回去补补整除和同余相关的数论吧
    bing1178
        5
    bing1178  
    OP
       2021-06-05 23:44:12 +08:00
    @iBugOne 感谢感谢。

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

    那么
    我有这个疑问的原因是:我觉得:因数多了,会有同比例的 欧拉 n 出现,我依然要验证哪个 欧拉 n 是对的。
    而实际 如您所回答,它们 2 个 比例并不一致, 而且是指数关系
    iBugOne
        6
    iBugOne  
       2021-06-05 23:47:28 +08:00   ❤️ 1
    > 因数多了,会有同比例的 欧拉 n 出现,我依然要验证哪个 欧拉 n 是对的

    ϕ(n) 是一个确定的函数,对于任何正整数 n,ϕ(n) 都有唯一确定的值。只要将 n 的全部质因数找出来,就可以算出这个唯一确定的值,这里有什么问题吗?
    bing1178
        7
    bing1178  
    OP
       2021-06-05 23:56:36 +08:00
    @iBugOne 没问题没问题。 我刚才验算卡在之前的认知里。 用合数 ( p-1 )*( q-1 ) 求欧拉 n 了。。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2552 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 29ms · UTC 10:30 · PVG 18:30 · LAX 02:30 · JFK 05:30
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.