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

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

Наиболее известные методы факторизации целых чисел.

Методы факторизации с экспоненциальной сложностью:

1. Метод пробных делений.

2. Алгоритм Ферма.

3. (p - 1) – метод Полларда.

4. δ-метод Полларда.

5. Метод Шермана-Лемана.

6. Алгоритм Ленстры.

7. Алгоритм Полларда-Штрассена.

8. (p + 1) – метод Уильямса.

9. Метод Шэнкса.

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

1. Метод Диксона.

2. Алгоритм Бриллхарта-Моррисона.

3. Метод квадратичного решета QS (quadratic sieve) предложен К. Померансом в 1981 году эффективен для чисел n < 10110.

4. Методы Шнорра-Ленстры и Ленстры-Померанса (активно на практике не использовались).

5. Обобщенный метод решета числового поля GNFS (General number field sieve) на сегодняшний день лучший по показателям из официально опубликованных методов факторизации предложен в 1990 году.

6. Алгоритм Ленстры для факторизации с помощью эллиптических кривых (аналогичен (p - 1) – методу Полларда, но применяются вычисления в группе точек эллиптической кривой).

Таблица 14. Рекорды факторизации на примере системы RSA

Число Дата Сложность, MIPS-лет Алгоритм
RSA-100 Апрель 1991 QS
RSA-110 Апрель 1992 QS
RSA-120 Июнь QS
RSA-129 Апрель 1994 QS

Окончание табл. 14

RSA-130 Апрель 1996 GNFS
RSA-140 Февраль 1999 GNFS
RSA-155 Август 1999 GNFS

Последнее достижение – факторизация числа RSA-155, потребовавшая:

- использования 160 рабочих станций SGI и Sun (175-400 МГц);

- 8 процессоров SGI Origin 2000 (250 МГц);

- 120 персональных компьютеров Pentium II (300-450 МГц);

- 4 кластеров Digital\Compaq (500 МГц);

- 9 недель для настройки параметров GNFS;

- 5.2 месяца для сбора вспомогательных пар чисел;

- 3.2 Гб оперативной памяти, 224 часа вычислений на Cray C916 для обработки матрицы размером 6699191×6711336 c 417132631 ненулевыми элементами.