Схема подписи Эль-Гамаля - ElGamal signature scheme
Схема подписи Эль-Гамаля - это схема цифровой подписи , которая основана на сложности вычисления дискретных логарифмов . Он был описан Тахером Эльгамалом в 1985 году.
Алгоритм подписи Эль-Гамаля на практике используется редко. Гораздо более широко используется вариант, разработанный в АНБ и известный как алгоритм цифровой подписи . Есть еще несколько вариантов. Схему подписи Эль-Гамаля не следует путать с шифрованием Эль-Гамаля, которое также было изобретено Тахером Эльгамалом.
Обзор
Схема подписи Эль-Гамаля - это схема цифровой подписи, основанная на алгебраических свойствах модульного возведения в степень вместе с проблемой дискретного логарифмирования. Алгоритм использует пару ключей, состоящую из открытого и закрытого ключей . Закрытый ключ используется для создания цифровой подписи сообщения, и такая подпись может быть проверена с помощью соответствующего открытого ключа подписывающей стороны. Цифровая подпись обеспечивает аутентификацию сообщения (получатель может проверить источник сообщения), целостность (получатель может проверить, что сообщение не было изменено с момента его подписания) и неотказуемость (отправитель не может ложно утверждать, что они не подписал сообщение).
История
Схема подписи Эль-Гамаля была описана Тахером Эльгамалом в 1985 году.
Операция
Схема включает четыре операции: генерацию ключа (которая создает пару ключей), распространение ключей, подпись и проверку подписи.
Генерация ключей
Генерация ключей состоит из двух этапов. Первый этап - это выбор параметров алгоритма, которые могут использоваться разными пользователями системы, а на втором этапе вычисляется одна пара ключей для одного пользователя.
Генерация параметров
- Выберите длину ключа .
- Выберите -битовое простое число
- Выберите криптографическую хеш-функцию с битами выходной длины . Если используются только крайние левые биты хеш-вывода.
- Выберите генератор из мультипликативной группы целых чисел по модулю р , .
Параметры алгоритма . Эти параметры могут совместно использоваться пользователями системы.
Ключи для каждого пользователя
Учитывая набор параметров, на втором этапе вычисляется пара ключей для одного пользователя:
- Случайным образом выбрать целое число из .
- Вычислить .
- это закрытый ключ и открытый ключ.
Распределение ключей
Подписывающая сторона должна отправить открытый ключ получателю через надежный, но не обязательно секретный механизм. Подписывающая сторона должна хранить секретный ключ в секрете.
Подписание
Сообщение подписано следующим образом:
- Случайным образом выбрать целое число из числа с взаимно простым до .
- Вычислить .
- Вычислить .
- В том маловероятном случае, если это начнется снова, с другим рандомом .
Подпись есть .
Проверка подписи
Проверить, является ли подпись действительной подписью сообщения, можно следующим образом:
- Убедитесь, что и .
- Подпись действительна тогда и только тогда, когда
Правильность
Алгоритм верен в том смысле, что подпись, созданная с помощью алгоритма подписи, всегда будет принята верификатором.
Вычисление при генерации подписи подразумевает
Поскольку относительно просто ,
Безопасность
Третья сторона может подделывать подписи либо путем нахождения секретного ключа подписывающей стороны x, либо путем обнаружения коллизий в хэш-функции . Обе проблемы считаются сложными. Однако по состоянию на 2011 г. точного сведения к предположению о вычислительной сложности не известно.
Подписывающее лицо должно быть осторожным, чтобы выбрать другое k равномерно случайным образом для каждой подписи и быть уверенным, что k или даже частичная информация о k не просочится. В противном случае злоумышленник может получить секретный ключ x с меньшими трудностями, что, возможно, будет достаточно для практической атаки. В частности, если два сообщения отправляются с использованием одного и того же значения k и одного и того же ключа, злоумышленник может вычислить x напрямую.
Экзистенциальная подделка
Исходная статья не включала хеш-функцию в качестве системного параметра. Сообщение m использовалось непосредственно в алгоритме вместо H (m) . Это делает возможным атаку, называемую экзистенциальной подделкой , как описано в разделе IV документа. Пойнтшеваль и Стерн обобщили этот случай и описали два уровня подделок:
- Однопараметрическая подделка. Выберите такую что . Установите и . Тогда кортеж является действительной подписью сообщения .
- Двухпараметрическая подделка. Выберите , и . Установите и . Тогда кортеж является действительной подписью сообщения . Однопараметрическая подделка является частным случаем двухпараметрической подделки, когда .
Смотрите также
- Модульная арифметика
- Алгоритм цифровой подписи
- Эллиптическая кривая DSA
- Шифрование Эль-Гамаля
- Подпись Шнорра
- Алгоритм подписи Пойнтчеваля – Стерна