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

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

Разложение величины N на простые множители Р и Q позволяет вычислить функцию и затем определить секретное значение k_B, используя уравнение    К_B * k_B = 1 (mod (φ (N)).

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

x = P+Q = N-1 - φ(N),

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

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

.

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

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

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

.

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

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

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

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

Вывод:

Программная реализация RSA примерно в 100 раз медленнее программной реализации DES. С развитием технологии эти оценки могут несколько изменяться, но асимметричная криптосистема RSA никогда не достигнет быстродействия симметричных криптосистем.

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

Схема Эль-Гамаля

Схема была предложена Тахером Эль-Гамалем в 1984г. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.

Безопасность схемы Эль-Гамаля обусловлена сложностью вычисления дискретных логарифмов в конечном поле.

Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое число Р и большое целое число G, причем G < Р. Числа Р и G могут быть распространены среди группы пользователей.

Затем выбирают случайное целое число X, причем Х<Р. Число Х является секретным ключом и должно храниться в секрете.

Далее вычисляют Y = G^X (mod P). Число Y является открытым ключом.

Для того чтобы зашифровать сообщение М, выбирают случайное целое число К, 1<К<Р - 1, такое, что числа К и (Р-1) являются взаимно простыми.

Затем вычисляют числа

a=G^K (mod P),

b = Y^K М (mod P).

Пара чисел (а,b) является шифротекстом. Заметим, что длина шифротекста вдвое больше длины исходного открытого текста М.

Для того чтобы расшифровать шифртекст (а,b), вычисляют

При этом нетрудно проверить, что

и поэтому

.

Для практических вычислений больше подходит следующая формула:

Пример

§ Шифрование

1. Допустим что нужно зашифровать сообщение .

2. Произведем генерацию ключей:

1) пусть . Выберем - случайное целое число такое, что .

2) Вычислим .

3) Итак, открытым является тройка ,а закрытым ключом является число .

3. Выбираем случайное целое число такое, что 1 < k < (p − 1). Пусть .

4. Вычисляем число .

5. Вычисляем число .

6. Полученная пара является шифротекстом.

§ Расшифрование

1. Необходимо получить сообщение по известному шифротексту и закрытому ключу .

2. Вычисляем M по формуле:

3. Получили исходное сообщение .

В реальных схемах шифрования необходимо использовать в качестве модуля Р большое целое простое число, имеющее в двоичном представлении длину 512-1024 битов.

Вывод:

В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:

ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001г. используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.