Szyfrowanie RSA

RSA to kryptosystem klucza publicznego wprowadzony w 1977 roku przez Rona Rivesta, Adi Shamira i Leonarda Adlemana z MIT. Patent wygasł w 2000 roku, po czym rozprzestrzenił się na praktycznie każdą bibliotekę kryptograficzną. RSA umożliwia dwie uzupełniające się operacje: szyfrowanie kluczem publicznym, dzięki czemu tylko klucz prywatny może odszyfrować, oraz podpisywanie kluczem prywatnym, dzięki czemu każda osoba posiadająca klucz publiczny może zweryfikować.

Matematyka, w skrócie, bezpieczeństwo

RSA opiera się na trudności w rozkładaniu na czynniki dużych liczb. Generowanie klucza:

1. Wybierz dwie duże losowe liczby pierwsze p i q (zazwyczaj 2048 bitów każdy).
2. Oblicz n = p × q. To jest moduł public.
3. Oblicz totient Eulera: φ(n) = (p-1)(q-1).
4. Wybierz małą nieparzystą e względnie pierwszą do φ(n). Zwykle 65537 (=2^16+1).
5. Obliczenie d = e^(-1) mod φ(n). To jest klucz prywatny.

Klucz publiczny to para (n, e); klucz prywatny to d.

Tby zaszyfrować wiadomość m: tekst zaszyfrowany c = m^e mod n. Aby odszyfrować: m = c^d mod n. Każdy, kto ma klucz publiczny, może szyfrować; tylko osoba posiadająca klucz prywatny może odszyfrować. Aby podpisać, odwrotnie: s = m^d mod n, sprawdź za pomocą m = s^e mod n.

Dlaczego to działa

Sztuczka: obliczenie d wymaga znajomości φ(n), co wymaga rozkładu na czynniki n na p × q. Rozłożenie na czynniki 2048-bitowej liczby półpierwszej wymaga więcej mocy obliczeniowych niż ludzkość. Weryfikacja n = p × q, gdy znasz już p i q, jest banalna. Asymetria — łatwe mnożenie, twardy faktoring — to cała podstawa RSA.

Kluczowe rozmiary

• RSA-1024 — łamana w zasadzie przez dobrze wyposażonych przeciwników; NIST zakazał go w przypadku nowych wdrożeń od 2014 r.
• RSA-2048 — obecny poziom bazowy. Uważany za bezpieczny w perspektywie średnioterminowej przeciwko klasycznym przeciwnikom.
• RSA-3072 — zalecany w przypadku nowych wdrożeń zgodnie z harmonogramem przejściowym NIST do 2030 r.
• RSA-4096 — powszechny w przypadku podpisywania kodu, w którym klucz ma horyzont 10–20 lat. Wolniejsze, ale konserwatywnie bezpieczne.

RSA w praktyce

RSA prawie nigdy nie szyfruje bezpośrednio dużych wiadomości. Jest powolny — zaszyfrowanie kilobajta wymaga tysięcy potęg modułowych. Zamiast tego w używany jest szyfrowanie RSA : wygeneruj losowy klucz AES, zaszyfruj dane za pomocą AES, zaszyfruj tylko klucz AES za pomocą RSA. Strona deszyfrująca RSA-odszyfrowuje klucz, a następnie AES-odszyfrowuje dane. Każdy uścisk dłoni TLS RSA działa w ten sposób; każdy e-mail zaszyfrowany PGP działa w ten sposób.

Padding ma znaczenie

Zwykły („podręcznik”) RSA — szyfrowanie m bezpośrednio bez dopełnienia — jest katastrofalnie niebezpieczne. Wiele ataków wykorzystuje plastyczność, brak losowości i przypadki brzegowe, takie jak małe m. Real RSA wykorzystuje schematy dopełnienia:

• PKCS#1 v1.5 dopełnienie — oryginalne dopełnienie; podatny na atak Bleichenbachera, jeśli implementacje wyciekają, niezależnie od tego, czy dopełnienie jest prawidłowe. Wciąż szeroko stosowane.
• OAEP (Optimal Asymmetric Encryption Padding) — nowoczesne dopełnienie; odporny na ataki wybranym szyfrogramem. Użyj tego do nowego szyfrowania RSA.
• PSS (Probabilistic Signature Scheme) — nowoczesne dopełnienie podpisu; lepszy od PKCS#1 v1.5 pod względem podpisywania.

Schemat uzupełniania jest częścią wdrożonego protokołu, a nie opcjonalnym. Błędy w implementacji dopełnienia są najczęstszym źródłem luk w zabezpieczeniach RSA w rzeczywistych systemach. Powolne wycofywanie

RSA

RSA jest zastępowane z dwóch powodów:

• Rozmiar klucza. Klucze RSA-3072 są większe niż równoważne klucze o krzywej eliptycznej o 10×. Koszty uzgadniania TLS i przechowywania sumują się w skali.
• Oporność kwantowa. Wystarczająco duży komputer kwantowy uwzględniłby RSA za pomocą algorytmu Shora w czasie wielomianowym. ECC jest również podatny na ataki, ale alternatywy odporne na kwanty są łatwiejsze do wdrożenia.

TLS 1.3 wycofała wymianę kluczy RSA na rzecz ECDHE. Nowoczesne podpisywanie przez urzędy certyfikacji przenosi się do ECDSA. RSA zapewnia kompatybilność z zainstalowanymi bazami (PGP, JWT, karty inteligentne, podpisywanie kodu) i pozostanie przez lata.

Pytanie postkwantowe

Nawet jeśli komputery kwantowe zdolne do złamania RSA zostaną udostępnione za kilkadziesiąt lat, dziś zbierane są zaszyfrowane dane o długoterminowej wartości, zakładając, że uda się je później odszyfrować. Kable rządowe, dokumentacja medyczna, własność intelektualna – „zebierz teraz, odszyfruj później” to obecny model zagrożenia. Standardy postkwantowe NIST (CRYSTALS-Kyber do enkapsulacji kluczy, CRYSTALS-Dilithium do podpisów) są wdrażane wraz z RSA w konfiguracjach hybrydowych. Wdrożenia czystego RSA dla długoterminowych poufnych danych są coraz częściej uważane za nieodpowiednie.