Алгоритм создания пары ключей

Случайно выбрать большие простые числа $p$ и $q$ , для которых $\log_2p\simeq \log_2q>512$ бит.
Вычислить произведение $n=p\cdot q$
Вычислить функцию Эйлера $\varphi(n)=(p-1)(q-1)$
Выбирать $e\in[2,\varphi(n)-1]$ взаимно простое с $\varphi(n)$ .
Вычислить $d=e^{-1}~\bmod~\varphi(n)$
Пара $\{e,n\}$ публикуется в качестве открытого ключа RSA.
Пара $\{d,n\}$ играет роль закрытого ключа RSA.

Шифрование сообщения

Шифрование

Сообщение представляют целым числом $m\in[1,n-1]$ .
Шифротекст вычисляется как $c=E(m)=m^e~\bmod~n$

Шифротекст - тоже целое число из диапазона $[1,n-1]$ .

Расшифровывание

Владелец секретного ключа вычисляет: $m=c^d~\bmod~n$

Подпись сообщения

Подпись

Взять открытый текст $m\in[1,p-1]$ .
Создать цифровую подпись $s$ с помощью секретного ключа $\{d,n\}$ :

$s=m^d~\bmod~n$ .

Передать пару $\{m,s\}$ , состоящую из сообщения и подписи.

Проверка подписи

Вычислить прообраз сообщения из подписи с помощью открытого ключа: $m'=s^e~\bmod~n$
Проверить подлинность подписи и неизменность сообщения, сравнив $m$ и $m'$ .

Криптографическая стойкость

Алгоритм RSA не является семантически безопасным.

Семантически безопасной называется криптосистема, для которой вычислительно невозможно извлечь любую информацию из шифротекстов, кроме длины шифротекста.

Габидулин стр 95

Сказать "Спасибо"

RSA