- Схема Эль-Гамаля
-
Данные в этой статье приведены по состоянию на ГОСТ Р 34.10-94. Вы можете помочь, обновив информацию в статье.Схема Эль-Гамаля (Elgamal) — криптосистема с открытым ключом,основанная на трудности вычисления дискретных логарифмов в конечном поле. Криптосистема включает в себя алгоритм шифрования и алгоритм цифровой подписи. Схема Эль-Гамаля лежит в основе стандартов электронной цифровой подписи в США (DSA) и России (ГОСТ Р 34.10-94).
Схема была предложена Тахером Эль-Гамалем в 1984 году.[1] Эль-Гамаль разработал один из вариантов алгоритма Диффи-Хеллмана. Он усовершенствовал систему Диффи-Хеллмана и получил два алгоритма, которые использовались для шифрования и для обеспечения аутентификации. В отличие от RSA алгоритм Эль-Гамаля не был запатентован и, поэтому, стал более дешевой альтернативой, так как не требовалась оплата взносов за лицензию. Считается, что алгоритм попадает под действие патента Диффи-Хеллмана.
Содержание
Генерация ключей
- Генерируется случайное простое число длины битов.
- Выбирается случайный примитивный элемент поля .
- Выбирается случайное целое число такое, что .
- Вычисляется .
- Открытым ключом является тройка , закрытым ключом — число .
Работа в режиме шифрования
- Шифрсистема Эль-Гамаля является фактически одним из способов выработки открытых ключей Диффи — Хеллмана. Шифрование по схеме Эль-Гамаля не следует путать с алгоритмом цифровой подписи по схеме Эль-Гамаля.
Шифрование
Сообщение шифруется следующим образом:
- Выбирается сессионный ключ — случайное целое число такое, что
- Вычисляются числа и .
- Пара чисел является шифротекстом.
Нетрудно видеть, что длина шифротекста в схеме Эль-Гамаля длиннее исходного сообщения вдвое.
Расшифрование
Зная закрытый ключ , исходное сообщение можно вычислить из шифротекста по формуле:
При этом нетрудно проверить, что
и поэтому
- .
Для практических вычислений больше подходит следующая формула:
Схема шифрования
Пример
- Шифрование
- Допустим что нужно зашифровать сообщение .
- Произведем генерацию ключей :
- пусть . Выберем - случайное целое число такое,что .
- Вычислим .
- Итак , открытым является тройка ,а закрытым ключом является число .
- Выбираем случайное целое число такое, что 1 < k < (p − 1). Пусть .
- Вычисляем число .
- Вычисляем число .
- Полученная пара является шифротекстом.
- Расшифрование
- Необходимо получить сообщение по известному шифротексту и закрытому ключу .
- Вычисляем M по формуле :
- Получили исходное сообщение .
Так как в схему Эль-Гамаля вводится случайная величина ,то шифр Эль-Гамаля можно назвать шифром многозначной замены. Из-за случайности выбора числа такую схему еще называют схемой вероятностного шифрования. Вероятностный характер шифрования является преимуществом для схемы Эль-Гамаля, так как у схем вероятностного шифрования наблюдается большая стойкость по сравнению со схемами с определенным процессом шифрования. Недостатком схемы шифрования Эль-Гамаля является удвоение длины зашифрованного текста по сравнению с начальным текстом. Для схемы вероятностного шифрования само сообщение и ключ не определяют шифротекст однозначно. В схеме Эль-Гамаля необходимо использовать различные значения случайной величины для шифровки различных сообщений и . Если использовать одинаковые , то для соответствующих шифротектов и выполняется соотношение . Из этого выражения можно легко вычислить , если известно .
Работа в режиме подписи
Цифровая подпись служит для того чтобы можно было установить изменения данных и чтобы установить подлинность подписавшейся стороны. Получатель подписанного сообщения может использовать цифровую подпись для доказательства третьей стороне того, что подпись действительно сделана отправляющей стороной. При работе в режиме подписи предполагается наличие фиксированной хеш-функции , значения которой лежат в интервале .
Подпись сообщений
Для подписи сообщения выполняются следующие операции:
- Вычисляется дайджест сообщения :
- Выбирается случайное число взаимно простое с и вычисляется
- Вычисляется число .
- Подписью сообщения является пара .
Проверка подписи
Зная открытый ключ , подпись сообщения проверяется следующим образом:
- Проверяется выполнимость условий: и . Если хотя бы одно из них не выполняется,то подпись считается неверной.
- Вычисляется дайджест
- Подпись считается верной, если выполняется сравнение:
Пример
- Подпись сообщения.
- Допустим,что нужно подписать сообщение .
- Произведем генерацию ключей:
- Пусть переменные, которые известны некоторому сообществу. Секретный ключ — случайное целое число такое, что .
- Вычисляем открытый ключ : .
- Итак,открытым ключом является тройка .
- Теперь вычисляем хэш-функцию: .
- Выберем случайное число такое, что выполняется условие . Пусть .
- Вычисляем .
- Находим число . Такое существует, так как НОД(k,p-1)=1. Получим что .
- Итак, мы подписали сообщение: .
- Проверка подлинности полученного сообщения.
- Вычисляем хэш-функцию: .
- Проверяем сравнение .
- Вычислим левую часть по модулю 23: .
- Вычислим правую часть по модулю 23: .
- Так как правая и левая части равны, то это означает что подпись верна.
- Главным преимуществом схемы цифровой подписи Эль-Гамаля является возможность вырабатывать цифровые подписи для большого числа сообщений с использованием только одного секретного ключа. Чтобы злоумышленнику подделать подпись, ему нужно решить сложные математические задачи с нахождением логарифма в поле . Следует сделать несколько комментариев:
- Случайное число должно сразу после вычисления подписи уничтожаться,так как если злоумышленник знает случайное число и саму подпись, то он легко может найти секретный ключ по формуле: и полностью подделать подпись.
Число должно быть случайным и не должно дублироваться для различных подписей, полученных при одинаковом значении секретного ключа.
- Использование свертки объясняется тем,что это защищает подпись от перебора сообщений по известным злоумышленнику значениям подписи. Пример: если выбрать случайные числа ,удовлетворяющие условиям , НОД(j,p-1)=1 и предположить что
то легко удостовериться в том,что пара является верной цифровой подписью для сообщения .
- Цифровая подпись Эль-Гамаля стала примером построения других подписей, схожих по своим свойствам. В их основе лежит выполнение сравнения: , в котором тройка принимает значения одной из перестановок ±r, ±s и ±m при каком-то выборе знаков. Например, исходная схема Эль-Гамаля получается при ,, .На таком принципе построения подписи сделаны стандарты цифровой подписи США и России. В американском стандарте DSS (Digital Signature Standard), используется значения , ,, а в Российском стандарте: , , .
- Еще одним из преимуществ является возможность уменьшения длины подписи с помощью замены пары чисел на пару чисел ),где является каким-то простым делителем числа . При этом сравнение для проверки подписи по модулю нужно заменить на новое сравнение по модулю : . Так сделано в американском стандарте DSS (Digital Signature Standard).
Криптостойкость и особенности
В настоящее время криптосистемы с открытым ключом считаются наиболее перспективными. К ним относится и схема Эль-Гамаля, криптостойкость которой основана на вычислительной сложности проблемы дискретного логарифмирования, где по известным p, g и y требуется вычислить x, удовлетворяющий сравнению:
ГОСТ Р34.10-1994, принятый в 1994 году в Российской Федерации, регламентировавший процедуры формирования и проверки электронной цифровой подписи, был основан на схеме Эль-Гамаля. С 2001 года используется новый ГОСТ Р 34.10-2001, использующий арифметику эллиптических кривых, определенных над простыми полями Галуа. Существует большое количество алгоритмов, основанных на схеме Эль-Гамаля: это алгоритмы DSA, ECDSA, KCDSA, схема Шнорра.
Сравнение некоторых алгоритмов:
Алгоритм Ключ Назначение Криптостойкость, MIPS Примечания RSA До 4096 бит Шифрование и подпись 2,7•1028 для ключа 1300 бит Основан на трудности задачи факторизации больших чисел; один из первых асимметричных алгоритмов. Включен во многие стандарты ElGamal До 4096 бит Шифрование и подпись При одинаковой длине ключа криптостойкость равная RSA, т.е. 2,7•1028 для ключа 1300 бит Основан на трудной задаче вычисления дискретных логарифмов в конечном поле; позволяет быстро генерировать ключи без снижения стойкости. Используется в алгоритме цифровой подписи DSA-стандарта DSS DSA До 1024 бит Только подписание Основан на трудности задачи дискретного логарифмирования в конечном поле; принят в качестве гос. стандарта США; применяется для секретных и несекретных коммуникаций; разработчиком является АНБ. ECDSA До 4096 бит Шифрование и подпись Криптостойкость и скорость работы выше, чем у RSA Современное направление. Разрабатывается многими ведущими математиками Примечания
- ↑ Taher ElGamal (1985). «A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms». IEEE Transactions on Information Theory 31 (4): 469-472. DOI:10.1109/TIT.1985.1057074.
Ссылки
- Алфёров А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В Основы криптографии.
- Б. А. Фороузан Схема цифровой подписи Эль-Гамаля // Управление ключами шифрования и безопасность сети / Пер. А. Н. Берлин. — Курс лекций.
- Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone 11.5.2 The ElGamal signature scheme // Handbook of applied cryptography.
Криптосистемы с открытым ключом RSA • DSA • DSS • NTRUEncrypt • Эль-Гамаля • Меркля — Хеллмана • Шнорра • Эллиптические • ГОСТ Р 34.10-2001 • ДСТУ 4145-2002
Категория:- Шифры
Wikimedia Foundation. 2010.