Как работает RSA.
Вся асимметричная криптография держится на принципе:
Сразу с ума не сходи, сначала душная теория, а потом весёлая практика — на письках. Как ты любишь!
Берем простые числа:
Подставляем в формулу:
N=p*q=779ф(N)=(p-1)*(q-1)=720e=691d=571
N = p * q = 779 = это модуль, он используется как часть открытого и закрытого ключей.
φ(N) = (p - 1)(q - 1) = 18 * 40 = 720 = функция Эйлера от N, она показывает количество чисел, взаимно простых с N.
e = 691 = открытая экспонента, часть публичного ключа. Она должна быть взаимно проста с φ(N).
d = 571 = закрытая экспонента, часть приватного ключа. Это мультипликативная обратная величина к e по модулю φ(N) (то есть: (d * e) % φ(N) = 1).
Получается:
Открытый ключ: (e, N) = (691, 779)
Закрытый ключ: (d, N) = (571, 779)
Пример на письках
Антон спрашивает у Маши — а сколько сантиметров хуй у Ивана?
Маша знает что у Ивана хуй — 21 сантиметр. Но Маше нужно это сообщить Антону, чтобы Иван не узнал.
Для этого Маше нужно знать открытый ключ Антона.
Берем открытый ключ из предыдущих вычислений (691, 779).
И шифруем хуй Ивана:
21^691 mod 779 = 717
Возводим длину хуя Ивана в 691 степень по модулю 779 и получаем число 717.
Теперь Маша передает без палева число 717 Антону.
Антон же с помощью закрытого ключа расшифровывает длину хуя Ивана.
717^571 mod 779 = 21
Аналогично возводим в степень по модулю. С помощью математики Антон узнаёт сколько сантиметров хуй у Ивана.
Даже линейка не понадобилась!
Подытожим:
Вот тебе пример на Bash:
#!/bin/bash
# Исходные данные
m=21
e=691
d=571
n=779
# Шифруем: c = m^e mod n
c=$(echo "$m ^ $e % $n" | bc)
echo "Зашифрованное сообщение: $c"
# Расшифровываем: m = c^d mod n
decrypted=$(echo "$c ^ $d % $n" | bc)
echo "Расшифрованное сообщение: $decrypted"
В результате получим: 717 и 21. Что и требовалось доказать!
Чуть позже покажу как «ломают» такие ключи и как сгенерить RSA ключ с бэкдором.
Изучай!
Комментарии