Особенности протокола Эль-Гамаля

Схема цифровой подписи Эль–Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSA:

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

2. При выборе модуля P достаточно проверить, что это число является простым и что у числа (P –1) имеется большой простой множитель (то есть всего два достаточно просто проверяемых условия).

3. Процедура формирования подписи по схеме Эль–Гамаля не позволяет вычислять цифровые подписи под новыми сообщениями без знания секретного ключа (как в RSA).

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

Выделим отдельно особенности протокола Эль–Гамаля, сязанные с трудоемкостями его выполнения и возможных атак на этот протокол.

1) В этом протоколе, так же как и в системах подписи и использованием RSA, надо выполнить возведение в большую степень по модулю большого числа p. Однако вычисления, зависящие от m, на первом шаге не выполняются, то есть значение k может быть выбрано заранее и заранее вычислен вычет a. Таким образом, для получения собственно подписи надо выполнить одно вычитание, два умножения и одно обращение по mod p-1. То есть при условии выполнения предварительных вычислений, получение подписи здесь является значительно более быстрым, чем в системе RSA.

2) Стойкость системы Эль–Гамаля основывается на проблеме дискретного логарифмирования. Если противник сможет найти секретный ключ из открытого ключа , то он сможет подделывать подпись.

3) Если k известно противнику, то он имеет линейное сравнение относительно x

,

где m, a, b известны. Тогда при противник вычисляет . Неизвестное x можно найти опробованием l вариантов.

4) Для подделки подписи под сообщением m (хэш-значением сообщения) противник должен найти a, b такие, что , и

. (*)

При фиксировании случайным образом любой пары элементов из тройки m, a, b найти оставшийся элемент очень трудно.

5) Имеется способ одновременного выбора m, a, b, для которых выполняется (*). Выберем i, j такие, что и . Положим

, ,

,

.

Вычислим . Таким образом (*) выполнено.

6) Пусть противник располагает сообщением m, a, b с правильной подписью. Тогда он может создать множество сообщений с правильными подписями. Пусть h, i, j такие, что и . Положим

, ,

,

.

Вычислим , где . Тогда, учитывая, что , получаем

Очевидно, что это частный случай формул из предыдущего пункта при h=0 и b=1.

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

. (**)

Отсюда . Если сравнение имеет несколько решений, то найти истинное можно опробованием, так как равенство известно. Вычислив k, легко найти x из одного сравнения системы (**).

8) Рассмотрим еще один способ подделки подписи в системе Эль – Гамаля. Пусть p-1=e×w, где e – произведение маленьких простых чисел. Известен первообразный вычет d=c×w, где и такое t, что . Тогда для любого легко найти такие a, b, что выполняется (*) без знания секретного ключа x. Для этого надо выполнить следующее: вычислить вычет такой, что и положить a=d, b=t(m-cwz). Проверим выполнение сравнения (*). Вычислим

Этот метод может быть использован, если параметры системы подписи порождаются централизовано. Тот, кто выбирает параметры, может подделывать подписи всех обслуживаемых им участников системы связи. Для этого достаточно выбрать p и соответствующее d, далее замаскировать d выбором t, , и вычислением .