23. Дискретне логарифмування.

Стойкость широко распространенных в настоящее время схем ЭЦП (электронная цифровая подпись) основана на сложности решения частной задачи дискретного логарифмирования в простом поле GF(p). Задача эта формулируется следующим образом:

·  заданы простые числа p, q и натуральное число g < p порядка q, то есть

g^q º 1 (mod p);

· зная значение y = g^x (mod p), необходимо найти xÎ Z.

 

В настоящее время наиболее быстрым алгоритмом решения общей задачи дискретного логарифмирования (при произвольном выборе g) является алгоритм обобщенного решета числового поля, вычислительная сложность которого оценивается как

O(exp((c+O(1))(ln (p))^1/3(ln (ln (p)))^2/3

операций в поле GF(p), где c » (64/9)^1/3.

 

Методами решения частной задачи дискретного логарифмирования являются также r-метод и l-метод Полларда и некоторые близкие методы, требующие для ее решения выполнения порядка

Ö pq/4 операций умножения в поле GF(p). (1.2)

«При 1024-битовом p и 256-битовом q мы получаем приблизительно 1.3E+26 для метода решета числового поля и 3.0E+38 для r- и l-методов Полларда».

Национальные стандарты Digital Signature Standard (принят NIST в 1991 г. с последующими изменениями в 1993, 1996 г.), российский стандарт цифровой подписи ГОСТ Р 34.10-94 реализовывают ЭЦП в простом поле.

Прогресс в области решения задачи дискретного логарифмирования привел к тому, что стала возможна реальная компрометация схем ЭЦП, основанных на сложности вычислений в мультипликативной группе поля, со стороны нарушителя, обладающего довольно невысокими вычислительными и финансовыми ресурсами. Поэтому на рубеже XX и XXI века во многих странах мира стали использоваться схемы формирования ЭЦП, основанные на сложности решения задачи дискретного логарифмирования в группе точек эллиптической кривой. Эта задача формулируется следующим образом:

·        задана эллиптическая кривая E над полем GF(p), где p - простое число;

·        выбрана точка G, имеющая простой порядок q в группе точек кривой E;

·        зная точку kG необходимо восстановить натуральное число k.

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

В настоящее время наиболее быстрыми алгоритмами решения задачи дискретного логарифмирования в группе точек эллиптической кривой при правильном выборе параметров считаются r-метод и l-метод Полларда и близкие им методы. Их сложность оценивается формулой (1.2) и, таким образом, числом порядка 10³⁸ операций сложения точек кривой.

24. Метод Ель-Гамаля.

Алгоритм Эль-Гамаля может использоваться для формирования электронной подписи или для шифрования данных. Он базируется на трудности вычисления дискретного логарифма. Для генерации пары ключей сначала берется простое число p и два случайных числа g и x, каждое из которых меньше p. Затем вычисляется:

y = g^x mod p

Общедоступными ключами являются y, g и p, а секретным ключом является х. Для подписи сообщения M выбирается случайное число k, которое является простым по отношению к p-1. После этого вычисляется a = g^k mod p. Далее из уравнения M = (xa + kb) mod (p-1) находим b. Электронной подписью для сообщения M будет служить пара a и b. Случайное число k следует хранить в секрете. Для верификации подписи необходимо проверить равенство:

y^aa^b mod p = g^M mod p.

Пара a и b представляют собой зашифрованный текст. Следует заметить, что зашифрованный текст имеет размер в два раза больше исходного. Для дешифрования производится вычисление:

M = b/a^x mod p