Читаю про алгоритм RSA в википедии и не понимаю, как так получается, что секретная эспонента d вычисляется с помощью общедоступных данных (открытой экспоненты e и числа n). Ведь получение секретного ключа с помощью открытого ключа нарушает одно из основных требований к криптосистемам. Как так получается, что RSA сложно взломать?
1 ответ
Для того, чтобы вычислить d
из e
, нужно знать число (p-1)(q-1)
, где p
и q
делители числа N
.
Стойкость RSA основывается на сложности разложения больших чисел на множители. Несмотря на то, что все знают число N
из открытого ключа, вычислительных мощностей в обозримом будущем в принципе не хватит для разложения N
современных ключей на произведение p
и q
.
Например, число 1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557
из первой статьи про RSA, опубликованной в 1977 году, раскладывали 17 лет (правда, авторы ожидали, что разложение потребует миллионы лет :) )
На текущий момент самый лучший результат по разложению чисел на множители - число с 250 цифрами, которое потребовало 2700 лет счёта на суперкомпьютере. Принимая во внимание, что в реальной жизни используются ключи в 2.5 раз длиннее, можно не переживать за стойкость RSA до массового внедрения квантовых компьютеров.
-
Но ведь значение (p-1)*(q-1) - это функция эйлера от числа n, которое можно быстро получить используя любой онлайн калькулятор функции эйлера (для таких значений, как в википедии), а кроме вычисления функции эйлера числа p и q нигде больше не используются. Поправьте пожалуйста, если я где-то ошибаюсь.– Alyks15 июн 2021 в 2:59
-
@Alyks функция Эйлера быстро считается только для 64-х битных чисел. Уже для 128 бит это будет далеко не так быстро. А для 2048 бит, рекомендуемых для практических применений, это невозможно трудоёмкая задача.– Pak Uula15 июн 2021 в 3:09