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

редактировать

Схема подписи Эль-Гамаля - это схема цифровой подписи, основан на сложности вычисления дискретных логарифмов. Он был описан Тахером Эльгамалом в 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 {\ displaystyle N}N .
  • Выберите N {\ displaystyle N}N -битное простое число number p {\ displaystyle p}p
  • Выберите криптографическую хеш-функцию H {\ displaystyle H}H с выходной длиной L { \ displaystyle L}L бит. Если L>N {\ displaystyle L>N}{\displaystyle L>N} , используются только крайние левые N {\ displaystyle N}N бит хеш-вывода.
  • Выберите генератор g < p {\displaystyle g{\ displaystyle g <p} мультипликативной группы целых чисел по модулю p, Z p ∗ {\ displaystyle Z_ {p} ^ {*}}Z_p ^ * .

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

Пользовательские ключи

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

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

x {\ displaystyle x}x - закрытый ключ, а y {\ displaystyle y}y - открытый ключ.

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

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

Подписание

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

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

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

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

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

  • Убедитесь, что 0 < r < p {\displaystyle 00 <r <p и 0 < s < p − 1 {\displaystyle 00 <s <p-1 .
  • подпись действительна тогда и только тогда, когда g H (m) ≡ yrrs (mod p). {\ displaystyle g ^ {H (m)} \ Equiv y ^ {r} r ^ {s} {\ pmod {p}}.}g ^ {H (m)} \ Equiv y ^ rr ^ s \ pmod p.

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

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

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

H (m) ≡ x r + s k (mod p - 1). {\ displaystyle H (m) \, \ Equiv \, xr + sk {\ pmod {p-1}}.}H (m) \, \ Equiv \, xr + sk \ pmod {p-1}.

Поскольку g {\ displaystyle g}g является относительно простым п {\ displaystyle p}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 { выровнено}}}{\ displayst yle {\ 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}}. \\\ конец {выровнено} }}

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

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

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

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

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

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

См. Также

Ссылки

Последняя правка сделана 2021-05-18 10:02:20
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте