Na czym polega RSA
Za każdym razem, gdy przeglądarka pokazuje kłódkę, wiadomość zostaje podpisana albo program sprawdza aktualizację, działa kryptografia klucza publicznego, a RSA jest jej najbardziej znaną odmianą. Jej idea polega na tym, że klucz, który zamyka wiadomość, można opublikować, a klucz, który ją otwiera, pozostaje prywatny. Co niezwykłe, cały system opiera się na arytmetyce ze szkoły: liczbach pierwszych, mnożeniu i resztach z dzielenia.
Problem, który rozwiązuje RSA
Starsze szyfry, od przesunięcia Cezara po współczesny AES, używają tego samego klucza do zamykania i otwierania, więc obie strony muszą najpierw prywatnie uzgodnić tajny klucz. Kryptografia klucza publicznego usuwa ten krok. Każdy ma dwa klucze: klucz publiczny, którego każdy może użyć, by zaszyfrować wiadomość do niego, i klucz prywatny, który ma tylko on i który jako jedyny pozwala ją odszyfrować. Whitfield Diffie i Martin Hellman opisali ten pomysł w 1976 roku, a rok później Ron Rivest, Adi Shamir i Leonard Adleman z MIT znaleźli sposób, by go zrealizować, nazwany RSA od ich inicjałów.
Tworzenie kluczy
Wybierz dwie duże liczby pierwsze p i q i pomnóż je: n = p × q. Oblicz φ(n) = (p − 1)(q − 1), funkcję Eulera, która mówi, ile liczb mniejszych od n nie ma z nim wspólnego dzielnika. Wybierz wykładnik publiczny e, który nie ma wspólnego dzielnika z φ(n); zwykle wybiera się 65537. Następnie znajdź wykładnik prywatny d taki, że e × d daje resztę 1 z dzielenia przez φ(n). Rozszerzony algorytm Euklidesa robi to szybko. Kluczem publicznym jest para (e, n), kluczem prywatnym d. Dla p = 61 i q = 53 daje to n = 3233, φ(n) = 3120, e = 17 i d = 2753.
Szyfrowanie i odszyfrowywanie
Wiadomość najpierw zamienia się na liczbę m mniejszą od n. Aby ją zaszyfrować, oblicz c = mᵉ mod n, czyli resztę z dzielenia mᵉ przez n. Aby odszyfrować, oblicz cᵈ mod n. Twierdzenie Eulera gwarantuje, że daje to z powrotem m, bo e × d jest o jeden większe od wielokrotności φ(n). Przy powyższych kluczach litera A, kod 65, staje się 65¹⁷ mod 3233 = 2790, a 2790²⁷⁵³ mod 3233 znów daje 65. Tak dużych potęg nigdy się nie wypisuje: wielokrotne podnoszenie do kwadratu oblicza je z jednym podniesieniem do kwadratu na każdy bit wykładnika, biorąc resztę na każdym kroku.
Podpisy cyfrowe
RSA działa też w odwrotnym kierunku. Podniesienie wiadomości do wykładnika prywatnego, s = mᵈ mod n, daje podpis, który może złożyć tylko właściciel klucza. Każdy może go sprawdzić kluczem publicznym: jeśli sᵉ mod n daje z powrotem m, wiadomość pochodzi od posiadacza d i nie została po drodze zmieniona. W praktyce podpisuje się krótki skrót (hash) wiadomości, a nie samą wiadomość. Takie podpisy chronią aktualizacje oprogramowania, bezpieczne witryny i dokumenty elektroniczne.
Dlaczego jest bezpieczny
Każdy widzi n i e. Aby znaleźć d, atakujący potrzebuje φ(n), a aby znaleźć φ(n), potrzebuje p i q, więc złamanie RSA sprowadza się do rozłożenia n na czynniki. Pomnożenie dwóch liczb pierwszych zajmuje komputerowi ułamek mikrosekundy; rozłożenie iloczynu z powrotem na nie uważa się za niezwykle trudne. Największa dotąd rozłożona liczba z wyzwania RSA, RSA-250 w 2020 roku, ma 829 bitów, a jej faktoryzacja zajęła około 2700 lat pracy komputera. Używane dziś klucze mają co najmniej 2048 bitów, czyli około 617 cyfr.
Sekret odkryty dwukrotnie
W 1973 roku, cztery lata przed RSA, brytyjski matematyk Clifford Cocks znalazł ten sam schemat, pracując w agencji wywiadowczej GCHQ, i oparł się przy tym na pomyśle swojego kolegi Jamesa Ellisa. Praca była tajna i ujawniono ją dopiero w 1997 roku. Sam algorytm RSA opatentowano w Stanach Zjednoczonych w 1983 roku; patent wygasł we wrześniu 2000 roku, dwa tygodnie po tym, jak algorytm przekazano do domeny publicznej.
RSA w praktyce
W praktyce RSA nigdy nie szyfruje tekstu bezpośrednio. Wiadomość dopełnia się losowymi bajtami według schematu takiego jak OAEP, aby ta sama wiadomość za każdym razem szyfrowała się inaczej i żadne wzorce nie mogły wyciec. Ponieważ RSA jest powolny, służy głównie do wymiany lub ochrony krótkiego klucza dla szybkiego szyfru symetrycznego, takiego jak AES, albo do podpisywania. Odpowiednio duże komputery kwantowe mogłyby szybko rozłożyć n na czynniki algorytmem Shora z 1994 roku, dlatego obok RSA wprowadza się nowe metody postkwantowe.
Wypróbuj
Otwórz demonstrację szyfrowania RSA, aby budować klucze z własnych liczb pierwszych albo z losowych, od 2 do 8 cyfr, oglądać, jak rozszerzony algorytm Euklidesa wiersz po wierszu znajduje d, szyfrować lub podpisywać wiadomość znak po znaku i śledzić wielokrotne podnoszenie do kwadratu dla dowolnego znaku. Potem pozwól Eve rozłożyć n na czynniki i zobacz, jak potrzebny jej czas rośnie wraz z rozmiarem liczb pierwszych.
Często zadawane pytania
Dlaczego RSA potrzebuje liczb pierwszych?
Bo φ(n) łatwo obliczyć tylko wtedy, gdy wiadomo, jak n rozkłada się na czynniki pierwsze. Dla n = p × q, gdzie p i q są pierwsze, φ(n) = (p − 1)(q − 1). Liczby pierwsze sprawiają też, że n jest możliwie najtrudniejsze do rozłożenia jak na swój rozmiar, bo nie ma w ogóle małych dzielników.
Dlaczego e to często 65537?
65537 = 2¹⁶ + 1 jest liczbą pierwszą i ma w zapisie dwójkowym tylko dwie jedynki, więc szyfrowanie z jej użyciem wymaga tylko 16 podniesień do kwadratu i jednego mnożenia. Jest też na tyle duża, by uniknąć słabości bardzo małych wykładników, takich jak 3.
Czym różni się RSA od wymiany kluczy Diffiego-Hellmana?
Wymiana Diffiego-Hellmana pozwala dwóm osobom uzgodnić wspólny tajny klucz przez otwarty kanał; sama niczego nie szyfruje ani nie podpisuje. RSA szyfruje i podpisuje bezpośrednio za pomocą pary kluczy. Oba opierają się na problemach łatwych w jedną stronę i trudnych w drugą: RSA na rozkładzie na czynniki, Diffie-Hellman na logarytmie dyskretnym.
Czy kluczy z tej demonstracji można używać do prawdziwego szyfrowania?
Nie. Jej liczby pierwsze mają najwyżej dwanaście cyfr, więc każdy utworzony przez nią klucz można rozłożyć na czynniki w kilka sekund lub szybciej, a każdy znak jest szyfrowany osobno, bez dopełnienia. Służy do tego, by zobaczyć, jak działa RSA, a nie do ochrony czegokolwiek.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Otwórz demonstrację szyfrowania RSA