Пример алгоритма шифрования rsa

Содержание:

Шаги алгоритма RSA
Пример: шифрование сообщения с помощью RSA
Схема Рабина

Алгоритм RSA

Допустим, что объект А хочет передать сообщение объекту В в зашифрованном виде. Для этого используем алгоритм RSA. При передаче могут возникнут проблемы из-за характеристики проводных линий связи или плохую полосу пропускания и пропускную способность. Для этого нужно использовать методы обнаружения ошибок. Но для разных сетей разные методы.

Шаги:

объект В придумывает два любых больших простых числа Р и Q;
объект В решает значение модуля N = P × Q;
объект В решает функцию Эйлера:φ(N) = (P-1) × (Q-1);
и выбирает любым образом значение открытого ключа K_в с учетом условия:1 < K_в ≤ φ(N), НОД (K_в, φ(N)) = 1
объект В решает значение секретного ключа κ_в решая алгоритм Евклида когда достигается условие: κ_в ≡ K_в^-1 (mod φ(N)).
объект В передает объекту А пару числе (N, K_в) по незащищенному пути.
Если объект А хочет передать объекту В сообщение М, он должен разбить исходный открытый текст M на блоки, каждый из которых может быть показан в виде: M_i = 0, 1, 2, …, N — 1.
Объект А шифрует данные, показаны в виде последовательности чисел M_i по формуле: C_i = M_i^K_в (mod N), и отправляет криптограмму C₁, C₂, …, C_i … объекту В.
Пользователь В расшифровывает криптограмму C₁, C₂, …, C_i … используя секретный ключ κ_в по формуле: M_i = C_i^K_в (mod N)

При реализации алгоритма на практике, нужно иметь возможность без сильных затрат генерировать большие простые числа, к тому же быстро решать значение ключей.

Пример: шифрование сообщения

Для наглядности вычисления, будем использовать небольшие числа. Но на практике используют очень большие числа ( длиной 200-300 десятичных разрядов).

Действия объекта В:

Берет Р = 3, Q = 11.
Берет модуль N = P × Q = 3 × 11 = 33.
Берет значение функции Эйлера для N = 33: φ(N) = (P-1) × (Q-1) = 2 × 10 = 20.
Берет в качестве открытого ключа K_в произвольное число с учетом условия: 1 < K_в ≤ φ(N), НОД (K_в, φ(N)) = 1, допустим K_в = 7.
Решаем значение секретного ключа κ_в используя алгоритм Евклида: κ_в ≡ = 3.
объект В передает объекту А пару чисел (N = 33, K_в = 7).

Действия объекта A:

Показывает шифруемое сообщение как последовательность целых чисел в диапазоне 0…32. Допустим буква А представляется как число 1, буква В это 2 и С = 3. Припустим что сообщение С А В можно показать как последовательность числе 321, то есть M₁ = 3, M₂ = 1, M₃ = 2.
Шифрует сообщение, М используя ключ K_в = 7 и N = 33 по формуле: C_i = M_i^K_в (mod N) = M_i⁷(mod 3).
Получаем:
- C_i = 3⁷(mod 33) = 2187 (mod 33) = 9
- C_i = 1⁷(mod 33) = 1 (mod 33) = 1
- C_i = 2⁷(mod 33) = 128 (mod 33) = 29
Передает объекту В криптограмму: C₁, C₂, C₃ = 9, 1, 29.

Действия объекта B:

Расшифровывает принятую криптограмму C₁, C₂, C₃ используя секретный ключ ≡ = 3 по формуле:M_i = C_i^K_в (mod N) = C_i³ (mod 3)
- M₁= 9³ (mod 33) = 729 (mod 33) =3.
- M₂ = 1³ (mod 33) = 1 (mod 33) =1.
- M₂ = 29³ (mod 33) = 24389 (mod 33) =2.

Объект получил исходное сообщение, которое послал объект A.

Шифрование с помощью RSA есть одним из методов защиты информации при передачи данных через сеть Интернет. Схема Рабина очень похожа на схему RSA. Криптоалгоритм RSA признан стойким при дине ключа больше 1024 бит. Нужно отметить что алгоритм применяют как для шифрования так и для электронно-цифровой подписи. Нетрудно заметить что в асимметричной криптосистеме RSA количество ключей связано с количеством пользователей линейной зависимостью (N пользователей используют 2 × N ключей), а не квадратичной как это используется в симметричных системах.

Применение алгоритма может решить некоторые угрозы информационной безопасности в сети.

Если сравнивать самые популярных представителей асимметричного и симметричного шифрования, нужно отметить, что по скорости RSA уступает DES, да и реализация криптоалгоритма RSA сложнее. Поэтому RSA обычно используется для передачи небольших сообщений. Шифрование как таковое, частично решает проблемы защиты информации в сетях.