Szyfrowanie RSA: krok 3

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.