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

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

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

Обзор [ править ]

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

История [ править ]

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

Операция [ править ]

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

Генерация ключей [ править ]

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

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

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

См. Также [ править ]

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

Ссылки [ править ]