Изменения

Перейти к: навигация, поиск

RSA

19 374 байта добавлено, 19:34, 4 сентября 2022
м
rollbackEdits.php mass rollback
{{Определение
|definition='''RSA''' (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.}}
Криптосистема <tex>\mathtt{RSA}</tex> стала первой системой, пригодной и для шифрования, и для цифровой подписи.
Криптосистема ==Реализация==Алгоритм <tex>\mathtt{RSA стала первой системой}</tex> включает в себя четыре этапа: генерация ключей, пригодной передача ключей, шифрование и расшифрование. Криптографические системы с открытым ключом используют так называемые [[Односторонние_функции_и_псевдослучайные_генераторы|односторонние функции]].{{Определение |definition='''Односторонняя функция''' (англ. ''one-way function'') — математическая функция, которая легко вычисляется для любого входного значения, но задача нахождения аргумента по заданному значению функции относится к классу [[Понятие_NP-трудной_и_NP-полной_задачи|NP-полных задач]].}}Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени. В основу криптографической системы с открытым ключом <tex>\mathtt{RSA}</tex> положена сложность [[Разложение_на_множители_(факторизация)|задачи факторизации]] произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять [[Функция_Эйлера|функцию Эйлера]] от данного большого числа, для чего необходимо знать разложение числа на простые множители.В криптографической системе с открытым ключом каждый участник располагает как '''открытым ключом''' (англ. ''public key''), так и '''закрытым ключом''' (англ. ''private key''). В криптографической системе <tex>\mathtt{RSA}</tex> каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме <tex>\mathtt{RSA}</tex> образуют «согласованную пару» в том смысле, что они являются взаимно обратными. То есть для любых допустимых пар открытого и закрытого ключей <tex>(p,s)</tex> существуют соответствующие функции шифрования <tex>E_p(x)</tex> и расшифрования <tex>D_s(x)</tex> такие, что для любого сообщения <tex>m \in M</tex>, где <tex>M</tex> — множество допустимых сообщений, <tex>m=D_s(E_p(m))=E_p(D_s(m)).</tex> ===Создание открытого и секретного ключей===<tex>\mathtt{RSA}</tex>-ключи генерируются следующим образом: # Выбираются два различных [[простые_числа|случайных простых числа]] <math>p</math> и <math>q</math> заданного размера (например, <tex>1024</tex> бита каждое).# Вычисляется их произведение <tex>n=p\cdot q</tex>, которое называется ''модулем''.# Вычисляется значение [[Функция_Эйлера|функции Эйлера]] от числа <tex>n</tex>:#: <tex>\varphi(n) = (p-1)\cdot (q-1).</tex># Выбирается целое число <tex>e</tex> (<tex>1 < e < \varphi(n)</tex>), [[взаимно простые числа|взаимно простое]] со значением функции <tex>\varphi(n)</tex>. Обычно в качестве <tex>e</tex> берут простые числа, содержащие небольшое количество единичных бит в двоичной записи.#* Число <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>#: '''Примечание'''#: Сравнеие двух целых чисел по модулю натурального числа <tex>m</tex> — математическая операция, позволяющая ответить на вопрос о том, дают ли два выбранных целых числа при делении на <tex>m</tex> один и тот же остаток. Любое целое число при делении на <tex>m</tex> дает один из <tex>m</tex> m возможных остатков: число от <tex>0</tex> до <tex>m-1</tex>.#* Число <tex>d</tex> называется секретной экспонентой. Обычно, оно вычисляется при помощи [[Наибольший_общий_делитель|расширенного алгоритма Евклида]].# Пара <tex>\left\{ e, n \right\}</tex> публикуется в качестве открытого ключа <tex>\mathtt{RSA}</tex> (англ. ''<tex>\mathtt{RSA}</tex> public key'').# Пара <tex>\left\{ d, n \right\}</tex> играет роль закрытого ключа <tex>\mathtt{RSA}</tex> (англ. ''<tex>\mathtt{RSA}</tex> private key'') и держится в секрете. {{Определение |definition='''Случайное простое число''' (англ. ''random prime numbers'') — в криптографии, простое число, содержащее в двоичной записи заданное количество битов.}} ===Передача ключей===Предположим, что Боб хочет отправить Алисе информацию . Если они решат использовать <tex>\mathtt{RSA}</tex>, Боб должен знать открытый ключ Алисы для того чтобы зашифровать сообщение, а Алиса должна использовать свой закрытый ключ для расшифрования сообщения. Чтобы позволить Бобу отправлять свои зашифрованные сообщения, Алиса передает свой открытый ключ Бобу через надежный, но не обязательно секретный маршрут. Закрытый ключ Алисы никогда никому не передается. ===Шифрование===Предположим, Боб хочет послать Алисе сообщение <tex>m</tex>.Сообщениями являются целые числа в интервале от <tex>0</tex> до <tex>n - 1</tex>, то есть <tex>m \in \mathbb{Z}_{n}</tex>. Алгоритм: * Взять открытый ключ <tex>(e,n)</tex> Алисы* Взять открытый текст <tex>m</tex>* Зашифровать сообщение с использованием открытого ключа Алисы:*: <tex>c = E(m) = m^e \mod n ~~~~ (1)</tex> [[Файл:Gg1.png|800px|center]] ===Расшифрование===Алгоритм: * Принять зашифрованное сообщение <tex>c</tex>* Взять свой закрытый ключ <tex>(d,n)</tex>* Применить закрытый ключ для расшифрования сообщения:*: <tex>m = D(c) = c^d \mod n ~~~~ (2)</tex> ===Корректность схемы <tex>\mathtt{RSA}</tex>==={{Теорема|statement=Уравнения <tex>(1)</tex> и <tex>(2)</tex>, на которых основана схема <tex>\mathtt{RSA}</tex>, определяют взаимно обратные преобразования множества <tex>\mathbb{Z}_n</tex>|proof=Действительно, для <tex>\forall m \in \mathbb{Z}_{n}</tex>: <tex>D\left( {E\left( m \right)} \right) = E\left( {D\left( m \right)} \right) = m^{ed} \mod n</tex> Покажем, что:: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \pmod{p}</tex>. Возможны два случая:* <tex>m \not\equiv 0 \pmod{p}</tex>. Поскольку числа <tex>e</tex> и <tex>d</tex> являются взаимно обратными относительно умножения по модулю <tex>\varphi(n)=(p-1)(q-1)</tex>, то есть : <tex>ed=1+k(p-1)(q-1)</tex> для некоторого целого <tex>k</tex>, тогда: : <tex>\begin{align}m^{ed} & \equiv m^{1 + k\left( {p - 1} \right)\left( {q - 1} \right)} \pmod{p} \\ & \equiv m\left( {m^{p - 1} } \right)^{k\left( {q - 1} \right)} \pmod{p} \\ & \equiv m\left( 1 \right)^{k\left( {q - 1} \right)} \pmod{p} \equiv m \pmod{p}\end{align}</tex> где второе тождество следует из [[Теорема_Ферма|теоремы Ферма]]. * Рассмотрим второй случай:: <tex>m \equiv 0 \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 \pmod{p}</tex> Таким образом, при всех <tex>m</tex> выполняется равенство ::: <tex>m^{ed} \equiv m \pmod{p}</tex> Аналогично можно показать, что:: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \pmod{q}</tex>. Тогда, из [[китайская теорема об остатках|китайской теоремы об остатках]]: <tex>\forall m \in \mathbb{Z}_{n}: m^{ed} \equiv m \pmod{n}</tex>}} ===Криптографическая стойкость===Стойкость алгоритма основывается на сложности вычисления обратной функции к функции шифрования: <tex>c = E(m) = m ^ e \mod n</tex>. Для вычисления <tex>m</tex> по известным <tex>c, e, n</tex> нужно найти такой <tex>d</tex>, чтобы: <tex>e \cdot d \equiv 1 \pmod{\varphi(n)},</tex>то есть: <tex>d \equiv e^{-1} \pmod{\varphi(n)}.</tex> Вычисление обратного элемента по модулю не является сложной задачей, однако злоумышленнику неизвестно значение <tex>\varphi(n)</tex>. Для вычисления [[функция Эйлера|функции Эйлера]] от известного числа <tex>n</tex> необходимо знать разложение этого числа на простые множители. Нахождение таких множителей и является сложной задачей, а знание этих множителей — '''«потайной дверцей»''' (англ. ''backdoor''), которая используется для вычисления <tex>d</tex> владельцем ключа. Существует множество алгоритмов для нахождения простых сомножителей, факторизации, самый быстрый из которых на сегодняшний день — общий метод решета числового поля, скорость которого для k-битного целого числа составляет: <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>) в сочетании с симметричными алгоритмами. Наиболее используемым в настоящее время является смешанный алгоритм шифрования, в котором сначала шифруется сеансовый ключ, а потом уже с его помощью участники шифруют свои сообщения симметричными системами. После завершения сеанса сеансовый ключ, как правило, уничтожается. Алгоритм шифрования сеансового ключа выглядит следующим образом: [[Файл:Oo1.jpg|800px|center]]==Плюсы=Шифрование===Алгоритм:* Взять ''открытый ключ'' <tex>(e,n)</tex> Алисы* Создать случайный ''сеансовый ключ'' <tex>m</tex>* Зашифровать сеансовый ключ с использованием открытого ключа Алисы:*: <tex>c = E(m) = m^e \mod n</tex>* Расшифровать сообщение <tex>C</tex> с помощью сеансового ключа симметричным алгоритмом:*:<tex>M_A = D_m(C)</tex> ===Расшифрование===Алгоритм:* Принять зашифрованный сеансовый ключ Боба <tex>c</tex>* Взять свой ''закрытый ключ'' <tex>(d,n)</tex>* Применить закрытый ключ для расшифровывания сеансового ключа:*: <tex>m = D(c) = c^d \mod n</tex>* Зашифровать сообщение <tex>M_A</tex> с помощью сеансового ключа симметричным алгоритмом:*:<tex>C = E_m(M_A)</tex> 
==Минусы==
Алгоритм <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> ГГц), сообщения обычно шифруют с помощью более производительных симметричных алгоритмов со случайным сеансовым ключом (например, 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/RSA_(cryptosystem) <tex>\mathtt{RSA}</tex> (cryptosystem)]
* [https://ru.wikipedia.org/wiki/RSA <tex>\mathtt{RSA}</tex>]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Криптографические алгоритмы]]
Maintenance script
1632
правки
Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Служебная:Сравнение_версий/65178...85521»

Навигация