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 2
Jednokierunkowa funkcja z zapadką. Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
Rozwiązanie znalazł inny brytyjski matematyk
i kryptograf, Clifford Cocks. Musiał opracować specjalny rodzaj
funkcji jednokierunkowej, tzw. jednokierunkową
funkcję zapadkową. To funkcja, którą łatwo obliczyć
w jednym kierunku, ale trudno odwrócić, chyba że ma się specjalną
informację zwaną zapadką. W tym celu skorzystał
z potęgowania modularnego, które wprowadziliśmy przy omawianiu
protokołu Diffiego-Hellmana. Wybierzcie liczbę,
podnieście ją do którejś potęgi, podzielcie przez moduł,
a reszta będzie stanowić wynik. Można to wykorzystać
do zaszyfrowania wiadomości: wyobraźcie sobie, że Bob ma wiadomość,
którą zamienia na liczbę, m. Mnoży tę liczbę
przez siebie samą e razy, gdzie e jest publicznym wykładnikiem, a potem dzieli wynik
przez losową liczbę N. I wynikiem jest reszta z dzielenia. Ten wynik to liczba c.
Łatwo to obliczymy, jednak jeśli znamy tylko c, e i N, znacznie trudniej będzie nam
określić, którego m użyto. Musielibyśmy zastosować
metodę prób i błędów. To funkcja jednokierunkowa,
którą możemy zastosować do m. Łatwo wykonać, trudno odwrócić.
To nasz matematyczny zamek. A co z kluczem? Jest zapadką, informacją, która ułatwia deszyfrowanie. Musimy podnieść c
do innej potęgi, powiedzmy, d, która odwróci pierwszą operację
zastosowaną do m i przywróci oryginalną wiadomość m. Obie operacje razem
sprowadzają się do tego, co m do potęgi e
i wszystko razem do potęgi d. A to przecież to samo,
co m do potęgi e razy d. Liczba e odpowiada szyfrowaniu,
zaś d – deszyfrowaniu. Alicja potrzebuje sposobu,
żeby zbudować e oraz d, trudne do wyznaczenia
dla wszystkich innych osób. Wymaga to drugiej
funkcji jednokierunkowej, używanej do wygenerowania d.
Cocks zwrócił się ku Euklidesowi.