Криптография
RSA: математика
1977 год. Rivest, Shamir и Adleman опубликовали RSA в MIT Technical Memo. Ривест считал, что факторизация 100-цифрового числа займёт 74 квинтиллионов лет. Математика оказалась права - RSA-2048 до сих пор не взломан. Но каждый HTTPS-запрос, TLS-сертификат и SSH-ключ основаны именно на этой математике.
- **TLS/HTTPS**: RSA-2048 для подписи сертификатов и начального handshake. Постепенно заменяется ECDSA (P-256) из-за размера ключей.
- **SSH**: RSA-4096 - популярный выбор для аутентификации. Ed25519 (EdDSA на Curve25519) быстрее и безопаснее при вдвое меньшем ключе.
- **PGP/GPG**: RSA-2048 или RSA-4096 для шифрования email. Keybase использовал RSA для верификации ключей.
- **Квантовые компьютеры**: алгоритм Шора решает факторизацию за O(log^3 n) на квантовом компьютере. NIST стандартизирует постквантовые альтернативы RSA.
Генерация ключей RSA
RSA (Rivest, Shamir, Adleman, 1977) основан на вычислительной сложности факторизации больших чисел. Публичный ключ (n, e) и приватный ключ (n, d) связаны через функцию Эйлера: e*d ≡ 1 (mod φ(n)).
На практике RSA-2048 требует, чтобы p и q различались по длине, были безопасными простыми (p-1 имеет большой простой делитель), и не совпадали с заранее известными слабыми числами. OpenSSL генерирует RSA-2048 ключ за ~100ms. RSA-4096 - за ~2 секунды.
Почему стандартное значение e = 65537 используется в RSA?
Шифрование и дешифрование RSA
Шифрование RSA: C = M^e mod n, где M - сообщение как число (0 <= M < n). Дешифрование: M = C^d mod n. Корректность: (M^e)^d = M^(ed) ≡ M (mod n) - это требует доказательства через теорему Эйлера.
На практике RSA никогда не шифрует данные напрямую - только симметричные ключи (или хэши для подписи). Для шифрования данных используется гибридная схема: случайный AES-ключ шифруется RSA-OAEP, данные шифруются AES-GCM. PKCS#7/CMS описывает этот стандартный формат.
Почему RSA используется для шифрования только симметричных ключей, но не самих данных?
Доказательство корректности RSA
Нужно доказать: C^d ≡ M (mod n), то есть (M^e)^d ≡ M (mod n), то есть M^(ed) ≡ M (mod n). По построению: ed ≡ 1 (mod φ(n)), значит ed = 1 + k*φ(n) для некоторого целого k.
CRT (Chinese Remainder Theorem) используется не только в доказательстве, но и для ускорения RSA: приватная операция d вычисляется mod p и mod q отдельно (dp = d mod p-1, dq = d mod q-1), что ускоряет в ~4 раза. OpenSSL хранит p, q, dp, dq, qInv в приватном ключе.
Что обеспечивает обратимость операции RSA (дешифрование восстанавливает исходное сообщение)?
Теорема Эйлера и функция Кармайкла
Теорема Эйлера: для gcd(a, n) = 1 верно a^φ(n) ≡ 1 (mod n). Функция Эйлера φ(n) = число целых от 1 до n, взаимно простых с n. Для n = p*q: φ(n) = (p-1)(q-1).
Современный RFC 8017 (PKCS#1 v2.2) рекомендует использовать функцию Кармайкла λ(n) = lcm(p-1, q-1) вместо φ(n). λ(n) делит φ(n), что даёт меньшее d и ускоряет операции. Безопасность при этом не снижается.
RSA безопасен просто потому что факторизация n сложна
RSA безопасен если факторизация n сложна (необходимое условие), но этого недостаточно. Требуются правильная схема дополнения (OAEP), безопасное генерирование случайных чисел и защита от side-channel атак
Textbook RSA (без дополнения) детерминирован - одно сообщение всегда даёт один шифртекст. Это позволяет атаки через chosen plaintext и по структуре сообщения. OAEP добавляет случайность.
В чём преимущество функции Кармайкла λ(n) перед функцией Эйлера φ(n) в RSA?
Ключевые идеи
- **Генерация ключей**: два больших простых p, q -> n=pq, φ(n)=(p-1)(q-1), e=65537, d=e^(-1) mod φ(n). Безопасность = сложность факторизации n.
- **Операции**: C = M^e mod n (шифрование), M = C^d mod n (дешифрование). CRT ускоряет приватные операции в 4 раза.
- **Доказательство**: теорема Эйлера M^φ(n) ≡ 1 (mod n) гарантирует M^(ed) ≡ M (mod n).
- **На практике**: RSA шифрует только AES-ключи (гибридная схема). Textbook RSA небезопасен - нужен OAEP (урок 25).
Связанные темы
Математика RSA связана с широким контекстом:
- RSA на практике — OAEP, подписи PSS, атаки на слабые ключи - практическое применение математики RSA.
- Эллиптические кривые — ECDSA и ECDH - замена RSA с меньшими ключами. Та же идея публичного/приватного ключа на другой математической структуре.
- Квантовая угроза — Алгоритм Шора разрушает RSA: квантовый компьютер факторизирует n за полиномиальное время.
Вопросы для размышления
- Если факторизация RSA-2048 сложна, почему это не является доказательством безопасности RSA? Какие другие атаки возможны без факторизации?
- Почему RSA нельзя использовать с одинаковым n для разных пользователей? Что произойдёт?
- При генерации RSA-ключа p и q должны быть 'безопасными простыми' (p = 2p' + 1, где p' тоже простое). Зачем это условие?