Асимметрия на простых числах
RSA назван по фамилиям авторов Ривеста, Шамира и Адлемана, которые описали его в 1977 году. Он стал одним из первых практических алгоритмов с открытым ключом. Идея опирается на асимметрию в арифметике: перемножить два больших простых числа очень легко, а вот по их произведению найти исходные множители очень трудно, если число достаточно велико.
Открытый ключ включает это произведение, называемое модулем, и показатель степени, чаще всего 65537. Закрытый ключ содержит информацию, которая вычисляется из самих простых множителей. Пока множители неизвестны, восстановить закрытый ключ по открытому не удаётся. Общие принципы двух ключей описаны в статье об асимметричном шифровании.
Этот подход отличается от обмена по схеме Диффи-Хеллмана, где секрет вычисляется сообща, а не шифруется одной стороной для другой.
Как это работает без формул
Чтобы зашифровать сообщение, его представляют числом и возводят в степень открытого показателя по модулю. Расшифровать результат может тот, кто знает закрытый показатель, полученный из простых множителей. Для подписи всё наоборот: подписывающий применяет закрытый показатель, а проверяющий открытый.
В реальности «чистый» RSA не применяют. Сообщение сначала дополняют специальной схемой, такой как OAEP для шифрования или PSS для подписи. Без такого дополнения возможны атаки, использующие математическую структуру алгоритма. Кроме того, RSA шифрует только короткие блоки, порядка размера ключа, поэтому им обычно защищают небольшой сеансовый ключ, а данные шифруют быстрым симметричным шифром, например AES.
Почему ключи такие длинные
Когда говорят о 2048-битном ключе RSA, имеют в виду размер модуля. Столь большой размер нужен потому, что известные алгоритмы разложения на множители работают заметно быстрее, чем простой перебор. Поэтому 2048 бит RSA оценивают как примерно 112 бит стойкости, а у симметричного ключа AES-128 обеспечивает 128 бит стойкости при куда меньшей длине ключа.
Отсюда практические правила. Ключи короче 2048 бит считаются недостаточными для новых систем. Рекомендации многих организаций допускают 2048 бит для текущих задач, а для долгосрочной защиты советуют 3072 бит и более. Чем длиннее ключ, тем медленнее операции с закрытым ключом, и это одна из причин, почему на смену пришли эллиптические кривые, которым посвящена отдельная страница.
Где RSA встречается сегодня
Раньше RSA использовали для обмена ключами в TLS. Сегодня в TLS 1.3 такой обмен убран, но RSA остаётся популярным для подписей: много сертификатов сайтов по-прежнему содержат ключи RSA. SSH-ключи, PGP-ключи, подпись программ и документов часто тоже строятся на нём. Сам алгоритм остаётся стандартным и хорошо поддерживается везде.
В новых системах для подписей всё чаще выбирают эллиптические схемы вроде Ed25519 из-за компактности и скорости. Кроме того, RSA уязвим для квантовых компьютеров достаточной мощности, поскольку алгоритм Шора умеет быстро раскладывать числа на множители. Практических машин такого масштаба пока нет, а переход на новые схемы разбирает статья о постквантовой криптографии.
Заблуждения и как посмотреть ключ
Частое заблуждение: «чем длиннее ключ, тем всегда лучше». Слишком длинный ключ замедляет соединения и мало что добавляет. Другое: «RSA можно взломать перебором закрытого ключа». Атаковать будут через разложение модуля, а не через перебор, и для 2048 бит это остаётся недостижимым при известных методах. Реальные проблемы чаще связаны с плохим генератором случайных чисел, при котором ключи получаются слабыми или совпадают у разных устройств.
Посмотреть параметры своего ключа можно командой openssl rsa -in ключ -text -noout: там видны модуль и показатель. Для SSH ключа команда ssh-keygen -l -f файл покажет размер и тип. Если ключ короче 2048 бит, стоит выпустить новый.
Типичные ошибки при работе с ключами RSA
На практике проблемы чаще бытовые. Закрытый ключ оставляют в репозитории кода или на общем диске. Один ключ используют для многих серверов. Не защищают файл ключа парольной фразой. Срок действия сертификата не отслеживают. Для SSH-ключей на общих машинах разрешения на файл оставляют слишком широкими, и клиент отказывается его использовать. Хорошая практика: хранить закрытый ключ с правами только для владельца, задавать парольную фразу, применять аппаратные токены для критичных ключей и менять ключи при смене сотрудников и подозрении на утечку.