Атаки на криптосистемы, основанные на сложности задачи дискретного логарифмирования

Очевидное направление криптоанализа систем шифрования и цифровой подписи, основанных на сложности решения задачи дискретного логарифмирования – разработка переспективных методов дискретного логарифмирования.

Наиболее известные методы дискретного логарифмирования:

1. Алгоритм согласования.

2. Алгоритм Полига-Хеллмана.

3. δ-метод Полларда для дискретного логарифмирования.

4. Дискретное логарифмирование в простых полях (алгоритмы Адлемана, COS.)

5. Дискретное логарифмирование в полях Галуа (алгоритмы index-calculus, Эль-Гамаля, Копперсмита).

6. Алгоритмы решета числового поля для дискретного логарифмирования.

Рекорды дискретного логарифмирования: логарифмирование по простому модулю (алгоритм COS с гауссовыми целыми). Сложность 60 MIPS-лет для нахождения соотношений и около трех недель – решение системы линейных уравнений.