Стойкость ассиметричных алгоритмов в целом зависит от сложности обращения односторонних функций, лежащих в основе данного типа алгоритмов

Безопасность алгоритма RSA базируется на трудности решения задачи факторизации (разложение на множители) больших чисел.

Криптостойкость алгоритма RSA определяется тем, что после формирования секретного ключа К_В2 и открытого ключа К_В1 "стираются" значения простых чисел Р и Q. Тогда исключительно трудно определить секретный ключ К_В2 по открытому ключу К_В1 (сложность обращения односторонней функции ), поскольку для этого необходимо решить задачу нахождения делителей Р и Q модуля N.

Например могут быть такие способы криптоанализа:

1. Разложение величины N на простые множители Р и Q позволяет вычислить функцию и затем определить секретное значение К_В2, используя уравнение

2. Вычисление или подбор значения функции

Если установлено значение , то сомножители Р и Q вычисляются из системы

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

Однако эта атака не проще задачи факторизации модуля N.

Задача факторизации является трудно разрешимой задачей для больших значений модуля N.

Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые числа Р и Q случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, Р. Райвест, полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Однако этот прогноз не оправдался из-за сравнительно быстрого прогресса компьютеров и их вычислительной мощности, а также улучшения алгоритмов факторизации.

Один из наиболее быстрых алгоритмов, известных в настоящее время, алгоритм NFS (Number Field Sieve – метод решета числового поля) может выполнить факторизацию большого числа N (с числом десятичных разрядов больше 120) за число шагов, оцениваемых величиной

Для иллюстрации своего метода Ривест, Шамир и Адлеман зашифровали таким способом некоторую английскую фразу. Сначала она стандартным образом (а=01, b=02,..., z=26, пробел=00) была записана в виде целого числа x, а затем зашифрована при

N=

и K_B1 = 9007. Эти два числа были опубликованы, причем дополнительно сообщалось, что N = pq, где р и q – простые числа, записываемые соответственно 64 и 65 десятичными знаками. Первому, кто дешифрует соответствующее сообщение

была обещана награда в 100$.

Эта история завершилась спустя 17 лет в 1994 г., когда D. Atkins, М. Graff, А. К. Lenstra и Р. С. Leyland сообщили о дешифровке фразы, предложенной Она была вынесена в заголовок статьи, а соответствующие числа Р и Q оказались равными

Этот замечательный результат (разложение на множители 129-значного десятичного числа) был достигнут благодаря использованию алгоритма разложения чисел на множители, называемого методом квадратичного решета. Выполнение вычислений потребовало колоссальных ресурсов. В работе, возглавлявшейся четырьмя авторами проекта, и продолжавшейся после предварительной теоретической подготовки примерно 220 дней, на добровольных началах участвовало около 600 человек и примерно 1600 компьютеров, объединенных серью Internet. Наконец, отметим, что премия в 100$ была передана в Free Software Foundation.

В 1994 г. было факторизовано число со 129 десятичными цифрами. Это удалось осуществить математикам А. Ленстра и М. Манасси посредством организации распределенных вычислений на 1600 компьютерах, объединенных сетью, в течение восьми месяцев. По мнению А. Ленстра и М. Манасси, их работа компрометирует криптосистемы RSA и создает большую угрозу их дальнейшим применениям.

Дата добавления: 2014-01-04