Очевидное направление криптоанализа систем шифрования и цифровой подписи, основанных на сложности решения задачи факторизации – разработка переспективных методов факторизации целых чисел.
Наиболее известные методы факторизации целых чисел.
Методы факторизации с экспоненциальной сложностью:
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 ненулевыми элементами.