RSA Factoring Challenge - RSA Factoring Challenge

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

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

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

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

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

Математика

RSA Laboratories заявляет, что: для каждого номера RSA п, Существует простые числа п и q такой, что

п = п × q.

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

Призы и рекорды

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

Номера вызовов в белых линиях - это числа, выраженные в база 10, а номера задач в желтых линиях - это числа, выраженные в база 2
Номер RSAДесятичные цифрыДвоичные цифрыПредлагается денежный призФактор наФактор
RSA-1001003301000 долларов США[4]1 апреля 1991 г.[5]Арьен К. Ленстра
RSA-1101103644 429 долларов США[4]14 апреля 1992 г.[5]Арьен К. Ленстра и РС. Манассе
RSA-1201203975 898 долларов США[4]9 июля 1993 г.[6]Т. Денни и другие.
RSA-129 [**]129426100 долларов США26 апреля 1994 г.[5]Арьен К. Ленстра и другие.
RSA-13013043014 527 долларов США[4]10 апреля 1996 г.Арьен К. Ленстра и другие.
RSA-14014046317 226 долларов США2 февраля 1999 г.Герман те Риле и другие.
RSA-150150496 16 апреля 2004 г.Казумаро Аоки и другие.
RSA-1551555129 383 долл. США[4]22 августа 1999 г.Герман те Риле и другие.
RSA-160160530 1 апреля 2003 г.Йенс Франке и другие., Боннский университет
RSA-170 [*]170563 29 декабря 2009 г.Д. Боненбергер и М. Кроне [***]
RSA-57617457610 000 долларов США3 декабря 2003 г.Йенс Франке и другие., Боннский университет
RSA-180 [*]180596 8 мая 2010 г.Данилов С.А., Поповян И.А., Московский Государственный Университет[7]
RSA-190 [*]190629 8 ноября 2010 г.А. Тимофеев, И. А. Поповян
RSA-64019364020 000 долларов США2 ноября 2005 г.Йенс Франке и другие., Боннский университет
RSA-200 [*] ?200663 9 мая 2005 г.Йенс Франке и другие., Боннский университет
RSA-210 [*]21069626 сентября 2013 г.[8]Райан Проппер
RSA-704 [*]21270430 000 долларов США2 июля 2012 г.Ши Бай, Эммануэль Томе и Пауль Циммерманн
RSA-220 [*]220729 13 мая 2016С. Бай, П. Годри, А. Круппа, Э. Томе и П. Циммерманн
RSA-230 [*]230762 15 августа 2018 г.Сэмюэл С. Гросс, Noblis, Inc.
RSA-232 [*]232768 17 февраля 2020 г.[9]Замарашкин Н.Л., Желтков Д.А., Матвеев С.А.
RSA-768 [*]23276850 000 долларов США12 декабря 2009 г.Торстен Кляйнджунг и другие.
RSA-240 [*]240795 2 декабря 2019 г.[10]Ф. Будо, П. Годри, А. Гильевич, Н. Хенингер, Э. Томе и П. Циммерманн
РСА-250 [*]250829 28 февраля 2020 г.[11]Ф. Будо, П. Годри, А. Гильевич, Н. Хенингер, Э. Томе и П. Циммерманн
RSA-260260862 
RSA-270270895 
RSA-89627089675 000 долларов США
RSA-280280928 
RSA-290290962 
RSA-300300995 
RSA-3093091024 
RSA-10243091024100 000 долларов США
RSA-3103101028 
RSA-3203201061 
RSA-3303301094 
RSA-3403401128 
RSA-3503501161 
RSA-3603601194 
RSA-3703701227 
RSA-3803801261 
RSA-3903901294 
RSA-4004001327 
RSA-4104101360 
RSA-4204201393 
RSA-4304301427 
RSA-4404401460 
RSA-4504501493 
RSA-4604601526 
RSA-15364631536150 000 долларов США
RSA-4704701559 
RSA-4804801593 
RSA-4904901626 
RSA-5005001659 
RSA-6176172048 
RSA-20486172048200 000 долларов США

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

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

^ *** Двумя днями позже RSA-170 был также независимо проанализирован С. А. Даниловым и И. А. Поповяном.[7]

Смотрите также

Заметки

  1. ^ RSA Laboratories, Проблема факторинга RSA В архиве 2013-11-10 в Wayback Machine. Проверено 9 ноября 2013.
  2. ^ RSA Laboratories, Часто задаваемые вопросы о RSA Factoring Challenge В архиве 2013-11-10 в Wayback Machine. Проверено 9 ноября 2013.
  3. ^ RSA Laboratories. "Часто задаваемые вопросы о RSA Factoring Challenge". Архивировано из оригинал 21.09.2013. Получено 2008-08-05.
  4. ^ а б c d е «Статус / новостной отчет по проблеме факторинга данных RSA (по состоянию на 30.03.00)». 30 января 2002 г.
  5. ^ а б c Доска почета RSA
  6. ^ Денни, Т .; Додсон, В .; Ленстра, А. К .; Манассе, М. С. (1994). О факторизации RSA-120. Достижения в криптологии - CRYPTO '93. С. 166–174. Дои: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-обсуждение (Список рассылки).
  11. ^ Циммерманн, Пауль (28 февраля 2020 г.). «Факторизация РСА-250». cado-nfs-обсуждение (Список рассылки).

внешняя ссылка