素数作为 public 键 - 澄清一下？

Question

我读过here：

If you’ve watched a security certificate being generated on your computer ..., here is exactly what happens – it produces two large numbers , checks that they are both prime and multiplies them together. This gives you your “public key”, which you can share freely with the world. It allows other people to send you messages by encrypting them with your public key; however, since getting the original two prime numbers from your public key is hard (only your computer knows them because it generated them in the first place), you are the only one who can actually decrypt them!

所以我想测试 "Extract" 两个大素数相乘需要多少素数：

我不会取很大的数（只是为了演示）所以我去 to this site 取了 2 个大的（不是很大的）素数：

32,452,867

和

15,485,867

让我们将它们相乘得到：502560782130689

现在让我们看看这个数字是由哪些质数组成的：

void Main()
{
 double a, b;
Console.WriteLine("Please enter your integer: ");
a = double.Parse(Console.ReadLine());


for (b = 2; a > 1; b++)
    if (a % b == 0)
    {
        int x = 0;
        while (a % b == 0)
        {
            a /= b;
            x++;
        }
        Console.WriteLine("{0} is a prime factor {1} times!", b, x);
    }

}

花了2秒才发现：

问题

我很肯定我没有理解上面的段落，因为对我来说，找出这个数字是由什么组成的素数似乎很容易：所以我不理解这部分：

however, since getting the original two prime numbers from your public key is hard (???)

**更新：**

我想走得更远，选择更大的数字：

941,083,987 和 295,075,153（乘法 = 277690501449875011）

而且时间又足够短了：

Answer 1

正如我在评论中指出的那样，RSA 密钥的大小通常要大得多。你的例子很容易被暴力破解（！）。用于 SSH 和类似密钥的 RSA 密钥通常为 2048 位甚至 4096 位长（大约 616 位或 1233 位十进制数字）。在这一点上，试图暴力破解它们基本上需要永远，即使是已知的最好的算法也不会显着缩短破解它们的时间。

是否存在可以有效执行此操作的算法仍然是一个悬而未决的问题。

编辑：您询问了为什么首先使用素数：如果您不选择素数，该算法将不再有效。我建议阅读一本关于离散数学的书（或者可能只是维基百科文章）以了解 RSA 工作原理的详细信息。

素数作为 public 键 - 澄清一下？

Prime numbers as public key - clarification?

security

primes

certificate

prime-factoring