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

Схема Эль-Гамаль является одной из самых распространенных схем ЭЦП. Этому послужило, во-первых то, что при надлежащей и достаточно хорошо проверенной стойкости система имеет хорошую скорость вычисления. Во-вторых, схема имеет достаточно много модификаций, что в принципе мало свойственно асимметричным шифрам. В схеме Эль Гамаль абонент, подписывающий документ, доказывает все желающим проверить подпись, что знает секретный ключ х – степень, в которую был возведен образующий элемент а, чтобы получить открытый ключ b. Явным образом продемонстрировать х, естественно нельзя, так как любой участник информационного обмена начнет подписывать им документы. Поэтому приходится демонстрировать не само письмо, а результат некоторой математической формулы с участием х. При проверке само число х ни на каком этапе не раскрывается, но проверяющий на основе этой формулы удостоверяется, что отправитель сообщения действительно знает х.

Базовый элемент ЭЦП по схеме Эль Гамаля выглядит следующим образом. На этапе подписания отправитель:

1. Генерирует случайное число k, уникальное для каждого подписываемого документа, взаимно простое с числом (р -1).

2. Вычисляет r = (a^k mod p).

3. Вычисляет обратный элемент поля к числу k – его обозначают (k ^-1mod (p -1)) или 1/ k, в дальнейшем операция “деление на k ” равносильно умножению на 1/ k.

4. Вычисляет s=((h-x ´ r) /k) mod (p-1), где h – контрольная сумма (значение хэш-функции) подписываемого документа.

Пара чисел (r,s) является цифровой подписью для документа, имеющего контрольную сумму h. На приемной стороне получатель:

1. Вычисляет u=((b^r) ´ (r^s) mod p).

2. Вычисляет v=(a^h mod p).

3. Проверяет равенство значений u=v (если равенство выполняется, то подпись верна, в противном случае документ сфальcифицирован).

В случае корректности ЭЦП данное равенство является тождеством. Произведем несложные преобразования над u (подразумеваем, что все действия выполняются по модулю числа p):

u = (b^r) ´ (r^s) =(((a^x)^r) ´ ((a^k)^s) = a^{(xr + h-xr)} = ah = v.

Как видим, во-первых, получилось тождество, а, во-вторых, ни на одном этапе преобразований (а все они доступны проверяющему) число х не фигуриловало в открытом виде – его как бы ”экранируют” две величины r и k, причем вторая неизвестна получателю. Схема ЭЦП Эль Гамаля приведена на рис. 5.3.

В качестве особенностей ЭЦП схемы Эль Гамаля необходимо упомянуть требование проверять на приемной стороне неравенство (r<p). Если такой проверки не делать, то злоумышленник сможет подделать подпись, имея перехваченным хотя бы один документ, подписанный легальным пользователем. Правда по этому алгоритму значение r получается достаточно большим, что и позволяет защищаться от него сравнением r с простым числом p. Вторым требованием является наличие у числа (p -1) большого простого делителя. Обычно первоначально выбирается большое простое число q на один бит меньше требуемой, а затем р вычисляется как p =2 ´ q + 1 и проверяется на простоту.