Асимметричный алгоритм криптографии RSA, датой возникновения концепции которого считается 1976 год, сейчас очень активно используется для обмена данными, верификации источника программного обеспечения и в других сферах, где необходимо обмениваться данными или верифицировать отправителя. Кроме того, он является базовой частью HTTPS протокола, использование которого повсеместно достигло почти абсолютных показателей.

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

В отличие от симметричных алгоритмов шифрования, имеющих всего один ключ для шифрования и расшифровки информации, в алгоритме RSA используется 2 ключа – открытый (публичный) и закрытый (приватный).

Публичный ключ шифрования передаётся по открытым каналам связи, а приватный всегда держится в секрете. Но зачем нужно целых два ключа и как они работают?

В асимметричной криптографии и алгоритме RSA, в частности, публичный и приватный ключи являются двумя частями одного целого и неразрывны друг с другом. Для шифрования информации используется открытый ключ, а для её расшифровки – приватный.

Предположим, Алекс хочет передать Диане какое-то сообщение, но лично он это сделать не может, поэтому ему необходимо использовать посредника, например Влада. Однако Алекс передаёт Диане информацию про сюрприз для Влада на его день рождения, так что не может допустить, чтобы Влад это сообщение увидел. И тут ему пригодится протокол RSA:

  • Перед обменом сообщением, Алекс просит у Дианы её открытый ключ.
  • После получения ключа, переданного через Влада, Алекс шифрует своё сообщение ключом Дианы.
  • Далее Алекс, через Влад, передаёт Диане зашифрованное сообщение.
  • Диана расшифровывает сообщение своим закрытым ключом.

Таким образом, Влад видел открытый ключ Дианы и зашифрованное сообщение от Алекса, но без закрытого ключа Дианы это сообщение не расшифровать. То есть, пусть Влад и держал в руках все передаваемые данные, но он не может узнать, что Алекс передал Диане!

Проблема Человека посередине (MITM)

Вы можете задаться вопросом, а почему Влад не может подменить ключ Дианы на свой, расшифровать сообщение, а потом, подглядев его, зашифровать обратно на ключ Дианы? Ещё как может, это называется атака «человек посередине» (Man in the middle (MITM)). Но есть ли решение этой проблемы? Да! Chain of Trust, или «Цепочка доверия».

Перед тем как разбирать, что такое «Цепочка доверия», нужно знать про ещё одну возможность закрытого ключа – подпись информации. Она осуществляется с помощью закрытого ключа и проверяется открытым.

То есть, если Алекс и Диана заранее обменялись своими открытыми ключами, они могут писать друг другу сообщения и прикреплять к ним некий набор данных. Если взять этот набор данных, открытый ключ и само сообщение, можно проверить, действительно ли сообщение было отправлено собеседником и не подменил ли его кто-то по дороге.

С функцией подписи закрытого ключа разобрались, действительно полезная штука! Но как это решает проблему человека посередине, ведь если Алекс и Диана не могут без посредников обменяться открытыми ключами, Влад может подменить их при передаче?

А всё просто! Поскольку с помощью закрытого ключа можно подписать какие-то данные, с его помощью можно подписать и сам открытый ключ.

Если есть кто-то, предположим Артур, которому Алекс и Диана могут доверять и чей открытый ключ у них уже есть, то Артур может подписать их открытые ключи. Таким образом, если Влад попытается подменить открытый ключ Дианы, которая посылает его Алексу, то Алекс сразу обнаружит подмену, ведь на ключе не будет подписи Артура.

Также Артур может подписать открытый ключ Тимуру, который подпишет открытые ключи Алекса и Дианы, создав таким образом «цепочку доверия». В реальном мире существуют доверенные корневые центры сертификации (Артур), промежуточные центры (Тимур) и конечные получатели (Алекс и Диана).

Компрометация ключей и списки отзыва

А теперь предположим, что Диана оставила на виду свой закрытый ключ, его увидел Влад и теперь может подписывать любые сообщения, а также перехватывать и расшифровывать все данные, которые шифруются на открытый ключ Дианы. Такая проблема называется «Компрометация ключа».

На такой случай придумали «список отзыва» (Certificate Revocation List (CRL)), в котором публикуются скомпрометированные ключи, к которым больше нет доверия.

Адрес, где находится такой список отзыва, встроен во все сертификаты. То есть, если Диана заподозрит утечку закрытого ключа, она должна немедленно сообщить об этом Тимуру, который опубликует номер её сертификата в своём списке отзыва. Алекс со своей стороны при получении старого сертификата найдёт запись о его отзыве в списке Тимура и поймет, что доверять ему больше нельзя.

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

Процедура создания публичного и приватного ключей:

  1. Выбираем два случайных простых числа p и q.
  2. Вычисляем их произведение: N = p * q.
  3. Вычисляем функцию Эйлера: phi(N) = (p - 1) * (q - 1).
  4. Выбираем число e (обычно простое), которое меньше phi(N) и является взаимно простым с phi(N).
  5. Ищем число d, обратное числу e по модулю phi(N). Т.е. остаток от деления (d * e) на phi(N) должен быть равен 1.

Пример создания ключей на малых числах:

Пусть p = 19, q = 41. - N = 19 * 41 = 779 - phi(N) = (19 - 1) * (41 - 1) = 18 * 40 = 720 - Выберем e = 691 (оно меньше 720 и взаимно простое с ним) - Находим d, обратное к 691 по модулю 720. С помощью расширенного алгоритма Евклида получаем d = 571.

Итог вычислений: - Открытый ключ: {e=691, n=779} - Закрытый ключ: {d=571, n=779}

Шифрование сообщения:

Предположим, Диана хочет передать Алексу секретное число 21 (например, время начала вечеринки). Для этого она берет открытый ключ Алекса {691, 779} и возводит сообщение в степень e по модулю n: C = (21^691) mod 779 = 717

Число 717 — это зашифрованный текст. Алекс, получив его, берет свой закрытый ключ {571, 779} и производит обратную операцию: P = (717^571) mod 779 = 21

Магия математики вернула исходное сообщение 21!

Ниже представлен чистый код на языке Python, демонстрирующий генерацию ключей, шифрование и расшифрование нашего числового сообщения: