Современная криптография - Венбо Мао
ISBN 5-8459-0847-7
Скачать (прямая ссылка):
1. и *— m'm_1(modp— 1).
2. s' <— su(modp — 1).
364
Часть III. Основные методы криптографии
Алгоритм 10.3. Схема цифровой подписи Эль-Гамаля Генерация ключа
Процедура генерации ключа такая же, как и в криптосистеме Эль-Гамаля (раз-d дел 8.12).
(* Следовательно, параметрами открытого ключа Алисы является тройка (д, у,р)й где р — большое простое число, д Е F* — случайный мультипликативный образуй ющий элемент, уа = yXA(modp)7XA — секретное целое число, удовлетворяющее условию ха < Р — 1> а закрытым ключом является число ха- *) Генерация подписи
Для цифровой подписи сообщения т G F^- Алиса генерирует случайное числЛ ? ? иЩ>-\ (т-е- Ч- < V ~ 1 и gC{i(^,p — 1) = 1) и формирует пару (г, s), где
(* Число ?~ можно найти с помощью расширенного алгоритма Евклида (алго! ритм 4.2). *)
Верификация подписи
Допустим, Боб должен удостовериться, что параметры открытого ключа (д, ул^Рщ действительно принадлежит Алисе. Боб применяет к паре (m, (г, s)) следующую] процедуру верификации.
Verify(s,iM,p)(m' (г>s)) = Тте' если г < Р и УаТ8 = ffm(modp).
(* Примечание', сообщение т должно быть распознаваемым (см. разЧ дел 10.4.7.2). *)_
3. Вычисляется значение г', удовлетворяющее условию r'=ru(modp— 1) и г'= = r(modp). Это можно сделать с помощью китайской теоремы об остаткам (алгоритм 6.1).
Затем можно выполнить следующие рутинные преобразования.
Эта атака невозможна, если г < р, поскольку в этом случае значение г', вычисляемое на третьем шаге применения китайской теоремы об остатках, по величине сравнимо с числом р(р — 1).
Предостережение 2
Второе предостережение также было сформулировано Блайхенбахером [41], Алиса должна выбрать случайный элемент д из группы F*. Если этот параметр
г «- д (modp), s <— ?~1(т — х
(т — XAr){raodp — 1).
(10.4.21
уТАГ^ = у^ = (уАгТ^9'
= gm'(modp).
Глава 10. Методы защиты целостности данных
365
выбран не Алисой (это возможно, когда системные пользователи обладают одними и теми же открытыми параметрами д и р), то необходимо проверить, насколько случайным является параметр д (например, он может быть результатом применения псевдослучайной функции).
Допустим, что открытые параметры д и р выбраны Злоумышленником. Параметр р можно установить с помощью стандартного способа, описанного в разделе 8.4.1: пусть р — 1 = bq, где q — достаточно большое простое число, но число b может быть гладким (т.е. число b имеет только малые простые множители, и вычисление дискретного логарифма в группе порядка b не представляет труда).
Злоумышленник генерирует параметр д следующим образом
д = (3\modp),
где /3 = cqnc<b.
Как известно, вычисление дискретного логарифма открытого ключа у а — трудноразрешимая задача. Однако вычисление дискретного логарифма величины учА по основанию дч не создает никаких сложностей. Дискретный логарифм равен z = x^(mod b), т.е. выполняется следующее сравнение.
yA = (g")z(modp).
Вычислив значение z, Злоумышленник может подделать подпись Алисы с помощью следующих операций.
т <- /3 = cq,
s <— t(m — cqz)(modp — 1). Затем выполняются рутинные преобразования.
yATS = у0* (tff™** = g^gm-СЧг = g-(modp)
Следовательно, пара (r,s) действительно является корректной подписью сообщения т, созданного без помощи закрытого ключа ха (но с помощью числа жл(пкх1Ь)).
Заметим, что в этой процедуре фальсификации цифровой подписи число q является делителем числа г. Следовательно, атаку Блайхенбахера можно предотвратить, если во время верификации Боб проверяет условие q\r (предполагается, что в процессе выбора параметра р число q является открытым). В разделе 16.3.2.1 будет показано, что условие q\r является необходимым для доказательства формальной стойкости схемы цифровой подписи Эль-Гамаля к фальсификации.
366
Часть III. Основные методы криптографии
Предостережение 3
Третье предупреждение касается эфемерного ключа ?. Генерация цифровой подписи Эль-Гамаля представляет собой рандомизированный алгоритм, посколь-1 ку эфемерный ключ ? является случайным.
Алиса никогда не должна применять эфемерный ключ для подписи других сообщений. Если эфемерный ключ ? используется повторно для подписи двух сообщений mi и тч, удовлетворяющих условию mi ф m2(modp — 1), то И31 второго уравнения системы (10.4.2) следует, что
?{s\ — s2) = т,\ — (modp — 1)-
Поскольку число ?-1(modp— 1) существует, из неравенства т\ ф m2(modp— 1)1 следует, что
Г1 ее (Sl - s2)/(mi - m2)(modp - 1), (10.4.3)'
т.е. число ?~1 раскрыто. В свою очередь, закрытый ключ Алисы ха можно вы-| числить из второго уравнения системы (10.4.2) по формуле
ха = (mi — &si)/r(modp — 1). (10.4.4)
Заметим также, что эфемерный ключ должен извлекаться из пространства Z*_J с помощью простого случайного выбора. Особую осторожность следует прояв-1 лять, когда подпись генерируется небольшими вычислительными устройствами^ I например, кредитной карточкой с микропроцессором или портативным компьютером: необходимо убедиться, что эти приборы снабжены хорошими датчиками! случайных чисел.
Поскольку эфемерный ключ ? используется лишь один раз и генерируется с помощью датчика равномерно распределенных случайных чисел, из втором уравнения системы (10.4.2) следует, что для шифрования закрытого ключа хал по существу, используется одноразовый шифр. Таким образом, эти два ключ^( защищают друг друга в теоретико-информационном смысле.
