wstęp do kryptografii

Wstęp do kryptografii. Tajemnica liczb pierwszych.

Długość wpisu: 5-7 minut

Czego się dowiesz:

  • liczba pierwsza
  • spirala Ulama
  • rozkład na czynniki pierwsze
  • Protokół Diffiego-Hellmana

Liczba pierwsza to taka, której nie można już dalej podzielić. Odpowiednik atomu w świecie liczb. Niby nie jest to nic wielkiego, jednak okazuje się, że liczby te mają ciekawe właściwości, które pozwalają wykorzystać je np. do kryptografii. Kryptografia zajmuje się zabezpieczeniem informacji przed niepowołanym dostępem.

Wracając do liczb pierwszy i ich właściwości: pewien polski matematyk, Stanisław Ulam, zaprojektował graficzny obraz rozkładu liczb pierwszych zwany „spiralą Ulama”. Rozpisuje on liczby po kolei, spiralnie, obok siebie i zaznaczając liczby pierwsze np. innym tłem, ukazuje się niewyjaśnione do dziś zjawisko.

wstęp do kryptografii

To zjawisko obrazuje pewną prawidłowość w rozkładzie liczb pierwszych na spirali Ulama. Na niektórych przekątnych liczby pierwsze grupują się częściej niż na innych.

Euklides odkrył, że każdą liczbę naturalną można dzielić, aż do osiągnięcia najmniejszych, niepodzielnych czynników. Te czynniki będą zawsze liczbami pierwszymi. Każdą liczbę naturalną zatem można wyrazić jako mniejszą grupę liczb pierwszych. Niezależnie od tego, jakiej liczby byśmy nie wybrali, zawsze można ją złożyć z liczb pierwszych. To jest podstawowe twierdzenie arytmetyki.

Jeżeli weźmiemy dowolną liczbę naturalną, np. 30 i znajdziemy wszystkie liczby pierwsze, przez które dzieli się ona bez reszty, czyli 2, 3 i 5, to jest to rozkład na czynniki pierwsze. Mnożąc te czynniki określoną liczbę razy, orzymamy ponownie 30.

Dla 30 każdy czynnik wystarczy przemnożyć raz. Nie da się zbudować 30 przy użyciu innych liczb pierwszych mnożonych przez siebie. To jest właśnie klucz do zbudowania tej danej cyfry. Nigdy się on nie powtarza. Każda liczba ma jeden i tylko jeden taki klucz.

Do czego można użyć takiego klucza?

Jednym z najprostszych metod szyfrowania jest szyfr nazywany „Szyfrem Cezara„. Polega on na przypisaniu każdej literze alfabetu odpowiadającą mu kolejną liczbę. Następnie, aby zaszyfrować wiadomość, potrzebny jest klucz. Poniżej przykład jak zaszyfrować słowo „szyfr” z kluczem 3 oraz 6.

Mając już metodę szyfrowania, pozostaje pytanie jak uzgodnić klucz zakładając, że całość korespondencji będzie podsłuchiwana?

Z pomocą przychodzi matematyka i funkcja jednokierunkowa. Jest to taka funkcja, która jest prosta w jedną stronę, a trudna w drugą. Na przykład łatwo jest zmieszać dwa kolory ze sobą, ale trudno jest odzyskać początkowe dwa kolory z tak uzyskanej mieszaniny. Wiedząc o liczbach pierwszy to, co wyżej zostało napisane, można zrobić następujące działanie (uwaga matematyka).

mod – modulo, czyli reszta z dzielenia np. reszta z dzielenia 10 : 4 to dwa

s – oznacza uzgodniony klucz

Protokół Diffiego-Hellmana

Taką korespondencję można podsłuchać, a klucz nadal zostanie tajny, gdyż odwrócenie tej funkcji jednokierunkowej jest niepraktyczne – trwałoby długo. Znając już klucz można posłużyć się nim do przesunięcia Szyfru Cezara, co jest jak na dzisiejsze czasy dość archaiczną metodą, ale… z dziećmi można się pobawić w agentów, a przy okazji pokazać możliwości liczb pierwszych. Będzie to dla nich dobry wstęp do kryptografii.

Sprawdź też wpis Algorytmy – wprowadzenie