Редактирование: RSA

{{другие значения}}
{{Универсальная карточка}}
'''RSA''' (аббревиатура от фамилий Rivest, Shamir и Adleman) — [[Криптосистема с открытым ключом|криптографический алгоритм с открытым ключом]], основывающийся на [[Вычислительная сложность|вычислительной сложности]] [[Факторизация целых чисел|задачи факторизации]] больших [[Полупростое число|полупростых чисел]].

Криптосистема RSA стала первой системой, пригодной и для [[шифрование|шифрования]], и для [[цифровая подпись|цифровой подписи]]. Алгоритм используется в большом числе криптографических приложений, включая [[PGP]], [[S/MIME]], [[TLS]]/[[SSL]], [[IPSEC]]/[[IKE]] и других{{sfn|Bakhtiari, Maarof|2012|p=175}}.

== История ==
Алгоритм шифрования с открытым и закрытым ключом приписывается [[Диффи, Уитфилд|Уитфилду Диффи]] и [[Хеллман, Мартин|Мартину Хеллману]], которые опубликовали эту концепцию в 1976 году. Они также ввели цифровые подписи и попытались применить теорию чисел. В их формулировке использовался секретный ключ с общим доступом, созданный путем экспоненциализации некоторого числа, простого по модулю. Однако они оставили открытой проблему реализации односторонней функции, возможно, потому что сложность факторизации в то время не была хорошо изучена.

Рон Ривест, Ади Шамир и Леонард Адлеман из Массачусетского технологического института в течение года предприняли несколько попыток создать одностороннюю функцию, которую было бы трудно инвертировать. Ривест и Шамир, будучи компьютерными учеными, предложили множество потенциальных функций, а Адлеман, будучи математиком, отвечал за поиск их слабых мест. Они опробовали множество подходов, включая "ранцевый" и "перестановочные полиномы". Какое-то время они думали, что то, чего они хотели достичь, невозможно из-за противоречивых требований. В апреле 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}}. Читателям также было предложено дешифровать английскую фразу, зашифрованную описанным алгоритмом:
{{начало цитаты}}
{|
|
: 9686
: 1477
: 8829
: 7431
: 0816
: 3569
: 8962
: 1829
|
: 9613
: 1409
: 0575
: 9874
: 2982
: 3147
: 8013
: 9451
|
: 7546
: 2225
: 9991
: 6951
: 2514
: 6622
: 3919
: 5781
|
: 2206
: 4355
: 1245
: 2093
: 5708
: 8839
: 9055
: 5154
|}
{{конец цитаты}}

В качестве открытых параметров системы были использованы числа 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}}.

Заявка на патент была подана 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=1989-08|lang=en|accessdate=2012-03-18|archiveurl=https://www.webcitation.org/68d2lqdp3?url=http://www.ietf.org/rfc/rfc1115.txt|archivedate=2012-06-23|deadurl=yes}}</ref>, а в 1990 году использовать алгоритм начинает министерство обороны США<ref>{{cite web|url=http://www.fundinguniverse.com/company-histories/RSA-Security-Inc-company-History.html|title=RSA Security Inc. Company history|publisher=FundingUniverse|lang=en|accessdate=2012-03-18|archiveurl=https://www.webcitation.org/68d2mGrWl?url=http://www.fundinguniverse.com/company-histories/rsa-security-inc-history/|archivedate=2012-06-23|deadurl=yes}}</ref>.

