Алгоритм цифровой подписи Эль Гамаля (egsa)

Идея EGSA основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована задача дискретного логарифмирования.

Для реализации алгоритма участниками выбираются некоторые большие простые целые числа p(~10³⁸ или ~2¹⁰²⁴) и g(~10¹⁵⁴ или ~2⁵¹²), g < p.

Алгоритм реализации для отправителя

1. Выбирается случайное целое число x, 1<x<(p-1), которое является секретным ключом для подписывания документов.

2. Вычисляется число y

y = G^x mod p,

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

3. Определяется хэш-функция h(М) документа

m = h(М), 1<m (p-1),

4. Генерируется случайное целое число k, 1< k< (p -1), такое, что k и (p -1) являются взаимно простыми.

5.Вычисляется целое число а:

a = G^kmod p

6. Используя расширенный алгоритм Евклида, вычисляется c помощью секретного ключа x целое число b из уравнения

m = x • a + k • b ( mod (p-1)).

7. Электронный документ М, а также ЭЦП представленная парой (a,b) отправляются получателю.

Алгоритм реализации для отправителя

1. Получатель электронного документа (М, a,b) вычисляет по принятому сообщению M хэш-функцию

m = h(M),

2. Вычисляет значение А = y^a a^b (mod p)

3. Признает сообщение M подлинным, если, и только если выполняется условие А = g^m (mod p). Или y^a a^b (mod p) = g^m (mod p).

Пример.

Пусть p=11, g = 2 и секретный ключ x = 8, m = 5.

Вычисляем значение открытого ключа y = g^x mod p = 2⁸ mod 11=3.

ЭЦП отправителя

Выберем случайное целое число к = 9, при этом к и (Р-1) являются взаимно простыми.

НОД(9,10) = 1.

Вычислим элементы а и b подписи а = g^k mod p = 2⁹ mod 11=6,

m = x • a + k • b ( mod (p-1)).

5 = (6*8 + 9* b)(mod 10) или 9 • b = -43(mod 10).

Решение: b = 3.

Цифровая подпись представляет собой пару: а = 6, b = 3.

Получатель

Вычисляет хэш-значение для сообщения p : m = 5.

Вычисляет два числа:

1. y^a a^b (mod p) = 3⁶ • 6³ (mod 11) = 10 (mod 11);

2. g^m (mod p) = 2⁵ (mod 11) = 10 (mod 11).

Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.

Недостаток: по сравнению со схемой подписи RSA, длина цифровой подписи получается в 1,5 раза больше, что увеличивает время ее вычисления.

Отечественный стандарт электронной подписи (гост р 34.10-94)

ГОСТ Р 34.10-94, вступивший в силу в 1995г. используются следующие параметры:

р - большое простое число длиной от 509- 512 бит либо от 1020 - 1024 бит;

q - простой сомножитель числа (р -1), имеющий длину 254 -256 бит.

а - любое число, а< (р -1), a^q mod р=1;

р, q, а являются открытыми и используются всеми пользователями сети

х- некоторое число, x<q и является секретным ключом;

у = а^х mod p и является открытым ключом.

Алгоритм использует однонаправленную хэш-функцию h(х), ГОСТа Р 34.11-94, для этого отправитель:

1. Генерирует случайное секретное число k<q,

2. Вычисляет значения

При r=0, то k присваивают другое значение и начинают сначала, при =0, то принимают =1

3. Документ М и цифровая подпись, представляющая пару ( ), отправляются по сети.

Получатель вычисляет

u₁ = [(h(m)^-1 mod q)* s mod q]

u₂ =[(h(m)^-1 mod q) *(q-r) mod q)]

v = [(a^u1 y^u2) mod p] mod q

4. Подпись корректна, если v = r.

Подпись созданная с использованием стандарта ГОСТ 3410 называется рандомизированной, так как для одного и того же сообщения с использованием одного и того же закрытого ключа каждый раз будут создаваться разные подписи (r,s), из-за новое значение k.

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