Проблема факторинга RSA
Задача по разложению больших полупростых чисел

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

В 2001 году RSA Laboratories расширили задачу факторизации и предложили призы в размере от 10 000 до 200 000 долларов за факторизацию чисел длиной от 576 бит до 2048 бит. [2] [3] [4]

Конкурс RSA Factoring Challenges завершился в 2007 году. [5] RSA Laboratories заявили: «Теперь, когда отрасль имеет значительно более глубокое понимание криптоаналитической стойкости общих алгоритмов с симметричным и открытым ключом , эти конкурсы больше не актуальны». [6] Когда конкурс завершился в 2007 году, из номеров конкурса 2001 года были факторизованы только RSA-576 и RSA-640. [7]

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

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

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

Математика

RSA Laboratories утверждает, что: для каждого числа RSA n существуют простые числа p и q, такие что

n = p × q .

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

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

В следующей таблице представлен обзор всех чисел RSA. Обратите внимание, что RSA Factoring Challenge завершился в 2007 году [5] , и больше никаких призов за факторинг более высоких чисел не будет.

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

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

Примечания

  1. ↑ Калиски, Берт (18 марта 1991 г.). «Анонс «RSA Factoring Challenge»» . Проверено 8 марта 2021 г.[ мертвая ссылка ]
  2. ^ Лейден, Джон (25 июля 2001 г.). «RSA ставит криптовалюту на $200 000». The Register . Получено 8 марта 2021 г. .
  3. ^ RSA Laboratories. "Новая проблема факторинга RSA". Архивировано из оригинала 2001-07-14.
  4. ^ RSA Laboratories. "Числа испытаний RSA". Архивировано из оригинала 2001-08-05.
  5. ^ ab RSA Laboratories. "RSA Factoring Challenge". Архивировано из оригинала 2013-09-21 . Получено 2008-08-05 .
  6. ^ ab RSA Laboratories. "Часто задаваемые вопросы по RSA Factoring Challenge". Архивировано из оригинала 21.09.2013 . Получено 05.08.2008 .
  7. ^ RSA Laboratories. "The RSA Challenge Numbers". Архивировано из оригинала 21.09.2013 . Получено 05.08.2008 .
  8. ^ abcde «Отчет о состоянии/новостях по проблеме факторинга безопасности данных RSA (по состоянию на 30 марта 2000 г.)» . 30 января 2002 г.
  9. ^ abc RSA Honor Roll
  10. ^ Денни, Т.; Додсон, Б.; Ленстра, АК; Манассе, М.С. (1994). О факторизации RSA-120 . Достижения в криптологии – CRYPTO' 93. Конспект лекций по информатике. Том 773. С. 166–174. doi : 10.1007/3-540-48329-2_15 . ISBN 978-3-540-57766-9.
  11. ^ ab Данилов, СА; Поповян, IA (9 мая 2010 г.). "Факторизация RSA-180" (PDF) . Архив Cryptology ePrint .
  12. ^ Факторизованный RSA-210, mersenneforum.org
  13. ^ Новости ИВМ РАН
  14. ^ Кляйнджунг, Томас (18 февраля 2010 г.). «Факторизация 768-битного модуля RSA» (PDF) . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
  15. ^ Томе, Эммануэль (2 декабря 2019 г.). «795-битная факторизация и дискретные логарифмы». cado-nfs-discuss (список рассылки).
  16. ^ Циммерман, Пол (28 февраля 2020 г.). «Факторизация RSA-250». cado-nfs-discuss (список рассылки).
Взято с "https://en.wikipedia.org/w/index.php?title=RSA_Factoring_Challenge&oldid=1244140367"