Szyfrowanie RSA jest podstawą bezpiecznej komunikacji w Internecie. Jest to rodzaj kryptografii klucza publicznego, który chroni wiadomości e-mail, transakcje cyfrowe i wrażliwe dane przesyłane przez sieci. Algorytm nosi imię jego twórców: Ronalda L. Rivesta, Adi Shamira i Leonarda Adlemana. Opracowali ten system, pracując jako wykładowca w Massachusetts Institute of Technology.
Bezpieczeństwo RSA opiera się na prostej przeszkodzie matematycznej, którą można łatwo utworzyć, ale prawie niemożliwą do odwrócenia. Użytkownik zaczyna od wybrania dwóch dużych liczb pierwszych, p i q. Liczby te są tak duże, że pomnożenie ich w celu uzyskania n jest trywialne, ale rozłożenie n na czynniki przez p i q jest obliczeniowo niemożliwe.
Pomyśl o tym w ten sposób: pomnożenie dwóch ogromnych liczb zajmuje ułamek sekundy. Próbujesz dowiedzieć się, które dwie liczby zostały pomnożone, aby uzyskać ten wynik? Przy nowoczesnej technologii może to zająć miliardy lat.
Od 2015 r. standardy bezpieczeństwa rządu USA wymagają, aby n miało co najmniej 2048 bitów. W formie dziesiętnej oznacza to, że p i q mają po około 308 cyfr, co daje 617-cyfrową liczbę dla n. Największe liczby, które pomyślnie rozłożyliśmy na czynniki, mają tylko połowę tego rozmiaru. Złożoność faktoryzacji z grubsza podwaja się z każdymi dodatkowymi trzema cyframi modułu. Ten wykładniczy wzrost złożoności gwarantuje, że klucze składające się z 617 znaków będą chronione przed atakami typu brute-force przez dziesięciolecia.
Mechanika generowania kluczy
Po wybraniu p i q system generuje klucze publiczny i prywatny. Użytkownik wybiera liczbę całkowitą e mniejszą niż n. Liczba ta musi być liczbą względnie pierwszą iloczynu (p – 1) i (q – 1). Krótko mówiąc, e nie ma z tym produktem żadnych wspólnych czynników poza 1.
Ten konkretny wybór gwarantuje istnienie kolejnej liczby d. Jeśli pomnożysz e przez d i podzielisz przez najmniejszą wspólną wielokrotność (p – 1) i (q – 1), reszta wyniesie 1.
Znalezienie d jest łatwe, jeśli znasz p i q. Algorytm Euklidesa oblicza to w kilka chwil. Ale jeśli nie znasz p i q, znalezienie d z e jest tak trudne, jak rozłożenie na czynniki n. Ta złożoność stanowi całą podstawę bezpieczeństwa kryptograficznego RSA.
Bezpieczeństwo RSA to nie magia; to jest matematyka. W szczególności jest to asymetria pomiędzy łatwym mnożeniem a niemożliwą faktoryzacją.
Klucze publiczne a klucze prywatne
Etykiety d i e opisują funkcje, a nie ścisłe role. Klucze są wymienne. Ta elastyczność pozwala RSA wykonywać dwa różne zadania: prywatność i uwierzytelnianie.
Aby utworzyć kanał prywatności, użytkownik A publikuje e i n w katalogu publicznym. Użytkownik A utrzymuje d w tajemnicy. Kiedy ktoś chce wysłać prywatną wiadomość do A, konwertuje ją na liczby mniejsze niż n i szyfruje ją za pomocą e i n. Tylko A może go odszyfrować, ponieważ tylko A jest właścicielem d. Założeniem — i mocnymi dowodami — jest to, że nikt inny nie jest w stanie odszyfrować komunikatu bez uwzględnienia n.
Uwierzytelnianie działa inaczej. Użytkownik A publikuje d i n i utrzymuje e w tajemnicy. Użytkownik B chce się upewnić, że komunikuje się z A. B wysyła wiadomość weryfikacyjną do A. Jeśli A zwróci zaszyfrowaną wersję za pomocą e, B może ją odszyfrować, używając zwykłego tekstu d. Jeśli odszyfrowana wiadomość pasuje do wiadomości testowej, B wie, że nadawca jest właścicielem e. Ponieważ tylko A ma e, tożsamość jest potwierdzona.
Podpisy cyfrowe i haszowanie
Podpis cyfrowy dodaje warstwę złożoności. Wymaga silnej kryptograficznie funkcji skrótu. Jest to funkcja publiczna, która kompresuje dowolną wiadomość w mniejszą sumę kontrolną (skrót). Każdy fragment podsumowania zależy od każdego fragmentu oryginalnej wiadomości. Zmień jeden bit w oryginalnej wiadomości, a około połowa bitów w skrócie ulegnie zmianie.
Silny kryptograficznie skrót uniemożliwia obliczeniowo znalezienie wiadomości, która daje określoną, wcześniej przypisaną sumę kontrolną. Utrudnia to również znalezienie innej wiadomości o tej samej sumie kontrolnej, co znana.
Aby podpisać wiadomość, A szyfruje skrót swoim sekretem e i dołącza go do wiadomości. Sama wiadomość nie musi być tajna. Każdy może użyć klucza publicznego d A do odszyfrowania podpisu i odzyskania skrótu. Następnie niezależnie obliczają skrót odebranej wiadomości. Jeśli oba skróty są zgodne, podpis jest ważny. Tylko A może zaszyfrować skrót, ponieważ tylko A zna e.
Rzeczywistość hybrydowa
To bezpieczeństwo ma swoją cenę. Szyfrowanie asymetryczne wymaga znacznie więcej obliczeń niż szyfrowanie symetryczne (jednokluczowe). Wysokie zużycie procesora radykalnie zmniejsza przepustowość. Przez około 20 lat algorytmy jednokluczowe osiągały od 1000 do 10 000 razy większą przepustowość niż algorytmy dwukluczowe przy porównywalnym poziomie bezpieczeństwa.
Ponieważ RSA jest powolny, rzadko używa się go do bezpośredniego szyfrowania dużych ilości danych. Zamiast tego zasila systemy hybrydowe. RSA obsługuje większość prac związanych z uwierzytelnianiem i podpisem cyfrowym. Bezpiecznie wymienia również losowo wygenerowany klucz sesyjny. Po przesłaniu tego klucza system przełącza się na algorytm jednoklawiszowy w celu szybkiej transmisji rzeczywistych danych. Po zakończeniu sesji klucz jest odrzucany.
To połączenie daje nam to, co najlepsze z obu światów. Otrzymujemy bezpieczną wymianę kluczy za pomocą kryptografii klucza publicznego i szybkości szyfrowania symetrycznego dla większości naszych danych.
Matematyka trzyma poziom. Klucze pozostają bezpieczne. Jednak wraz ze wzrostem mocy obliczeniowej zmienia się definicja „dużej” liczby. To, czego dzisiaj nie da się zhakować, jutro może okazać się problemem możliwym do rozwiązania. Kontynuujemy tworzenie większych liczb pierwszych. Nadal mamy nadzieję, że różnica między łatwym mnożeniem a złożoną faktoryzacją pozostanie wystarczająco duża, aby chronić nasze cyfrowe życie.
