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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$x$ это закрытый ключ и $y$ является открытым ключом.

Распределение ключей [ править ]

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

Подписание [ править ]

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

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

Подпись $(r,s)$ .

Проверка подписи [ править ]

Можно проверить, что подпись $(r,s)$ является допустимой подписью для сообщения $m$ следующее:

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

Корректность [ править ]

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

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

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

С $g$ является относительно простым для $p$ ,

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

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

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

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

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