Шифрование RSA является основой безопасной связи в интернете. Это вид криптографии с открытым ключом, который защищает электронные письма, цифровые транзакции и конфиденциальные данные, передаваемые по сетям. Алгоритм назван в честь своих создателей: Рональда Л. Ривеста, Ади Шамира и Леонарда Адлемана. Они разработали эту систему, работая преподавателями в Массачусетском технологическом институте.
Безопасность RSA опирается на простое математическое препятствие, которое легко создать, но почти невозможно обратить вспять. Пользователь начинает с выбора двух больших простых чисел, p и q. Эти числа настолько велики, что умножение их для получения n тривиально, но факторизация n обратно на p и q вычислительно невозможна.
Представьте себе это так: умножение двух огромных чисел занимает долю секунды. Попытка выяснить, какие два числа были перемножены, чтобы получить этот результат? С использованием современных технологий это может занять миллиарды лет.
По состоянию на 2015 год стандарты безопасности правительства США требуют, чтобы модуль n составлял не менее 2048 бит. В десятичной системе это означает, что p и q имеют около 308 цифр каждое, что создает 617-значное число для n. Самые большие числа, которые нам удалось успешно разложить на множители, имеют лишь половину этого размера. Сложность факторизации примерно удваивается с каждыми дополнительными тремя цифрами в модуле. Этот экспоненциальный рост сложности гарантирует, что 617-значные ключи остаются защищенными от атак методом грубой силы на протяжении десятилетий.
Механика генерации ключей
После выбора p и q система генерирует открытый и закрытый ключи. Пользователь выбирает целое число e, меньшее n. Это число должно быть взаимно простым с произведением (p – 1) и (q – 1). Простыми словами, e не имеет общих множителей с этим произведением, кроме 1.
Этот конкретный выбор гарантирует существование другого числа d. Когда вы умножаете e на d и делите на наименьшее общее кратное (p – 1) и (q – 1), остаток равен 1.
Найти d легко, если вы знаете p и q. Алгоритм Евклида вычисляет его за мгновения. Но если вы не знаете p и q, нахождение d из e так же сложно, как и факторизация n. Эта сложность является всей основой криптографической безопасности RSA.
Безопасность RSA — это не магия; это математика. В частности, это асимметрия между легким умножением и невозможной факторизацией.
Открытые ключи против закрытых ключей
Метки d и e описывают функции, а не строгие роли. Ключи взаимозаменяемы. Эта гибкость позволяет RSA выполнять две различные задачи: обеспечение секретности и аутентификацию.
Для создания канала секретности пользователь А публикует e и n в открытом каталоге. Пользователь А хранит d в секрете. Когда кто-то хочет отправить приватное сообщение А, он преобразует сообщение в числа, меньшие n, и шифрует его, используя e и n. Только А может расшифровать его, потому что только А владеет d. Предположение — и сильные доказательства — гласят, что никто другой не может расшифровать сообщение без факторизации n.
Аутентификация работает иначе. Пользователь А публикует d и n и хранит e в секрете. Пользователь B хочет убедиться, что он общается с А. B отправляет проверочное сообщение А. Если А возвращает зашифрованную версию, используя e, B может расшифровать ее с помощью открытого d. Если расшифрованное сообщение совпадает с проверочным, B знает, что отправитель владеет e. Поскольку только А имеет e, личность подтверждена.
Цифровые подписи и хеширование
Цифровая подпись добавляет слой сложности. Она требует криптографически стойкой хеш-функции. Это публичная функция, которая сжимает любое сообщение в меньшую контрольную сумму (дайджест). Каждый бит дайджеста зависит от каждого бита исходного сообщения. Измените один бит в исходном сообщении, и примерно половина битов в дайджесте изменится.
Криптографически стойкий хеш делает вычислительно невозможным нахождение сообщения, которое дает конкретную заранее назначенную контрольную сумму. Он также затрудняет нахождение другого сообщения с той же контрольной суммой, что и у известного.
Чтобы подписать сообщение, А шифрует дайджест своим секретным e и добавляет его к сообщению. Само сообщение не обязательно должно быть секретным. Любой может использовать открытый ключ d А для расшифровки подписи и восстановления дайджеста. Затем они независимо вычисляют дайджет полученного сообщения. Если два дайджеста совпадают, подпись действительна. Только А мог зашифровать дайджест, потому что только А знает e.
Гибридная реальность
За эту безопасность приходится платить. Асимметричное шифрование требует значительно больше вычислений, чем симметричное (с одним ключом) шифрование. Это высокое потребление процессорных ресурсов резко снижает пропускную способность. На протяжении примерно 20 лет алгоритмы с одним ключом достигали пропускной способности в 1000–10 000 раз выше, чем алгоритмы с двумя ключами, при сопоставимом уровне безопасности.
Поскольку RSA работает медленно, он редко используется для прямого шифрования больших объемов данных. Вместо этого он питает гибридные системы. RSA берет на себя основную работу по аутентификации и цифровым подписям. Он также безопасно обменивается случайно сгенерированным сеансовым ключом. После того как этот ключ передан, система переключается на алгоритм с одним ключом для высокоскоростной передачи фактических данных. Когда сеанс заканчивается, ключ отбрасывается.
Это сочетание дает нам лучшее из обоих миров. Мы получаем безопасный обмен ключами с помощью криптографии с открытым ключом и скорость симметричного шифрования для основной части наших данных.
Математика выдерживает проверку. Ключи остаются в безопасности. Но по мере роста вычислительной мощности определение «большого» числа меняется. То, что сегодня невозможно взломать, завтра может оказаться решаемой задачей. Мы продолжаем создавать более большие простые числа. Мы продолжаем надеяться, что разрыв между легким умножением и сложной факторизацией остается достаточно широким, чтобы защитить нашу цифровую жизнь.
