Есть ли простой для восприятия алгоритм ассимитричного шифрования?

Question

[pogromist]

Хочу понять как работают алгоритмы шифрования с двумя ключами. Искал информацию о rsa но понял что там используется какие-то сложные математические вычисления которые мне не по зубам.
Хотел узнать, может кто сможет привести пример простого ассиметричного шифрования (с использованием двух ключей), что бы это можно было повторить в ручную, без супер-пупер математики.

Comments

[mayton2019]

Смотря для чего. Если тебе хочется просто его использовать - то для этого не нужно знать RSA. Тебе достаточно просто знать его свойства. Например если ты подписал текстовый документ - то любой может проверить что текст - твой. И изменить текст не сломав подпись нельзя. И подделать подпись нельзя.

Ради общего развития, RSA - не единственный. Есть еще метод эллиптических кривых. Используется для подписи транзакций в Bitcoin.

Я находил где-то статьи которые описывают некий упрощённый вариант ЭЦП на коротких числах. На таких что можно вручную на бумажке посчитать делители и функцию эйлера. Но я не уверен что этот опыт переносим на RSA.

[RAX7]

https://www.youtube.com/watch?v=vFjq9pID4-E

Answer 1

[Rsa97]

База асимметричного шифрования весьма проста. Для RSA:
Берём два простых числа p и s, например
p = 19
s = 13
Вычисляем их произведение n и функцию Эйлера f:
n = p * s = 247
f = (p - 1) * (s - 1) = 216
Подбираем коэффициент k и экспоненту e так, чтобы значение d = (k * f + 1)/e было целым
k = 9
e = 5
d = 389, целое
Пара (e, n) даёт нам ключ для шифрования, пара (d, n) - ключ для дешифрования.
crypted = message^e % n
decrypted = crypted^d % n
Очевидно, что из за операций по модулю мы можем шифровать сообщения в диапазоне [0, n - 1].
message = 200
crypted = 200⁵ % 247 = 174
decrypted = 174³⁸⁹ % 247 = 200
Основная сложность в том, что для защиты от подбора ключа нам нужны очень большие простые числа и значения n. Вот тут и возникают алгоритмы вычисления степеней, модулей и прочих операций с 1024-, 2048-, 4096-разрядными числами.

Comments

[Pike Pikovskyy]

Ключи вроде всегда 16-ти разрядные, но размер их ..., 1024, 2048, 4096, ... бит

[Rsa97]

Pike Pikovskyy, Бит - это и есть разряд двоичного числа.

[Pike Pikovskyy]

Rsa97, да, не 16-ти разрядные, конечно, а 16-ричные))

[Rsa97]

Pike Pikovskyy, 16-ричной бывает форма записи числа. Само число одно и то же, как его ни записывай.
35₁₀ = 23₁₆ = 100011₂ = Л҃Е҃ = 卅五 = XXXV