Klucze
Jak znaleźć d: rozszerzony algorytm Euklidesa
Każdy wiersz powstaje z dzielenia dwóch wierszy nad nim. W wierszu z resztą 1 ostatnia kolumna to d (jeśli jest ujemna, dodaj φ(n)).
| Iloraz | Reszta | Współczynnik przy e |
|---|
Wiadomość
Wysłane przez sieć
| Bit | Do kwadratu | Pomnóż przez m |
|---|
Łamanie klucza
Demonstracja szyfrowania RSA
RSA pozwala każdemu zamknąć wiadomość twoim kluczem publicznym, a otworzyć ją możesz tylko ty swoim kluczem prywatnym. Stoi za tym kilka linijek szkolnej arytmetyki: dwie liczby pierwsze, mnożenie, reszta z dzielenia i sprytna odwrotność. Zbuduj parę kluczy z wybranych przez siebie liczb pierwszych, zaszyfruj i odszyfruj wiadomość znak po znaku, podpisz ją, aby każdy mógł sprawdzić, że pochodzi od ciebie, a potem wciel się w atakującego i rozłóż n na czynniki, by zobaczyć, dlaczego prawdziwe klucze potrzebują setek cyfr. Wybierz dwie liczby pierwsze p i q albo naciśnij „Nowe liczby pierwsze”. Aplikacja tworzy klucz publiczny (e, n) i klucz prywatny d oraz pokazuje, jak rozszerzony algorytm Euklidesa znajduje d. Wpisz wiadomość: każdy znak jest szyfrowany kluczem publicznym i odszyfrowywany kluczem prywatnym. Kliknij wiersz, aby zobaczyć potęgę obliczoną przez wielokrotne podnoszenie do kwadratu. Przełącz na „Podpisz”, aby zamiast tego podpisywać kluczem prywatnym, i naciśnij „Rozłóż n”, aby zobaczyć, jak szybko padają małe klucze.
Jak to działa
- Wpisz dwie liczby pierwsze p i q albo wybierz rozmiar i naciśnij „Nowe liczby pierwsze”; aplikacja obliczy n, φ(n), e i d oraz pokaże, jak znajduje się d.
- Wpisz wiadomość i wybierz „Szyfruj” lub „Podpisz”. Każdy znak zamienia się w liczbę i jest podnoszony do potęgi mod n; kliknij wiersz, aby zobaczyć wielokrotne podnoszenie do kwadratu.
- Naciśnij „Rozłóż n”, aby Eve rozłożyła n na dwie liczby pierwsze i odzyskała klucz prywatny.
Jak działają klucze
Pomnóż dwie liczby pierwsze: n = p × q. Dla p = 61 i q = 53 otrzymujemy n = 3233. Liczba φ(n) = (p − 1)(q − 1) = 3120 mówi, ile liczb mniejszych od n nie ma z nim wspólnego dzielnika, i obliczyć ją może tylko ktoś, kto zna p i q. Wybierz e = 17, które nie ma wspólnego dzielnika z 3120, i znajdź d takie, że e × d jest o 1 większe od wielokrotności φ(n): tutaj d = 2753, bo 17 × 2753 = 46801 = 15 × 3120 + 1. Opublikuj (e, n) i zachowaj d dla siebie. Wiadomość m staje się c = mᵉ mod n, a twierdzenie Eulera gwarantuje, że cᵈ mod n daje z powrotem m.
Dlaczego trudno go złamać
Wszystko, czego potrzebuje atakujący, kryje się w czynnikach n. Przy n = 3233 to żadna ochrona: sprawdzanie nieparzystych dzielników znajduje 53 po mniej więcej dwudziestu kilku próbach. Ale wysiłek rośnie wraz z pierwiastkiem kwadratowym z n. Moduł o długości 2048 bitów ma około 617 cyfr i żadna znana metoda, na żadnym istniejącym dziś komputerze, nie rozłoży go na czynniki w rozsądnym czasie. Podpisywanie to RSA w odwrotnym kierunku: s = mᵈ mod n można utworzyć tylko kluczem prywatnym, a każdy może sprawdzić, że sᵉ mod n daje z powrotem m.
Często zadawane pytania
Dlaczego nikt nie może obliczyć d z klucza publicznego?
Aby znaleźć d, potrzebujesz φ(n) = (p − 1)(q − 1), a aby poznać φ(n), potrzebujesz p i q. Odzyskanie ich z n oznacza rozłożenie n na czynniki, a dla liczb o setkach cyfr nie jest znana żadna szybka metoda. Demonstracja pozwala rozkładać zabawkowe klucze w ułamku sekundy, co dokładnie pokazuje, dlaczego prawdziwe klucze są tak duże.
Dlaczego wiadomość jest szyfrowana znak po znaku?
Bo zabawkowe klucze są małe: RSA może zaszyfrować tylko liczbę mniejszą od n. Przy n = 3233 mieści się kod każdego znaku, ale całe zdanie już nie. W prawdziwych zastosowaniach RSA używa modułu o długości 2048 bitów lub więcej, dopełnia wiadomość losowymi bajtami, aby ta sama wiadomość nigdy nie była zaszyfrowana dwa razy tak samo, a w praktyce szyfruje tylko krótki klucz dla szybszego szyfru, takiego jak AES.
Co robi wielokrotne podnoszenie do kwadratu?
Oblicza ogromne potęgi, takie jak m²⁷⁵³ mod n, bez zapisywania ogromnej liczby. Zapisz wykładnik w systemie dwójkowym i przejdź przez jego bity: dla każdego bitu podnieś bieżący wynik do kwadratu, a dla każdej jedynki pomnóż go przez m, za każdym razem biorąc resztę mod n. Wykładnik o długości 2048 bitów wymaga tylko około 2048 podniesień do kwadratu.
Czym różni się szyfrowanie od podpisywania?
Szyfrowanie używa klucza publicznego odbiorcy, tak aby cofnąć je mógł tylko klucz prywatny odbiorcy. Podpisywanie używa klucza prywatnego nadawcy, tak aby każdy mógł sprawdzić podpis kluczem publicznym nadawcy i wiedzieć, że wiadomość pochodzi od posiadacza tego klucza i nie została zmieniona.
Czy moja wiadomość jest gdzieś wysyłana?
Nie. Wszystko jest obliczane w twojej przeglądarce, a twoje liczby pierwsze i wiadomość zostają w lokalnej pamięci tej przeglądarki.
Chcesz wypróbować?
Otwórz PictorX w swojej przeglądarce — do uruchomienia nie jest wymagana żadna instalacja ani karta kredytowa.
Przejdź do edytora