Простые числа как открытый ключ - уточнение?

Я прочитал здесь, что:

Если вы наблюдали за созданием сертификата безопасности на вашем компьютере..., вот что происходит: он создает два больших числа , проверяет, что они оба простые, и перемножает их вместе. Это дает вам ваш «открытый ключ», которым вы можете свободно делиться со всем миром. Это позволяет другим людям отправлять вам сообщения, шифруя их с помощью вашего открытого ключа; однако, поскольку получить исходные два простых числа из открытого ключа сложно (их знает только ваш компьютер, потому что он их сгенерировал), вы единственный, кто может их расшифровать!

Поэтому я хотел проверить, сколько нужно, чтобы «извлечь» простые числа из умножения 2 больших простых чисел:

Я не буду брать огромное количество (только для демонстрации), поэтому я зашел на этот сайт и взял 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 секунды, чтобы узнать:

введите здесь описание изображения

Вопрос

Я уверен, что не понял абзац выше, потому что мне кажется довольно легко выяснить, из каких простых чисел состоит число: поэтому я не понимаю эту часть:

однако, поскольку получить исходные два простых числа из вашего открытого ключа сложно (???)

**Обновлять : **

Я хотел пойти дальше и выбрать большие числа:

941 083 987 и 295 075 153 (умножение = 277690501449875011)

И снова времени было мало:

введите здесь описание изображения


person Royi Namir    schedule 21.02.2015    source источник
comment
Эти цифры невелики. Обычно ключи RSA имеют размер 2048 бит или даже больше. Это соответствует ок. 600 и более десятичных цифр.   -  person CBenni    schedule 21.02.2015
comment
@CBenni Спасибо за ответ. Вы знаете, где я могу найти и поиграть с этими (такими) числами (можно ссылку?)   -  person Royi Namir    schedule 21.02.2015
comment
Я не знаю, есть ли веб-сайт с такими простыми числами, отформатированными как числа, обычно они хранятся в виде файлов подписи. Команда linux ssh-keygen -t rsa может использоваться для генерации такого ключа случайным образом.   -  person CBenni    schedule 21.02.2015


Ответы (1)


Как отмечено в моем комментарии, ключи RSA обычно намного больше по размеру. Ваши примеры могут быть легко перебраны (!). Ключи RSA, используемые для SSH и подобных, обычно имеют длину 2048 или даже 4096 бит (примерно 616 или 1233 десятичных разряда). В этот момент попытка их грубой силы занимает практически вечность, даже самые лучшие известные алгоритмы не улучшают время их взлома значительно.

Вопрос о том, существует ли алгоритм, который делает это эффективно, остается открытым.

РЕДАКТИРОВАТЬ: Вы спросили, почему в первую очередь используются простые числа: если вы не выберете простые числа, алгоритм больше не будет работать. Я предлагаю прочитать книгу по дискретной математике (или, возможно, просто статью в Википедии), чтобы узнать, как работает RSA.

person CBenni    schedule 21.02.2015
comment
Благодарим Вас за разъяснения. - person Royi Namir; 21.02.2015