Получение закрытой экспоненты в RSA
Читаю про алгоритм 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 до массового внедрения квантовых компьютеров.