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

Таким образом, для r1,s1 проверочное соотношение выполняется, т.е.

подпись может быть подделана, если не контролируются ограничения на длины параметров.

9.3.4. Варианты цифровой подписи типа Эль-Гамаля

Построение различных вариантов подписей типа Эль-Гамаля можно осуществить, исходя из сравнения вида Ak + Bx +C = 0 mod q ,

связывающего секретный ключ x и рандомизатор k с блоками цифровой

подписи r, s . Здесь A, B,C ≠ 0(q), где	q = p −1 (для краткости
обозначений).
Из Ak + Bx + C = 0 mod q следует, что A = −k−1Bx − k−1C modq .
С очевидными переобозначениями, можно записать: A = bx + c mod q .
Следовательно, g A =[g x ]b gc (mod p), т.е.	через g x и другие параметры

можно проверить некоторое соотношение, не раскрывая значения x .
	В классической подписи Эль-Гамаля для сообщения m, r = gk (p), а блок
s	определяется		из	сравнения	Ak + Bx +C = 0 mod q ,			при
(A, B,C)=(s,r,−h(m)).				Действительно,		в	этом	случае,
s = k−1(h − xr)mod(q), т.е. h = xr + ks mod(p −1).
	Рассмотрим пример на построение цифровой подписи Эль-Гамаля.
	Выберем	p =17 .	Поскольку 3(p−1) 2 = 6561 = −1(p), то g = 3 -
первообразный элемент.
	Примем	x =5.	Тогда	открытый	ключ		y = g x (p)=35 =5(17).
Пустьh(m)=9 .

s = k−1(h − xr)mod(q), где

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

Выберем рандомизатор k = 7 . Вычислим первую часть подписи

r = gk (p)=37 =11(17).

Затем – вторую часть подписи, по формуле

k −1 = 7(16). Получим s =14(16). Подпись равна 11,14 .

Проверка подписи. Вычисляем хэш-код сообщения h =9) и проверяем соотношениеgh = yr rs (p).

Получим: gh =39 =14(17), yr = 511 =11(17),

14 =99(17), то есть в данном случае подпись верна.

h (допустим, что

rs =1114 =9(17),

Глава 10.

АЛГОРИТМ СИЛЬВЕРА-ПОЛЛИГА- ХЭЛЛМАНА

Основное в этой главе…

Алгоритм дискретного логарифмиро-

вания ……………….…………………....130

Логарифмирование в группе единиц кольца вычетов по модулю pr……..134

Фальсификация подписи Эль-Гамаля в специальном случае выбора первообразного элемента и характеристики поля………..…….………………………..137

q = Pα

задачу

y = bx . В этом

128 Глава 10. АЛГОРИТМ СИЛЬВЕРА - ПОЛЛИГА - ХЭЛЛМАНА

Известно, что дискретная экспонента, т.е. функция вида f (x)= axmod p , где p - простое, ведет себя при больших значениях x и ord pa как односторонняя. Соответствующая обратная функция (дискретный логарифм) вычислительно нереализуема.

Аналогичная ситуация может возникнуть и в общем случае коммутативной конечной группы.

Групповая операция в мультипликативной записи называется умножением. Возведение в степень x определяется как произведение элемента b G на себя x раз.

Пусть G конечная коммутативная группа, b G , и

случае x называется дискретным логарифмом элемента y по основанию b.

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

Алгоритм Сильвера-Поллига-Хэллмана позволяет решить дискретного логарифмирования в конечном поле Fq , состоящем из элементов, при условии, что число q −1 - «гладкое», т.е. все простые делители числа q −1 невелики [15,44,45].

Последнее означает, что имеющиеся ресурсы памяти и вычислительной мощности позволяют провести необходимые вычисления в реальное время.

Заметим, что вычисление больших степеней элементов в конечном поле можно выполнить относительно быстро.

10.1. Обозначения и постановка задачи

Обозначим множество ненулевых элементов поля Fq через Fq* .

Задача дискретного логарифмирования, которую мы рассмотрим, формулируется следующим образом.