RSA: различия между версиями
| [непроверенная версия] | [непроверенная версия] |
Содержимое удалено Содержимое добавлено
| (не показано 47 промежуточных версий 33 участников) | |||
Строка 1:
{{другие значения}}
{{Универсальная карточка}}
'''RSA''' (аббревиатура от фамилий Rivest, Shamir и Adleman) — [[Криптосистема с открытым ключом|криптографический алгоритм с открытым ключом]], основывающийся на [[Вычислительная сложность|вычислительной сложности]] [[Факторизация целых чисел|задачи факторизации]] больших [[
Криптосистема RSA стала первой системой, пригодной и для [[шифрование|шифрования]], и для [[цифровая подпись|цифровой подписи]]. Алгоритм используется в большом числе криптографических приложений, включая [[PGP]], [[S/MIME]], [[TLS]]/[[SSL]], [[IPSEC]]/[[IKE]] и других{{sfn|Bakhtiari, Maarof|2012|p=175}}.
== История ==
Рон Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института в течение года предприняли несколько попыток создать одностороннюю функцию, которую было бы трудно инвертировать. Ривест и Шамир, будучи компьютерными учеными, предложили множество потенциальных функций, а Адлеман, будучи математиком, отвечал за поиск их слабых мест. Они опробовали множество подходов, включая "ранцевый" и "перестановочные полиномы". Какое-то время они думали, что то, чего они хотели достичь, невозможно из-за противоречивых требований. В апреле 1977 года они провели Песах в доме одного из студентов и выпили много манишевицкого вина, а затем вернулись к себе домой около полуночи. Ривест, не в силах заснуть, лег на диван с учебником математики и начал думать о своей односторонней функции. Остаток ночи он провел, формализуя свою идею, и к рассвету большая часть статьи была готова. Алгоритм теперь известен как RSA - инициалы их фамилий в том же порядке, что и в их статье.
Клиффорд Кокс, английский математик, работавший в британской разведывательной службе [[Центр правительственной связи|Government Communications Headquarters]] (GCHQ), описал эквивалентную систему во внутреннем документе в 1973 г. Однако, учитывая относительно дорогие компьютеры, необходимые для ее реализации в то время, она считалась в основном курьезом и, насколько известно, так и не была применена. Однако его открытие было раскрыто только в 1997 году из-за его
В августе [[1977 год]]а в колонке «Математические игры» Мартина Гарднера в журнале [[Scientific American]] с разрешения Рональда Ривеста<ref>{{cite web|url=http://blogs.scientificamerican.com/observations/2010/05/29/a-quarter-century-of-recreational-m-2010-05-26/|title=A Quarter Century of Recreational Mathematics, by Martin Gardner|publisher=Scientific American|lang=en|accessdate=2012-03-03|archiveurl=https://www.webcitation.org/68d2hJ129?url=http://blogs.scientificamerican.com/observations/2010/05/29/a-quarter-century-of-recreational-m-2010-05-26/|archivedate=2012-06-23|quote=Ronald L. Rivest of the Massachusetts Institute of Technology allowed me to be the first to reveal—in the August 1977 column—the «publickey» cipher system that he co-invented|deadurl=yes}}</ref> появилось первое описание криптосистемы RSA{{sfn|Gardner|1977}}. Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом:
Строка 54:
{{конец цитаты}}
В качестве открытых параметров системы были использованы числа n={{comment|1143816...6879541|114381625757888867669235779976146612010218296721242362562561842935706935245733897830597123563958705058989075147599290026879543541}} (129 десятичных знаков, 425 [[бит]], также известно как [[RSA-числа#RSA-129|RSA-129]]) и e=9007. За расшифровку была обещана награда в 100 долларов США. По заявлению Ривеста, для факторизации числа потребовалось бы более 40 квадриллионов лет<ref>{{cite web|url=http://sattlers.org/mickey/tech/privacy/topics/pgp/factoring.html|title=Factoring — State of the Art and Predictions|author=Bruce Schneier.|date=1995-02-12|lang=en|accessdate=2012-03-03|archiveurl=https://www.webcitation.org/68d2kSSYB?url=http://sattlers.org/mickey/tech/privacy/topics/pgp/factoring.html|archivedate=2012-06-23|deadurl=yes}}</ref>{{sfn|Bakhtiari, Maarof|2012|p=175}}. Однако чуть более, чем через 15 лет, 3 сентября [[1993 год]]а, было объявлено о запуске проекта [[распределённые вычисления|распределённых вычислений]] с координацией через электронную почту по нахождению сомножителей числа RSA-129 и решению головоломки. На протяжении полугода более 600 добровольцев из 20 стран жертвовали процессорное время 1600 машин (три из которых были факс-машинами{{Нет АИ|15|12|2015}}). В результате были найдены простые множители и расшифровано исходное сообщение, которое представляет собой фразу «{{нп1|THE MAGIC WORDS ARE SQUEAMISH OSSIFRAGE||en|The Magic Words are Squeamish Ossifrage}}» («Волшебные слова — это брезгливый [[ягнятник]]»)<ref>{{cite web|url=http://www.math.okstate.edu/~wrightd/numthry/rsa129.html|title=A Discussion of RSA-129 Activity|author=Donald T. Davis.|date=2003-11-25|lang=en|accessdate=2012-03-03|archiveurl=https://www.webcitation.org/68d2kyfmN?url=http://www.math.okstate.edu/~wrightd/numthry/rsa129.html|archivedate=2012-06-23|deadurl=yes}}</ref><ref>{{книга|автор=Чмора А. Л.|часть=4.6.4. Силовая атака на основе распределенных вычислений|заглавие=Современная прикладная криптография|год=2002|isbn=5-85438-046-3|тираж=2000}}</ref>. Полученную награду победители пожертвовали в [[фонд свободного программного обеспечения]].
После публикации Мартина Гарднера полное описание новой криптосистемы любой желающий мог получить, выслав по почте запрос Рональду Ривесту с приложенным конвертом с обратным адресом и марками на 35 центов.{{sfn|Gardner|1977}} Полное описание новой криптосистемы было опубликовано в журнале «[[Communications of the ACM]]» в феврале 1978 года{{sfn|Rivest, Shamir, Adleman|1978}}.
Строка 60:
Заявка на патент была подана 14 декабря 1977 года, в качестве владельца был указан MIT. Патент 4405829 был выдан 20 сентября [[1983 год]]а, а 21 сентября 2000 года срок его действия истёк<ref>Ronald L. Rivest et al. {{US patent|4405829|Cryptographic Communications System and Method}}</ref>. Однако за пределами США у изобретателей патента на алгоритм не было, так как в большинстве стран его необходимо было получить до первой публикации<ref>{{cite web|url=http://www.cypherspace.org/adam/timeline/|title=PGP Timeline|author=Adam Back.|lang=en|accessdate=2012-03-03|archiveurl=https://www.webcitation.org/68d2lPEnk?url=http://www.cypherspace.org/adam/timeline/|archivedate=2012-06-23|deadurl=yes}}</ref>.
В 1982 году Ривест, Шамир и Адлеман организовали компанию {{нп1|RSA Data Security||en|RSA (security firm)}} (в настоящий момент — подразделение [[EMC]]). В 1989 году RSA, вместе с симметричным шифром [[DES]], упоминается в RFC 1115, тем самым начиная использование алгоритма в зарождающейся сети Internet<ref>{{cite web|url=http://www.ietf.org/rfc/rfc1115.txt|title=Privacy Enhancement for Internet Electronic Mail: Part III — Algorithms, Modes, and Identifiers|author=J. Linn.|date=
В ноябре 1993 года открыто публикуется версия 1.5 стандарта {{нп1|PKCS1||en|PKCS1}}, описывающего применение RSA для шифрования и создания электронной подписи. Последние версии стандарта также доступны в виде [[RFC]] (RFC 2313 — 1.5, 1993 год; RFC 2437 — 2.0, 1998 год; RFC 3447 — 2.1, 2002 год).
В декабре [[1997 год]]а была обнародована информация
== Описание алгоритма ==
Строка 94:
: 4) выбирается целое число <math>e</math> (<math>1 < e < \varphi(n)</math>), [[взаимно простые числа|взаимно простое]] со значением функции <math>\varphi(n)</math>;
:: число <math>e</math> называется ''открытой экспонентой'' ({{lang-en|public exponent}});
:: обычно в качестве <math>e</math> берут простые числа, содержащие небольшое количество единичных бит в [[Двоичная система счисления|двоичной записи]], например, <br>простые из [[числа Ферма|чисел Ферма]]: 17, 257 или 65537, так как в этом случае время, необходимое для шифрования с использованием <br>[[Алгоритм быстрого возведения в степень|быстрого возведения в степень]], будет меньше;
:: слишком малые значения <math>e</math>, например 3, потенциально могут ослабить безопасность схемы RSA.{{sfn|Boneh|1999}};
: 5) вычисляется число <math>d</math>, [[
:: <math>d\cdot e \equiv 1 \pmod{\varphi(n)}</math>
:: (число <math>d</math> называется ''секретной экспонентой''; обычно оно вычисляется при помощи [[Расширенный алгоритм Евклида|расширенного алгоритма Евклида]]);
Строка 105:
Предположим, Боб хочет послать Алисе сообщение <math>m</math>.
Сообщениями являются [[целое число|целые числа]] в интервале от <math>0</math> до <math>n - 1</math>. {{sfn|Menezes,
[[Файл:Public key encryption, transmission and decryption light-ru-rendered.svg|center|650px]]
Строка 126:
=== Алгоритм шифрования сеансового ключа ===
Алгоритм шифрования сеансового ключа выглядит следующим образом<ref name="Shnaer">Брюс Шнайер. Прикладная криптография 2-е издание протоколы, алгоритмы и исходные тексты на языке C++</ref>:
Строка 221:
|[[#Скорость работы алгоритма RSA|Выбрать открытую экспоненту]]
|
:
|-
|[[#Выбор значения секретного показателя|Вычислить секретную экспоненту]]
Строка 333:
: <math> \exp (( c + o(1))k^{\frac{1}{3}} \log^{\frac{2}{3}}k)</math> для некоторого <math>c < 2</math>.
В 2010 году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта RSA длиной 768 бит. Нахождение простых сомножителей осуществлялось [[Общий метод решета числового поля|общим методом решета числового поля]]<ref>[https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt Анонс факторизации RSA-768] {{Wayback|url=https://documents.epfl.ch/users/l/le/lenstra/public/papers/rsa768.txt |date=20140413141828 }}{{ref-en}}</ref>. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только RSA-ключи длиной 1024 бита и более. Причём от шифрования ключом длиной в 1024 бит стоит отказаться в ближайшие три-четыре года<ref>[http://eprint.iacr.org/2010/006 Факторизация RSA-768] {{Wayback|url=http://eprint.iacr.org/2010/006 |date=20121213095435 }}{{ref-en}}</ref>. С 31 декабря 2013 года браузеры Mozilla перестали поддерживать сертификаты удостоверяющих центров с ключами RSA меньше 2048 бит<ref>
Кроме того, при неправильной или неоптимальной реализации или использовании алгоритма возможны специальные криптографические атаки, такие как атаки на схемы с малой секретной экспонентой или на схемы с общим выбранным значением модуля.
Строка 374:
где <math>d</math> — секретная экспонента, а <math>N</math> — модуль RSA. [[Боне, Дэн|Боне]] и Дерфи, используя двумерный аналог [[Теорема Копперсмита|Теоремы Копперсмита]], смогли обобщить [[Атака Винера|атаку Винера]]<ref name="Smart" /> на случай, когда<br>
<center><math> d \le N^{0,292}.</math></center>
=== Атака посредника, или атака «человек посередине» ===
[[Атака посредника]] не опасна если злоумышленник может только прослушивать канал связи по которому передаётся открытый ключ. В этом случаи злоумышленник сможет перехватить открытый ключ и зашифрованные сообщения, и подписи. Но при условии, что злоумышленник перехватил ключ и может отправлять сообщения по каналу связи. Злоумышленник может отправлять ложные сообщения.
== Применение RSA ==
Строка 380 ⟶ 383 :
Также она используется в открытой системе шифрования [[PGP]] и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с [[симметричный алгоритм шифрования|симметричными алгоритмами]].
Из-за низкой скорости шифрования
== Примечания ==
| |||