Как работает шифрование с открытым ключом: RSA простыми словами

Представьте почтовый ящик с прорезью: бросить письмо может любой, а достать — только владелец ключа.

Открытый ключ умеет «запирать», но не умеет «отпирать». Это и есть вся идея асимметричной криптографии.

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

Замок, который умеет только закрываться

В обычном замке один ключ и закрывает, и открывает. В RSA ключей два, и они разные. Один — открытый — вы публикуете на весь мир: пусть кто угодно зашифрует им письмо для вас. Второй — закрытый — храните только вы, и лишь он расшифровывает. Подслушивающий видит открытый ключ и зашифрованный текст, но без закрытого ключа это бесполезный мусор.

Магия в том, что вычислить закрытый ключ из открытого практически невозможно — на это ушли бы миллионы лет даже у суперкомпьютера. Почему? Об этом ниже.

Немного арифметики остатков

Сердце RSA — модулярная арифметика, та самая «арифметика часов». Берём два больших простых числа, $p$ и $q$, и перемножаем их в модуль $n = p \cdot q$. Это $n$ становится частью открытого ключа.

Шифрование сообщения $m$ — это возведение в степень по модулю:

$$c = m^e \bmod n$$

А расшифровка — возведение в другую степень:

$$m = c^d \bmod n$$

Числа $e$ и $d$ подобраны так, что последовательное применение возвращает исходное сообщение. Открытый ключ — это пара $(e, n)$, закрытый — пара $(d, n)$. Показатель $d$ вычисляется из $p$ и $q$, и без знания этих множителей его не найти.

Крошечный пример на пальцах

Возьмём игрушечные числа: $p = 3$, $q = 11$, тогда $n = 33$. Пусть $e = 7$, а подобранное $d = 3$. Зашифруем число $m = 4$:

$$c = 4^7 \bmod 33 = 16384 \bmod 33 = 16$$

Теперь расшифруем обратно:

$$m = 16^3 \bmod 33 = 4096 \bmod 33 = 4$$

Вернулась четвёрка! В настоящем RSA числа не двузначные, а на 600+ цифр, но принцип ровно тот же.

Почему это так трудно взломать

Чтобы вычислить $d$, злоумышленнику нужно знать $p$ и $q$. Но ему дано только их произведение $n$. А разложить огромное число на простые множители — задача, для которой не придумано быстрого алгоритма. Перемножить два тысячезначных простых легко, а вот «расцепить» результат обратно — вычислительный кошмар.

Эта асимметрия «легко в одну сторону, невозможно в обратную» называется односторонней функцией — фундамент почти всей современной криптографии.

Где вы пользуетесь RSA каждый день

Замочек в адресной строке браузера, подпись обновлений на телефоне, защищённая почта — везде в основе лежат идеи RSA или его родственников. Когда вы заходите на сайт банка, ваш браузер и сервер обмениваются ключами именно так: на глазах у всего интернета, но в полной безопасности.

Любопытно, что квантовые компьютеры теоретически умеют быстро раскладывать числа на множители (алгоритм Шора), поэтому учёные уже готовят постквантовую криптографию на других математических задачах. Но пока RSA исправно стережёт ваши секреты — благодаря простому факту, что умножать легче, чем разлагать.