Оценка стойкости криптосистемы Эль-Гамаля

В современном обществе, когда информационные технологии играют важную роль, актуальной становится проблема защиты информационных технологий от многих видов угроз или нападений, которые могут привести к потере денег или репутации и, таким образом, уничтожить бизнес. Открытый ключ криптосистемы Эль-Гамаля часто используется в современных коммуникациях и системных технологиях; это один из первых определенных криптосистем с открытым ключом, обеспечивающий безопасность общения через публичные незащищенные каналы связи. Эта статья – краткое исследование стойкости криптосистемы Эль-Гамаля, в ней приведены некоторые примеры нападения на схеме Эль-Гамаля, а также способы избежать атак.

Ключевые слова: криптосистема с открытым ключом, криптосистема Эль-Гамаля, стойкость алгоритма.

1. ВВЕДЕНИЕ

Термин «информационная безопасность» является одним из основных понятий и включает в себя много компонентов, таких как: процесс, передача, хранение или изменение информации. Для слаженной работы всех перечисленных компонентов необходимы подходящие технологии и системы безопасности, отвечающие потребностям и требованиям безопасной работы.

Многие системы безопасности (например, протокола безопасности, алгоритмы или приложения) были разработаны на основе стандартов, которые в основном были предложены известными организациями (IAB, IETF и т. д.), чтобы обеспечить совместную и слаженную работу в функционировании таких систем и реализовать наши потребности в области безопасности в использовании информационных технологий.

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

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

В криптографии различают частные ключевые криптографические системы и ключевые криптографические системы с общественностью. Секретный ключ криптографии, также известный как секретный ключ или симметричный ключ шифрования, имеет давнюю историю, и основан он на использовании одного ключа для шифрования и дешифрования. Многие развитые современные частные ключевые криптографические системы основаны на Feistel шифре (например, национальный стандарт шифрования США (DES), шифр (стандарт) DES с трёхкратным шифрованием (3DES), новый национальный стандарт шифрования США (AES), международный алгоритм шифрования данных (IDEA), Blowfish, RC5, CAST и т. д.

В 1976 г. Диффи и Хеллман опубликовали документ, описывающий новую концепцию с открытым ключом, основанную на использовании двух ключей (открытого и закрытого). С помощью новой концепции мы можем решать многие проблемы (например, ключевую проблему обмена) в  криптографии. С тех пор было изобретено много систем открытых ключей шифрования (например, RSA, ElGamal, обмена ключами Диффи-Хеллмана, эллиптических кривых и т. д.).

Безопасность баз данных, основанная на использовании открытого ключа криптосистемы, обнаруживает трудности некоторых математических задач теории чисел (например, проблему дискретного логарифма над конечными полями и эллиптическими кривыми, задачи факторизации целых чисел или Диффи-Хеллмана и т. д.).

Протокол Диффи-Хеллмана отлично противостоит пассивному нападению, но в случае реализации атаки «человек в центре» он не устоит [5, 6]. Схема Эль-Гамаля была предложена Тахером Эль-Гамалем в 1984 году. Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана. Алгоритм Эль-Гамаля нашел применение в нашумевшей системе Pretty good privacy (PGP), где с помощью него осуществляется управление ключами. Использовался алгоритм цифровой подписи DSA, разработанный NIST (Национальный институт стандартов и технологий) и являющийся частью стандарта DSS (Национальный стандарт ЭЦП США).

Для данной работы была выбрана криптосистема Эль-Гамаля и на её основе исследована стойкости криптосистемы Эль-Гамаля, некоторые нападения на схеме Эль-Гамаля, чтобы избежать атак.

2. КРИПТОСИСТЕМЫ ЭЛЬ-ГАМАЛЯ

Рассмотрим алгоритм Эль-Гамаля [1, 2], использующийся для передачи секретных сообщений по открытым каналам с использованием открытого ключа.

Выбирается простое число  и два случайных числа  и  , степени которого по модулю  порождают большое число элементов . Вычисляется

Числа  — публикуются как открытый ключ,  — сохраняется как секретный ключ.

Предположим, что пользователь В желает послать сообщение  пользователю А. Для того, чтобы зашифровать сообщение  выбирается случайное число , взаимно простое с числом , т. е..

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

,

,

или

где  обозначает побитовое «исключающее ИЛИ».

Пара чисел  образует криптотекст. В посылает А пару .

Для расшифрования сообщения пользователь А вычисляет

,

или .

Поскольку

,

,

этот протокол можно использовать для передачи сообщений.

3. СТОЙКОСТЬ АЛГОРИТМА

Стойкость схемы Эль-Гамаля основана на (гипотетической) сложности задачи дискретного логарифмирования по основанию . Однако стойкость этой схемы в предположении сложности дискретного логарифмирования по основанию пока не доказана. Очевидно, что это предположение необходимо для стойкости схемы Эль-Гамаля, так как в противном случае противник сможет полностью раскрыть схему, вычислив секретный ключ по известному открытому.

Укажем некоторые определенные недостатки в схеме Эль-Гамаля:

Отсутствие семантической стойкости:  будет квадратичным вычетом, тогда и только тогда само сообщение  будет квадратичным вычетом. Итак, если хакер имеет шифрованный текст и открытый ключ, то он может получать некоторую информацию об исходном тексте.

Делимость шифра: если дан шифрованный текст , то можно получить другой шифрованный текст, изменив только вторую часть сообщения. В самом деле, умножив на  , получим шифртекст для другого сообщения .

Для защиты от недостатков схемы Эль-Гамаля, Шнорром и Якобссоном было предложено объединить схему шифрования Эль-Гамаля с цифровой подписью Шнорра, что позволяет не только шифровать сообщение, но и аутентифицировать его.

Литература:

1.             Алферов А. П., Зубов А. Ю., Кузьмин А. С., Черемушкин А. В. Основы криптографии. 3-е изд., испр. и доп. — М.: Гелиос АРБ. 2005.

2.             Баричев Б. Б., Гончаров В. В., Серов Р. Е. Основы современной криптографии. М.: Горячая линия-Телеком, 2011.

3.             Болотов А. А., Гашков С. Б., Фролов А. Б., Часовских А. А. Алгоритмические основы эллиптической криптографии. М. Мэи. 2000.

4.             Прасолов В. В., Соловьев Ю. П. Эллиптические функции и алгебраические уравнения. М.: Факториал. 1977.

5.             Яковлев А. В., Безбогов А. А., Родин В. В., Шамкин В. Н. Криптографическая защита информации. Издательство ТГТУ. 2006.

6.             William Stallings. Cryptography and Network Security Principles and Practice. Prentice Hall. 2011.