Szyfrowanie / deszyfrowanie RSA

Dwie liczby pierwsze i furtka. Klucz RSA zaczyna się od dwóch dużych losowych liczb pierwszych p i q; ich iloczyn n (moduł, stąd „klucz 2048-bitowy”) jest publikowany w kluczu publicznym razem z wykładnikiem e (prawie zawsze 65537). Klucz prywatny to wykładnik d, odwrotność modularna e − obliczona z p i q — plus skróty wynikające z liczb pierwszych, które przyspieszają operacje kluczem prywatnym 4×.

Szyfrowanie i podpisywanie to to samo potęgowanie. Zaszyfrowanie bloku wiadomości m oznacza obliczenie m^e mod n; deszyfrowanie to c^d mod n. Podpisanie wcześniej sformatowanego bloku wykładnikiem prywatnym i weryfikacja wykładnikiem publicznym to ta sama operacja w odwrotnym kierunku. Wszystko inne na tej stronie — OAEP, PSS, PKCS#1 — dotyczy bezpiecznego formatowania tego bloku, tak aby surowe potęgowanie nigdy nie było wystawione.

Dlaczego to wolne. Jedna operacja RSA na kluczu 2048-bitowym kosztuje rzędu miliona razy więcej procesora niż zaszyfrowanie jednego bloku AES. Dlatego TLS używa RSA (lub ECC) tylko do uzgodnienia losowego klucza AES, a potem przełącza się. Ta sama zasada dotyczy wszystkiego, co się buduje: RSA na klucz, AES na dane.

Rozmiar klucza. Długość modułu to pokrętło bezpieczeństwa: 1024-bit jest łamany ze względu na politykę (faktoryzacja jest w zasięgu państw), 2048-bit ≈ 112-bitowa siła symetryczna, 3072-bit ≈ 128-bit, 15360-bit odpowiadałby kluczowi symetrycznemu 256-bitowemu. Uwaga post-kwantowa: algorytm Shora łamie RSA wprost na dużym komputerze kwantowym — kolejny powód, by czas życia kluczy był ograniczony.

Problem surowego RSA. Podręcznikowe RSA (m^e mod n na surowej wiadomości) jest deterministyczne i podatne na modyfikacje: identyczne wiadomości szyfrują się identycznie, atakujący może pomnożyć szyfrogram przez zaszyfrowane 2, by podwoić tekst jawny, a krótkie wiadomości padają w ataku meet-in-the-middle. Nigdy nie wolno go używać wprost.

