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 3
Szyfrowanie RSA (krok 3). Stworzone przez: Brit Cruise.
Chcesz dołączyć do dyskusji?
Na razie brak głosów w dyskusji
Transkrypcja filmu video
Ponad 2000 lat temu Euklides wykazał,
że każda liczba ma dokładnie jeden rozkład na czynniki
pierwsze. Uznajmy go za tajny klucz. Okazuje się, że rozkład na czynniki
pierwsze to trudny problem. Wyjaśnijmy, co rozumiemy
przez „łatwy” i „trudny”, wprowadzając pojęcie
tzw. złożoności czasowej. Każdy z nas mnożył liczby i ma własne sposoby,
żeby to przyspieszyć. Odpowiednio zaprogramowany komputer będzie mnożył liczby
znacznie szybciej niż człowiek. Na wykresie przedstawiono
czas potrzebny komputerowi do pomnożenia dwu liczb. Czas potrzebny
do znalezienia odpowiedzi wydłuża się wraz ze wzrostem liczb. Zauważcie, że czas obliczeniowy jest znacznie krótszy od sekundy
nawet przy dużych liczbach. Dlatego wykonanie jest „łatwe”. Porównajmy to z rozkładem
na czynniki pierwsze. Gdyby ktoś kazał wam
rozłożyć liczbę 589, od razu byście wiedzieli,
że będzie trudno. Niezależnie od obranej strategii, metodą prób i błędów
będziecie szukać liczby, przez którą
bez reszty dzieli się 589. Pomęczycie się trochę i ustalicie,
że ten rozkład to 19 razy 31. Gdyby kazano wam rozłożyć
na czynniki pierwsze liczbę 437231, zapewne poddalibyście się
i zaprzęgli do pomocy komputer. Uda się to przy małych wartościach, ale gdy każemy komputerowi
rozkładać coraz większe liczby, wystąpi efekt lawiny. Czas potrzebny do wykonania obliczeń będzie rósł bardzo szybko,
bo jest więcej etapów. W miarę wzrostu liczb, komputer
będzie potrzebował minut, godzin… aż wreszcie - setek lub tysięcy lat, by przeprowadzić
rozkład ogromnych liczb. Dlatego zadanie nazwiemy trudnym, z powodu czasu potrzebnego
na znalezienie rozwiązania. Rozkładu na czynniki pierwsze
użył Cocks w rozwiązaniu zapadkowym. Krok pierwszy: że Alicja losowo
wygenerowała liczbę pierwszą o długości ponad 150 cyfr.
Nazwijmy ją P1. Wygenerowała kolejną liczbę pierwszą,
podobnej wielkości; nazwiemy ją P2. Teraz mnoży te liczby pierwsze i uzyskuje liczbę złożoną N, mającą ponad 300 cyfr. Mnożenie potrwa mniej niż sekundę; poradzi sobie z nim
nawet przeglądarka internetowa. Potem Alicja
bierze czynniki pierwsze N, czyli P1 razy P2, i ukrywa je. Gdyby podała komuś N, przez wiele lat
komputerowo szukałby rozwiązania. Krok drugi:
Cocks musiał znaleźć funkcję, która zależy od tego, czy znamy
rozkład N na czynniki pierwsze. Sięgnął więc do opublikowanej
w 1760 roku pracy szwajcarskiego matematyka
Leonharda Eulera.