Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

RSA Факторинг вызов является вызовом , выдвинутое 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 году, только RSA-576 и RSA-640 были выведены из числа проверок 2001 года. [7]

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

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

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

Математика [ править ]

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

п = p × q .

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

Призы и рекорды [ править ]

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

Номера испытаний в белых линиях - это числа, выраженные по основанию 10 , а номера вызовов в желтых линиях - это числа, выраженные по основанию 2.
Номер RSAДесятичные цифрыДвоичные цифрыПредлагается денежный призФактор наФактор
RSA-1001003301 000 долларов США [8]1 апреля 1991 г. [9]Арьен К. Ленстра
RSA-1101103644 429 долл. США [8]14 апреля 1992 г. [9]Арьен К. Ленстра и М.С. Манассе
RSA-1201203975 898 долл. США [8]9 июля 1993 г. [10]T. Denny et al.
RSA-129 [а]129426100 долларов США26 апреля 1994 г. [9]Арьен К. Ленстра и др.
RSA-13013043014 527 долларов США [8]10 апреля 1996 г.Арьен К. Ленстра и др.
RSA-14014046317 226 долларов США2 февраля 1999 г.Герман те Риле и др.
RSA-150150496 16 апреля 2004 г.Казумаро Аоки и др.
RSA-1551555129 383 долл. США [8]22 августа 1999 г.Герман те Риле и др.
RSA-160160530 1 апреля 2003 г.Jens Franke et al. , Боннский университет
РСА-170 [б]170563 29 декабря 2009 г.Д. Боненбергер и М. Кроне [c]
RSA-57617457610 000 долларов США3 декабря 2003 г.Jens Franke et al. , Боннский университет
РСА-180 [б]180596 8 мая 2010 г.Данилов С.А., Поповян И.А., МГУ [11]
RSA-190 [б]190629 8 ноября 2010 г.А. Тимофеев, И. А. Поповян
RSA-64019364020 000 долларов США2 ноября 2005 г.Jens Franke et al. , Боннский университет
РСА-200 [б]  ?200663 9 мая 2005 г.Jens Franke et al. , Боннский университет
РСА-210 [б]21069626 сентября 2013 г. [12]Райан Проппер
RSA-704 [b]21270430 000 долларов США2 июля 2012 г.Ши Бай, Эммануэль Томе и Пол Циммерманн
РСА-220 [б]220729 13 мая, 2016С. Бай, П. Годри, А. Круппа, Э. Томе и П. Циммерманн
РСА-230 [б]230762 15 августа 2018 г.Сэмюэл С. Гросс, Noblis, Inc.
RSA-232 [b]232768 17 февраля 2020 г. [13]Н.Л. Замарашкин, Д.А. Желтков, С.А. Матвеев.
RSA-768 [b]23276850 000 долларов США12 декабря 2009 г.Thorsten Kleinjung et al. [14]
РСА-240 [б]240795 2 декабря 2019 г. [15]Ф. Будо, П. Годри, А. Гильевич, Н. Хенингер, Э. Томе и П. Циммерманн
РСА-250 [б]250829 28 февраля 2020 г. [16]Ф. Будо, П. Годри, А. Гильевич, Н. Хенингер, Э. Томе и П. Циммерманн
RSA-260260862 
RSA-270270895 
RSA-89627089675 000 долларов США [d]
RSA-280280928 
RSA-290290962 
RSA-300300995 
RSA-3093091024 
RSA-10243091024100 000 долларов США [d]
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 долларов США [d]
RSA-4704701559 
RSA-4804801593 
RSA-4904901626 
RSA-5005001659 
RSA-6176172048 
RSA-20486172048200 000 долларов США [d]
  1. ^ RSA-129 не был частью RSA Factoring Challenge, но был связан с колонкой Мартина Гарднера в Scientific American .
  2. ^ a b c d e f g h i j k l После завершения испытания число было учтено.
  3. ^ RSA-170 был также независимо проанализирован С.А. Даниловым и И.А. Поповяном двумя днями позже. [11]
  4. ^ a b c d Вызов завершился до присуждения этой награды.

См. Также [ править ]

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

Заметки [ править ]

  1. ^ Kaliski, Burt (18 марта 1991). «Анонс« RSA Factoring Challenge » » . Проверено 8 марта 2021 года .
  2. ↑ Лейден, Джон (25 июля 2001 г.). «RSA представляет собой криптовалютный вызов на $ 200 000» . Реестр . Проверено 8 марта 2021 года .
  3. ^ Лаборатории RSA. «Новый вызов факторинга RSA» . Архивировано из оригинала на 2001-07-14.
  4. ^ Лаборатории RSA. «Номера вызовов RSA» . Архивировано из оригинала на 2001-08-05.
  5. ^ a b Лаборатории RSA. «RSA Factoring Challenge» . Архивировано из оригинала на 2013-09-21 . Проверено 5 августа 2008 . CS1 maint: обескураженный параметр ( ссылка )
  6. ^ a b Лаборатории RSA. «Вопросы и ответы по RSA Factoring Challenge» . Архивировано из оригинала на 2013-09-21 . Проверено 5 августа 2008 . CS1 maint: обескураженный параметр ( ссылка )
  7. ^ Лаборатории RSA. «Номера вызовов RSA» . Архивировано из оригинала на 2013-09-21 . Проверено 5 августа 2008 . CS1 maint: обескураженный параметр ( ссылка )
  8. ^ a b c d e "Статус / новостной отчет по проблеме факторинга безопасности данных RSA (по состоянию на 30.03.00)" . 30 января 2002 г.
  9. ^ a b c Список почета RSA
  10. ^ Денни, Т .; Додсон, В .; Ленстра, АК; Манассе, М.С. (1994). О факторизации RSA-120 . Достижения в криптологии - CRYPTO '93 . С. 166–174. DOI : 10.1007 / 3-540-48329-2_15 .
  11. ^ a b Данилов С.А.; Поповян И.А. (9 мая 2010 г.). «Факторизация РСА-180» (PDF) . Cryptology ePrint Archive .
  12. ^ RSA-210 разложенный , mersenneforum.org
  13. ^ Новости ИВМ РАН
  14. ^ Kleinjung, Томас (18 февраля 2010). «Факторизация 768-битного модуля RSA» (PDF) . Цитировать журнал требует |journal=( помощь )
  15. ^ Thomé, Эммануэль (2 декабря 2019). «795-битное разложение и дискретные логарифмы» . cado-nfs-Discussion (Список рассылки).
  16. ↑ Циммерманн, Пол (28 февраля 2020 г.). «Факторизация РСА-250» . cado-nfs-Discussion (Список рассылки).