Co robi OAEP. OAEP (PKCS#1 v2, RFC 8017) miesza wiadomość z losowym ziarnem przez sieć Feistela opartą na funkcji skrótu, zanim nastąpi potęgowanie. Wynik: szyfrowanie jest randomizowane (ten sam tekst jawny daje za każdym razem inny szyfrogram — uruchom Przykład OAEP dwa razy i porównaj), manipulacja jest wykrywana przy deszyfrowaniu, a wiadomość musi zmieścić się w module z miejscem na skrót — limit k−2·hashLen−2 zestawiony powyżej.

Etykieta. Opcjonalny jawny ciąg związany z wypełnieniem. Obie strony muszą podać identyczną etykietę, inaczej deszyfrowanie się nie powiedzie — jak AAD w AES-GCM pozwala związać szyfrogram z kontekstem (nazwą pliku, identyfikatorem algorytmu). Pusta etykieta jest normalna.

Szyfrowanie PKCS#1 v1.5 jest celowo pominięte. Wypełnienie z lat 90. nie ma integralności i wycieka informacje przez zachowanie błędów deszyfrowania (atak Bleichenbachera z 1998 zamienia padding oracle w pełne deszyfrowanie za pomocą kilku milionów spreparowanych szyfrogramów; wciąż łamie prawdziwe systemy jako ROBOT, 2017). WebCrypto odmawia jego implementacji; tak samo ta strona.

Podpisanie = skrót, potem wypełnienie, potem potęgowanie. Oba schematy haszują wiadomość (tutaj SHA-256/384/512), formatują skrót w blok i stosują wykładnik prywatny. Weryfikacja ponownie formatuje blok kluczem publicznym i porównuje. Różnica tkwi w formatowaniu:

Który wybrać. Nowe projekty: PSS. Interoperacyjność z istniejącymi certyfikatami, JWT (RS256) lub starszymi partnerami: v1.5. Oba są bezpieczne jako schematy podpisu — katastrofa v1.5 dotyczy *szyfrowania*, to inna konstrukcja mimo podobnej nazwy.

PEM to po prostu DER owinięty w base64. Plik PEM to etykieta plus base64 struktury DER (binarnego ASN.1). Etykieta mówi, jaka to struktura — i właśnie na tym polega cała różnica między czterema formatami, które generuje ta strona:

Ten sam klucz, inne opakowania. Wszystkie cztery pola powyżej po wygenerowaniu zawierają ten sam klucz — publiczne SPKI i PKCS#1 mają identyczne n, e; prywatne PKCS#8 i PKCS#1 mają identyczne wartości prywatne. Ta strona konwertuje między nimi bezstratnie w przeglądarce (jej samotest sprawdza konwersje w obie strony). Mylenie formatów to najczęstsza przyczyna błędów „invalid key” przy wklejaniu kluczy między narzędziami.

Zaszyfrowane PEM-y (-----BEGIN ENCRYPTED PRIVATE KEY-----) to PKCS#8 z warstwą szyfrowania opartą na haśle. Ta strona ich nie przyjmuje — najpierw należy je odszyfrować offline (openssl pkcs8 -in enc.pem -out plain.pem).

• Szyfrowanie dużych danych przez RSA. Poza twardym limitem rozmiaru OAEP jest to absurdalnie wolne. Schemat jest taki: wygeneruj losowy klucz AES, zaszyfruj go RSA-OAEP, zaszyfruj dane AES-GCM i wyślij obie części.
• Wysyłanie klucza prywatnego, bo „to tylko test”. Przykładowe klucze osadzone w wektorach tej strony są opublikowane celowo — mogą służyć wyłącznie do podpisywania danych testowych. Prawdziwe klucze tak nie wyglądają.
• Weryfikowanie kluczem prywatnym. Zwykle „działa” matematycznie i niektóre narzędzia na to pozwalają, ale rozdawanie klucza prywatnego weryfikatorom niszczy cały model. Weryfikuj kluczem publicznym (ta strona to wymusza).
• Porównywanie podpisów bajt po bajcie w celu sprawdzenia kodu. PSS (i OAEP) są randomizowane: dwa poprawne przebiegi dają różne wyniki. Porównuj przez weryfikację, a nie równość — tylko podpisy v1.5 są deterministyczne.
• Klucze 1024-bitowe „bo są szybsze”. Są też w zasięgu dobrze finansowanej faktoryzacji. Argument szybkości przestał działać wraz z szyfrowaniem hybrydowym: RSA działa raz na sesję, a nie na każdy bajt.
• Zakodowanie na stałe długości soli innej niż długość skrótu dla PSS. Weryfikator musi się zgodzić; długość skrótu (wybór tej strony i -sigopt rsa_pss_saltlen:32 w OpenSSL) jest domyślną wersją interoperacyjną.

Dlaczego deszyfrowanie się nie powiodło z komunikatem „zły klucz, zły skrót lub uszkodzony szyfrogram”? Deszyfrowanie OAEP kończy się niepowodzeniem, gdy: to nie jest pasujący klucz prywatny, skrót różni się od strony szyfrującej, etykieta się różni albo zmienił się bajt szyfrogramu. Komunikat jest celowo identyczny we wszystkich przypadkach — ujawnienie, która kontrola zawiodła, samo w sobie jest wyciekiem typu padding oracle.

Czy mogę uzyskać klucz publiczny z prywatnego? Tak — formaty prywatne zawierają również n i e. Ta strona pokazuje oba po wygenerowaniu; OpenSSL robi to poleceniem openssl pkey -in priv.pem -pubout.

Dlaczego 65537 jako wykładnik? Jest liczbą pierwszą, ma tylko dwie jedynki binarne (szybkie potęgowanie) i jest na tyle duża, by uniknąć ataków z niskim wykładnikiem, które dotykają e=3. Jest standardowym wyborem od lat 90.; „dziwny” wykładnik zwykle oznacza słaby lub niestandardowy klucz.

Czy RSA jest martwe przez komputery kwantowe? Jeszcze nie — nie istnieje maszyna zdolna uruchomić algorytm Shora na module 2048-bitowym. Ale dane, które muszą pozostać tajne do lat 30. i dalej, już się migruje; rozwiązaniem inżynieryjnym są hybrydowe schematy PQC.

A co z openssl rsautl? To przestarzały poprzednik pkeyutl. Domyślnie używa wypełnienia szyfrowania v1.5 — kolejny powód, dla którego go wycofano.