RSA-130

RSA-130 — это 130-значное (430-битное) число, которое в 1996 году было успешно разложено на два простых множителя в рамках международного проекта по факторизации больших чисел, организованного в сети Интернет. RSA-130 относится к классу RSA-чисел — полупростых чисел, используемых для проверки стойкости криптосистемы RSA. Успешное разложение RSA-130 стало важным этапом в развитии методов факторизации и продемонстрировало возможности распределённых вычислений.

История

Предпосылки

В 1977 году Рональд Ривест, Ади Шамир и Леонард Адлеман опубликовали описание криптосистемы RSA, стойкость которой основана на практической сложности разложения больших составных чисел на простые множители. Для демонстрации надёжности алгоритма авторы предложили факторизовать 129-значное число (RSA-129), опубликованное в журнале Scientific American. В 1994 году это число было разложено группой учёных под руководством Атолла Ленстры и Джеймса Полларда с использованием метода квадратичного решета.

Проект RSA Factoring Challenge

В 1991 году компания RSA Laboratories (впоследствии — подразделение RSA Security) запустила RSA Factoring Challenge — серию задач по факторизации полупростых чисел различной длины. Числа обозначались как RSA-<количество десятичных цифр>, например RSA-100, RSA-110, RSA-120 и так далее. Участники могли получить денежное вознаграждение за успешную факторизацию.

Разложение RSA-130

RSA-130 было опубликовано в 1991 году как часть испытания. В 1996 году международная группа исследователей, включавшая специалистов из Нидерландов, Великобритании, Франции, США и других стран, приступила к его факторизации. Работа велась под руководством Атолла Ленстры (CWI, Амстердам) и Джеймса Полларда (Microsoft Research). Для вычислений использовался метод решета числового поля (NFS — Number Field Sieve), который на тот момент считался наиболее эффективным алгоритмом для факторизации чисел размером более 100 десятичных знаков.

Процесс факторизации занял около 4 месяцев. Основная вычислительная нагрузка была распределена между несколькими компьютерами, работавшими в сети Интернет. Общее процессорное время составило около 500 MIPS-лет (миллионов инструкций в секунду за год). Результат был объявлен 10 апреля 1996 года: RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243 × 45534498646735972188403686897274408864356301263205069600999044599.

Характеристики

Числовые параметры

RSA-130 представляло собой полупростое число (произведение двух простых чисел) длиной 130 десятичных цифр (430 бит). Его десятичная запись:

114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541

Сложность факторизации

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

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

Метод решета числового поля

Метод решета числового поля (NFS) — это алгоритм факторизации больших чисел, основанный на теории алгебраических чисел. Он был разработан в 1980-х годах Джеймсом Поллардом, Хендриком Ленстрой и другими математиками. Для RSA-130 использовалась его модификация — специальное решето числового поля (SNFS), оптимизированное для чисел специального вида (например, чисел вида 2^n ± 1). Однако RSA-130 не относилось к числам специального вида, поэтому применялась общая версия NFS (GNFS).

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

Факторизация RSA-130 стала одним из первых крупных проектов, в котором использовались распределённые вычисления через Интернет. Участники проекта добровольно предоставляли вычислительные ресурсы своих компьютеров для выполнения отдельных этапов алгоритма. Координация работы осуществлялась через центральный сервер в CWI. Этот подход впоследствии лёг в основу более масштабных проектов, таких как GIMPS (Great Internet Mersenne Prime Search) и BOINC.

Значение

Для криптографии

Успешная факторизация RSA-130 подтвердила, что 430-битные ключи RSA не обеспечивают достаточной стойкости против атак с использованием современных вычислительных методов. Это побудило криптографическое сообщество рекомендовать использование ключей длиной не менее 1024 бит (около 300 десятичных цифр) для обеспечения долговременной безопасности. Впоследствии, с ростом вычислительных мощностей, минимальная рекомендуемая длина ключей RSA была увеличена до 2048 бит.

Для развития алгоритмов

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

Критика

Некоторые специалисты отмечали, что RSA Factoring Challenge, включая задачу RSA-130, имел ограниченное практическое значение, поскольку использованные числа были специально сконструированы для проверки алгоритмов, а не для реальных криптографических приложений. Кроме того, денежные призы за факторизацию были относительно невелики (например, за RSA-130 полагалось 1000 долларов США), что не стимулировало массового участия.

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

• RSA-130 было разложено спустя 5 лет после публикации, что на тот момент было рекордно коротким сроком для числа такого размера.
• В проекте участвовали компьютеры из 11 стран, включая Россию, США, Великобританию, Германию, Францию, Нидерланды, Японию, Австралию, Канаду, Швейцарию и Италию.
• После успешной факторизации RSA-130 компания RSA Security увеличила призовые за последующие числа: за RSA-140 было предложено 2000 долларов, за RSA-155 — 5000 долларов.

Источники

• Lenstra, A. K., & Pollard, J. M. (1996). Factorization of RSA-130. CWI Report.
• RSA Laboratories. (1991). RSA Factoring Challenge.
• Pomerance, C. (1996). A Tale of Two Sieves. Notices of the AMS.
• Crandall, R., & Pomerance, C. (2005). Prime Numbers: A Computational Perspective. Springer.