0

Читаю про алгоритм RSA в википедии и не понимаю, как так получается, что секретная эспонента d вычисляется с помощью общедоступных данных (открытой экспоненты e и числа n). Ведь получение секретного ключа с помощью открытого ключа нарушает одно из основных требований к криптосистемам. Как так получается, что RSA сложно взломать?

1 ответ 1

2

Для того, чтобы вычислить d из e, нужно знать число (p-1)(q-1), где p и q делители числа N.

Стойкость RSA основывается на сложности разложения больших чисел на множители. Несмотря на то, что все знают число N из открытого ключа, вычислительных мощностей в обозримом будущем в принципе не хватит для разложения N современных ключей на произведение p и q.

Например, число 1807082088687404805951656164405905566278102516769401349170127021450056662540244048387341127590812303371781887966563182013214880557 из первой статьи про RSA, опубликованной в 1977 году, раскладывали 17 лет (правда, авторы ожидали, что разложение потребует миллионы лет :) )

На текущий момент самый лучший результат по разложению чисел на множители - число с 250 цифрами, которое потребовало 2700 лет счёта на суперкомпьютере. Принимая во внимание, что в реальной жизни используются ключи в 2.5 раз длиннее, можно не переживать за стойкость RSA до массового внедрения квантовых компьютеров.

2
  • Но ведь значение (p-1)*(q-1) - это функция эйлера от числа n, которое можно быстро получить используя любой онлайн калькулятор функции эйлера (для таких значений, как в википедии), а кроме вычисления функции эйлера числа p и q нигде больше не используются. Поправьте пожалуйста, если я где-то ошибаюсь.
    – Alyks
    15 июн 2021 в 2:59
  • @Alyks функция Эйлера быстро считается только для 64-х битных чисел. Уже для 128 бит это будет далеко не так быстро. А для 2048 бит, рекомендуемых для практических применений, это невозможно трудоёмкая задача.
    – Pak Uula
    15 июн 2021 в 3:09

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.