RSA Factoring Challenge

RSA Factoring Challenge — это серия математических соревнований, организованных компанией RSA Laboratories (подразделение корпорации RSA Security, входящей в состав Dell Technologies), целью которых было стимулирование исследований в области факторизации больших целых чисел. В рамках задачи участникам предлагалось разложить на простые множители (факторизовать) полупростые числа (произведения двух простых чисел) заданной длины, которые использовались в качестве модуля в криптосистеме RSA. За успешное решение присуждались денежные призы.

История

Предпосылки и запуск

Криптосистема RSA, изобретённая в 1977 году Роном Ривестом, Ади Шамиром и Леонардом Адлеманом, основана на практической сложности факторизации больших чисел. В 1991 году, когда вычислительные мощности и алгоритмы факторизации начали активно развиваться, RSA Laboratories опубликовала список из 42 чисел (RSA-100, RSA-110, ..., RSA-500), где число в названии указывало количество десятичных цифр. Первоначально соревнование называлось «The RSA Factoring Challenge» и предлагало призы за факторизацию чисел от 100 до 500 цифр. В 1996 году список был расширен до 54 чисел, а в 2001 году — до 57, с добавлением чисел RSA-576, RSA-640, RSA-704, RSA-768, RSA-896, RSA-1024, RSA-1536 и RSA-2048. Последнее число, RSA-2048, имело 617 десятичных цифр (2048 бит).

Основные этапы

Соревнование проходило в несколько этапов. Первые числа (до 155 цифр) были факторизованы относительно быстро — в течение 1990-х годов. Ключевым прорывом стало использование алгоритма решета числового поля (GNFS), который стал основным методом для факторизации больших чисел. В 1999 году было факторизовано число RSA-155 (512 бит), что продемонстрировало уязвимость 512-битных ключей RSA. В 2009 году группа учёных из нескольких стран (включая EPFL, NTT, Боннский университет и др.) факторизовала RSA-768 (232 десятичные цифры, 768 бит), затратив около двух лет вычислений на сотнях компьютеров. Это стало последним решённым числом в рамках официального соревнования.

Завершение

В 2007 году RSA Laboratories объявила о прекращении соревнования, сославшись на то, что его первоначальная цель — стимулирование исследований — была достигнута. Однако некоторые числа, такие как RSA-896, RSA-1024 и более крупные, остались нерешёнными. В 2013 году RSA Laboratories официально сняла все оставшиеся призы, и соревнование было закрыто. Тем не менее, независимые исследователи продолжают попытки факторизации оставшихся чисел, в том числе с использованием распределённых вычислений (например, проекты Mersenne Forum).

Классификация чисел

Числа в рамках RSA Factoring Challenge классифицировались по длине в битах и десятичных цифрах. Каждое число обозначалось как RSA-<длина в десятичных цифрах> (например, RSA-100 — 100 десятичных цифр, что соответствует примерно 330 битам). Все числа были полупростыми — произведением двух простых чисел примерно одинаковой длины.

Список решённых чисел (выборочно)

Нерешённые числа (на момент закрытия)

• RSA-896 (270 цифр, 896 бит)
• RSA-1024 (309 цифр, 1024 бита)
• RSA-1536 (463 цифры, 1536 бит)
• RSA-2048 (617 цифр, 2048 бит)

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

Алгоритм GNFS

Основным методом, использованным для решения большинства чисел RSA Factoring Challenge, является алгоритм решета числового поля (General Number Field Sieve, GNFS). Он состоит из этапов: выбор полиномов, просеивание, обработка матриц, решение линейной системы и извлечение квадратного корня. Для RSA-768 потребовалось около 2·10^20 операций, что эквивалентно примерно 2000 годам работы одного ядра современного процессора.

Другие методы

• Метод квадратичного решета (QS) — использовался для чисел меньшей длины (до RSA-129).
• Метод эллиптических кривых (ECM) — применялся для поиска малых простых множителей, но не годился для полупростых чисел RSA.
• Квантовые алгоритмы — теоретически алгоритм Шора позволяет факторизовать числа за полиномиальное время, но на практике квантовые компьютеры пока не способны обрабатывать числа такого размера.

Значение для криптографии

Влияние на длину ключей RSA

Результаты RSA Factoring Challenge напрямую повлияли на рекомендации по выбору длины ключей RSA. После факторизации RSA-155 (512 бит) в 1999 году Национальный институт стандартов и технологий США (NIST) рекомендовал отказаться от 512-битных ключей. После факторизации RSA-768 (768 бит) в 2009 году минимальная рекомендуемая длина ключа была повышена до 2048 бит. В настоящее время для долгосрочной безопасности рекомендуется использовать ключи длиной 3072 или 4096 бит.

Демонстрация практической сложности

Соревнование показало, что факторизация чисел длиной 1024 бита (RSA-1024) остаётся практически невозможной при современном уровне вычислительной техники, но может стать доступной в течение 10–20 лет при развитии технологий. Это стимулировало переход на более длинные ключи и развитие постквантовой криптографии.

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

Критика организации

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

Ограничения соревнования

• Соревнование не учитывало возможность использования квантовых компьютеров.
• Не рассматривались атаки, не связанные с факторизацией (например, атаки на основе побочных каналов или утечки ключей).
• Призы были относительно скромными (до $10 000 за RSA-768), что не стимулировало масштабные проекты.

Интересные факты

• Число RSA-129 (129 цифр, 426 бит) было факторизовано в 1994 году группой из 600 добровольцев с использованием Интернета — это был один из первых примеров распределённых вычислений.
• Для факторизации RSA-768 потребовалось более 2 лет вычислений на кластере из сотен компьютеров, общий объём данных составил около 2 ТБ.
• Последнее решённое число — RSA-768 — было факторизовано в 2009 году, и с тех пор ни одно число из серии RSA большей длины не было факторизовано.

Источники

• RSA Laboratories, "The RSA Factoring Challenge", 1991–2007.
• A. K. Lenstra, H. W. Lenstra, M. S. Manasse, J. M. Pollard, "The Number Field Sieve", 1993.
• F. Bahr, M. Boehm, J. Franke, T. Kleinjung, "Factorization of RSA-768", 2009.
• NIST Special Publication 800-57, "Recommendation for Key Management", 2016.
• M. J. Wiener, "Cryptanalysis of Short RSA Secret Exponents", 1990.