В ноябре 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 год]]а была обнародована информация о приоритете Клиффорда Кокса<ref>C. C. Cocks [http://www.cesg.gov.uk/publications/media/notense.pdf A note on «non-secret encryption»] {{webarchive|url=https://web.archive.org/web/20090804152223/http://www.cesg.gov.uk/publications/media/notense.pdf |date=2009-08-04 }}{{ref-en}} 20 ноября 1973</ref>.

== Описание алгоритма ==

=== Введение ===
Криптографические системы с открытым ключом используют так называемые [[Односторонняя функция|односторонние функции]], которые обладают следующим свойством:

* если известно <math>x</math>, то <math>f(x)</math> вычислить относительно просто;
* если известно <math>y=f(x)</math>, то для вычисления <math>x</math> нет простого (эффективного) пути.

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

В основу криптографической системы с открытым ключом RSA положена сложность [[Факторизация целых чисел|задачи факторизации]] произведения двух больших простых чисел. Для шифрования используется операция [[возведение в степень по модулю|возведения в степень по модулю]] большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять [[Функция Эйлера|функцию Эйлера]] от данного большого числа, для чего необходимо знать разложение числа на простые множители.

В криптографической системе с открытым ключом каждый участник располагает как открытым ключом ({{lang-en|public key}}), так и закрытым ключом ({{lang-en|private key}}). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются ''взаимно обратными'', то есть:

: <math>\forall</math> допустимых пар открытого и закрытого ключей <math>(p,s)</math>
:: <math>\exist</math> соответствующие функции шифрования <math>E_p(x)</math> и расшифрования <math>D_s(x)</math> такие, что
::: <math>\forall</math> сообщения <math>m \in M</math>, где <math>M</math> — множество допустимых сообщений,
:::: <math>m=D_s(E_p(m))=E_p(D_s(m)).</math>

=== Алгоритм создания открытого и секретного ключей ===
RSA-ключи генерируются следующим образом{{sfn|Menezes, Oorschot, Vanstone|1996|loc=8.2. RSA public-key encryption}}:

: 1) выбираются два различных [[случайное простое число|случайных простых числа]] <math>p</math> и <math>q</math> заданного размера (например, 1024 [[бит]]а каждое);
: 2) вычисляется их произведение <math>n=p\cdot q</math>, которое называется ''модулем'';
: 3) вычисляется значение [[функция Эйлера|функции Эйлера]] от числа <math>n</math>:
:: <math>\varphi(n) = (p-1)\cdot (q-1)</math>;
: 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>e</math> по модулю <math>\varphi(n)</math>, то есть число, удовлетворяющее [[Сравнение по модулю|сравнению]]:
:: <math>d\cdot e \equiv 1 \pmod{\varphi(n)}</math>
:: (число <math>d</math> называется ''секретной экспонентой''; обычно оно вычисляется при помощи [[Расширенный алгоритм Евклида|расширенного алгоритма Евклида]]);
: 6) пара <math>(e, n)</math> публикуется в качестве ''открытого ключа RSA'' ({{lang-en|RSA public key}});
: 7) пара <math>(d, n)</math> играет роль ''закрытого ключа RSA'' ({{lang-en|RSA private key}}) и держится в секрете.

=== Шифрование и расшифрование ===
Предположим, Боб хочет послать Алисе сообщение <math>m</math>.

Сообщениями являются [[целое число|целые числа]] в интервале от <math>0</math> до <math>n - 1</math>. {{sfn|Menezes, Oorschot, Vanstone|1996|loc=8.2. RSA public-key encryption}}

[[Файл:Public key encryption, transmission and decryption light-ru-rendered.svg|center|650px]]

{{col-begin}}
{{col-2}}
'''Алгоритм шифрования'''{{sfn|Menezes, Oorschot, Vanstone|1996|loc=8.2. RSA public-key encryption}}:
* Взять ''открытый ключ'' <math>(e,n)</math> Алисы
* Взять ''открытый текст'' <math>m</math>
* Зашифровать сообщение с использованием открытого ключа Алисы:
*: <math>c = E(m) = m^e \mod n ~~~~ (1)</math>
{{col-2}}
'''Алгоритм расшифрования''':
* Принять зашифрованное сообщение <math>c</math>
* Взять свой ''закрытый ключ'' <math>(d,n)</math>
* Применить закрытый ключ для расшифрования сообщения:
*: <math>m = D(c) = c^d \mod n ~~~~(2)</math>
{{col-end}}
Данная схема на практике не используется по причине того, что она не является ''практически надёжной'' (semantically secured). Действительно, односторонняя функция E(m) является ''детерминированной'' — при одних и тех же значениях входных параметров (ключа и сообщения) выдаёт одинаковый результат. Это значит, что не выполняется необходимое условие практической (семантической) надёжности шифра.

