Kodowanie Tajemnic: Odkrywanie Sztuki Łączenia Liczb Pierwszych z Kryptografią

Liczby pierwsze nie szyfrują danych same z siebie. Ich znaczenie polega na tym, że pozwalają zbudować działania matematyczne łatwe do wykonania w jedną stronę, lecz bardzo kosztowne do odwrócenia bez dodatkowej informacji. Właśnie na tej asymetrii opiera się RSA, część mechanizmów wymiany kluczy oraz wiele konstrukcji używanych do podpisywania dokumentów, aktualizacji oprogramowania i certyfikatów.

Najważniejsza praktyczna różnica przebiega jednak nie między „małą” a „dużą” liczbą pierwszą, lecz między poprawnie wdrożoną kryptografią a kodem napisanym samodzielnie na podstawie kilku wzorów. Klucz RSA może mieć odpowiednią długość i nadal być bezużyteczny, jeżeli liczby pierwsze wygenerowano przewidywalnie, zastosowano niewłaściwe dopełnienie albo ujawniono fragment klucza przez różnice czasu wykonywania operacji.

Dlaczego rozkład liczby na czynniki chroni klucz prywatny

Liczba pierwsza jest liczbą naturalną większą od 1, mającą dokładnie dwa dodatnie dzielniki: 1 oraz samą siebie. Przykłady to 2, 3, 5, 7, 11 i 13. W kryptografii nie chodzi jednak o pojedyncze niewielkie liczby, lecz o liczby pierwsze mające setki cyfr dziesiętnych.

Najbardziej czytelny przykład daje RSA. Podczas tworzenia klucza wybiera się dwie duże, niezależnie wygenerowane liczby pierwsze oznaczane zwykle jako p i q, a następnie oblicza ich iloczyn:

n = p × q

Liczba n staje się częścią klucza publicznego. Można ją bezpiecznie ujawnić. Tajemnicą pozostają natomiast czynniki p i q oraz wartości wyprowadzone z nich podczas obliczania klucza prywatnego.

Na małym, całkowicie niebezpiecznym przykładzie można przyjąć:

• p = 61,
• q = 53,
• n = 3233,
• φ(n) = (61 − 1) × (53 − 1) = 3120,
• wykładnik publiczny e = 17,
• wykładnik prywatny d = 2753.

Wartość d jest dobrana tak, aby spełniała odpowiednią zależność modularną względem e i φ(n). Klucz publiczny można więc zapisać jako parę (3233, 17), a prywatny zawiera wartość 2753 oraz — w rzeczywistych implementacjach — dodatkowe parametry przyspieszające obliczenia.

Dla n = 3233 rozkład na 61 i 53 jest banalny. Dla poprawnie wygenerowanego modułu RSA o długości 2048 lub 3072 bitów sytuacja wygląda zupełnie inaczej. Nie istnieje obecnie znana klasyczna metoda, która pozwalałaby sprawnie rozkładać dowolne tak duże moduły na czynniki przy użyciu dostępnych zasobów obliczeniowych.

To nie znaczy, że „duża liczba pierwsza jest niemożliwa do złamania”. Bezpieczeństwo wynika z kilku warunków jednocześnie:

• p i q muszą pochodzić z kryptograficznie bezpiecznego generatora losowego;
• liczby nie mogą być równe ani podejrzanie bliskie;
• muszą przejść odpowiednie testy pierwszości;
• moduł nie może być zbyt krótki;
• klucz nie może współdzielić czynnika pierwszego z innym kluczem;
• implementacja musi być odporna na ataki czasowe, błędy sprzętowe i wycieki z pamięci.

W praktyce liczby pierwsze generuje się przez losowanie nieparzystych kandydatów o określonej długości i sprawdzanie ich testami pierwszości. Nie trzeba matematycznie dowodzić pierwszości każdej liczby od zera. Stosuje się bardzo wiarygodne testy probabilistyczne, między innymi Miller–Rabina, często połączone ze wstępnym odrzucaniem liczb podzielnych przez małe liczby pierwsze.

Prawdopodobieństwo błędnego uznania liczby złożonej za pierwszą można przez kolejne rundy testu obniżyć do poziomu pomijalnego. Problem zaczyna się nie w samym teście, lecz w źródle losowości. Jeżeli dwa urządzenia wygenerują klucze RSA mające wspólny czynnik p, oba moduły można rozłożyć przez obliczenie ich największego wspólnego dzielnika. Taka operacja jest szybka. Zdarzało się to urządzeniom wbudowanym uruchamianym przy małej ilości entropii.

