Схема подписи Эль-Гамаля

Схема цифровой подписи

Схема подписи Эль-Гамаля — это схема цифровой подписи , основанная на сложности вычисления дискретных логарифмов . Он был описан Тахером Эльгамалем в 1985 году. ^[1]

Алгоритм подписи Эль-Гамаля на практике используется редко. Гораздо более широко используется вариант, разработанный в АНБ и известный как алгоритм цифровой подписи . Есть еще несколько вариантов. ^[2] Схему подписи Эль-Гамаля не следует путать с шифрованием Эль-Гамаля , которое также было изобретено Тахером Эльгамалем.

Обзор

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

История

Схема подписи Эль-Гамаля была описана Тахером Эльгамалем в 1985 году. ^[1] Она основана на проблеме Диффи-Хеллмана .

Операция

Схема включает четыре операции: генерацию ключей (которая создает пару ключей), распространение ключей, подписание и проверку подписи.

Генерация ключей

Генерация ключей состоит из двух этапов. Первый этап — это выбор параметров алгоритма, которые могут быть общими для разных пользователей системы, а второй этап — вычисление одной пары ключей для одного пользователя.

Генерация параметров

• Выберите длину ключа . ${\displaystyle N}$
• Выберите -битное простое число ${\displaystyle N}$ ${\displaystyle p}$
• Выберите криптографическую хеш-функцию с битами выходной длины . Если , используются только самые левые биты вывода хэша. ${\displaystyle H}$ ${\displaystyle L}$ ${\displaystyle L>N}$ ${\displaystyle N}$
• Выберите генератор мультипликативной группы целых чисел по модулю p , . ${\displaystyle g<p}$ ${\displaystyle Z_{p}^{*}}$

Параметры алгоритма: . Эти параметры могут быть общими между пользователями системы. ${\displaystyle (p,g)}$

Ключи для каждого пользователя

Учитывая набор параметров, второй этап вычисляет пару ключей для одного пользователя:

• Случайным образом выберите целое число из . ${\displaystyle x}$ ${\displaystyle \{1\ldots p-2\}}$
• Вычислить . ${\displaystyle y:=g^{x}{\bmod {p}}}$

${\displaystyle x}$является закрытым ключом и является открытым ключом. ${\displaystyle y}$

Распределение ключей

Подписывающая сторона должна отправить открытый ключ получателю с помощью надежного, но не обязательно секретного механизма. Подписавшая сторона должна хранить секретный ключ в секрете. ${\displaystyle y}$ ${\displaystyle x}$

Подписание

Сообщение подписывается следующим образом: ${\displaystyle m}$

• Случайным образом выберите целое число от с относительно простым до . ${\displaystyle k}$ ${\displaystyle \{2\ldots p-2\}}$ ${\displaystyle k}$ ${\displaystyle p-1}$
• Вычислить . ${\displaystyle r:=g^{k}{\bmod {p}}}$
• Вычислить . ${\displaystyle s:=(H(m)-xr)k^{-1}{\bmod {(}}p-1)}$
• В том маловероятном случае, что начнется снова с другим случайным . ${\displaystyle s=0}$ ${\displaystyle k}$

Подпись есть . ${\displaystyle (r,s)}$

Проверка подписи

Проверить, что подпись является действительной подписью сообщения, можно следующим образом: ${\displaystyle (r,s)}$ ${\displaystyle m}$

• Убедитесь в этом и . ${\displaystyle 0<r<p}$ ${\displaystyle 0<s<p-1}$
• Подпись действительна тогда и только тогда, когда ${\displaystyle g^{H(m)}\equiv y^{r}r^{s}{\pmod {p}}.}$

Корректность

Алгоритм корректен в том смысле, что подпись, созданная с помощью алгоритма подписи, всегда будет принята проверяющим лицом.

Вычисление во время генерации подписи подразумевает ${\displaystyle s}$

${\displaystyle H(m)\,\equiv \,xr+sk{\pmod {p-1}}.}$

