Более надежный и удобный для реализации на персональных компьютерах алгоритм цифровой подписи был разработан в 1984 г. американцем арабского происхождения Тахером Эль-Гамалем. В 1991г. НИСТ США обосновал перед комиссией Конгресса США выбор алгоритма цифровой подписи Эль-Гамаля в качестве основы для национального стандарта.
Алгоритм цифровой подписи Эль-Гамаля (ЕGSА)
Название ЕGSА происходит от слов ЕІ GаmаІ Signaturе Аlgorithm (алгоритм цифровой подписи Эль-Гамаля). Идея ЕGSА основана на том, что для обоснования практической невозможности фальсификации цифровой подписи может быть использована более сложная вычислительная задача, чем разложение на множители большого целого числа, - задача дискретного логарифмирования. Кроме того, Эль-Гамалю удалось избежать явной слабости алгоритма цифровой подписи RSА, связанной с возможностью подделки цифровой подписи под некоторыми сообщениями без определения секретного ключа.
Рассмотрим подробнее алгоритм цифровой подписи Эль-Гамаля. Для того чтобы генерировать пару ключей (открытый ключ - секретный ключ), сначала выбирают некоторое большое простое целое число Р и большое целое число G, причем G < Р. Отправитель и получатель подписанного документа используют при вычислениях одинаковые большие целые числа Р (~10308 или ~21024) и G (~10154 или ~2512), которые не являются секретными.
Отправитель выбирает случайное целое число X, 1 < Х ≤ (Р-1), и вычисляет
Y =GX mod Р.
Число Y является открытым ключом, используемым для проверки подписи отправителя. Число Y открыто передается всем потенциальным получателям документов.
Число Х является секретным ключом отправителя для подписания документов и должно храниться в секрете. Для того чтобы подписать сообщение М, сначала отправитель хэширует его с помощью хэш-функции h() в целое число m:
m = h(М), 1<m<(Р-1),
и генерирует случайное целое число К, 1 < К < (Р -1), такое, что К и (Р-1) являются взаимно простыми. Затем отправитель вычисляет целое число а:
а = GK mod Р
и, применяя расширенный алгоритм Евклида, вычисляет с помощью секретного ключа Х целое число b из уравнения
m = Х * а + К * b (mod (Р-1)).
Пара чисел (а,b) образует цифровую подпись S:
S = (а, b),
проставляемую под документом М.
Тройка чисел (М, а, b) передается получателю, в то время как пара чисел (Х, К) держится в секрете. После приема подписанного сообщения (М, а, b) получатель должен проверить, соответствует ли подпись
S = (а, b)
сообщению М. Для этого получатель сначала вычисляет по принятому сообщению М число
m = h(М),
т.е. хэширует принятое сообщение М.
Затем получатель вычисляет значение
А = Ya ab (mod Р)
и признает сообщение М подлинным, если, и только если
А = Gm (mod Р).
Иначе говоря, получатель проверяет справедливость соотношения
Ya ab (mod Р) = Gm (mod Р).
Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S= (а, b) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправителем сообщения М был обладатель именно данного секретного ключа X, не раскрывая при этом сам ключ, и что отправитель подписал именно этот конкретный документ М.
Следует отметить, что выполнение каждой подписи по методу Эль-Гамаля требует нового значения К, причем это значение должно выбираться случайным образом. Если нарушитель раскроет когда-либо значение К, повторно используемое отправителем, то он сможет раскрыть секретный ключ Х отправителя.
Выберем: числа Р=11, G=2 и секретный ключ Х = 8. Вычисляем значение открытого ключа:
Y = GX mod Р = Y = 28 mod 11=3.
Предположим, что исходное сообщение М характеризуется хэш-значением m = 5.
Для того чтобы вычислить цифровую подпись для сообщения М, имеющего хэш-значение m = 5, сначала выберем случайное целое число К = 9. Убедимся, что числа К и (Р -1) являются взаимно простыми. Действительно, НОД (9,10)=1. Далее вычисляем элементы а и b подписи:
а = GK mod Р = 29 mod 11 = 6,
элемент b определяем, используя расширенный алгоритм Евклида:
m = Х * а + К * b (mod (Р-1)).
При m = 5, а = 6, Х = 8, К = 9, Р = 11 получаем
5 = (6* 8+9* b)(mod 10)
или
9* b= -43(mod 10).
Решение: b = 3. Цифровая подпись представляет собой пару: а = 6, b = 3. Далее отправитель передает подписанное сообщение. Приняв подписанное сообщение и открытый ключ Y = 3, получатель вычисляет хэш-значение для сообщения М :
m = 5,
а затем вычисляет два числа:
1) Yaab (mod Р) = 36 * 63 (mod 11) =10 (mod 11);
2) Gm (mod Р) = 25 (mod 11) =10 (mod 11).
Так как эти два целых числа равны, принятое получателем сообщение признается подлинным.
Следует отметить, что схема Эль-Гамаля является характерным примером подхода, который допускает пересылку сообщения М в открытой форме вместе с присоединенным аутентификатором (а, b). В таких случаях процедура установления подлинности принятого сообщения состоит в проверке соответствия аутентификатора сообщению.
Схема цифровой подписи Эль-Гамаля имеет ряд преимуществ по сравнению со схемой цифровой подписи RSА:
При заданном уровне стойкости алгоритма цифровой подписи целые числа, участвующие в вычислениях, имеют запись на 25% короче, что уменьшает сложность вычислений почти в два раза и позволяет заметно сократить объем используемой памяти.
При выборе модуля Р достаточно проверить, что это число является простым и что у числа (Р-1) имеется большой простой множитель (т.е. всего два достаточно просто проверяемых условия).
Процедура формирования подписи по схеме Эль-Гамаля не позволяет вычислять цифровые подписи под новыми сообщениями без знания секретного ключа (как в RSА).
Однако алгоритм цифровой подписи Эль-Гамаля имеет и некоторые недостатки по сравнению со схемой подписи RSА. В частности, длина цифровой подписи получается в 1,5 раза больше, что, в свою очередь, увеличивает время ее вычисления.
Алгоритм цифровой подписи DSА (Digital Signature Algorithm) предложен в 1991г. в НИСТ США для использования в стандарте цифровой подписи DSS (Digital Signature Standard). Алгоритм DSА является развитием алгоритмов цифровой подписи Эль-Гамаля и К.Шнорра.
Отправитель и получатель электронного документа используют при вычислении большие целые числа: G и Р - простые числа, L бит каждое (512 ≤ L ≤ 1024); q - простое число длиной 160 бит (делитель числа (Р-1)). Числа G, Р, q являются открытыми и могут быть общими для всех пользователей сети.
Отправитель выбирает случайное целое число X, 1 < Х < q. Число Х является секретным ключом отправителя для формирования электронной цифровой подписи.
Затем отправитель вычисляет значение
У = Gmod Р.
Число У является открытым ключом для проверки подписи отправителя. Число Y передается всем получателям документов.
Этот алгоритм также предусматривает использование односторонней функции хэширования h(). В стандарте DSS определен алгоритм безопасного хэширования SНА (Secure Hash Algorithm).
Для того чтобы подписать документ М, отправитель хэширует его в целое хэш-значение m:
m = h(М), 1<m<q,
затем генерирует случайное целое число К, 1< К< q, и вычисляет число r
r = (GK mod Р) mod q.
Затем отправитель вычисляет с помощью секретного ключа Х целое число s:
s = ((m + r * X)/K) mod q.
Пара чисел r и s образует цифровую подпись
S = (r,s)
под документом М.
Таким образом, подписанное сообщение представляет собой тройку чисел [М, r, s]. Получатель подписанного сообщения [М, r, s] проверяет выполнение условий
0 < r < q, 0 < s < q
и отвергает подпись, если хотя бы одно из этих условий не выполнено. Затем получатель вычисляет значение
w =(1/s) mod q,
хэш-значение
m = h(М)
и числа
u1 = (m * w) mod q,
u2 = (r * w) mod q.
Далее получатель с помощью открытого ключа У вычисляет значение
v = ((Gu1 * Yu2) mod Р) mod q
и проверяет выполнение условия
v = r
Если условие v = r выполняется, тогда подпись
S = (r,s)
под документом М признается получателем подлинной. Можно строго математически доказать, что последнее равенство будет выполняться тогда, и только тогда, когда подпись S = (r,s) под документом М получена с помощью именно того секретного ключа X, из которого был получен открытый ключ Y. Таким образом, можно надежно удостовериться, что отправитель сообщения владеет именно данным секретным ключом Х (не раскрывая при этом значения ключа X) и что отправитель подписал именно данный документ М.
По сравнению с алгоритмом цифровой подписи Эль-Гамаля алгоритм DSА имеет следующие основные преимущества:
1. При любом допустимом уровне стойкости, т.е. при любой паре чисел G и Р (от 512 до 1024 бит), числа q, X, r, s имеют длину по 160 бит, сокращая длину подписи до 320 бит.
2. Большинство операций с числами К, r, s, Х при вычислении подписи производится по модулю числа q длиной 160 бит, что сокращает время вычисления подписи.
3. При проверке подписи большинство операций с числами u1, u2, v, w также производится по модулю числа q длиной 160 бит, что сокращает объем памяти и время вычисления.
Недостатком алгоритма DSА является то, что при подписании и при проверке подписи приходится выполнять сложные операции деления по модулю q:
s = ((m + rX)/K) (mod q), w = (1/s) (mod q),
что не позволяет получать максимальное быстродействие.
Следует отметить, что реальное исполнение алгоритма DSА может быть ускорено с помощью выполнения предварительных вычислений. Заметим, что значение r не зависит от сообщения М и его хэш-значения m. Можно заранее создать строку случайных значений К и затем для каждого из этих значений вычислить значения r. Можно также заранее вычислить обратные значения К-1 для каждого из значений К. Затем, при поступлении сообщения М, можно вычислить значение s для данных значений r и К-1. Эти предварительные вычисления значительно ускоряют работу алгоритма DSА.
