RSA
Безопасность алгоритма RSA базируется на трудности решения задачи факторизации больших чисел, являющихся произведениями двух больших простых чисел. Действительно, криптостойкость алгоритма RSA определяется тем, что после формирования секретного ключа kв и открытого ключа Кв "стираются" значения простых чисел Р и Q, и тогда исключительно трудно определить секретный ключ kв по открытому ключу Кв, поскольку для этого необходимо решить задачу нахождения делителей Р и Q модуля N.
Разложение величины N на простые множители Р и Q позволяет вычислить функцию j (N) = (P –1)(Q –1) и затем определить секретное значение kв, используя уравнение
Кв * kв º1 (mod j (N)).
Другим возможным способом криптоанализа алгоритма RSA является непосредственное вычисление или подбор значения функции
j (N) = (P –1)(Q –1). Если установлено значение j (n), то сомножители P и Q вычисляются достаточно просто. В самом деле, пусть
x = P + Q = N +1 – j (N),
y = (P – Q)2 = (Р + Q)2 – 4*N.
Зная j (N), можно определить x и затем y; зная x и y, можно определить числа Р и Q из следующих соотношений:
|
|
P = 1/2 (x + ), Q = 1/2 (x – ).
Однако эта атака не проще задачи факторизации модуля N [28].
Задача факторизации является трудно разрешимой задачей для больших значений модуля N.
Сначала авторы алгоритма RSA предлагали для вычисления модуля N выбирать простые числа P и Q случайным образом, по 50 десятичных разрядов каждое. Считалось, что такие большие числа N очень трудно разложить на простые множители. Один из авторов алгоритма RSA, P. Pайвест, полагал, что разложение на простые множители числа из почти 130 десятичных цифр, приведенного в их публикации, потребует более 40 квадриллионов лет машинного времени. Однако этот прогноз не оправдался из-за сравнительно быстрого прогресса компьютеров и их вычислительной мощности, а также улучшения алгоритмов факторизации.
Ряд алгоритмов факторизации приведен в [45]. Один из наиболее быстрых алгоритмов, известных в настоящее время, алгоритм NFS (Number Field Sieve) может выполнить факторизацию большого числа N (с числом десятичных разрядов больше 120) за число шагов, оцениваемых величиной
.
В 1994 г. было факторизовано число со 129 десятичными цифрами. Это удалось осуществить математикам А.Ленстра и М.Манасси посредством организации распределенных вычислений на 1600 компьютерах, объединенных сетью, в течение восьми месяцев. По мнению А.Ленстра и М.Манасси, их работа компрометирует криптосистемы RSA и создает большую угрозу их дальнейшим применениям. Теперь разработчикам криптоалгоритмов с открытым ключом на базе RSA приходится избегать применения чисел длиной менее 200 десятичных разрядов. Самые последние публикации предлагают применять для этого числа длиной не менее 250 – 300 десятичных разрядов.
|
|
Была сделана попытка расчета оценок безопасных длин ключей асимметричных криптосистем на ближайшие 20 лет исходя из прогноза развития компьютеров и их вычислительной мощности, а также возможного совершенствования алгоритмов факторизации. Эти оценки (табл.4.1.) даны для трех групп пользователей (индивидуальных пользователей, корпораций и государственных организаций), в соответствии с различием требований к их информационной безопасности. Конечно, данные оценки следует рассматривать как сугубо приблизительные, как возможную тенденцию изменений безопасных длин ключей асимметричных криптосистем со временем.
Таблица 4.1