Gdzie liczby pierwsze pracują, choć użytkownik ich nie widzi

RSA bywa przedstawiany jako mechanizm służący do szyfrowania całych wiadomości. To mylący obraz. RSA jest wolny, ma ograniczony rozmiar wejścia i nie powinien bezpośrednio szyfrować dużych plików. W poprawnie zaprojektowanym systemie kryptografia asymetryczna chroni niewielki sekret, a właściwe dane szyfruje szybki algorytm symetryczny.

Typowy schemat hybrydowy wygląda następująco:

1. system losuje klucz dla algorytmu symetrycznego, np. AES-256;
2. dane szyfruje AES-em w trybie uwierzytelnionym, np. GCM;
3. klucz symetryczny zabezpiecza mechanizmem asymetrycznym;
4. odbiorca odzyskuje klucz i dopiero nim odszyfrowuje dane.

W samym RSA nie wolno stosować operacji potęgowania modularnego bez odpowiedniego schematu kodowania. Tak zwany podręcznikowy RSA jest deterministyczny i podatny na ataki. Dwie identyczne wiadomości dałyby identyczny szyfrogram, a struktura danych mogłaby ułatwić manipulację.

Do szyfrowania RSA używa się dopełnienia OAEP, a do podpisów — przede wszystkim RSA-PSS. Starszy format podpisu PKCS#1 v1.5 nadal występuje w istniejących systemach, ale przy projektowaniu nowego rozwiązania PSS jest rozsądniejszym wyborem. Sam podpis także nie polega na „zaszyfrowaniu dokumentu kluczem prywatnym”. Najpierw obliczany jest skrót wiadomości, następnie przygotowywana jest odpowiednio zakodowana struktura, a dopiero na niej wykonywana jest operacja RSA.

Liczby pierwsze pojawiają się również w kryptografii opartej na logarytmie dyskretnym. Klasyczny Diffie–Hellman wykonuje działania w grupie modularnej związanej z dużą liczbą pierwszą. Dwie strony mogą dzięki temu wyprowadzić wspólny sekret, mimo że część danych wymieniana jest przez publiczny kanał.

W praktyce internetowej częściej spotyka się dziś ECDHE, czyli efemeryczny Diffie–Hellman na krzywych eliptycznych. Krzywe eliptyczne także działają nad skończonymi ciałami matematycznymi, często o charakterystyce będącej liczbą pierwszą. Nie wykorzystują jednak prostego mechanizmu „pomnóż dwie liczby pierwsze”, charakterystycznego dla RSA.

Ta różnica ma konsekwencje techniczne. Klucze oparte na krzywych eliptycznych mogą być znacznie krótsze niż klucze RSA oferujące zbliżony poziom bezpieczeństwa. Przykładowo:

• RSA 2048 bitów odpowiada orientacyjnie około 112 bitom bezpieczeństwa;
• RSA 3072 bitów odpowiada około 128 bitom bezpieczeństwa;
• popularne krzywe 256-bitowe również zapewniają w przybliżeniu 128 bitów bezpieczeństwa.

Nie należy porównywać długości kluczy jeden do jednego. Klucz 256-bitowy oparty na krzywej eliptycznej nie jest „osiem razy słabszy” od RSA-2048. Oba systemy opierają bezpieczeństwo na innych problemach matematycznych i wymagają innych nakładów atakującego.

Dla nowych kluczy RSA 2048 bitów jest obecnie praktycznym minimum, ale w systemach projektowanych na dłuższy okres często wybiera się 3072 bity. RSA-4096 zwiększa koszt ataku, lecz jednocześnie powiększa podpisy i certyfikaty oraz spowalnia operacje. Nie jest automatycznie najlepszym wyborem. W serwerze obsługującym dużą liczbę żądań może oznaczać większe zużycie procesora bez proporcjonalnej korzyści.

W praktycznym wdrożeniu priorytety powinny wyglądać tak:

• najpierw biblioteka i protokół, nie ręczne implementowanie wzorów;
• następnie bezpieczne generowanie i przechowywanie kluczy;
• później dobór długości klucza do okresu ochrony danych;
• dopiero na końcu optymalizacja szybkości.

