Как работает RSA и почему ему угрожают квантовые компьютеры

Представьте себе 70-е годы прошлого века: мир активно подключается к открытым каналам связи, а защита данных становится вопросом первостепенной важности. В то время три профессора-математика Массачусетского технологического института — Рональд Ривест, Ади Шамир и Леонард Адлеман — размышляли над революционным способом шифрования. Они искали подход, который бы позволил передавать данные в открытом доступе, не рискуя безопасностью. В итоге они придумали алгоритм, известный сегодня как RSA (аббревиатура, составленная из первых букв фамилий его создателей: Rivest, Shamir и Adleman), и долгое время считавшийся стандартом безопасности. Но кажется, его время скоро пройдет.

Используйте навигацию, если не хотите читать текст полностью:

→ Что такое RSA и почему стал легендой
→ Математика и магия: как работает RSA
→ Генерация простых чисел: почему именно они, как их искать и почему стоит избегать «плохих» простых чисел
→ Особенности экспоненциальной функции в алгоритме и ее роль в безопасности RSA
→ RSA и квантовые компьютеры: что ждет алгоритм завтра
→ Популярные ошибки при реализации RSA

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

Так появился RSA — алгоритм, положивший начало эре асимметричной криптографии. Его безопасность основывается на сложности разложения больших чисел на простые множители, что позволило создать систему, в которой public key (публичный ключ) используется для шифрования, а private key (приватный ключ) — для расшифровки. Эта идея позволила обойти проблему передачи секретных ключей и стала революцией в цифровой безопасности.

Согласно данным проекта SSL Pulse за ноябрь 2024, который отслеживает качество поддержки SSL/TLS на 150 000 популярных веб-сайтов, алгоритм RSA используется в 21% сертификатов в системе HTTPS, особенно в SSL/TLS-протоколах для обеспечения защищенных интернет-соединений.

В дополнение, RSA составляет примерно 23% от всех методов, применяемых для цифровых подписей и аутентификации электронной почты в рамках протоколов, таких как S/MIME и PGP (по данным отчета Entrust Datacard).

Зачем использовать асимметричное шифрование и почему симметричные алгоритмы уже не справляются

Симметричные алгоритмы шифрования, такие как DES и AES, используют один и тот же ключ для шифрования и расшифрования данных. Хотя они эффективны и быстры, их основной недостаток заключается в необходимости безопасной передачи этого общего ключа между отправителем и получателем. Если ключ будет перехвачен злоумышленником, вся система безопасности окажется под угрозой.

RSA, как первый практически применимый алгоритм асимметричного шифрования, устранил эту проблему, введя концепцию public key и private key. Использование пары ключей позволяет шифровать данные с помощью публичного ключа, который может быть свободно передан через открытые каналы связи. При этом только владельцу приватного ключа доступна возможность расшифровать сообщение. Шифрование приватным ключом возможно, но не для защиты данных, а для подтверждения подлинности. Сообщение, зашифрованное приватным ключом, можно расшифровать публичным ключом, что доказывает его отправку владельцем приватного ключа.

Это решает проблему их передачи и обеспечивает высокий уровень безопасности, даже если злоумышленник перехватит сообщение или публичный ключ.

Сферы применения RSA

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

Публичный ключ может проверить подпись, потому что он расшифровывает хэш, зашифрованный приватным ключом. Затем этот хэш сравнивается с хэшем исходных данных. Если они совпадают, это подтверждает, что подпись подлинная и данные не изменены.

Это обеспечивает юридическую и технологическую защиту документов, контрактов и других важных данных в электронном виде.

Также RSA — основа для многих криптографических протоколов, таких как SSL/TLS, используемых в HTTPS, и SSH. В этих протоколах RSA применяется для защиты сессий обмена данными, обеспечивая их конфиденциальность и защищенность от атак.

RSA используется для обеспечения безопасности соединений, например, в протоколах SSL/TLS, которые применяются в защищенных email системах, VPN и других сценариях, требующих безопасного обмена данными.

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

Итак, RSA — это асимметричный алгоритм, основанный на использовании пары ключей. Ниже представлены основные этапы его работы.

Источник.

Генерация ключей

• Выбираем два больших простых числа p и q.
• Вычисляем их произведение n=p×q, которое будет модулем.
• Определяем значение функции Эйлера φ(n)=(p−1)×(q−1).
• Выбираем число e (публичную экспоненту), которое является взаимно простым с φ(n).
• Находим d — число, которое при умножении на e дает остаток 1 по модулю: e×d≡1(mod φ(n)).

Шифрование

• Представляем сообщение как число M, где 0 ≤ M < n.
• Шифруем сообщение, используя публичный ключ и формулу: C=M^e Mod n, где C — зашифрованное сообщение.

Расшифрование

• Расшифровываем зашифрованное сообщение C с помощью приватного ключа d: M=C^d mod n.
• Возвращаем исходное сообщение M.

Но давайте рассмотрим все на примере. Для наглядности возьмем небольшие числа.

• Выбор простых чисел: пусть p=7 и q=11.
• Вычисление n: n=p×q=7×11=77.
• Функция Эйлера φ(n)φ(n): φ(n)=(p−1)×(q−1)=6×10=60.
• Выбор e: пусть e=17 (взаимно просто с φ(n) = 60).
• Расчет d: находим d=53 (поскольку 17×53≡1 mod 60).

Теперь у нас есть:

• public key: (e,n)=(17,77),
• private key: (d,n)=(53,77).

