Факторинговый вызов 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 Challenge завершилась в 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 такие, что
- п знак равно п × q .
Проблема состоит в том, чтобы найти эти два простых числа, зная только n .
Призы и рекорды
[ редактировать ]В следующей таблице представлен обзор всех номеров RSA. Обратите внимание, что конкурс RSA Factoring Challenge завершился в 2007 году. [5] и никакие дополнительные призы не будут присуждаться за факторинг более высоких чисел.
- Номера задач, отмеченные белыми линиями, являются частью исходной задачи и выражены по базе 10 , тогда как номера задач, отмеченные желтыми линиями, являются частью расширения 2001 года и выражены по базе 2.
| номер RSA | Десятичные цифры | Двоичные цифры | Предлагается денежный приз | С учетом | факторизовано |
|---|---|---|---|---|---|
| RSA100 | 100 | 330 | 1000 долларов США [8] | 1 апреля 1991 г. [9] | Арьен К. Ленстра |
| RSA110 | 110 | 364 | 4429 долларов США [8] | 14 апреля 1992 г. [9] | Арьен К. Ленстра и М.С. Манассе |
| RSA120 | 120 | 397 | 5898 долларов США [8] | 9 июля 1993 г. [10] | Т. Денни и др. |
| RSA129 [а] | 129 | 426 | 100 долларов США | 26 апреля 1994 г. [9] | Арьен К. Ленстра и др. |
| RSA130 | 130 | 430 | 14 527 долларов США [8] | 10 апреля 1996 г. | Арьен К. Ленстра и др. |
| RSA140 | 140 | 463 | 17 226 долларов США | 2 февраля 1999 г. | Герман те Риле и др. |
| RSA150 | 150 | 496 | 16 апреля 2004 г. | Кадзумаро Аоки и др. | |
| RSA155 | 155 | 512 | 9 383 доллара США [8] | 22 августа 1999 г. | Герман те Риле и др. |
| RSA160 | 160 | 530 | 1 апреля 2003 г. | Йенс Франке и др. , Боннский университет | |
| RSA170 [б] | 170 | 563 | 29 декабря 2009 г. | Д. Боненбергер и М. Кроне [с] | |
| RSA576 | 174 | 576 | 10 000 долларов США | 3 декабря 2003 г. | Йенс Франке и др. , Боннский университет |
| RSA180 [б] | 180 | 596 | 8 мая 2010 г. | С.А. Данилов и И.А. Поповян, МГУ [11] | |
| RSA190 [б] | 190 | 629 | 8 ноября 2010 г. | А. Тимофеев и И. А. Поповян | |
| RSA640 | 193 | 640 | 20 000 долларов США | 2 ноября 2005 г. | Йенс Франке и др. , Боннский университет |
| РСА200 [б] ? | 200 | 663 | 9 мая 2005 г. | Йенс Франке и др. , Боннский университет | |
| RSA210 [б] | 210 | 696 | 26 сентября 2013 г. [12] | Райан Проппер | |
| RSA704 [б] | 212 | 704 | 30 000 долларов США | 2 июля 2012 г. | Ши Бай, Эммануэль Томе и Пол Циммерманн |
| RSA220 [б] | 220 | 729 | 13 мая 2016 г. | С. Бай, П. Годри, А. Круппа, Э. Томе и П. Циммерманн | |
| RSA230 [б] | 230 | 762 | 15 августа 2018 г. | Сэмюэл С. Гросс, Noblis, Inc. | |
| RSA232 [б] | 232 | 768 | 17 февраля 2020 г. [13] | Н.Л. Замарашкин, Д.А. Желтков и С.А. Матвеев. | |
| RSA768 [б] | 232 | 768 | 50 000 долларов США | 12 декабря 2009 г. | Торстен Кляйнюнг и др. [14] |
| RSA240 [б] | 240 | 795 | 2 декабря 2019 г. [15] | Ф. Будо, П. Годри, А. Гильевич, Н. Хенингер, Э. Томе и П. Циммерманн | |
| RSA250 [б] | 250 | 829 | 28 февраля 2020 г. [16] | Ф. Будо, П. Годри, А. Гильевич, Н. Хенингер, Э. Томе и П. Циммерманн | |
| RSA260 | 260 | 862 | |||
| RSA270 | 270 | 895 | |||
| RSA896 | 270 | 896 | 75 000 долларов США [д] | ||
| RSA280 | 280 | 928 | |||
| RSA290 | 290 | 962 | |||
| RSA300 | 300 | 995 | |||
| RSA309 | 309 | 1024 | |||
| RSA1024 | 309 | 1024 | 100 000 долларов США [д] | ||
| RSA310 | 310 | 1028 | |||
| RSA320 | 320 | 1061 | |||
| RSA330 | 330 | 1094 | |||
| RSA340 | 340 | 1128 | |||
| RSA350 | 350 | 1161 | |||
| RSA360 | 360 | 1194 | |||
| RSA370 | 370 | 1227 | |||
| RSA380 | 380 | 1261 | |||
| RSA390 | 390 | 1294 | |||
| РСА400 | 400 | 1327 | |||
| RSA410 | 410 | 1360 | |||
| RSA420 | 420 | 1393 | |||
| RSA430 | 430 | 1427 | |||
| RSA440 | 440 | 1460 | |||
| RSA450 | 450 | 1493 | |||
| RSA460 | 460 | 1526 | |||
| RSA1536 | 463 | 1536 | 150 000 долларов США [д] | ||
| RSA470 | 470 | 1559 | |||
| RSA480 | 480 | 1593 | |||
| RSA490 | 490 | 1626 | |||
| RSA500 | 500 | 1659 | |||
| RSA617 | 617 | 2048 | |||
| RSA2048 | 617 | 2048 | 200 000 долларов США [д] | ||
- ^ RSA-129 не был частью RSA Factoring Challenge, но был связан с колонкой Мартина Гарднера в Scientific American .
- ^ Jump up to: Перейти обратно: а б с д и ж г час я дж к л Число было учтено после окончания испытания.
- ↑ RSA-170 также была независимо факторизована С.А. Даниловым и И.А. Поповяном два дня спустя. [11]
- ^ Jump up to: Перейти обратно: а б с д Соревнование закончилось до того, как этот приз был вручен.
См. также
[ редактировать ]- Числа RSA , десятичные разложения чисел и известные факторизации
- ЛКС35
- Волшебные слова — это брезгливая костеобразование , решение, найденное в 1993 году для решения другой проблемы RSA, поставленной в 1977 году.
- Вызов секретного ключа RSA
- Записи целочисленной факторизации
Примечания
[ редактировать ]- ^ Калиски, Берт (18 марта 1991 г.). «Анонс «RSA Factoring Challenge» » . Проверено 8 марта 2021 г. [ мертвая ссылка ]
- ^ Лейден, Джон (25 июля 2001 г.). «RSA представляет собой криптовалютный вызов на сумму 200 000 долларов» . Регистр . Проверено 8 марта 2021 г.
- ^ Лаборатории РСА. «Новая проблема факторинга RSA» . Архивировано из оригинала 14 июля 2001 г.
- ^ Лаборатории РСА. «Цифры вызовов RSA» . Архивировано из оригинала 5 августа 2001 г.
- ^ Jump up to: Перейти обратно: а б Лаборатории РСА. «Вызов факторинга RSA» . Архивировано из оригинала 21 сентября 2013 г. Проверено 5 августа 2008 г.
- ^ Jump up to: Перейти обратно: а б Лаборатории РСА. «Часто задаваемые вопросы по факторингу RSA» . Архивировано из оригинала 21 сентября 2013 г. Проверено 5 августа 2008 г.
- ^ Лаборатории РСА. «Цифры вызовов RSA» . Архивировано из оригинала 21 сентября 2013 г. Проверено 5 августа 2008 г.
- ^ Jump up to: Перейти обратно: а б с д и «Отчет о состоянии/новостях по проблеме факторинга безопасности данных RSA (по состоянию на 30 марта 2000 г.)» . 30 января 2002 г.
- ^ Jump up to: Перейти обратно: а б с Доска почета ЮАР
- ^ Денни, Т.; Додсон, Б.; Ленстра, АК; Манасс, М.С. (1994). О факторизации RSA-120 . Достижения криптологии – КРИПТО' 93 . Конспекты лекций по информатике. Том. 773. стр. 166–174. дои : 10.1007/3-540-48329-2_15 . ISBN 978-3-540-57766-9 .
- ^ Jump up to: Перейти обратно: а б Данилов С.А.; Поповян, И.А. (9 мая 2010 г.). «Факторизация RSA-180» (PDF) . Архив электронной печати по криптологии .
- ^ RSA-210 с учетом , mersenneforum.org
- ^ Новости ИВМ РАН
- ^ Кляйнджунг, Томас (18 февраля 2010 г.). «Факторизация 768-битного модуля RSA» (PDF) .
{{cite journal}}: Для цитирования журнала требуется|journal=( помощь ) - ^ Томе, Эммануэль (2 декабря 2019 г.). «795-битный факторинг и дискретные логарифмы» . cado-nfs-discuss (список рассылки).
- ^ Циммерманн, Пол (28 февраля 2020 г.). «Факторизация RSA-250» . cado-nfs-discuss (список рассылки).