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

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

Одним из примеров использования сложности задачи дискретного логарифмирования в криптографии является т.н. схема Эль-Гамаля, которую можно использовать как для цифровой подписи, так и для шифрования [43].

9.3.1. Криптосистема Эль-Гамаля

Криптосистема Эль-Гамаля является асимметричной. Для построения пары

ключей выбирается большое простое число p	и два псевдослучайных числа,
меньших p −1.
Одно из них, g , должно быть элементом большого порядка по модулю				p ,
скажем, первообразным корнем. Второе число,		x , выбирается	в качестве
секретного ключа. Полагается, что сообщения – вычеты по модулю			p .
Открытым ключом является тройка чисел p, g, y = g x (p).
Заметим, что дискретное возведение	в	степень ведет	себя	как

односторонняя функция, но не как односторонняя функция с лазейкой.

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

Для зашифрования сообщения m выбирается псевдослучайное число k

(рандомизатор, разовый ключ) с условием НОД(k, p −1)=1. Рандомизаторы не должны повторяться и должны содержаться в секрете.

Затем вычисляются	числа a = gk (p) - лазейка и	b = yk m(p)	-
шифртекст. Криптограммой является пара блоков данных a,b .
Для расшифрования	достаточно получить сомножитель	yk , что можно

сделать с помощью секретного ключа, вычислив значение ax = gkx (p).

Действительно, yk = g xk (p), поэтому m = a−xb(p).

122 Глава 9. КРИПТОСИСТЕМА RSA, ПРОТОКОЛ ДИФФИ-ХЭЛЛМАНА И ЦИФРОВАЯ ПОДПИСЬ ЭЛЬ-ГАМАЛЯ

9.3.2. Механизм цифровой подписи Эль-Гамаля

Цифровая подпись Эль-Гамаля состоит из пары блоков r, s .

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

Лицо, подписывающее документ, должно для каждого подписываемого сообщения m выбрать рандомизатор k и вычислить «предподпись»

r = gk (p).

Затем необходимо использовать секретный ключ как один из коэффициентов сравнения, из которого определяется блок подписи s .

Сравнение имеет вид h = h(m)= xr + ks mod(p −1). Здесь модулем сравнения выбрано число p −1, поскольку обе части сравнения в проверочном соотношении будут участвовать в показателях.

Заметим, что число r может равняться		p −1, поскольку оно определяется
из сравнения по модулю p .
Подпись r, s считается действительной, если gh = g xr+ks (p).
Поскольку y = g x (p)	и r = gk (p), то окончательный вид проверочного
соотношения следующий:	gh = yr rs (p).	Таким образом, для проверки

подписи достаточно знания открытого ключа.

Очевидно, необходимость выбора рандомизатора требует применения криптографически стойких датчиков (генераторов) псевдослучайных чисел.

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

Выходные последовательности таких генераторов являются непредсказуемыми. Кроме того, структура выходной последовательности не позволяет определить начальное состояние и, возможно, другие параметры соответствующего датчика.

Определение и свойства криптографически стойкого псевдослучайного генератора можно найти в [2].

В Государственном Стандарте Украины ДСТУ 4145-2002 [19] для построения рандомизаторов цифровой подписи применяется датчик псевдослучайных чисел, схема которого использует криптоалгоритм ГОСТ

28147-89.

9.3.3. Ослабление подписи Эль-Гамаля вследствие некорректной реализации схемы

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

рекомендаций стандартов может привести к ослаблению подписи.
Приведем	примеры.		Пусть	k известно,	тогда	из	соотношения
h = xr + ks mod(p −1)		находим секретный ключ			x и можем подписывать
сообщения вместо владельца подписи.
Далее. При повторении рандомизатора получим систему сравнений
относительно	x	и	k	вида	h1 = xr1 + ks1 mod(p −1),
h2 = xr2 + ks2 mod(p −1),			что	позволяет определить		ключ	даже при

переменной хэш-функции.

Третий пример – несоблюдение ограничения на размер параметра: r < p .

Допустим, что проверяющая сторона не учитывает возможность возникновения ситуации, когда r > p .

124 Глава 9. КРИПТОСИСТЕМА RSA, ПРОТОКОЛ ДИФФИ-ХЭЛЛМАНА И ЦИФРОВАЯ ПОДПИСЬ ЭЛЬ-ГАМАЛЯ

Наблюдая за сетью связи, можно получить подписанное сообщение m и выделить блоки некоторой истинной подписи r, s , связанные со значением хэш-кода h = h(m).

Пусть необходимо подделать подпись для сообщения m1 с хэш-кодом. h1 = h(m1 ). Предположим, хэш-коды двух рассматриваемых сообщений отличаются некоторым множителем u , который можно найти из сравнения h1 =uh mod(p −1). (Если это сравнение не имеет решения, то перехватим в сети следующее подписанное сообщение и т.д.)

Для истинной подписи выполняется проверочное соотношение

gh = yr rs (p). Попытаемся подобрать такую подпись r ,s , чтобы аналогичное
1	1
соотношение выполнялось для r1,s1 , h1 .
Рассмотрим gh1 = guh =[yr rs ]u (p), т.е. gh1 = yru r su (p).
Очевидно, можно принять s1 = su mod(p −1).	Однако, если принять

r1 = ru mod(p −1), то проверочное соотношение выполняться не будет, так как r1 должно участвовать в основании и показателе степени одновременно, что не имеет места. Оказывается, выход из положения существует, если допускается возможность значений r1 > p .

Действительно, r1 в показателе и основании степени приводятся по различным модулям, т.е. должны одновременно выполняться сравнения

r1 = ru mod(p −1) и r1 = r mod(p).

Модули сравнений взаимно просты, следовательно, по китайской теореме об остатках, существует решение r1 = r mod(p(p −1)), однако r1 > p .