security - 从用户的 RSA 公钥计算用户的私钥

Question

我知道我们会将(N,e)作为我们的公钥提供给每个人，N是两个素数的乘积P> 和Q。但我知道两个素数的乘积只有 4 个约数(1、本身、P、Q)，并且使用简单的 while 循环黑客可以轻松获得 P 和Q 并计算phi。由于他们已经知道 E，因此可以使用 E^-1 mod phi(N) 公式轻松确定 D 。那么我错过了什么？

Answer 1

就是这样。如果p和q很大，则分解n(计算出p和q它)很难。它也称为 RSA 问题。正如您所描述的，这种简单的算法非常困难，需要在集群上花费很多年才能从公钥中计算出私钥。如今，n 的良好起始值通常为 2048 或 4096 位。

让我们以 2048 位的 n 为例。您需要检查平均 2¹⁰²¹ 和 2¹⁰²³ 之间的数字，看看它们是否是一个因素。为此，您需要对每个数字至少进行一次除法，其中除法是成本最高的操作。假设您每秒可以进行 2⁵⁰(这已经太乐观了)划分。因此需要 2¹⁰²¹ * 2^-50 = 2⁹⁷¹ 秒天真地暴力破解它。或者那么多年:

632876810481582893092457100785400357073646391563754928178128882051373633900610117258040958109029585581349076244353277284364674653853879268372390854352115493505836400606001292655231393152068425666747005563338382798494041874404131909211331579289714661817326517908344762063152744555537801

比您描述的更好的算法是 general number field sieve 。有些量子算法应该运行得更快。