RSA
RSA — асимметричная криптосистема (Rivest, Shamir, Adleman, 1977). Стойкость на сложности факторизации больших чисел. Самая распространённая, но постепенно вытесняется ECDSA/Ed25519.
Математика (упрощённо)
- Выбираем два простых
p,q. Считаемn = p×q. - φ(n) = (p-1)(q-1)
- Выбираем
eвзаимно простое с φ(n). Обычно e=65537. - d = e⁻¹ mod φ(n)
- Публичный ключ: (n, e). Приватный: (n, d).
- Шифрование:
c = m^e mod n. Расшифровка:m = c^d mod n.
Стойкость
| Размер ключа | Эквивалент симметрич. | Статус |
|---|---|---|
| 1024 bit | ~80 bit | взломан |
| 2048 bit | ~112 bit | безопасно до ~2030 |
| 3072 bit | ~128 bit | рекомендовано |
| 4096 bit | ~140 bit | параноик |
Стойкость — против GNFS (General Number Field Sieve), лучший алгоритм факторизации. Квантовый компьютер (алгоритм Шора) сломает RSA полностью.
Padding
Голый RSA (textbook) уязвим. Нужен padding:
- PKCS #1 v1.5 — старый, уязвим к Bleichenbacher (1998)
- OAEP — для шифрования, доказуемо безопасен
- PSS — для подписи, безопаснее v1.5
CRT (Chinese Remainder Theorem)
Ускоряет расшифровку ~4x, храня p, q, d_p, d_q, q_inv отдельно.
Использование
- TLS handshake — key exchange (устарело) или подпись
- S/MIME — шифрование почты
- SSH RSA-ключи
- Bitcoin — не использует (там secp256k1)