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

Более надежный и удобный для реализации на персональ­ных ком­пьютерах алгоритм цифровой подписи был разработан в 1984 г. американ­цем арабского происхождения Эль Гамалем. В 1991г. НИСТ США обос­новал перед комиссией Конгресca США выбор алгоритма цифровой под­писи Эль Гамаля в каче­стве основы для национального стандарта.

Идея EGSA (El Gamal Signature Algorithm) основана на том, что для обоснования практической невозможности фальсификации цифро­вой подписи может быть использована более сложная вычислительная за­дача, чем разложение на мно­жители большого целого числа — задача диск­рет­ного логарифми­рования. Кроме того, Эль Гамалю удалось избежать явной слабо­сти алгоритма цифровой подписи RSA, связанной с воз­можностью подделки цифровой подписи под некоторыми сообщениями без опре­деле­ния секретного ключа.

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

Ø Выбирают несекретные параметры алгоритма: два больших целых числа p — простое и  g < p:

p (~10³⁰⁸ или ~2¹⁰²⁴) и g (~10¹⁵⁴ или ~2⁵¹²);

Ø Отправитель выбирает секретный ключ x для подписывания докумен­тов. Им является случайное целое число x ÎZ _p, то есть 1< x < p;

Ø Отправитель вычисляет открытый ключ y, используемый для проверки своей подписи. Он и вычисляет

y = g^x mod p

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

Ø Отправи­тель хэширует сообщение M с помощью хэш-функции h (·) в целое число m:

m = h (M), 1< m <(p -1);

Ø Отправи­тель генерирует секретный параметр алгоритма: случайное целое число k, 1< k <(p -1), такое, что k и (p -1) являются взаимно простыми;

Ø Наконец отправитель вычис­ляет цифровую подпись S=(а, b), состоя­щую из двух целых чисел а и b, вычисляемых следующим образом:

а = g^k mod p,

и число b вычисляется с помо­щью секретного ключа x из уравнения

m = x · a + k · b mod (p - 1),

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

Тройка чисел (M, а, b) передаётся получателю, в то время как пара чисел (x, k) держится в секрете.

После приема подписанного сообщения (M, а, b) получатель дол­жен проверить, соответствует ли подпись S=(а,b) сообщению M. Для этого получатель:

Ø Хеширует принятое сообщение M, то есть вычисляет m = h (M).

Ø Вычисляет значение А = g^m mod p.

Ø Признает сообщение M подлинным только, если оно совпало с

А = y^a a^b mod p.

Иначе говоря, он проверяет справедливость соот­ношения

А = y^a a^b mod p = g^m mod p.

Mожно строго математически доказать, что последнее ра­венство будет выполняться тогда и только тогда, когда подпись S=(a, b) под доку­ментом M получена с помощью именно того сек­ретного ключа x, из кото­рого был получен открытый ключ y. Таким образом, можно надежно удо­стовериться, что отправителем сообщения M был обладатель именно дан­ного секретного ключа x, не раскрывая при этом сам ключ, и что отправи­тель подписал именно этот конкретный документ M.

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

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

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

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

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

Убедимся, что числа k и (p -1) являются взаимно простыми. Действительно, HОД (9,10) =1.

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

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

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

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

При m = 5, а = 6, x = 8, k = 9, p = 11 получаем b = 3 как решение уравнения

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

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

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

y^aa^b mod p = 3⁶ · б³ mod 11 =10 mod 11;

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

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

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

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

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

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

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