Поскольку относительно просто , ${\displaystyle g}$ ${\displaystyle p}$

${\displaystyle {\begin{aligned}g^{H(m)}&\equiv g^{xr+sk}{\pmod {p}}\\&\equiv (g^{x})^{r}(g^{k})^{s}{\pmod {p}}\\&\equiv (y)^{r}(r)^{s}{\pmod {p}}.\\\end{aligned}}}$

Безопасность

Третья сторона может подделать подписи, найдя секретный ключ x подписывающего лица или обнаружив коллизии в хэш-функции . Обе проблемы считаются трудными. Однако по состоянию на 2011 год не было известно о жестком снижении допущения о вычислительной сложности . ${\displaystyle H(m)\equiv H(M){\pmod {p-1}}}$

Подписавший должен быть осторожен и равномерно случайным образом выбирать разные k для каждой подписи и быть уверенным, что k или даже частичная информация о k не будет утеряна. В противном случае злоумышленник сможет получить секретный ключ x с меньшими трудностями, возможно, достаточными для практической атаки. В частности, если два сообщения отправляются с использованием одного и того же значения k и одного и того же ключа, злоумышленник может вычислить x напрямую. ^[1]

Экзистенциальная подделка

В оригинальной статье ^[1] хеш-функция не использовалась в качестве системного параметра. Сообщение m использовалось непосредственно в алгоритме вместо H(m) . Это делает возможным атаку, называемую экзистенциальной подделкой , как описано в разделе IV статьи. Пойнтчеваль и Стерн обобщили этот случай и описали два уровня подделок: ^[3]

1. Однопараметрическая подделка. Выберите такой, чтобы . Установите и . Тогда кортеж является допустимой подписью сообщения . ${\displaystyle e}$ ${\displaystyle 1<e<p-1}$ ${\displaystyle r:=g^{e}y{\bmod {p}}}$ ${\displaystyle s:=-r{\bmod {(p-1)}}}$ ${\displaystyle (r,s)}$ ${\displaystyle m=es{\bmod {(p-1)}}}$
2. Двухпараметрическая подделка. Выберите , и . Установите и . Тогда кортеж является допустимой подписью сообщения . Однопараметрическая подделка является частным случаем двухпараметрической подделки, когда . ${\displaystyle 1<e,v<p-1}$ ${\displaystyle \gcd(v,p-1)=1}$ ${\displaystyle r:=g^{e}y^{v}{\bmod {p}}}$ ${\displaystyle s:=-rv^{-1}{\bmod {(p-1)}}}$ ${\displaystyle (r,s)}$ ${\displaystyle m=es{\bmod {(p-1)}}}$ ${\displaystyle v=1}$

Смотрите также

• Модульная арифметика
• Алгоритм цифровой подписи
• Алгоритм цифровой подписи эллиптической кривой
• Шифрование Эль-Гамаля
• подпись Шнорра
• Алгоритм подписи Пойнтчеваля – Штерна

Рекомендации

1. Тахер Эль-Гамаль (1985). «Криптосистема с открытым ключом и схема подписи на основе дискретных логарифмов» (PDF) . Транзакции IEEE по теории информации . 31 (4): 469–472. CiteSeerX  10.1.1.476.4791 . дои : 10.1109/TIT.1985.1057074. S2CID  2973271.(версия конференции появилась в CRYPTO '84, стр. 10–18)
2. К. Ниберг, Р. А. Рюппель (1996). «Восстановление сообщений для схем подписи на основе задачи дискретного логарифмирования». Проекты, коды и криптография . 7 (1–2): 61–81. дои : 10.1007/BF00125076. S2CID  123533321.
3. Пойнтчеваль, Дэвид; Стерн, Жак (2000). «Аргументы безопасности цифровых подписей и слепых подписей» (PDF) . Дж Криптология . 13 (3): 361–396. CiteSeerX 10.1.1.208.8352 . дои : 10.1007/s001450010003. S2CID  1912537. Архивировано из оригинала (PDF) 22 апреля 2021 г. Проверено 17 августа 2019 г.