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

 

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

Для генерации пары ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число и большое целое число , причем . Отправи­тель и получатель подписанного документа используют при вы­числениях одинаковые большие целые числа ( или ) и ( или ), которые не являются секретными. Отправитель выбирает случайное целое число , , и вычисляет . Число является открытым ключом, используемым для проверки подписи отправителя. Число открыто передается всем потенциальным получателям документов. Число является секретным ключом отправителя для подписывания документов и должно храниться в секрете. Для того чтобы подписать сообщение , сначала отправи­тель хэширует его с помощью хэш-функции в целое число , , и генерирует случайное целое число , , такое, что и являются взаимно простыми. Затем отправитель вычисляет целое число : и, применяя расширенный алгоритм Евклида, вычисляет с помо­щью секретного ключа целое число из уравнения .

Пара чисел образует цифровую подпись : , проставляемую под документом . Тройка чисел передается получателю, в то время как пара чисел держится в секрете.

После приема подписанного сообщения получатель должен проверить, соответствует ли подпись сообщению . Для этого получатель сначала вычисляет по принятому сооб­щению число , т.е. хэширует принятое сообщение . Затем получатель вычисляет значение и признает сообщение подлинным, если, и только если . Иначе говоря, получатель проверяет справедливость соот­ношения .

Можно строго математически доказать, что последнее ра­венство будет выполняться тогда, и только тогда, когда подпись под документом получена с помощью именно того сек­ретного ключа , из которого был получен открытый ключ . Та­ким образом, можно надежно удостовериться, что отправителем сообщения был обладатель именно данного секретного ключа , не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ .

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

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

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

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

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

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

Пример. Выберем числа , и секретный ключ . Вычисля­ем значение открытого ключа . Предположим, что исходное сообщение характеризуется хэш-значением . Для того чтобы вычислить цифровую подпись для сообщения , имеющего хэш-значение , сначала выберем случайное целое число . Убедимся, что числа и являются взаимно простыми. Действительно, НОД . Далее вычисляем элементы и подписи: , элемент определяем из уравнения , используя расширенный алгоритм Евклида. При , , , получаем или . Решение b = 3. Цифровая подпись представляет собой пару , . Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ , получатель вычисляет хэш-значение для сообще­ния : , а затем вычисляет:

1. ,

2. .

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