Информационная безопасность. Макаренко С.И. - 132 стр.

простых чисел. Действительно, криптостойкость алгоритма RSA
определяется тем, что после формирования секретного ключа kв и открытого
ключа Кв «стираются» значения простых чисел Р и Q, и тогда исключительно
трудно определить секретный ключ kв по открытому ключу Кв, поскольку для
этого необходимо решить задачу нахождения делителей Р и Q модуля N.
      Разложение величины N на простые множители Р и Q позволяет
вычислить функцию φ(N) = (P-T) (Q-T) и затем определить секретное
значение kB используя уравнение
                            (KB ∙ kв) mod ( φ(N) ) = 1.
      Другим возможным способом криптоанализа алгоритма RSA является
непосредственное      вычисление    или     подбор    значения   функции
φ(N) = (P -T) (Q-T). Если установлено значение φ(N), то сомножители Р и Q
вычисляются достаточно просто. В самом деле, пусть



      Зная φ(N), можно определить х и затем у; зная х и у, можно определить
числа Р и Q из следующих соотношений:


      Однако эта атака не проще задачи факторизации модуля N.
      Задача факторизации является трудно разрешимой задачей для
больших значений модуля N.
      Сначала авторы алгоритма RSA предлагали для вычисления модуля N
выбирать простые числа Р и Q случайным образом, по 50 десятичных
разрядов каждое. Считалось, что такие большие числа N очень трудно
разложить на простые множители. Один из авторов алгоритма RSA,
Р. Райвест, полагал, что разложение на простые множители числа из почти
130 десятичных цифр, приведенного в их публикации, потребует более 40
квадриллионов лет машинного времени. Однако этот прогноз не оправдался
из-за сравнительно быстрого прогресса компьютеров и их вычислительной
мощности, а также улучшения алгоритмов факторизации.
      Один из наиболее быстрых алгоритмов, известных в настоящее время,
алгоритм NFS (Number Field Sieve) может выполнить факторизацию
большого числа N (с числом десятичных разрядов больше 120) за число
шагов, оцениваемых величиной                 .
     В 1994 г. было факторизовано число со 129 десятичными цифрами. Это
удалось осуществить математикам А. Ленстра и М. Манасси посредством
организации распределенных вычислений на 1600 компьютерах,
объединенных сетью, в течение восьми месяцев. По мнению А. Ленстра и
М. Манасси, их работа компрометирует криптосистемы RSA и создает
большую угрозу их дальнейшим применениям. Теперь разработчикам
криптоалгоритмов с открытым ключом на базе RSA приходится избегать


                                    132