Szyfrowanie RSA: Matematyka Wielkich Liczb Pierwszych

Klucze publiczne i pułapka z faktoryzacją

Przed RSA bezpieczna komunikacja wymagała współdzielonego sekretu, który trzeba było wymieniać osobiście. Kryptografia kluczem publicznym, opublikowana przez Rivesta, Shamira i Adleman w 1977 roku, eliminuje to: każdy publikuje klucz publiczny, którym każdy może użyć do zablokowania wiadomości, ale tylko posiadacz dopasowanego klucza prywatnego może go odblokować. Zablokowanie jest jednokierunkowe – łatwe do zastosowania, obliczeniowo niemożliwe do odwrócenia – dzięki pułapce z faktoryzacją liczb całkowitych: mnożenie dwóch dużych liczb pierwszych jest natychmiastowe, ale rozkład ich iloczynu na czynniki uważa się za wymagający wykładniczego czasu w liczbie cyfr. Wszystkie operacje arytmetyczne odbywają się modulo n, "arytmetyka zegarowa", gdzie liczy się tylko reszta, co tworzy skończoną grupę cykliczną, w której potęgowanie jest łatwe, ale odwrotne (logarytm dyskretny) jest trudne.

Twierdzenie Eulera i generowanie kluczy

Serce RSA opiera się na twierdzeniu Eulera: dla dowolnego m będącego liczbą pierwszą względnie prostą z n, m^φ(n) ≡ 1 (mod n), gdzie φ(n) oznacza funkcję Eulerską – liczbę naturalną do n będącą liczbą pierwszą względną z n. Dla n = p×q (dwóch różnych liczb pierwszych), φ(n) = (p−1)(q−1), a jej obliczenie wymaga znajomości czynników pierwszych – kluczowe spostrzeżenie, które zapewnia bezpieczeństwo RSA. Generowanie kluczy: wybierz dwie duże, różne liczby pierwsze p, q (każda o przybliżonej wartości 617 cyfr dziesiętnych dla RSA o długości 2048 bitów); oblicz n = p×q i φ(n); wybierz publiczny wykładnik e będący liczbą pierwszą względną z φ(n), zwykle e = 65537; oblicz prywatny wykładnik d = e⁻¹ mod φ(n) za pomocą Rozszerzonego Algorytmu Euklidesa; opublikuj (n, e) i zachowaj (n, d) w tajemnicy, zniszczając p, q oraz φ(n).

Szyfrowanie, odszyfrowywanie i jak to działa

Aby zaszyfować wiadomość m < n przy kluczu publicznym, oblicz c = mᵉ mod n. Aby ją odszyfrować, oblicz m = c^d mod n — a ponieważ ed ≡ 1 (mod φ(n)), twierdzenie Eulera gwarantuje, że m^(ed) ≡ m (mod n), dzięki czemu oryginalna wiadomość wraca dokładnie. Przykładowy, prosty przykład: p=61, q=53, n=3233, φ(n)=3120, e=17, d=2753. Zaszyfrowanie m=65 daje c = 65¹⁷ mod 3233 = 2790, a odszyfrowanie 2790²⁷⁵³ mod 3233 zwraca 65.

n = p·q             φ(n) = (p−1)(q−1)         e·d ≡ 1 (mod φ(n))
Encrypt:  c = m^e mod n        Decrypt:  m = c^d mod n
2048-bit RSA GNFS factoring time: ~10^18 years on today's fastest hardware

Bezpieczeństwo współczesne, a zagrożenie kwantowe

Najlepsza znana klasyczna metoda ataku, Algorytm Ogólnego Pola Liczbowego, zajęłoby około 10¹⁸ lat na sfałdowanie modułu 2048-bitowego na najszybszym komputerze na świecie — RSA-2048 stanowi obecnie standard certyfikatów TLS, a RSA-4096 oferuje margines bezpieczeństwa na dziesięciolecia. Kryptografia krzywowopłaszczowa osiąga równy poziom bezpieczeństwa przy znacznie krótszych kluczach (ECC-256 ≈ RSA-3072), dlatego TLS 1.3 preferuje ECDHE do wymiany kluczy. Rzeczywiste, długoterminowe zagrożenie stanowi kwantowość: algorytm Shore'a sfałdowanie liczb całkowitych w czasie wielomianowym na wystarczająco dużym komputerze kwantowym, a złamanie RSA-2048 szacuje się na 4000+ kubitów logicznych w porównaniu z dzisiejszymi około 1000 kubitami fizycznymi. NIST zdefiniował algorytmy post-kwantowe oparte na siatkach — ML-KEM i ML-DSA — w 2024 roku jako zabezpieczenie przed tym przyszłym zagrożeniem.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz the simulation i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.