1632
правки
Изменения
RSA
,rollbackEdits.php mass rollback
Криптографические системы с открытым ключом используют так называемые [[Односторонние_функции_и_псевдослучайные_генераторы|односторонние функции]].
{{Определение
|definition='''Односторонняя функция''' (англ. ''one-way function'') — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент задача нахождения аргумента по заданному значению функцииотносится к классу [[Понятие_NP-трудной_и_NP-полной_задачи|NP-полных задач]].}}
Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.
{{Определение
|definition='''Случайное простое число''' (англ. ''random prime numbers'') — в криптографии, простое число, содержащее в двоичной записи заданное количество битов <tex>k</tex>.}}
===Передача ключей===
Покажем, что:
: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod pmod{p}</tex>.
Возможны два случая:
* <tex>m \not\equiv 0 \mod pmod{p}</tex>.
Поскольку числа <tex>e</tex> и <tex>d</tex> являются взаимно обратными относительно умножения по модулю <tex>\varphi(n)=(p-1)(q-1)</tex>, то есть
: <tex>\begin{align}
m^{ed} & \equiv m^{1 + k\left( {p - 1} \right)\left( {q - 1} \right)} & \equiv & \mod pmod{p } \\ & \equiv m\left( {m^{p - 1} } \right)^{k\left( {q - 1} \right)} & \equiv & \mod pmod{p } \\ & \equiv m\left( 1 \right)^{k\left( {q - 1} \right)} & \pmod{p} \equiv m & \mod pmod{p}
\end{align}</tex>
* Рассмотрим второй случай:
: <tex>m \equiv 0 \mod pmod{p}</tex>, то есть <tex>m</tex> кратно <tex>p</tex>. Значит, <tex>m^{ed}</tex> кратно <tex>p</tex>,тогдатаким образом:: <tex>m^{ed} \equiv 0 \pmod{p} \equiv m \mod pmod{p}</tex>
Таким образом, при всех <tex>m</tex> выполняется равенство
::: <tex>m^{ed} \equiv m \mod pmod{p}</tex>
Аналогично можно показать, что:
: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod pmod{q}</tex>.
Тогда, из [[китайская теорема об остатках|китайской теоремы об остатках]]
: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \mod pmod{n}</tex>
}}
: <tex> \exp (( c + o(1))k^{\frac{1}{3}} \log^{\frac{2}{3}}k)</tex> для некоторого <tex>c < 2</tex>.
В <tex>2010 </tex> году группе учёных из Швейцарии, Японии, Франции, Нидерландов, Германии и США удалось успешно вычислить данные, зашифрованные при помощи криптографического ключа стандарта <tex>\mathtt{RSA}</tex> длиной <tex>768 </tex> бит. Нахождение простых сомножителей осуществлялось общим методом решета числового поля. По словам исследователей, после их работы в качестве надежной системы шифрования можно рассматривать только <tex>\mathtt{RSA}</tex>-ключи длиной <tex>1024 </tex> бита и более. Причём от шифрования ключом длиной в <tex>1024 </tex> бит стоит отказаться в ближайшие три-четыре года. С <tex>31 </tex> декабря <tex>2013 </tex> года браузеры Mozilla перестали поддерживать сертификаты удостоверяющих центров с ключами <tex>\mathtt{RSA}</tex> меньше <tex>2048 </tex> бит.
==Применение==
Система <tex>\mathtt{RSA}</tex> используется для защиты программного обеспечения и в схемах цифровой подписи. Также она используется в открытой системе шифрования PGP <ref>[https://ru.wikipedia.org/wiki/PGP Wikipedia — PGP]</ref> и иных системах шифрования (к примеру, DarkCryptTC <ref>[http://www.tckb.ru/wiki/DarkCryptTC Русскоязычная база знаний о Total Commander — DarkCryptTC]</ref> и формат xdc<ref>[http://totalcmd.net/plugring/darkcrypttc.html DarkCrypt IV description]</ref>) в сочетании с симметричными алгоритмами.
Наиболее используемым в настоящее время является смешанный алгоритм шифрования, в котором сначала шифруется сеансовый ключ, а потом уже с его помощью участники шифруют свои сообщения симметричными системами. После завершения сеанса сеансовый ключ, как правило, уничтожается.
==Минусы==
Алгоритм <tex>\mathtt{RSA}</tex> намного медленнее, чем AES <ref>[https://ru.wikipedia.org/wiki/Advanced_Encryption_Standard Wikipedia — AES]</ref> и другие алгоритмы, использующие симметричные блочные шифры.
При неправильной или неоптимальной реализации или использовании алгоритма возможны специальные криптографические атаки, такие как атаки на схемы с малой секретной экспонентой или на схемы с общим выбранным значением модуля.
Из-за низкой скорости шифрования (около <tex>30 </tex> кбит/с при <tex>512 </tex> битном ключе на процессоре <tex>2 </tex> ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным сеансовым ключом (например, AES, IDEA<ref>[https://ru.wikipedia.org/wiki/IDEA Википедиа — IDEA]</ref>, Serpent<ref>[https://ru.wikipedia.org/wiki/Serpent Википедиа — Serpent]</ref>, Twofish<ref>[https://ru.wikipedia.org/wiki/Twofish Википедиа — Twofish]</ref>), а с помощью <tex>\mathtt{RSA}</tex> шифруют лишь этот ключ, таким образом реализуется гибридная криптосистема.
==См. также==
* [[Классы чисел]]
==Примечания==
<references />
== Источники информации ==
* [https://en.wikipedia.org/wiki/<tex>\mathtt{RSA}</tex>_RSA_(cryptosystem) <tex>\mathtt{RSA}</tex> (cryptosystem)]* [https://ru.wikipedia.org/wiki/<tex>\mathtt{RSA}</tex> <tex>\mathtt{RSA}</tex>]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Криптографические алгоритмы]]