=== Алгоритм шифрования сеансового ключа ===
Более надёжным является смешанный алгоритм шифрования, в котором сначала шифруется сеансовый ключ, а потом уже с его помощью участники шифруют свои сообщения симметричными системами. После завершения сеанса сеансовый ключ, как правило, уничтожается.

Алгоритм шифрования сеансового ключа выглядит следующим образом<ref name="Shnaer">Брюс Шнайер. Прикладная криптография 2-е издание протоколы, алгоритмы и исходные тексты на языке C++</ref>:

[[Файл:Public key encryption for rsa only key.jpg|center|950px]]

{{col-begin}}
{{col-2}}
'''Алгоритм''':
* Взять ''открытый ключ'' <math>(e,n)</math> Алисы
* Создать случайный ''сеансовый ключ'' <math>m</math>
* Зашифровать сеансовый ключ с использованием открытого ключа Алисы:
*: <math>c = E(m) = m^e \mod n</math>
* Зашифровать сообщение <math>M_A</math> с помощью сеансового ключа симметричным алгоритмом:
*: <math>C = E_m(M_A)</math>

{{col-2}}
'''Алгоритм''':
* Принять зашифрованный сеансовый ключ Боба <math>c</math>
* Взять свой ''закрытый ключ'' <math>(d,n)</math>
* Применить закрытый ключ для расшифровывания сеансового ключа:
*: <math>m = D(c) = c^d \mod n</math>
* Расшифровать сообщение <math>C</math> с помощью сеансового ключа симметричным алгоритмом:
*: <math>M_A = D_m(C)</math>

{{col-end}}

В случае, когда сеансовый ключ больше, чем модуль <math>n</math>, сеансовый ключ разбивают на блоки нужной длины (в случае необходимости дополняют нулями) и шифруют каждый блок.

