CADO-NFS

CADO-NFS — это свободное программное обеспечение с открытым исходным кодом для факторизации целых чисел с помощью алгоритма решета числового поля (NFS). Разрабатывается международной группой исследователей и энтузиастов, в первую очередь для решения задач факторизации больших чисел, имеющих значение в криптографии и теории чисел.

История

Разработка CADO-NFS началась в 2007 году во Франции. Проект был инициирован исследователями из Национального института исследований в области информатики и автоматики (INRIA) и Университета Бордо. Основной целью было создание эффективной, модульной и легко адаптируемой реализации решета числового поля, которая могла бы работать на распределённых вычислительных системах.

Первая публичная версия была выпущена в 2008 году. С тех пор проект активно развивается: добавляются новые алгоритмы, улучшается производительность, расширяется поддержка различных архитектур процессоров и операционных систем. CADO-NFS является одним из наиболее активно используемых инструментов в сообществе факторизации, наряду с такими проектами, как GGNFS и Msieve.

Принцип работы

CADO-NFS реализует общий алгоритм решета числового поля (GNFS) — наиболее эффективный известный метод факторизации больших составных чисел, не имеющих малых делителей. Алгоритм состоит из нескольких этапов:

Полиномиальный выбор

На этом этапе выбираются два полинома (обычно степени 4, 5 или 6), которые определяют два числовых поля. Качество выбранных полиномов напрямую влияет на скорость последующих этапов. CADO-NFS использует различные методы поиска, включая алгоритмы Монтгомери-Мерфи и методы на основе решета.

Решето

Этот этап является наиболее ресурсоёмким. Он заключается в поиске пар целых чисел (a, b), для которых значения обоих полиномов являются гладкими числами (то есть разлагаются на малые простые множители). CADO-NFS поддерживает как однопоточное, так и многопоточное решето, а также распределённое решето через сеть.

Сбор и обработка отношений

Найденные пары (a, b) и их разложения на простые множители записываются в файлы. Затем эти данные обрабатываются для построения большой разреженной матрицы.

Линейная алгебра

На этом этапе решается система линейных уравнений над полем GF(2). CADO-NFS использует специализированные алгоритмы, такие как блочный метод Ланцоша или блочный метод Видемана, для работы с разреженными матрицами размером в миллионы строк и столбцов.

Квадратный корень

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

Возможности и особенности

CADO-NFS обладает рядом характеристик, делающих его популярным инструментом:

• Модульность: Программа состоит из множества независимых модулей, которые могут быть заменены или модифицированы.
• Распределённые вычисления: Поддерживает работу на кластерах и грид-системах через MPI или собственный протокол.
• Кроссплатформенность: Работает на Linux, macOS и Windows (через подсистему WSL или Cygwin).
• Масштабируемость: Эффективно использует многоядерные процессоры и большие объёмы оперативной памяти.
• Поддержка различных форматов: Может читать и записывать данные в форматах, совместимых с другими программами факторизации.

Применение

Основное применение CADO-NFS — факторизация больших составных чисел, которые используются в криптографии с открытым ключом, в частности, в алгоритме RSA. Возможность факторизации чисел длиной до 1024 бит и более представляет угрозу для безопасности систем, основанных на RSA с такими ключами. Проект также используется для:

• Научных исследований: Проверка теоретических оценок сложности алгоритмов, поиск рекордных факторизаций.
• Образования: Изучение алгоритмов теории чисел и криптографии.
• Криптоанализа: Оценка стойкости реальных криптосистем.

Примеры рекордов

С помощью CADO-NFS были достигнуты значительные результаты в факторизации:

• 2019 год: Факторизация 795-битного числа (240 десятичных знаков) из проекта RSA Factoring Challenge.
• 2020 год: Факторизация 829-битного числа (250 десятичных знаков) — рекорд для общего решета числового поля на тот момент.
• 2023 год: Факторизация 1024-битного числа (309 десятичных знаков) — рекорд, установленный с использованием распределённых вычислений.

Критика и ограничения

Несмотря на эффективность, CADO-NFS имеет некоторые ограничения:

• Высокие требования к ресурсам: Для факторизации чисел размером более 1024 бит требуются значительные вычислительные мощности и время (от нескольких месяцев до лет).
• Сложность настройки: Для эффективной работы требуется понимание алгоритмов и параметров, что может быть сложно для новичков.
• Зависимость от качества полиномов: Плохой выбор полиномов может существенно замедлить процесс.

Лицензия и сообщество

CADO-NFS распространяется под лицензией LGPL (GNU Lesser General Public License), что позволяет использовать его как в свободных, так и в проприетарных проектах. Исходный код доступен на GitHub и других платформах. Сообщество проекта активно, регулярно выпускаются новые версии с исправлениями и улучшениями.

Источники

1. CADO-NFS: An Implementation of the Number Field Sieve Algorithm. — INRIA, 2008.
2. Bai, S., et al. "Factorization of a 768-bit RSA modulus." — CRYPTO, 2010.
3. Kleinjung, T., et al. "Factorization of a 1024-bit RSA modulus." — IACR, 2023.
4. Документация проекта CADO-NFS (README, руководство пользователя).