cryptography - 在 RSA 加密算法中查找 p 和 q

Question

在 RSA 加密算法中，如何找到和的因数p，q是e已知的。我试图搜索但找不到任何来源。任何提示、参考或解决方案就足够了。dn

(e,n)和(d,n)分别是公钥和私钥，n = pq.

score 0 · Accepted Answer

我找到了一个用德语写的源代码（第 12+13 页），它描述了一种随机算法来计算p和q.

算法：

计算和s = max { t : 2^t | (ed-1) }k = (ed-1) / (2^s)
选择一个随机a数[2,n-1]
计算g = gcd(a,n)
如果g > 1 ⇒ g = p和q = n/g。
否则为t = s-1, ... ,0：
1. g = gcd( a^{k ⋅ 2^t}, n )
2. 如果g < n ⇒ g = p和q = n/g。
  否则选择一个新的随机数a并[2,n-1]转到3。

如果选择a随机数（均匀分布），则找到p和的概率q为1/2，因此预计 2 次尝试后得到解。

这个工作的证明与中国剩余定理有关。

备注：如果您已经拥有私钥，则很可能没有理由计算的因数，因为同n一个的密钥永远不会超过一对。但是你可以使用这个算法来证明破解 RSA 和分解一样难。（RSA 并不比因式分解更难，因为如果你有和，你可以简单地计算私钥）。(e,d)nndpq

1 回答 1