Główna zawartość
Informatyka
Kurs: Informatyka > Rozdział 2
Lekcja 4: Współczesna kryptografia- Podstawowe twierdzenie arytmetyki
- Kryptografia klucza publicznego. Co to jest?
- Zagadnienie logarytmu dyskretnego
- Protokól Diffiego-Hellmana
- Szyfrowanie RSA: krok 1
- Szyfrowanie RSA: krok 2
- Szyfrowanie RSA: krok 3
- Badanie złożoności czasowej
- Funkcja φ (tocjent) Eulera
- Badanie funkcji Eulera
- Szyfrowanie RSA: krok 4
- Czego powinniśmy nauczyć się dalej?
© 2023 Khan AcademyWarunki użytkowaniapolitykę prywatnościInformacja o plikach cookie
Szyfrowanie RSA: krok 4
Przykład funkcjowowania RSA. Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
- nieogarniam nieogarniam(3 głosy)
Transkrypcja filmu video
Mamy już zapadkę do wyznaczania
wartości funkcji φ. Znając rozkład N na czynniki pierwsze,
wartość φ wyznaczycie bez trudu. Np. rozkład liczby 77 na czynniki
pierwsze to 7 razy 11, więc wartość funkcji φ dla 77
wynosi 6 razy 10, czyli 60. Krok trzeci: jak powiązać funkcję φ
z potęgowaniem modularnym? Cocks posiłkował się
twierdzeniem Eulera, które właśnie opisuje związek
między funkcją φ a potęgowaniem modularnym: Mamy: m do potęgi φ policzonej dla n jest przystające do 1 mod n. To znaczy, że możemy wybrać
dwie dowolne liczby, byle nie miały wspólnych dzielników…
Nazwijmy je „m” i „n”. Powiedzmy, że m = 5, a n = 8. Gdy podniesiemy m
do potęgi φ od n, czyli 4, i podzielimy to przez n,
to zawsze zostanie 1. Musimy tylko zmodyfikować to równanie
z pomocą dwu prostych reguł. Po pierwsze, jeśli podniesiecie
1 do dowolnej potęgi, k, to zawsze uzyskacie 1. Tak samo, możemy pomnożyć
wykładnik φ od n przez dowolną liczbę k,
a wynik zawsze będzie wynosił 1. Po drugie, jeśli pomnożycie 1
przez dowolną liczbę, np. m, zawsze wyjdzie m. Zatem możemy pomnożyć
lewą stronę przez m, żeby uzyskać m po stronie prawej. A to można uprościć do postaci: m do potęgi (k razy φ od n) plus 1. I to jest przełom. Mamy teraz równanie
do wyznaczenia e razy d, które zależy od φ od n. Zatem obliczyć d
jest łatwo tylko wtedy, gdy znamy rozkład n
na czynniki pierwsze. Czyli d powinno być
prywatnym kluczem Alicji. To zapadka, która pozwoli jej
odwrócić efekt e. Na prostym przykładzie zobaczmy,
jak to wszystko działa. Bob ma wiadomość,
którą przekształcił w liczbę z pomocą schematu dopełnienia.
Nazwijmy ją „m”. Później Alicja generuje swoje klucze,
publiczny i prywatny: najpierw generuje dwie losowe
liczby pierwsze podobnej wielkości i mnoży je, żeby uzyskać n: 3127. Potem łatwo oblicza wartość φ od n,
bo zna rozkład n na czynniki pierwsze. Uzyskuje 3016. Teraz wybiera mały wykładnik publiczny, e, przy czym musi to być
liczba nieparzysta niemająca wspólnego dzielnika
z φ od n. Wybiera e równe 3. W końcu znajduje wartość
prywatnego wykładnika, d, który w tym przypadku wynosi
2 razy φ od n, plus 1, podzielone przez 3, czyli 2011. Teraz ukrywa wszystko
poza wartościami n oraz e, bo n oraz e
tworzą jej klucz publiczny. To jakby otwarty zamek. Wysyła to Bobowi,
żeby zamknął swoją wiadomość. Bob zamyka wiadomość, obliczając m do potęgi e mod n.
Nazwijmy to „c”, jego zaszyfrowaną wiadomością,
którą wysyła do Alicji. W końcu Alicja deszyfruje wiadomość
używając prywatnego klucza, d, do którego dostała się
przez swoją zapadkę. C do potęgi d mod n jest przystające
do oryginalnej wiadomości Boba, m. Zauważcie, że Ewa lub ktoś inny,
mając c, n oraz e, wyznaczy wykładnik d tylko wtedy,
gdy może obliczyć wartość φ od n, a w tym celu musi znać
rozkład n na czynniki pierwsze. Przy dostatecznie dużym n Alicja jest pewna,
że szukanie potrwa setki lat, nawet za pomocą
najpotężniejszej sieci komputerowej. Ta metoda została utajniona
od razu po publikacji, jednak w 1977 r. niezależnie odkryli ją Ron Rivest, Adi Shamir i Len Adleman, dlatego teraz jest w kryptografii
znana pod nazwą RSA. RSA to najczęściej na świecie
używany algorytm z kluczem publicznym. I najczęściej kopiowane
oprogramowanie w historii. Każdy użytkownik Internetu
na świecie używa RSA lub jakiegoś wariantu tej metody,
świadomie czy nie. Siła algorytmu opiera się o trudność
rozkładu na czynniki pierwsze. To zaś wynika z trudnego zagadnienia
dystrybucji liczb pierwszych. Kwestia przez tysiące lat
nie doczekała się rozwiązania!