ИнтВизТеория чисел · модуль 10 из 14
RSA: как шифруются сообщения в интернете
Открытый ключ (e, n) знают все, закрытый ключ d — только получатель. Зашифровать может любой, а расшифровать — только тот, кто знает разложение n на простые множители. Здесь числа маленькие, чтобы были видны все шаги.
| Символ | m (код) | c = mᵉ mod n | cᵈ mod n | Итог |
|---|
Генерирую ключи…
Теория
Генерация ключей RSA:
- Выбираются два различных простых числа $p$ и $q$, вычисляется модуль $n = p\,q$.
- Вычисляется функция Эйлера $\varphi(n) = (p - 1)(q - 1)$ — количество чисел от 1 до $n$, взаимно простых с $n$.
- Выбирается открытая экспонента $e$, взаимно простая с $\varphi(n)$: $\gcd(e, \varphi(n)) = 1$.
- Закрытая экспонента $d$ — обратный к $e$ элемент по модулю $\varphi(n)$:
$$ e\,d \equiv 1 \pmod{\varphi(n)} . $$
Число $d$ находится расширенным алгоритмом Евклида: последовательные деления с остатком для пары $(\varphi(n), e)$ дают коэффициенты Безу $\varphi(n)\,s + e\,t = 1$, откуда $d = t \bmod \varphi(n)$.
Шифрование и расшифровка. Сообщение $m < n$ шифруется открытым ключом $(e, n)$ и расшифровывается закрытым ключом $d$:
$$ c = m^e \bmod n, \qquad m = c^d \bmod n . $$
Корректность следует из теоремы Эйлера: $m^{e d} = m^{1 + k \varphi(n)} \equiv m \pmod n$.
Стойкость. Зная $p$ и $q$, легко найти $\varphi(n)$ и $d$. Поэтому стойкость RSA держится на сложности разложения $n$ на множители: перебор делителей требует около $\sqrt{n}$ проверок, что для 2048-битного $n$ недостижимо.
Где это применяется в IT
RSA защищает HTTPS-соединения, SSH-доступ к серверам и цифровые подписи. Стойкость держится на том, что перемножить два простых числа легко, а разложить произведение на множители очень долго.
- Длина ключа. В реальных ключах $n$ имеет длину 2048 бит, это около 617 десятичных цифр; перебор делителей такого числа не закончится за время существования Вселенной.
- Закрытый ключ. $d$ находят расширенным алгоритмом Евклида как обратный к $e$ элемент по модулю $\varphi(n)$.
- Практика. Берут $e = 65537$, а сообщение перед шифрованием дополняют случайными байтами (OAEP). Посимвольное шифрование годится только для демонстрации.
Код на Python
Загружаю пример…