1632
правки
Изменения
RSA
,rollbackEdits.php mass rollback
Криптографические системы с открытым ключом используют так называемые [[Односторонние_функции_и_псевдослучайные_генераторы|односторонние функции]].
{{Определение
|definition='''Односторонняя функция''' (англ. ''one-way function'') — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент задача нахождения аргумента по заданному значению функцииотносится к классу [[Понятие_NP-трудной_и_NP-полной_задачи|NP-полных задач]].}}
Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.
#* Число <tex>e</tex> называется открытой экспонентой (англ. ''public exponent'')
#* Время, необходимое для шифрования с использованием [[Быстрое_возведение_в_степень|быстрого возведения в степень]], пропорционально числу единичных бит в <tex>e</tex>.
#* Слишком малые значения <tex>e</tex>, например <tex>3</tex>, потенциально могут ослабить безопасность схемы <tex>\mathtt{RSA}</tex>.
# Вычисляется число <tex>d</tex>, [[Мультипликативность_функции,_свертка_Дирихле|мультипликативно]] обратное к числу <tex>e</tex> по модулю <tex>\varphi(n)</tex>, то есть число, удовлетворяющее сравнению:
#: <tex>d\cdot e \equiv 1 \pmod{\varphi(n)}.</tex>
{{Определение
|definition='''Случайное простое число''' (англ. ''random prime numbers'') — в криптографии, простое число, содержащее в двоичной записи заданное количество битов <tex>k</tex>.}}
===Передача ключей===
Предположим, что Боб хочет отправить Алисе информацию . Если они решат использовать <tex>\mathtt{RSA}</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>]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Криптографические алгоритмы]]