Dla polskiej firmy oznacza to korzystanie z dojrzałych mechanizmów oferowanych przez OpenSSL, BoringSSL, libsodium, Java Cryptography Architecture, Microsoft CNG albo sprawdzone usługi HSM i KMS. Pisanie własnego generatora liczb pierwszych zwykle nie daje żadnej przewagi. Za to tworzy nową powierzchnię ataku.

Najczęstsze awarie i granica bezpieczeństwa RSA

Największym zagrożeniem dla systemów opartych na liczbach pierwszych rzadko jest spektakularne odkrycie matematyczne. Znacznie częściej problemem okazuje się błąd wdrożeniowy.

Pierwszy typowy błąd to słaba losowość. Generator pseudolosowy uruchomiony ze stałym ziarnem może tworzyć powtarzalne klucze. Podobny problem występuje w urządzeniach IoT, które próbują wygenerować klucz natychmiast po włączeniu, zanim system zbierze dostateczną ilość nieprzewidywalnych zdarzeń.

Drugi błąd to pozostawienie klucza prywatnego w miejscu łatwiejszym do zdobycia niż zaszyfrowane dane. Plik PEM zapisany obok kopii zapasowej, dostępny dla całego zespołu lub umieszczony w repozytorium Git przekreśla matematyczną siłę RSA. Atakujący nie musi rozkładać modułu na czynniki. Po prostu kopiuje klucz.

Trzeci problem stanowią przestarzałe schematy. W szczególności należy unikać:

• kluczy RSA krótszych niż 2048 bitów w nowych systemach;
• surowego, podręcznikowego RSA;
• szyfrowania bez OAEP;
• własnych formatów podpisu;
• przestarzałych funkcji skrótu, takich jak MD5 i SHA-1;
• ujawniania szczegółowych komunikatów o błędach podczas deszyfrowania;
• używania jednego klucza bez planu rotacji przez wiele lat.

Nie wszystkie zastosowania RSA są dziś równie rozsądne. Do podpisywania dokumentów, kodu lub certyfikatów nadal może być właściwy, zwłaszcza gdy wymaga tego kompatybilność z istniejącą infrastrukturą. W nowych protokołach wymiany kluczy częściej lepszy będzie ECDHE albo mechanizm postkwantowy. RSA nie zapewnia też sam z siebie forward secrecy. Jeżeli historyczna sesja została nagrana, a później wykradziono długoterminowy klucz używany bez mechanizmu efemerycznego, wcześniejsze dane mogą zostać odszyfrowane.

Najpoważniejsze ograniczenie ma charakter przyszłościowy. Dostatecznie duży, odporny na błędy komputer kwantowy mógłby wykorzystać algorytm Shora do efektywnej faktoryzacji dużych liczb i rozwiązywania problemu logarytmu dyskretnego. Zagroziłoby to zarówno RSA, jak i klasycznym systemom Diffiego–Hellmana oraz kryptografii krzywych eliptycznych.

Nie oznacza to, że współczesne komputery kwantowe potrafią łamać produkcyjne klucze RSA-2048. Nie potrafią. Błędem byłoby jednak czekanie na moment, w którym taka możliwość stanie się praktyczna. Migracja kryptograficzna w banku, urzędzie, szpitalu lub dużym systemie przemysłowym może potrwać kilka lat.

Od 2024 roku dostępne są pierwsze finalne standardy kryptografii postkwantowej NIST:

• ML-KEM do ustanawiania wspólnego sekretu;
• ML-DSA do podpisów cyfrowych;
• SLH-DSA jako podpis oparty na funkcjach skrótu.

Algorytmy te nie opierają bezpieczeństwa na faktoryzacji dużych liczb pierwszych. ML-KEM i ML-DSA bazują na problemach związanych z kratami matematycznymi, a SLH-DSA na konstrukcjach haszowych. Mają inne rozmiary kluczy, podpisów i szyfrogramów niż RSA czy kryptografia krzywych eliptycznych. Wdrożenie wymaga więc testów wydajności, zgodności protokołów, limitów transmisji i sposobu przechowywania kluczy.

