Nowości z przeszłości

Stara Delta

Uniwersalny szyfr

W naszych czasach coraz więcej rzeczy staje się tajnych. To dlatego, że nasze życie jest coraz bardziej uzależnione od setek i tysięcy drobiazgów, a kontrolę nad nimi każdy chce zachować dla siebie. Przyjdzie może czas, kiedy na posiadanie tablic logarytmicznych wymagane będzie zezwolenie. Żarty? Mam nadzieję. Na razie grozi nam utajnienie tablic rozkładów liczb na czynniki pierwsze. A oto dlaczego...

Każdy szyfr ma jedną zasadniczą wadę: jeżeli znamy sposób szyfrowania, to i deszyfrowania. Dlatego im więcej osób może przesyłać nam zaszyfrowane wiadomości, tym łatwiej policja rozpracuje naszą siatkę. Nawet, gdy używamy tak doskonałego szyfru, jak ten opisany w przygodach dzielnego wojaka Szwejka (tom III, "Przesławne lanie"). Każdy z nas bez wahania założyłby się, że znajomość sposobu szyfrowania umożliwia odczytanie każdej zaszyfrowanej wiadomości. A tymczasem rzecz ma się trochę inaczej. Oto jak grupa osób może ustalić system szyfrów tak, by

każda z osób mogła ogłosić publicznie (na przykład w gazecie): adresowane do mnie wiadomości proszę szyfrować tak a tak. Szyfrowaną wiadomość (adresowana do jednej z osób tej grupy) może wysłać dowolna, niekoniecznie wtajemniczona osoba. Dowolna osoba może ogłosić: przystępuję do spółki; proszę przeznaczone dla mnie wiadomości szyfrować tak a tak,
oraz by zaszyfrowanego komunikatu nie mógł odczytać nikt poza adresatem.

Do zbudowania takiego szyfru posłużono się teorią liczb. Oto nieskomplikowane twierdzenie:

Twierdzenie. Jeżeli liczba naturalna $N$ jest iloczynem dwu liczb pierwszych $|p,q,$ to dla $|M= (p − 1)(q − 1)+ 1$ i dla każdego $n < N$ zachodzi

nM ≡ n(mod N);

tj. $M n$ oraz $|n$ dają z dzielenia przez $|N$ tę samą resztę.

Każda z osób, chcących mieć własny szyfr, wybiera sobie dwie dość duże liczby pierwsze (co najmniej kilkudziesięciocyfrowe) $p,q,$ oblicza ich iloczyn $N,$ oraz liczbę $M = (p− 1)(q −1) +1.$ Do wiadomości ogólnej podaje $|N$ i pewien dzielnik liczby $M,$ oznaczmy go przez $.K$ Dla siebie zachowuje rozkład $N$ na $p$ i $|q$ oraz liczbę $|M.$ Gdy nadawca NAD chce wysłać wiadomość do odbiorcy ODB, postępuje tak. Zamienia tekst słowny na ciąg cyfr w jakiś standardowy, ustalony i jawny sposób, np. $=1,B=2 A$ itd. Otrzymaną tak dużą liczbę (komunikat nie może być długi) podnosi do potęgi $ODB K$ i bierze resztę z dzielenia przez $N . ODB$ Potrzebna jest do tego maszyna matematyczna, ale nic ponadto. Tak zakodowaną wiadomość (będącą teraz liczbą mniejszą niż $NODB$ ) wysyła się do odbiorcy lub publikuje w gazecie. Odbiorca winien podnieść tę liczbę do potęgi $|MODB- KODB$ - otrzyma wtedy ciąg liczb wysłany przez nadawcę. Przetworzenie go na tekst słowny odbywa się we wspomniany jawny i standardowy sposób. Co w tym takiego rewelacyjnego? - zapytacie. A to, że podniesienie nawet bardzo dużej liczby do bardzo dużej potęgi $M$ jest dla maszyny matematycznej mało pracochłonne, zwłaszcza że wszystkie obliczenia robi się i tak modulo $N.$ Wynik dostaje się w ułamku sekundy. Osoba postronna nie zna jednak liczby $|M$ ; mogłaby ją obliczyć, znając $|p$ i $q.$ Ale zna tylko $N,$ równe $|pq.$ Gdy $|p$ i $q$ mają po kilkadziesiąt cyfr, $N$ ma sto kilkadziesiąt. Znalezienie rozkładu takiej liczby na czynniki nawet najszybciej działającej maszynie zajęłoby (przy obecnym stanie techniki, informatyki i organizacji maszyn cyfrowych) wiele, wiele lat pracy. Szyfr ten nie daje się złamać najgroźniejszą bronią: analizą statystyczną, rozpracowującą szybko wszystkie szyfry polegające na stałym przyporządkowaniu litera-liczba. Autorzy tego szyfru napisali (w Scientific American), że są niezbicie pewni, iż nikt nie potrafi odczytać zaszyfrowanej przez nich do samych siebie wiadomości.

Autor Nieznany

***

Komentarz współczesny

Kilka lat temu zapytałem Mordechaja "Motiego" Yunga (obecnie pracuje jako badacz naukowy w Google) o to, na ile zmienił się obraz badań naukowych z dziedziny kryptologii od czasów, gdy zaczynał, a więc od lat 80. W swej odpowiedzi (wyrażonej dość komunikatywną polszczyzną!) jako największą różnicę wskazał liczbę publikowanych prac. Stwierdził, że w początkach swojej kariery był w stanie, bez większego wysiłku, śledzić na bieżąco WSZYSTKIE artykuły dotyczące kryptologii, które ukazywały się na świecie. Dziś natomiast ciężko byłoby młodemu badaczowi przebrnąć w ciągu roku choćby przez połowę publikacji prezentowanych na jednej dużej konferencji kryptologicznej, których organizuje się przecież co najmniej kilka w roku.

Powyższa opinia Motiego dobrze koresponduje z obecnością kryptologii w Delcie. Do końca lat 80. (a więc przez 190 numerów) w Delcie ukazały się tylko dwa krótkie teksty dotyczące zagadnień kryptologicznych - oba prezentujemy w tym numerze. Wówczas była to dziedzina dostarczająca przede wszystkim eleganckich (często zaskakujących) wyników-ciekawostek, kojarzonych głównie ze sztuczkami z teorii liczb. W takim też duchu utrzymane są oba dziś prezentowane wyimki ze $|𝔖 𝔱𝔞 𝔯𝔢𝔧𝔇 𝔢𝔩𝔱𝔶.$

Oczywiście wraz z rozwojem komputerów i sieci komputerowych znaczenie kryptologii wzrosło niebotycznie. Dziś jest to ogromna gałąź informatyki teoretycznej. Również w Delcie artykułów z tej dziedziny w późniejszym okresie było znacznie więcej. Ostatnio prezentowaliśmy nawet niemal roczny cykl A jednak się da (od Delty 10/2018 do Delty 8/2019), poświęcony w całości kryptologii. Co ciekawe: oba zagadnienia z lat 80. były obecne w tym cyklu (choć autorzy wybierali tematy zupełnie niezależnie), a artykuł otwierający cykl dotyczył dokładnie tego samego tematu, co pierwszy artykuł kryptologiczny w Delcie z roku 1980!

Tomasz Kazana