Схема подписи Эль-Гамаля - это схема цифровой подписи, основан на сложности вычисления дискретных логарифмов. Он был описан Тахером Эльгамалом в 1985 году.
Алгоритм подписи Эль-Гамаля редко используется на практике. Гораздо более широко используется вариант, разработанный в NSA и известный как алгоритм цифровой подписи. Есть еще несколько вариантов. Схему подписи Эль-Гамаля не следует путать с шифрованием Эль-Гамаля, которое также было изобретено Тахером Эльгамалом.
Содержание
- 1 Обзор
- 2 История
- 3 Работа
- 3.1 Генерация ключей
- 3.1.1 Генерация параметров
- 3.1.2 Индивидуальные ключи
- 3.2 Распределение ключей
- 3.3 Подпись
- 3.4 Проверка подписи
- 4 Корректность
- 5 Безопасность
- 5.1 Экзистенциальная подделка
- 6 См. Также
- 7 Ссылки
Обзор
The ElGamal Схема подписи - это схема цифровой подписи, основанная на алгебраических свойствах модульного возведения в степень вместе с проблемой дискретного логарифмирования. Алгоритм использует пару ключей, состоящую из открытого ключа и закрытого ключа . Закрытый ключ используется для создания цифровой подписи для сообщения, и такая подпись может быть проверена с помощью соответствующего открытого ключа подписывающей стороны. Цифровая подпись обеспечивает аутентификацию сообщения (получатель может проверить источник сообщения), целостность (получатель может проверить, что сообщение не было изменено с момента его подписания) и невозможность отказа от авторства (отправитель не может ложно утверждать, что они не подписал сообщение).
История
Схема подписи Эль-Гамаля была описана Тахиром Эльгамалом в 1985 году.
Операция
Схема включает четыре операции: генерация ключа (которая создает пара ключей), распространение ключей, подпись и проверка подписи.
Генерация ключа
Генерация ключа состоит из двух этапов. Первый этап - это выбор параметров алгоритма, которые могут использоваться разными пользователями системы, а на втором этапе вычисляется одна пара ключей для одного пользователя.
Создание параметров
Параметры алгоритма: . Эти параметры могут совместно использоваться пользователями системы.
Пользовательские ключи
Учитывая набор параметров, на втором этапе вычисляется пара ключей для одного пользователя:
- Выбрать целое число случайным образом из .
- Вычислить .
- закрытый ключ, а - открытый ключ.
Распределение ключей n
Подписывающая сторона должна послать открытый ключ получателю через надежный, но не обязательно секретный механизм. Подписывающая сторона должна держать закрытый ключ в секрете.
Подписание
Сообщение подписано следующим образом:
- Выберите целое число случайным образом из с взаимно простое с .
- Compute .
- Вычислить .
- В том маловероятном случае, когда начнется снова с другим случайным .
Подпись: .
Проверка подписи
Можно проверить, что подпись - действительная подпись для сообщения следующим образом:
- Убедитесь, что
- подпись действительна тогда и только тогда, когда g H (m) ≡ yrrs (mod p). {\ displaystyle g ^ {H (m)} \ Equiv y ^ {r} r ^ {s} {\ pmod {p}}.}
Корректность
Алгоритм правильный в том смысле, что подпись, созданная с помощью алгоритма подписи, всегда будет принята проверяющим.
Вычисление s {\ displaystyle s}во время генерации подписи подразумевает, что
- H (m) ≡ x r + s k (mod p - 1). {\ displaystyle H (m) \, \ Equiv \, xr + sk {\ pmod {p-1}}.}
Поскольку g {\ displaystyle g}является относительно простым п {\ displaystyle p},
- г ЧАС (м) ≡ gxr + sk (mod p) ≡ (gx) r (gk) s (mod p) ≡ (y) r (r) s (mod p). {\ displaystyle {\ begin {align} 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 { выровнено}}}
Безопасность
Третья сторона может подделать подписи либо путем нахождения секретного ключа подписывающей стороны x, либо путем обнаружения конфликтов в хэш-функции H (m) ≡ H (M) (mod п - 1) {\ Displaystyle Н (м) \ экв Н (М) {\ pmod {р-1}}}Обе проблемы считаются сложными. Тем не менее, по состоянию на 2011 г. точного сокращения до предположения о вычислительной сложности не известно.
Подписавшая сторона должна быть осторожна, чтобы выбрать другое k равномерно случайным образом для каждой подписи и быть уверенным, что k или даже частичная информация о k не просочится. В противном случае злоумышленник может получить секретный ключ x с меньшими трудностями, что, возможно, будет достаточно для практической атаки. В частности, если два сообщения отправляются с использованием одного и того же значения k и одного и того же ключа, тогда злоумышленник может вычислить x напрямую.
Экзистенциальная подделка
Исходная статья не содержала хэш-функция в качестве системного параметра. Сообщение m использовалось непосредственно в алгоритме вместо H (m). Это делает возможным атаку под названием экзистенциальная подделка, как описано в разделе IV документа. Пойнтшевал и Стерн обобщили этот случай и описали два уровня подделки:
- Подделка с одним параметром. Выберите e {\ displaystyle e}такой, что 1 < e < p − 1 {\displaystyle 1. Установите r: = gey mod p {\ displaystyle r: = g ^ {e} y {\ bmod {p}}}и s: = - r mod (p - 1) {\ displaystyle s: = - r {\ bmod {(p-1)}}}. Тогда кортеж (r, s) {\ displaystyle (r, s)}является действительной подписью для сообщения m = es mod (p - 1) {\ displaystyle m = es {\ bmod {(p-1)}}}.
- Подделка с двумя параметрами. Выберите 1 < e, v < p − 1 {\displaystyle 1и gcd (v, p - 1) = 1 {\ displaystyle \ gcd ( v, p-1) = 1}. Установите r: = geyv mod p {\ displaystyle r: = g ^ {e} y ^ {v} {\ bmod {p}}}и s: = - rv - 1 мод (p - 1) {\ displaystyle s: = - rv ^ {- 1} {\ bmod {(p-1)}}}. Тогда кортеж (r, s) {\ displaystyle (r, s)}является действительной подписью для сообщения m = es mod (p - 1) {\ displaystyle m = es {\ bmod {(p-1)}}}. Подделка с одним параметром - частный случай подделки с двумя параметрами, когда v = 1 {\ displaystyle v = 1}.
См. Также
Ссылки