Dla organizacji przechowujących dane przez 10–20 lat istotny jest scenariusz „zbierz teraz, odszyfruj później”. Atakujący może dziś przechwycić zaszyfrowany ruch i zachować go do czasu powstania komputera zdolnego złamać klasyczną kryptografię asymetryczną. Szczególnie dotyczy to dokumentacji medycznej, tajemnic przedsiębiorstwa, danych administracji publicznej i materiałów badawczych.

Rozsądna migracja nie polega na natychmiastowym usunięciu RSA ze wszystkich systemów. Najpierw trzeba przygotować inwentaryzację:

• gdzie powstają klucze;
• które aplikacje używają RSA, ECDH lub ECDSA;
• jak długo informacje muszą pozostać poufne;
• czy biblioteki obsługują algorytmy postkwantowe;
• czy urządzenia sieciowe przyjmą większe certyfikaty, klucze i podpisy;
• czy system umożliwia zmianę algorytmu bez przebudowania całej aplikacji.

Najbardziej irytującym etapem zwykle nie jest wymiana samego algorytmu. Problemem są stare urządzenia, zaszyte na stałe formaty danych, certyfikaty z wieloletnim okresem ważności oraz zależności, których nikt wcześniej nie zinwentaryzował.

FAQ

Czy każda liczba pierwsza nadaje się do kryptografii?
Nie. Małe liczby można szybko sprawdzić i rozłożyć, a liczby generowane przewidywalnie nie zapewniają bezpieczeństwa. Potrzebne są odpowiednio długie, losowe i niezależne liczby spełniające wymagania danego standardu.

Czy RSA-2048 jest nadal bezpieczne?
Przy prawidłowej implementacji RSA-2048 nadal jest używane i nie jest praktycznie łamane przez znane klasyczne metody. Dla nowych systemów o długim okresie eksploatacji lepiej rozważyć RSA-3072, krzywe eliptyczne albo rozwiązania przygotowane do migracji postkwantowej.

Czy RSA-4096 zawsze jest lepsze od RSA-3072?
Nie. Daje większy margines bezpieczeństwa, ale zwiększa rozmiar kluczy i podpisów oraz obciążenie procesora. W wielu zastosowaniach RSA-3072 zapewnia rozsądniejszy kompromis między bezpieczeństwem, kompatybilnością i wydajnością.

Czy można samodzielnie napisać generator kluczy RSA?
Można jako ćwiczenie edukacyjne, lecz nie należy używać takiego kodu do ochrony prawdziwych danych. Najtrudniejsze są nie wzory, ale losowość, testy parametrów, ochrona przed wyciekami bocznymi, kodowanie OAEP lub PSS oraz bezpieczne zarządzanie pamięcią.

Czy HTTPS zawsze wykorzystuje RSA?
Nie. Współczesne połączenia TLS zwykle ustanawiają klucz sesji za pomocą efemerycznego mechanizmu ECDHE, a dane szyfrują algorytmem symetrycznym. RSA może nadal pojawiać się w certyfikacie i podpisie, ale nie musi służyć do wymiany klucza.

Czy komputer kwantowy już dziś złamie RSA-2048?
Nie. Dostępne komputery kwantowe nie mają skali ani odporności na błędy potrzebnych do takiego ataku. Ryzyko jest jednak poważne dla danych wymagających wieloletniej poufności, dlatego migrację należy planować przed pojawieniem się odpowiednio silnych maszyn.

Czy liczby pierwsze znikną z kryptografii po przejściu na algorytmy postkwantowe?
Nie znikną z matematyki ani ze wszystkich systemów, ale faktoryzacja dużych liczb przestanie być właściwym fundamentem ochrony przed przeciwnikiem dysponującym komputerem kwantowym. Nowe algorytmy opierają bezpieczeństwo na innych problemach obliczeniowych.

Pierwszym krokiem nie powinno być zwiększanie klucza z 2048 do 4096 bitów. Najpierw trzeba sprawdzić, gdzie organizacja używa RSA, kto kontroluje klucze prywatne, jakie schematy dopełnienia są aktywne i jak długo chronione dane mają pozostać tajne. Jeżeli klucz znajduje się w repozytorium, kopii zapasowej bez kontroli dostępu albo aplikacja stosuje surowe RSA, to właśnie ten błąd należy usunąć jako pierwszy. Dłuższy moduł nie naprawi wadliwej implementacji.