RSA-155

RSA-155 — это 155-значное (512-битное) число, являвшееся модулем RSA-ключа, факторизация которого была успешно выполнена в августе 1999 года международной группой исследователей. Это событие стало важной вехой в истории криптоанализа, продемонстрировав уязвимость ключей длиной 512 бит для атак с использованием распределённых вычислений и совершенных алгоритмов.

История

Предпосылки

В середине 1990-х годов алгоритм RSA, основанный на сложности факторизации больших составных чисел, оставался стандартом де-факто для асимметричного шифрования. Ключи длиной 512 бит (155 десятичных цифр) считались достаточно безопасными для коммерческого использования, но их криптостойкость не была подтверждена практическими атаками. Для стимулирования исследований в области факторизации компания RSA Laboratories (организация, разработавшая алгоритм) в 1991 году запустила проект «RSA Factoring Challenge» — серию чисел различной длины, факторизация которых вознаграждалась призами.

Хронология взлома

Число RSA-155 было опубликовано в рамках вызова как одно из промежуточных. В 1999 году группа учёных под руководством Германа те Риле (CWI, Нидерланды) и Арджен Ленстры (Bell Labs, США) объявила о завершении факторизации. Работа велась с использованием метода решета числового поля (NFS) — на тот момент самого эффективного алгоритма для факторизации чисел общего вида. Процесс занял около 7 месяцев и включал три этапа:

1. Сбор отношений (sieving) — распределённый поиск гладких чисел, занявший 3,7 месяца на 300 компьютерах.
2. Линейная алгебра — решение разреженной системы линейных уравнений, потребовавшее 224 часа на суперкомпьютере Cray C916.
3. Извлечение корней — финальный этап, занявший менее 2 часов.

Результат был объявлен 22 августа 1999 года. За факторизацию RSA-155 участники получили приз в размере 10 000 долларов США от RSA Laboratories.

Значение

Успешная факторизация RSA-155 показала, что 512-битные ключи могут быть взломаны с использованием общедоступных вычислительных ресурсов. Это привело к пересмотру рекомендаций по длине ключей: Национальный институт стандартов и технологий США (NIST) и другие организации повысили минимальную рекомендуемую длину до 1024 бит, а позже — до 2048 бит. RSA-155 также стал последним числом из вызова RSA Laboratories, факторизованным до 2000 года; последующие числа (RSA-160, RSA-200) требовали ещё больших усилий.

Метод факторизации

Решето числового поля (NFS)

Для факторизации RSA-155 применялся вариант общего решета числового поля (GNFS) — алгоритм, разработанный в 1990-х годах. Его сложность для числа n оценивается как: \[ O\left(\exp\left(\left(\sqrt[3]{\frac{64}{9}} + o(1)\right) \cdot (\log n)^{1/3} \cdot (\log \log n)^{2/3}\right)\right) \] Для 512-битного числа это составляло около 10^19 операций, что было на грани возможностей тогдашних вычислительных систем.

Распределённые вычисления

Ключевым фактором успеха стало использование сети из 300 компьютеров, объединённых через Интернет. Этап сбора отношений (sieving) выполнялся на машинах в Нидерландах, США, Германии, Франции и других странах. Каждый компьютер обрабатывал свой диапазон чисел, а результаты затем агрегировались в единую базу данных. Такой подход позволил сократить время с нескольких лет до нескольких месяцев.

Результаты

Факторы числа

RSA-155 — это произведение двух простых чисел, которые были найдены в ходе факторизации:

• p = 102639592829741105772054196573991675900716567808038066803341933521790711307779
• q = 106603488380168454820927220360012878679207958575989291522270608237193062808643

Произведение этих чисел даёт исходный модуль RSA-155.

Влияние на криптографию

Факторизация RSA-155 продемонстрировала, что 512-битные ключи не обеспечивают долгосрочной безопасности. В течение нескольких лет после этого события:

• Крупные компании (например, Netscape, Microsoft) перешли на ключи длиной 1024 бита.
• Стандарты шифрования (SSL/TLS) начали требовать минимальную длину ключа 1024 бита.
• Исследователи сосредоточились на разработке методов факторизации для чисел длиной 1024 бита, хотя к 2024 году такие числа ещё не были факторизованы.

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

Сложность масштабирования

Хотя RSA-155 был успешно факторизован, метод NFS требует экспоненциального роста вычислительных ресурсов при увеличении длины ключа. Для 1024-битного числа сложность возрастает примерно в 10^6 раз по сравнению с 512-битным, что делает его факторизацию практически невозможной при текущем уровне технологий. Однако с развитием квантовых компьютеров алгоритм Шора может сделать RSA уязвимым для ключей любой длины.

Практическая значимость

К 2024 году 512-битные ключи уже не используются в современных системах безопасности, но факторизация RSA-155 остаётся важным историческим примером, демонстрирующим пределы классической криптографии. Она также стимулировала развитие распределённых вычислений и алгоритмов факторизации, которые находят применение в других областях (например, в теории чисел).

Примечания

• Число RSA-155 было выбрано не случайно: его длина (155 десятичных цифр) соответствует 512 битам, что было стандартной длиной ключа в коммерческих системах середины 1990-х годов.
• Факторизация была выполнена на оборудовании, которое по современным меркам является устаревшим (процессоры Pentium II, суперкомпьютер Cray C916). Современные графические процессоры (GPU) и облачные вычисления могли бы сократить время до нескольких дней.

Источники

• RSA Laboratories. «RSA Factoring Challenge». 1991.
• A. K. Lenstra, H. W. Lenstra, M. S. Manasse, J. M. Pollard. «The Number Field Sieve». 1993.
• H. J. J. te Riele, A. K. Lenstra, et al. «Factorization of a 512-bit RSA Key». 1999.
• NIST Special Publication 800-57. «Recommendation for Key Management». 2003.