Skip to content
Назад к результатам поиска

Криптосистема RSA

Автор метода
Ronald Rivest
Год
1978
Тип
asymmetric encryption algorithm
Семейство
Public-key cryptography

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

RSA — это основополагающая криптосистема с открытым ключом, разработанная Ривестом, Шамиром и Адлеманом в 1978 году.

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

Интуиция метода

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

История

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

Когда применять

RSA подходит для шифрования небольших объемов данных, установления безопасных каналов и создания цифровых подписей. Он обычно используется в протоколах TLS/SSL, шифровании электронной почты (PGP) и центрах сертификации. RSA требует тщательных схем дополнения (OAEP для шифрования, PSS для подписей) для обеспечения безопасности. Современные реализации должны использовать ключи размером не менее 2048 бит для разумной безопасности против текущих вычислительных мощностей.

Ограничения и замечания

  • Вычислительно затратен по сравнению с симметричным шифрованием; обычно используется для обмена ключами, а не для шифрования больших объемов данных
  • Размер ключа должен быть большим (2048 бит или более) для адекватной безопасности, что делает шифрование и дешифрование медленнее, чем симметричные альтернативы
  • Уязвим для квантовых компьютеров, если они станут практически применимыми, что требует постквантовых альтернатив

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Широко стандартизирован и поддерживается на различных платформах и в библиотеках
  • Позволяет как шифрование, так и генерацию цифровой подписи с использованием одной и той же пары ключей
  • Математически элегантная основа, базирующаяся на проблеме факторизации
  • Обратная совместимость с десятилетиями существующей инфраструктуры

Применение

  • Протоколы HTTPS и TLS/SSL для обеспечения безопасности веб-связи и электронной коммерции
  • Pretty Good Privacy (PGP) и S/MIME для шифрования сообщений электронной почты
  • Цифровые сертификаты и инфраструктура открытых ключей (PKI) для аутентификации личности в Интернете
  • Системы блокчейн и криптовалюта для подписи и проверки транзакций
  • Аутентификация смарт-карт и шифрование государственных удостоверений личности
  • Аппаратные модули безопасности (HSM) для управления корпоративными ключами

Как это работает

Как это работает

1

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

2

Для шифрования сообщения m вычислите шифротекст c = m^e mod n, где e и n — открытый ключ получателя.

3

Для дешифрования шифротекста c вычислите открытый текст m = c^d mod n, где d и n — закрытый ключ.

4

Цифровые подписи создаются путем шифрования хеша сообщения закрытым ключом и проверяются путем дешифрования открытым ключом для подтверждения совпадения хеша.

Частые ошибки

  • Использование RSA без надлежащих схем дополнения (OAEP или PSS) может сделать алгоритм уязвимым для различных атак
  • Повторное использование одного и того же ключа RSA как для операций шифрования, так и для операций подписи увеличивает поверхность атаки; предпочтительны выделенные пары ключей
  • Неправильная генерация простых чисел или слабая случайность при генерации ключей может полностью скомпрометировать безопасность

Часто задаваемые вопросы

Почему RSA медленнее по сравнению с симметричным шифрованием, таким как AES?

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

Что произойдет, если кто-то факторизует модуль n моего открытого ключа?

Если злоумышленник факторизует n на его простые множители p и q, он может вычислить φ(n), а затем вывести ваш закрытый ключ d из вашего открытого показателя e. Вот почему использование достаточно больших простых чисел и размеров ключей имеет решающее значение.

Могут ли подписи RSA быть подделаны без закрытого ключа?

Не при правильно дополненных подписях (PSS). Однако неподготовленные или неправильно дополненные подписи RSA уязвимы для различных математических атак. Всегда используйте стандартные схемы дополнения.

Безопасен ли RSA в 2026 году?

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

Как выбрать подходящие простые числа p и q?

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

Похожие методы

Источники

  1. Rivest, R. L., Shamir, A., & Adleman, L. (1978). A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2), 120-126.

    Открыть ссылку DOI
    Скопировано.
  2. Koblitz, N. (1987). A Course in Number Theory and Cryptography. Springer-Verlag.

    ISBN: 978-0387966618
    Скопировано.