=== Корректность схемы RSA ===
: Уравнения <math>(1)</math> и <math>(2)</math>, на которых основана схема RSA, определяют [[#Описание алгоритма|взаимно обратные преобразования]] множества <math>\mathbb{Z}_n</math>

{{hider|hidden=1|title=Доказательство{{sfn|Menezes, Oorschot, Vanstone|1996|loc=8.2. RSA public-key encryption}}{{sfn|Rivest, Shamir, Adleman|1978|pp=7—8}}|content-style=text-align: left|content=

Действительно, для <math>\forall m \isin \mathbb{Z}_{n}</math>
: <math>D\left( {E\left( m \right)} \right) = E\left( {D\left( m \right)} \right) = m^{ed} \mod n</math>

Покажем, что:
: <math>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod p</math>.

Возможны два случая:
* <math>m \not\equiv 0 \mod p</math>.

Поскольку числа <math>e</math> и <math>d</math> являются взаимно обратными относительно умножения по модулю <math>\varphi(n)=(p-1)(q-1)</math>, т.e

: <math>ed=1+k(p-1)(q-1)</math> для некоторого целого <math>k</math>,

тогда:

: <math>\begin{align}
m^{ed} & \equiv m^{1 + k\left( {p - 1} \right)\left( {q - 1} \right)}  & \equiv   & \mod p \\
       & \equiv m\left( {m^{p - 1} } \right)^{k\left( {q - 1} \right)} & \equiv   & \mod p \\
       & \equiv m\left( 1 \right)^{k\left( {q - 1} \right)}            & \equiv m & \mod p
\end{align}</math>

где второе тождество следует из [[Малая теорема Ферма|теоремы Ферма]].

* Рассмотрим второй случай:
: <math>m \equiv 0 \mod p</math>,
тогда
: <math>m^{ed} \equiv 0 \equiv m \mod p</math>

Таким образом, при всех <math>m</math> выполняется равенство

::: <math>m^{ed} \equiv m \mod p</math>

Аналогично можно показать, что:
: <math>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod q</math>.

Тогда, из [[китайская теорема об остатках|китайской теоремы об остатках]]
: <math>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod n</math>
}}

=== Пример ===
{| class="wikitable" style="width: 100%"
!Этап
!Описание операции
!Результат операции
|-
!rowspan="7"| Генерация [[ключ (криптография)|ключей]]
|Выбрать два простых различных числа
|
: <math>p=3557</math>,
: <math>q=2579</math>
|-
|Вычислить произведение
|
: <math> n = p \cdot q = 3557 \cdot 2579 = 9173503</math>
|-
|Вычислить [[функция Эйлера|функцию Эйлера]]
|
: <math>\varphi(n) = (p-1) (q-1) = 9167368</math>
|-
|[[#Скорость работы алгоритма RSA|Выбрать открытую экспоненту]]
|
: e = 3
|-
|[[#Выбор значения секретного показателя|Вычислить секретную экспоненту]]
|
:<math>\begin{align}
 d &= (k \cdot \varphi(n) + 1) / e \\
  &= (2 \cdot 9167368 + 1) / 3 \\
  &= 6111579
\end{align}</math>
|-
|Опубликовать ''открытый ключ''
|
: <math>\{e, n\} = \{3,9173503 \}</math>
|-
|Сохранить ''закрытый ключ''
|
: <math>\{d, n\} = \{6111579, 9173503 \}</math>
|-
!rowspan="2"|[[Шифрование]]
|Выбрать текст для зашифрования
|
: <math>m = 111111</math>
|-
|Вычислить шифротекст
|
: <math>\begin{align}
c &= E(m) \\
 &= m^e \mod n \\
 &= 111111^3   \mod 9173503 \\
 &= 4051753
\end{align}</math>
|-
! Расшифрование
| Вычислить исходное сообщение
|
: <math>\begin{align}
m &= D(c) = \\
  &= c^d \mod n \\
  &= 4051753^{6111579} \mod 9173503 \\
  &= 111111
\end{align}</math>
|}

== Цифровая подпись ==
Система RSA может использоваться не только для шифрования, но и для [[Цифровая подпись|цифровой подписи]].

Предположим, что Алисе (стороне <math>A</math>) нужно отправить Бобу (стороне <math>B</math>) сообщение <math>m</math>, подтверждённое ''[[Электронная цифровая подпись|электронной цифровой подписью]]''.

[[Файл:Public key signature with transmission and check light-ru-render.svg|center|700px]]

{{col-begin}}
{{col-2}}
'''Алгоритм''':
* Взять открытый текст <math>m</math>
* Создать цифровую подпись <math>s</math> с помощью своего секретного ключа <math>\left\{ d, n \right\}</math>:
: <math>s = S_A \left( m \right) = m^d \mod n</math>
* Передать пару <math>\left\{ m, s \right\}</math>, состоящую из сообщения и подписи.
{{col-2}}
'''Алгоритм''':
* Принять пару <math>\left\{ m, s \right\}</math>
* Взять открытый ключ <math>\left\{ e, n \right\}</math> Алисы
* Вычислить прообраз сообщения из подписи:
: <math>m' = P_A \left( s \right) = s^e \mod n</math>
* Проверить подлинность подписи (и неизменность сообщения), сравнив <math>m</math> и <math>m'</math>
{{col-end}}

Поскольку [[цифровая подпись]] обеспечивает как [[аутентификация|аутентификацию]] автора сообщения, так и подтверждение целостности содержимого подписанного сообщения, она служит аналогом подписи, сделанной от руки в конце рукописного документа.

Важное свойство цифровой подписи заключается в том, что её может проверить каждый, кто имеет доступ к открытому ключу её автора. Один из участников обмена сообщениями после проверки подлинности цифровой подписи может передать подписанное сообщение ещё кому-то, кто тоже в состоянии проверить эту подпись. Например, сторона <math>A</math> может переслать стороне <math>B</math> электронный чек. После того как сторона <math>B</math> проверит подпись стороны <math>A</math> на чеке, она может передать его в свой банк, служащие которого также имеют возможность проверить подпись и осуществить соответствующую денежную операцию.

Заметим, что подписанное сообщение <math>m</math> не [[шифрование|зашифровано]]. Оно пересылается в исходном виде и его содержимое не защищено от нарушения конфиденциальности. Путём совместного применения представленных выше схем шифрования и цифровой подписи в системе RSA можно создавать сообщения, которые будут и зашифрованы, и содержать цифровую подпись. Для этого автор сначала должен добавить к сообщению свою цифровую подпись, а затем — зашифровать получившуюся в результате пару (состоящую из самого сообщения и подписи к нему) с помощью открытого ключа, принадлежащего получателю. Получатель расшифровывает полученное сообщение с помощью своего секретного ключа<ref name="Shnaer"></ref>. Если проводить аналогию с пересылкой обычных бумажных документов, то этот процесс похож на то, как если бы автор документа поставил под ним свою печать, а затем положил его в бумажный конверт и запечатал, с тем чтобы конверт был распечатан только тем человеком, кому адресовано сообщение.

== Скорость работы алгоритма RSA ==
Поскольку генерация ключей происходит значительно реже операций, реализующих шифрование, расшифрование, а также создание и проверку цифровой подписи, задача вычисления <math>a=b^c \bmod n</math> представляет основную вычислительную сложность. Эта задача может быть разрешена с помощью [[алгоритм быстрого возведения в степень|алгоритма быстрого возведения в степень]]. С использованием этого алгоритма для вычисления <math>m^e \bmod n</math> требуется <math>O\left( \ln e \right)</math> операций [[модульная арифметика|умножения по модулю]]{{sfn|Rivest, Shamir, Adleman|1978|p=8}}.
{{hider|hidden=1|title=Подробнее|content-style=text-align:left|content=
* представим <math>e</math> в двоичной системе счисления:
:: <math>e=e_k \cdot 2^k+e_{k-1} \cdot 2^{k-1} + \dots + e_1 \cdot 2 + e_0</math>, где
:: <math>e_k=1, e_i \in \left\{ 0,1 \right\}</math>
* положим <math>m_0=m</math> и затем для <math>i = 1, \dots, k</math> вычислим
:: <math>m_i= \left( m_{i-1}^2 \cdot m^{e_{k-i}} \right) \bmod n</math>
* найденное <math>m_k</math> и будет искомым значением <math> m^e \bmod n</math>

Т. к. каждое вычисление на шаге 2 требует не более трёх умножений  по модулю <math>n</math> и этот шаг выполняется <math>k \le \log_2 e</math> раз, то сложность алгоритма может быть оценена величиной <math>O( \ln e)</math>.
}}
Чтобы проанализировать время выполнения операций с открытым и закрытым ключами, предположим, что открытый ключ <math>\left\{ e, n \right\}</math> и закрытый ключ <math>\left\{ d, n \right\}</math> удовлетворяют соотношениям <math> \log_2 e =O(1)</math>, <math>\log_2 d \le \beta</math>. Тогда в процессах их применения выполняется соответственно <math>O \left( 1 \right)</math> и <math>O \left( \beta \right)</math> умножений по модулю.

Таким образом время выполнения операций растёт с увеличением количества ненулевых битов в [[двоичная система счисления|двоичном представлении]] открытой экспоненты ''e''. Чтобы увеличить скорость шифрования, значение ''e'' часто выбирают равным 17, 257 или 65537 — [[Простое число|простым числам]], двоичное представление которых содержит лишь две единицы: 17<sub>10</sub>=10001<sub>2</sub>, 257<sub>10</sub>=100000001<sub>2</sub>, 65537<sub>10</sub>=10000000000000001<sub>2</sub> (простые [[числа Ферма]]).

По эвристическим оценкам длина секретной экспоненты <math>d</math>, нетривиальным образом зависящей от открытой экспоненты <math>e</math> и модуля <math>n</math>, с большой вероятностью близка к длине <math>n</math>. Поэтому расшифрование данных идёт медленнее, чем шифрование, а проверка подписи – быстрее, чем её создание.

Алгоритм RSA намного медленнее, чем [[Advanced Encryption Standard|AES]] и другие алгоритмы, использующие симметричные [[блочный шифр|блочные шифры]].

=== Использование китайской теоремы об остатках для ускорения расшифрования ===
При расшифровании или подписывании сообщения в алгоритме RSA показатель вычисляемой степени будет довольно большим числом (порядка 1000 бит). Поэтому требуется алгоритм, сокращающий количество операций. Так как числа <math> p </math> и <math> q </math> в разложении <math> N = pq </math> известны владельцу закрытого ключа, то можно вычислить:
<center> <math> m_p = C^d \bmod p = C^{d\bmod {p-1}} \bmod p,</math></center>
<center> <math> m_q = C^d \bmod q = C^{d\bmod {q-1}} \bmod q.</math></center>
Поскольку <math> p </math> и <math> q </math> — числа порядка <math> 2^{512}, </math> на эти действия потребуется два возведения числа в 512-битовую степень по модулю 512-битового числа. Это существенно (для 1024 бит тестирование показало в 3 раза) быстрее, чем одно возведение в 1024-битовую степень по модулю 1024-битового числа.
Далее осталось восстановить <math> m </math> по <math> m_p </math> и <math> m_q, </math> что можно сделать с помощью [[китайская теорема об остатках|китайской теоремы об остатках]]<ref name="Smart"></ref>.

== Криптоанализ RSA ==
{{main|Криптоанализ RSA}}

Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования<ref>Ян С. Й. Криптоанализ RSA. — М.—Ижевск: НИЦ «Регулярная и хаотическая динамика», Ижевский институт компьютерных исследований, 2011. — 312 с.</ref>
: <math>c = E(m) = m ^ e \mod n</math>.

Для вычисления <math>m</math> по известным <math>c, e, n</math> нужно найти такой <math>d</math>, чтобы
: <math>e \cdot d \equiv 1 \pmod{\varphi(n)},</math>
то есть найти [[обратный элемент]] к <math>e</math> в [[Мультипликативная группа кольца вычетов|мультипликативной группе вычетов]] по модулю <math>\varphi(n).</math>

Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение <math>\varphi(n)</math>. Для вычисления [[функция Эйлера|функции Эйлера]] от известного числа <math>n</math> необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — ''«потайной дверцей»'' ({{lang-en|[[backdoor]]}}), которая используется для вычисления <math>d</math> владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, так называемой ''[[Факторизация целых чисел|факторизации]]'', самый быстрый из которых на сегодняшний день — [[общий метод решета числового поля]], скорость которого для k-битного целого числа составляет
: <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>{{Cite web |url=https://wiki.mozilla.org/CA:MD5and1024 |title=Dates for Phasing out MD5-based signatures and 1024-bit moduli |access-date=2013-03-02 |archive-date=2012-11-20 |archive-url=https://web.archive.org/web/20121120021037/https://wiki.mozilla.org/CA:MD5and1024 |deadlink=no }}</ref>.

Кроме того, при неправильной или неоптимальной реализации или использовании алгоритма возможны специальные криптографические атаки, такие как атаки на схемы с малой секретной экспонентой или на схемы с общим выбранным значением модуля.

== Атаки на алгоритм RSA ==

=== Атака Винера на RSA ===
{{main|Атака Винера}}
В некоторых приложениях требуется ускорить процесс расшифровывания в алгоритме RSA. Поэтому выбирается небольшая расшифровывающая экспонента. В случае когда расшифровывающая экспонента <math>d < N^{\frac{1}{4}}</math> можно определить <math>d</math> за полиномиальное время с помощью [[Атака Винера|атаки Винера]]<ref name="Smart"> Н. СМАРТ Мир программирования Криптография — изд. Техносфера, Москва 2006</ref>, опирающейся на [[непрерывная дробь|непрерывные дроби]].
{{hider|hidden=1|title=Подробнее|content-style=text-align:left|content=
По вещественному числу <math>\alpha \in \mathbb R</math> определим последовательности: <br><center>
<math>\alpha_0 = \alpha, p_0 = q_0 = 1, p_1 = a_0a_1 + 1, q_1 = a_1,</math><br>
<math>\alpha_i = \lfloor \alpha_i \rfloor, \alpha_{i+1} = \frac{1}{\alpha_i - a_i},</math><br> 
<math>p_i = a_ip_{i-1} + p_{i-1}</math> при <math>i \ge 2,</math><br>
<math>q_i = a_iq_{i-1} + q_{i-1}</math> при <math>i \ge 2.</math><br></center>
Целые числа <math>a_0, a_1, a_2, ...</math> называются [[непрерывная дробь|непрерывной дробью]], представляющей <math> \alpha, </math>&nbsp;а рациональные числа <math> \frac{p_i}{q_i} -</math> подходящими дробями. Каждая из подходящих дробей несократима, а скорость роста их знаменателей сравнима с показательной.
Один из важных результатов теории [[непрерывная дробь|непрерывных дробей]]:<br>
Если несократимая дробь <math> \frac{p}{q} </math> удовлетворяет неравенству:<br><center>
<math>\left|\alpha - \frac{p}{q}\right| \le \frac{1}{2q^2},</math><br></center>
то <math>\frac{p}{q} -</math> одна из подходящих дробей в разложении <math> \alpha</math> в [[непрерывная дробь|непрерывную дробь]].
Пусть у нас есть модуль <math> N = pq,</math> причём <math> q < p < 2q. </math>&nbsp;&nbsp;Допустим нападающему известна шифрующая экспонента E, обладающая свойством <br><center>
<math> Ed = 1 \mod \varphi, </math><br></center>
где <math>\varphi = \varphi (N) = (p - 1)(q - 1). </math>&nbsp;&nbsp;Будем также считать, что <math>E < \varphi,</math> поскольку это выполнено в большинстве приложений. Из предположений следует, что<br><center>
<math> Ed - k\varphi = 1.</math><br></center>
Следовательно,<br><center>
<math>\left|\frac{E}{\varphi} - \frac{k}{d}\right| = \frac{1}{d\varphi}.</math><br>
<math>\left |N - \varphi \right| = \left| p + q - 1\right| < 3N^{\frac{1}{2}}.</math><br></center>
Отсюда видно, что <math> \frac{E}{N} - </math> довольно хорошее приближение для <math> \frac{k}{d}. </math> &nbsp;Действительно,<br><center>
<math>\left |\frac{E}{N} - \frac{k}{d} \right| = \left |\frac{Ed - Nk}{dN} \right| = \left |\frac{Ed - k\varphi - Nk + k\varphi}{dN} \right| = \left |\frac{1 - k(N - \varphi)}{dN} \right| \le \left |\frac{3kN^\frac{1}{2}}{dN} \right| = \frac{3k}{dN^{\frac{1}{2}}}.</math><br> </center> 
Так как <math> E < \varphi,</math> очевидно<math>, k < d.</math> Кроме того, так как предполагалось, что <math> d < \frac{1}{4}N^{\frac{1}{4}}.</math> Значит,}}
<center>
<math> \left |\frac{E}{N} - \frac{k}{d} \right| < \frac{1}{2d^2}.</math><br></center>
Поскольку НОД<math>(k,d) = 1,</math> то <math> \frac{k}{d} -</math> подходящая дробь в разложении дроби <math> \frac{E}{N}</math> в [[непрерывная дробь|непрерывную]]. Таким образом, можно узнать расшифровывающую экспоненту, поочерёдно подставляя знаменатели подходящих дробей в выражение:<br><center>
<math> (M^E)^d = M \mod N</math> <br></center>
для некоторого случайного числа <math>M.</math> Получив равенство, найдём <math>d.</math> Общее число подходящих дробей, которое придётся проверить оценивается как <math>O(ln N).</math>

=== Обобщённая атака Винера ===
[[Атака Винера]], описанная выше, возможна лишь в том случае, когда атакующему известно о неравенстве <br>
<center><math> d \le \frac{1}{3} N^{\frac{1}{4}},</math></center>
где <math>d</math> — секретная экспонента, а <math>N</math> — модуль RSA. [[Боне, Дэн|Боне]] и Дерфи, используя двумерный аналог [[Теорема Копперсмита|Теоремы Копперсмита]], смогли обобщить [[Атака Винера|атаку Винера]]<ref name="Smart" /> на случай, когда<br>
<center><math> d \le N^{0,292}.</math></center>

=== Атака посредника, или атака «человек посередине» ===
[[Атака посредника]] не опасна если злоумышленник может только прослушивать канал связи по которому передаётся открытый ключ. В этом случаи злоумышленник сможет перехватить открытый ключ и зашифрованные сообщения, и подписи. Но при условии, что злоумышленник перехватил ключ и может отправлять сообщения по каналу связи. Злоумышленник может отправлять ложные сообщения.

== Применение RSA ==
Система RSA используется для защиты [[Программное обеспечение|программного обеспечения]] и в схемах [[Электронная цифровая подпись|цифровой подписи]].

Также она используется в открытой системе шифрования [[PGP]] и иных системах шифрования (к примеру, DarkCryptTC и формат xdc) в сочетании с [[симметричный алгоритм шифрования|симметричными алгоритмами]].

Из-за низкой скорости шифрования сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным ''сеансовым ключом'' (например, [[Advanced Encryption Standard|AES]], [[IDEA]], [[Serpent]], [[Twofish]]), а с помощью RSA шифруют лишь этот ключ, таким образом реализуется [[гибридная криптосистема]]. Такой механизм имеет потенциальные уязвимости ввиду необходимости использовать [[криптографически стойкий генератор псевдослучайных чисел]] для формирования случайного сеансового ключа симметричного шифрования.

== Примечания ==
{{примечания|2}}

== Литература ==
* {{source|Q27178858|ref=Diffie, Hellman|ref-year=1976}} <!-- New Directions in Cryptography // IEEE Trans. Inf. Theory -->
* {{source|Q27209317|ref=Gardner|ref-year=1977}} <!-- A New Kind of Cipher that Would Take Millions of Years to Break // Scientific American -->
* {{source|Q27177229|ref=Rivest, Shamir, Adleman|ref-year=1978}} <!-- A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM -->
* {{source|Q21725116|ref=Menezes, Oorschot, Vanstone|ref-year=1996}} <!-- Handbook of Applied Cryptography -->
* {{source|Q27210308|ref=Boneh|ref-year=1999}} <!-- Twenty Years of attacks on the RSA Cryptosystem // Notices Amer. Math. Soc. -->
* {{source|Q27209155|ref=Bakhtiari, Maarof|ref-year=2012}} <!-- Serious Security Weakness in RSA Cryptosystem // IJCSI -->

* {{Книга:Фергюсон Н., Шнайер Б.: Практическая криптография}}
* {{Книга:Прикладная криптография}}

{{^}}
{{Криптосистемы с открытым ключом}}

[[Категория:Криптография с открытым ключом]]
[[Категория:Электронная подпись]]