База асимметричного шифрования весьма проста. Для 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 = messagee % n
decrypted = cryptedd % n
Очевидно, что из за операций по модулю мы можем шифровать сообщения в диапазоне [0, n - 1].
message = 200
crypted = 2005 % 247 = 174
decrypted = 174389 % 247 = 200
Основная сложность в том, что для защиты от подбора ключа нам нужны очень большие простые числа и значения n. Вот тут и возникают алгоритмы вычисления степеней, модулей и прочих операций с 1024-, 2048-, 4096-разрядными числами.
