302
правки
Изменения
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>
===Создание открытого и секретного ключей===
#* Время, необходимое для шифрования с использованием [[Быстрое_возведение_в_степень|быстрого возведения в степень]], пропорционально числу единичных бит в <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> называется секретной экспонентой. Обычно, оно вычисляется при помощи [[Наибольший_общий_делитель|расширенного алгоритма Евклида]].
{{Определение
|definition='''Случайное простое число''' (англ. ''random prime numbers'') — в криптографии, простое число, содержащее в двоичной записи заданное количество битов <tex>k</tex>}}
===Передача ключей===
Предположим, что Боб хочет отправить Алисе информацию . Если они решат использовать RSA, Боб должен знать открытый ключ Алисы для того чтобы зашифровать сообщение, а Алиса должна использовать свой закрытый ключ для расшифрования сообщения. Чтобы позволить Бобу отправлять свои зашифрованные сообщения, Алиса передает свой открытый ключ Бобу через надежный, но не обязательно секретный маршрут. Закрытый ключ Алисы никогда никому не передается.
===Шифрование===
Предположим, Боб хочет послать Алисе сообщение <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 </tex>
[[Файл:Gg1.png|650px|center]]
===Расшифрование===
Алгоритм:
* Принять зашифрованное сообщение <tex>c</tex>
* Взять свой закрытый ключ <tex>(d,n)</tex>
* Применить закрытый ключ для расшифрования сообщения:
*: <tex>m = D(c) = c^d \mod n </tex>
==Применение==
==Плюсы==
==Минусы==
