Безопасность и быстродействие криптосистемы RSА.

Безопасность алгоритма РЗА базируется на трудности ре­шения задачи факторизации больших чисел, являющихся произ­ведениями двух больших простых чисел. Действительно, криптостойкость алгоритма RSА определяется тем, что после формиро­вания секретного ключа k_B и открытого ключа К_B "стираются" значения простых чисел Р и Q, и тогда исключительно трудно оп­ределить секретный ключ k_B по открытому ключу К_B, поскольку для этого необходимо решить задачу нахождения делителей Р и Q модуля N.

Разложение величины N на простые множители Р и Q по­зволяет вычислить функцию f (N) = (Р -1)(Q -1) и затем опреде­лить секретное значение k_B, используя уравнение

К_B * k_B =1 (mod f (N)).

Другим возможным способом криптоанализа алгоритма RSА является непосредственное вычисление или подбор значения функции f (N) = (Р -1)(Q -1). Если установлено значение f (N), то сомножители Р и Q вычисляются достаточно просто. В самом де­ле, пусть

х = Р + Q = N +1 – f (N),

у = (Р-Q)² = (Р + Q)² - 4*N.

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

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

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

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

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

е^{2(lп n)1/3(lп(lп n))2/3}

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

В [102] сделана попытка расчета оценок безопасных длин ключей асимметричных криптосистем на ближайшие 20 лет исходя из прогноза развитии компьютеров и их вычислительной мощно­сти, а также возможного совершенствования алгоритмов фактори­зации. Эти оценки (табл. 4.8.) даны для трех групп пользователей (индивидуальных пользователей, корпораций и государственных организаций), в соответствии с различием требований к их инфор­мационной безопасности. Конечно, данные оценки следует рас­сматривать как сугубо приблизительные, как возможную тенден­цию изменений безопасных длин ключей асимметричных крипто­систем со временем.

Таблица 4.8

Оценки длин ключей для асимметричных криптосистем, бит

Криптосистемы RSА реализуются как аппаратным, так и программным путем.

Для аппаратной реализации операций зашифрования и расшифрования RSА разработаны специальные процессоры. Эти процессоры, реализованные на сверхбольших интегральных схе­мах (СБИС), позволяют выполнять операции RSА, связанные с возведением больших чисел в колоссально большую степень по модулю N, за относительно короткое время. И все же аппаратная реализация RSА примерно в 1000 раз медленнее аппаратной реа­лизации симметричного криптоалгоритма DЕS.

Одна из самых быстрых аппаратных реализаций RSА с мо­дулем 512 бит на сверхбольшой интегральной схеме имеет быст­родействие 64 Кбит/с. Лучшими из серийно выпускаемых СБИС являются процессоры фирмы CYLINK, выполняющие 1024-битовое шифрование RSА.

Программная реализация RSА примерно в 100 раз мед­леннее программной реализации DЕS. С развитием технологии эти оценки могут несколько изменяться, но асимметричная криптоси­стема RSА никогда не достигнет быстродействия симметричных криптосистем.

Следует отметить, что малое быстродействие криптоси­стем RSА ограничивает область их применения, но не перечерки­вает их ценность.