40.6. Цифровая подпись Эль-Гамаля

Этот протокол, опубликованный в 1984 году, послужил прототипом стандартов США и России электронной цифровой подписи.

Зафиксируем конечное поле , где p – простое число. Пусть g – первообразный вычет по mod p. Вычет является секретным ключом отправителя А, а вычет является его открытым ключом. Обозначим через сообщение (хэш-значение сообщения), которое хочет подписать А. Протокол подписи и проверки.

1) А выбирает случайное секретное , вычисляет , .

2) Отправитель сообщения А, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа x целое число из уравнения m = x∙a + k b (mod (p –1)) и формирует подписанное сообщение (m,a,b) (пара, (a,b) есть подпись сообщения m).

3) Для проверки подписи получатель Б вычисляет и . Если вычисленные значения совпадают, то подпись принимается, в противном случае отвергается.

Нетрудно проверить, что если подпись правильная, то выполняется сравнение

. (*)

Следует отметить, что выполнение каждой подписи по методу Эль – Гамаля требует нового значения k, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение k, повторно используемое отправителем, то он сможет раскрыть секретный ключ x отправителя.

Пример. Выберем: числа p =11, g = 2 и секретный ключ x = 8. Вычисляем значение открытого ключа:

y = g^x mod p =2⁸ mod 11 = 3.

Предположим, что исходное сообщение M характеризуется хэш-значением m = 5.

Для того чтобы вычислить цифровую подпись для сообщения M, имеющего хэш-значение m = 5, сначала выберем случайное целое число k = 9. Убедимся, что числа k и (p – 1) являются взаимно простыми. Действительно,

НОД (9, 10) = 1.

Далее вычисляем элементы a и b подписи:

a = g^k mod p = 2⁹ mod 11 = 6,

элемент b определяем, используя расширенный алгоритм Евклида:

m = x∙a + k b (mod (p – 1)).

При m = 5, a = 6, x = 8, k = 9, p = 11 получаем 5 = (6∙8 + 9∙b)(mod 10)

Или 9∙b  – 43 (mod 10). Решение: b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3.

Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ y = 3, получатель вычисляет хэш-значение m = 5 для сообщения M, а затем вычисляет два числа:

1) y^aa^b (mod p) = 3⁶∙6³ (mod 11) =10 (mod 11);

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

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

Следует отметить, что схема Эль–Гамаля является характерным примером подхода, который допускает пересылку сообщения M в открытой форме вместе с присоединенным аутентификатором (a,b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.

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

Схема цифровой подписи Эль–Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи 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, , и вычислением .