RSA Factoring Challenge

RSA Factoring Challenge - это вызов, выдвинутый RSA Laboratories в марте 18, 1991, чтобы поощрить исследование теории вычислительных чисел и практических трудностей разложения на множители больших целых чисел и взлома ключей RSA, используемых в криптография. Они опубликовали список полупростых чисел (чисел с двумя простыми множителями ), известных как числа RSA, с денежным призом за успешную факторизацию некоторых из них.. Наименьшее из них, число из 100 десятичных цифр, называемое RSA-100, было учтено к 1 апреля 1991 года, но многие из более крупных чисел до сих пор не учтены и, как ожидается, в течение некоторого времени не будут учтены., однако достижения в квантовых компьютерах делают этот прогноз неопределенным из-за алгоритма Шора.

Проблемы RSA закончились в 2007 году. RSA Laboratories заявила: «Теперь, когда отрасль имеет значительно более глубокое понимание криптоаналитическая стойкость общих алгоритмов с симметричным ключом и с открытым ключом, эти проблемы больше не действуют ».

Задача факторинга была предназначена для отслеживания передовых достижений в целочисленная факторизация. Первичное приложение предназначено для выбора длины ключа схемы RSA шифрования с открытым ключом. Прогресс в решении этой задачи должен дать представление о том, какие размеры ключей по-прежнему безопасны и как долго. Поскольку RSA Laboratories является поставщиком продуктов на основе RSA, они использовали этот вызов как стимул для академического сообщества атаковать ядро ​​своих решений - чтобы доказать свою силу.

Номера RSA были сгенерированы на компьютере без какого-либо сетевого подключения. Впоследствии жесткий диск компьютера был уничтожен, так что нигде не осталось записей о решении проблемы факторинга.

Первые сгенерированные номера RSA, от RSA-100 до RSA-500 и RSA-617, были помечены по количеству десятичных цифр; другие номера RSA (начиная с RSA-576) были сгенерированы позже и помечены в соответствии с их количеством двоичных цифр. Числа в таблице ниже перечислены в порядке возрастания, несмотря на переход от десятичной системы к двоичной.

• 1 Математика
• 2 Призы и рекорды
• 3 См. Также
• 4 Примечания
• 5 Внешние ссылки

Лаборатории RSA заявляют, что : для каждого номера RSA n существует простых чисел p и q, таких что

n = p × q.

Проблема состоит в том, чтобы найти эти два простых числа, учитывая только n.

В следующей таблице представлен обзор всех номеров RSA.

Номера вызовов в белых линиях - это числа, выраженные в базе 10, а номера вызовов в желтых строках - это числа, выраженные в базе 2

Число было пересчитано после того, как вызов стал неактивным.

RSA-129 не был частью RSA Factoring Challenge, но был связан с колонкой Мартина Гарднера в Scientific American.

RSA-170 также независимо проанализировали С.А. Данилов и И.А. Поповян два дня спустя.

• числа RSA, десятичные разложения чисел и известные факторизации
• LCS35
• Волшебные слова - это Squeamish Ossifrage, решение, найденное в 1993 году для другого RSA Проблема, поставленная в 1977 г.
• Вызов RSA Secret-Key
• Записи целочисленной факторизации

1. ^RSA Laboratories, Проблема RSA Factoring Challenge Архивировано 2013-11-10 в Wayback Machine. Проверено 9 ноября 2013.
2. ^RSA Laboratories, FAQ по RSA Factoring Challenge Архивировано 10 ноября 2013 г. на Wayback Machine. Проверено 9 ноября 2013.
3. ^Лаборатории RSA. «Вопросы и ответы по RSA Factoring Challenge». Архивировано с оригинального 21.09.2013. Проверено 5 августа 2008 г.
4. ^ «Отчет о состоянии / новостях по проблеме факторинга данных RSA (по состоянию на 30.03.00)». 30 января 2002 г.
5. ^ RSA Honor Roll
6. ^Denny, T.; Додсон, В.; Ленстра, А. К.; Манассе, М. С. (1994). О факторизации RSA-120. Достижения криптологии - CRYPTO '93. С. 166–174. doi : 10.1007 / 3-540-48329-2_15.
7. ^ Данилов, С.А.; Поповян И.А. (9 мая 2010 г.). «Факторизация РСА-180» (PDF). Архив криптологии ePrint.
8. ^Факторизация RSA-210, mersenneforum.org
9. ^Новости ИВМ РАН
10. ^Томе, Эммануэль (2 декабря 2019 г.). «795-битное разложение и дискретные логарифмы». cado-nfs-Discussion (Список рассылки).
11. ^Циммерманн, Пол (28 февраля 2020 г.). «Факторизация РСА-250». cado-nfs-обсуждение (Список рассылки).

• Безопасность RSA: проблема факторинга RSA
• MathWorld: номер RSA
• Пакет Mathematica для номеров RSA
• Первоначальное объявление о вызове на sci. crypt
• Исходное объявление о вызове на sci.crypt (обновленная ссылка)
• Certicom ECC Challenge
• MTC3 Благодаря RSA Inc, криптовалютный конкурс MTC3 содержит все нерешенные номера RSA и предлагает пользователям дополнительную информацию и отзывы об этих проблемах факторизации.