从用户的 RSA public 密钥计算用户的私钥
Computing private key of a user from his RSA public key
我知道我们会给每个人 (N,e) 作为我们的 public 键，而 N 是两个质数 P 和 Q 的乘积。但我知道两个素数的乘积只有 4 个除数（1，本身，P，Q）并且使用一个简单的 while 循环黑客可以轻松获得 P 和 Q 并计算 phi 。由于他们已经知道 E，因此他们可以使用 E-1[=37= 轻松确定 D ] mod phi(N) 公式。那我错过了什么？
就是这样。如果 p 和 q 很大，分解 n （计算 p 和 q ）很难。它也称为 RSA 问题。正如您所描述的那样，这种天真的算法很难在集群上花费很多年才能从 public 密钥中计算出私钥。今天，n 的良好起始值通常是 2048 或 4096 位大小。
让我们以 2048 位的 n 为例。您需要检查 21021 和 21023[=37= 之间的某处] 平均数字，看看它们是否是一个因素。为此，您需要对每个数字至少进行一次除法，而除法是成本最高的操作。假设您每秒可以进行 250（这已经太乐观了）除法。所以需要 21021 * 2-50 = 2971秒天真地暴力破解。或者那么多年：
632876810481582893092457100785400357073646391563754928178128882051373633900610117258040958109029585581349076244353277284364674653853879268372390854352115493505836400606001292655231393152068425666747005563338382798494041874404131909211331579289714661817326517908344762063152744555537801
比您描述的更好的算法是 general number field sieve。有些量子算法应该 运行 更快。
我知道我们会给每个人 (N,e) 作为我们的 public 键，而 N 是两个质数 P 和 Q 的乘积。但我知道两个素数的乘积只有 4 个除数（1，本身，P，Q）并且使用一个简单的 while 循环黑客可以轻松获得 P 和 Q 并计算 phi 。由于他们已经知道 E，因此他们可以使用 E-1[=37= 轻松确定 D ] mod phi(N) 公式。那我错过了什么？
就是这样。如果 p 和 q 很大，分解 n （计算 p 和 q ）很难。它也称为 RSA 问题。正如您所描述的那样，这种天真的算法很难在集群上花费很多年才能从 public 密钥中计算出私钥。今天，n 的良好起始值通常是 2048 或 4096 位大小。
让我们以 2048 位的 n 为例。您需要检查 21021 和 21023[=37= 之间的某处] 平均数字，看看它们是否是一个因素。为此，您需要对每个数字至少进行一次除法，而除法是成本最高的操作。假设您每秒可以进行 250（这已经太乐观了）除法。所以需要 21021 * 2-50 = 2971秒天真地暴力破解。或者那么多年：
632876810481582893092457100785400357073646391563754928178128882051373633900610117258040958109029585581349076244353277284364674653853879268372390854352115493505836400606001292655231393152068425666747005563338382798494041874404131909211331579289714661817326517908344762063152744555537801
比您描述的更好的算法是 general number field sieve。有些量子算法应该 运行 更快。