И, наконец, вот так будут выглядеть шифрование и расшифровка:

• Шифрование: Пусть M=20. Тогда C=20^17 mod 77=63
• Расшифровка: Чтобы получить исходное сообщение, применяем M=63^53 mod 77=20.

Пример использования RSA. Источник.

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

Почему именно простые числа

Они обладают двумя уникальными свойствами, которые делают их идеальными для шифрования. Первое — устойчивость к факторизации. Произведение двух больших простых чисел создает число, которое трудно разложить на исходные множители. Без приватного ключа вычислить эти числа с помощью классических алгоритмов крайне сложно, особенно при длине ключа в 2 048 или 4 096 бит.

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

Как искать простые числа

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

Сначала генерируются большие случайные числа, которые потенциально могут быть простыми. Затем они проверяются на простоту с использованием тестов, таких как тест Миллера-Рабина или тест Ферма. Эти методы позволяют определить вероятность того, что число простое, с высокой точностью. Чем большее количество проверок проходит число, тем выше уверенность в его простоте. Наконец, используются криптографически стойкие генераторы случайных чисел. Они минимизируют риск того, что числа будут слишком предсказуемыми или легко вычислимыми злоумышленником.

Почему стоит избегать «плохих» простых чисел

Не все йогурты одинаково полезны простые числа одинаково безопасны. Существуют «плохие» простые числа, использование которых может значительно снизить стойкость алгоритма.

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

Во-вторых, слишком близкие друг к другу простые числа. Если p и q слишком близки, разложение на множители становится проще. Это снижает стойкость алгоритма.

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

Экспоненциальная функция делает обратное вычисление крайне трудоемким. Сложность нахождения M связана с невозможностью извлечения корня степени e без приватного ключа d. Это обеспечивает стойкость RSA к атакам на основе грубой силы.

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

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

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

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

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

Алгоритм Шора

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

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

На данный момент квантовые компьютеры еще недостаточно мощны для практического взлома RSA. Однако очевидно, что так будет не всегда. Кажется, момент, когда квантовые компьютеры станут достаточно массово применяться, не так далек, как казалось несколько лет назад.

Идеи для будущего: квантово-устойчивые алгоритмы и гибридные криптосистемы как потенциальные замены RSA

Для обеспечения безопасности в эру квантовых вычислений разрабатываются квантово-устойчивые алгоритмы, такие как алгоритмы на основе решеток (например, NTRU), код Гоппы и системы на основе изогенных эллиптических кривых. Эти алгоритмы считаются достаточно стойкими даже для квантовых компьютеров.

В 2024 году Национальный институт стандартов и технологий (NIST) утвердил три квантово-устойчивых алгоритма для защиты данных в условиях квантовых вычислений. Одним из них стал CRYSTALS-Kyber, который использует математические решетки и предназначен для надежного шифрования данных в будущем. Также утверждены алгоритмы CRYSTALS-Dilithium и FALCON для цифровых подписей. Они обеспечивают защиту от квантовых атак и активно внедряются как новые стандарты.

Также предлагаются гибридные криптосистемы, сочетающие традиционные и квантово-устойчивые методы. Они позволяют обеспечить плавный переход к новым стандартам безопасности. Например, в браузере Google Chrome 116 была введена поддержка гибридной квантово-устойчивой криптографии X25519Kyber768, объединяющей алгоритм эллиптической кривой X25519 и квантово-устойчивый метод инкапсуляции ключей Kyber-768. Это позволит обеспечить плавный переход и дать пользователям время адаптироваться к новому типу защиты. Гибридные системы являются промежуточным решением, которое помогает организациям использовать как текущие алгоритмы, так и новейшие квантово-устойчивые методы.

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

• Использование статических ключей. Не используйте одни и те же ключи на протяжении длительного времени. Это увеличивает риск компрометации.
• Повторное использование чисел. Повторное использование простых чисел при генерации ключей делает систему уязвимой для атак.
• Слабые библиотеки. Устаревшие версии библиотек часто содержат неисправленные уязвимости. Регулярное обновление — обязательное условие для поддержания безопасности.
• Плохая защита приватных ключей. Приватные ключи должны быть защищены с помощью HSM (Hardware Security Module) или других методов.
• Неправильное заполнение. Использование небезопасных методов заполнения (например, PKCS#1 v1.5) делает RSA уязвимым к атакам на шифрованные сообщения. Лучше использовать OAEP (Optimal Asymmetric Encryption Padding).

А вот подборка ссылок на проверенные библиотеки и руководства:

• OpenSSL: Одна из самых популярных библиотек, регулярно обновляемая, она предоставляет необходимые инструменты для настройки и реализации RSA с защитой на уровне актуальных стандартов. Руководство по OpenSSL.
• Bouncy Castle: Кроссплатформенная библиотека для Java и C#, поддерживающая реализацию RSA и других криптоалгоритмов. Рекомендуется для приложений на Java и встраиваемых систем. Документация Bouncy Castle.
• PyCryptodome: Современная библиотека для работы с криптографией в Python, поддерживает RSA и обеспечивает надёжные методы заполнения, такие как OAEP. Документация PyCryptodome.
• NIST (Национальный институт стандартов и технологий): Стандарты и рекомендации для реализации RSA и других криптографических алгоритмов. Полезный источник для соблюдения лучших практик в криптографии. Руководство NIST по RSA.

А вы уже задумались о переходе на квантово-устойчивые алгоритмы? Пишите, что думаете, в комментариях!