302
правки
Изменения
RSA
,Нет описания правки
{{Определение
|definition='''RSA''' (аббревиатура от фамилий Rivest, Shamir и Adleman) — криптографический алгоритм с открытым ключом, основывающийся на вычислительной сложности задачи факторизации больших целых чисел.}}
Криптосистема RSA стала первой системой, пригодной и для шифрования, и для цифровой подписи.
==Реализация==
Алгоритм RSA включает в себя четыре этапа: генерация ключей, передача ключей, шифрование и расшифрование.
Криптографические системы с открытым ключом используют так называемые [[Односторонние_функции_и_псевдослучайные_генераторы|односторонние функции]].
{{Определение
|definition='''Односторонняя функция''' (англ. ''one-way function'') — математическая функция, которая легко вычисляется для любого входного значения, но трудно найти аргумент по заданному значению функции.}}
Под односторонностью понимается не теоретическая однонаправленность, а практическая невозможность вычислить обратное значение, используя современные вычислительные средства, за обозримый интервал времени.
В основу криптографической системы с открытым ключом RSA положена сложность [[Разложение_на_множители_(факторизация)|задачи факторизации]] произведения двух больших простых чисел. Для шифрования используется операция возведения в степень по модулю большого числа. Для дешифрования (обратной операции) за разумное время необходимо уметь вычислять [[Функция_Эйлера|функцию Эйлера]] от данного большого числа, для чего необходимо знать разложение числа на простые множители.
{{Определение
|definition='''Возведение в степень по модулю''' (англ. ''modular exponentiation'') — это вычисление остатка от деления натурального числа <tex>b</tex> (основание), возведенного в степень <tex>n</tex> (показатель степени), на натуральное число <tex>m</tex> (модуль). Обозначается:
<tex>c\equiv b^{n} \pmod m</tex>}}
В криптографической системе с открытым ключом каждый участник располагает как открытым ключом (англ. ''public key''), так и закрытым ключом (англ. ''private key''). В криптографической системе RSA каждый ключ состоит из пары целых чисел. Каждый участник создаёт свой открытый и закрытый ключ самостоятельно. Закрытый ключ каждый из них держит в секрете, а открытые ключи можно сообщать кому угодно или даже публиковать их. Открытый и закрытый ключи каждого участника обмена сообщениями в криптосистеме RSA образуют «согласованную пару» в том смысле, что они являются ''взаимно обратными''. То есть для любых допустимых пар открытого и закрытого ключей <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>
===Создание открытого и секретного ключей===
RSA-ключи генерируются следующим образом:
# Выбираются два различных [[простые_числа|случайных простых числа]] <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>, например 3, потенциально могут ослабить безопасность схемы RSA.
# Вычисляется число <tex>d</tex>, [[Мультипликативная функция|мультипликативно]] обратное к числу <tex>e</tex> по модулю <tex>\varphi(n)</tex>, то есть число, удовлетворяющее сравнению:
#: <tex>d\cdot e \equiv 1 \pmod{\varphi(n)}.</tex>
#* Число <tex>d</tex> называется секретной экспонентой. Обычно, оно вычисляется при помощи [[Расширенный алгоритм Евклида|расширенного алгоритма Евклида]].
# Пара <tex>\left\{ e, n \right\}</tex> публикуется в качестве открытого ключа RSA (англ. ''RSA public key'').
# Пара <tex>\left\{ d, n \right\}</tex> играет роль закрытого ключа RSA (англ. ''RSA private key'') и держится в секрете.
===Передача ключей===
===Шифрование===
===Расшифрование===
==Применение==
==Плюсы==
==Минусы==
