Skip to content

W poszukiwaniu szyfru idealnego


Nie będę tłumaczył czym jest szyfrowanie. Skoro tutaj trafiliście to znaczy, że dostrzegacie, z takiego czy innego powodu, potrzebę uczynienia pewnych informacji zupełnie nieczytelnymi dla nieuprawnionych osób.

Na przestrzeni stuleci narzędzia służące do tego celu, tj. zmiany informacji z czytelnej postaci na nieczytelną i na odwrót, zmieniały się wraz z rozwojem naukowym, technicznym i ogólnym wzrostem świadomości tego zagadnienia.


Język jako szyfr

Nie wszystko co jest nieczytelne zostało uprzednio zaszyfrowane. Aby coś zaszyfrować (a raczej ukryć), można do tego celu użyć pewnego języka znanego stronom biorącym udział w komunikacji, ale nieznanego osobom chcącym poznać treść przekazu.

  • Wojna sześciodnowa (5 czerwca 1967 -- 10 czerwca 1967)
  • Historia amerykańskich "code talkers", Indian używających m.in. języka nawaho do szyfrowanej komunikacji podczas II wojny światowej na Pacyfiku jest już dobrze znana, opowiedziana m.in. w filmie "The Windtalkers" z 2002 r. Indianie nie stworzyli szyfru. Oni porozumiewali się swoim, tylko sobie znanym, językiem.
  • Kamień z Rosetty.
    Na kamieniu wyryty został tekst dwujęzyczny w trzech wersjach –- po egipsku pismem hieroglificznym i demotycznym oraz po grecku. Tekst zapisany greką został szybko odczytany przez filologów. Ponieważ tekst grecki był znany, możliwe stało się odczytanie hieroglifów, czego dokonali w 1822 roku Jean-François Champollion i w 1823 roku Thomas Young.

Zalety:

  • Łatwość użycia (przy założeniu uprzedniej znajomości języka).

Wady:

  • Duża podatność na złamanie szyfru.

Wniosek 1:
"Szyfrowanie" przez ukrywanie może być skuteczne, ale z pewnością jest bardzo ryzykowne.


Kodowanie -- szczególny rodzaj szyfrowania

Istnieje pewien szczególny rodzaj tajnego przekazu, który z biegiem wieków stopniowo wychodził z użycia. Polega on na zastąpieniu całych słów lub zwrotów innym słowem, liczbą lub symbolem. Na przykład komnikat

Prezes założył marynarkę. Czeka na auto.

może oznaczać

Oddział komandosów zajął pozycje. Oczekuje na rozkaz rozpoczęcia ataku.

W takiej sytuacji będzimy mówić raczej o kodowaniu niż o szyfrowaniu.


Zalety:

  • Nie ma możliwości "odszyfrowania" takiego przekazu. Pod zwrotem A może być "zaszyfrowany" dowolny zwrot B, zależnie od przyjętej umowy.

Wady:

  • Zdolność do przekazywania informacji ograniczona jedynie do wcześniej ustalonego zbioru "komunikatów" -- brak uniwersalności.
  • Konieczność aktualizacji zbioru dopuszczalnych kodów.

Wniosek 2:
Metoda szyfowania powinna być tak ogólna jak tylko jest to możliwe, pozwalając szyfrować dowolne komunikaty.


Szyfry przestawieniowe

Dzisiaj zamiast kodów stosuje się szyfry. Jest to mechanizm działajcy na niższym poziomie (pojedynczych znaków zamiast słów lub zwrotów), polegający na zastąpieniu poszczegolnych znaków innymi znakami (zamiast słów innymi słowami).

Metody kryptografii (szyfrowania) dzielą się na dwie kategorie, w zależności od tego czy szyfrowanie polega na przestawieniu, czy podstawieniu.

Przestawienie polega na zmianie uporządkowania znaków tekstu, czyli stworzeniu anagramu. W przypadku krótkich wiadomości, metoda ta nie zapewnia bezpieczeństwa, ponieważ liczba wsystkich możliwych sekwencji ograniczonego zbioru liter jest stosunkowo mała. Na przykład, trzy litry można uporządkować tylko na sześć sposobów:

Jednak w miarę jak rośnie liczba znaków, liczba sekwencji gwałtownie wzrasta i odtworzenie oryginalnego tekstu staje się niemożliwe bez znajomości procedury przestawiania (obliczenia wykonane w Wolfram Alpha):

Jak więc widać, istotna jest umiejętność określenia sposbu tworzenia anagramu, gdyż bez jego znajomości otrzymujemy tekst owszem niemożliwy praktycznie do odczytania przez osobę niepowołaną, ale także i przez adresata. Musimy zatem w jakiś sposób kontrolować tworzony anagram -- mówiąc inaczej, musimy wymyślić schemat budowy anagramu, czyli skonstruować konkretny szyfr.


Szyfr płotkowy

W najprostszej postaci ta technika szyfrowania polega na zapisywaniu kolejnych znaków na zmianę w dwóch wierszach, po czym dolny wiersz dołączany jest na zakończenie górnego wiersza. Oto przykład

W metodzie można zwiększyć liczbę wierszy, na przykład do 4

Zamiast zaczynać "wpisywanie" tekstu od górnego wiersza, można od dowolnego innego (ustalonego), na przykład szyforwanie na 4 wierszach z offsetem (przesunięciem) o 5

Szyfr taki jest bardzo łatwy do złamania, szczególnie w dzisiejszych czasach, gdy mamy komputery. Spróbujmy rozszyfrować następujący szyfrogram


W szyfrogramie mamy 19 znaków. Pozwala to oszacować z góry liczbę wszystkich testów jakie należy wykonać. Przy szyfrowaniu tym sposobem sens ma tylko rozpatrywanie połowy łącznej liczby znaków zaokrąglonej w dół do liczby całkowitej, czyli w naszym przypadku 9. Maksymalne przesunięcie to 9*2-1=17. Tak więc po wykonaniu 9*17=153 testów powinniśmy znaleźć rozwiązanie. W najgorszym razie trzeba będzie wykonać 19*37=703 testów, przy czym w tym drugim przypadku już po częściowej analizie szyfrogramu można wpaść na rozwiązanie.

Procedura odszyfrowania wymaga określenia (odgadnięcia) liczyb wierszy $R$ i przesunięcia $O$. Spróbujmy rozszyfrować tekst przyjmując, że do jego zaszyfrowania użyto następującej liczyb wierszy $R$ i przesunięcia $O

  • R=2, O=0
    Gdyby użyto 2 wierszy bez przesunięcia, wówczas 19 znaków podczas szyfrowania zostałoby rozmieszczonych jak poniżej

    co dałoby szyfrogram postaci

    Zatem tekstem oryginalnym musiałoby być:
  • R=2, O=1
    Gdyby użyto 2 wierszy z przesunięciem równym 1, wówczas 19 znaków podczas szyfrowania zostałoby rozmieszczonych jak poniżej

    co dałoby szyfrogram postaci

    Zatem tekstem oryginalnym musiałoby być:
  • R=3, O=1
    Gdyby użyto 3 wierszy bez przesunięcia, wówczas 19 znaków podczas szyfrowania zostałoby rozmieszczonych jak poniżej

    co dałoby szyfrogram postaci

    Zatem tekstem oryginalnym musiałoby być:
  • R=3, O=1
    Gdyby użyto 3 wierszy z przesunięciem równym 1, wówczas 19 znaków podczas szyfrowania zostałoby rozmieszczonych jak poniżej

    co dałoby szyfrogram postaci

    Zatem tekstem oryginalnym musiałoby być:

Jak więc widać, stosując wyłącznie metodę siłową, sprawdzając kolejne możliwe "parametry" szyfru (kolejne "hasła") otzymujemy ciąg odszyfrowanych wiadomości, z których sensowna będzie najpardopodobniej tylko jedna.


Wniosek 3
Metoda powinna być tak skonstruowan aby znajomość sposobu szyfrowania nie była wystarczająca do odszyfrowania tekstu.
Ewentualnie i znacznie lepiej: upublicznić (odtajnić) samą metodę i jej opis, ale wprowadzić do niej mechanizm klucza, który ze względu na złożoność i mnogość alternatywnych rozwiązań zabezpiecza tekst.

Podstawowa zasada kryptologii: dla bezpieczeństwa istotny jest klucz, a nie algorytm.

Ostateczną postać nadał jej holenderski lingwista Auguste Kerckhoffs von Nieuwenhof w książce La Cryptographie militaire:
Bezpieczeństwo systemu kryptogtaficznego nie może zależeć od zachowania w tajemnicy algorytmu szyfrującego. Bezpieczeństwo zależy wyłącznie od zachowania w tajemnicy klucza.

Cytat z: Simon Singh, Księga szyfrow, Wydawnictwo Albatros A. Kuryłowicz, Warszawa 2001.


Szyfry podstawieniowe

Jak możemy zauważyć, w przestawieniowych metodach szyfrowania każdy znak zachowuje tożsamość (nie zmienia się na żaden inny znak), ale zmienia położenie. Komplementarnym (uzupełniającym) do przestawieniowej powyżej metody szyfrowania jest szyfrowanie podstawieniowe. W metodzie tej zmienia się tożsamość litery, ale jej położenie jest ustalone.

Jedna z najprostszych metod polega na losowym połączeń liter alfabetu w pary, a następnie zastąpieniu w jawnym tekście kolejnych liter przez literę z danej pary.

Zauważmy, że w tym sposobie tworzenia par nie ma możliwości aby jakiś znak pojawił się więcej niż jeden raz; mowiąc dokładniej, każdy dopuszczalny znak musi pojawić się dokładnie jeden raz jako każdy z elementów pary. Na przykład litera A występuje w parach (A, B) oraz (Q, A) -- raz na pierwszej pozycji i raz na drugiej.

Używając powyższych podstawień do zaszyfrowania tekstu TEKST_JAWNY, otrzymujemy:

Kompletny zestaw par staje się w tym przypadku kluczem, czyli elementem niezbędnym do zaszyfrowania i odszyfrowania treści. Problem w tym, że taki klucz, jeśli jest losowy, jest trudny do zapamiętania.


Szyfry Cezara

Względnie łatwo możemy określać podstawienie dokonując przesunięcia całego alfabetu (listy znaków) o zadaną ilość znaków. W przypadku szyfru Cezara przesunięcie to wynosiło 3 znaki

Używając powyższych podstawień do zaszyfrowania tekstu TEKST_JAWNY, otrzymujemy:

Słabością tego szyfru jest bardzo mała liczba kluczy, wynosząca w podanym przykładzie 26 (27 różnych znaków). Możemy zatem próbować wszystkich możliwych kluczy aż do uzyskania sensownej odpowiedzi. Podobnie jak wcześniej, sensowna będzie najpardopodobniej tylko jedna wiadomość.

Spróbujmy rozszyfrować następujący szyfrogram

Po kolei będziemy sprawdzać wyniki otrzymane przy użyciu alfabetu przesuniętego o 1, 2, 3 itd znaki

W kroku czwartm otrzymujemy sensownie brzmiący tekst TO_NIE_TAKIE_TRUDNE i najprawdopodobniej będzie to jedyny sensownie brzmiący tekst otzymany podczas sprawdzania wszystkich możliwych kluczy powstałych w wyniku przesunięcia.

We względnie prosty sposób można zmodyfikować sposób tworzenia podstawienia tak aby z jednej strony dawał znacznie większy zestaw potencjalnych kluczy a z drugiej był łatwy do zapamietania. W tym celu posłużymy się słowem kluczowym nazywanym także wyrażeniem kluczowym -- za jego pomocą wygenerujemy właściwy klucz. Na przykład wykorzystując jako wyrażenie kluczowe zwrot STAR_WARS, otrzymujemy

Używając powyższych podstawień do zaszyfrowania tekstu TEKST_JAWNY, otrzymujemy:

W tym przypadku odszyfrowanie tesktu jest zadaniem znacznie trudniejszym w porównaniu z szyfrem Cezara -- ze względu na występowanie wyrażenia kluczowego liczba potencjalnych kluczy jest znacznie większa.


Wniosek 4
W metodzie szyfrującej zapewnić aby ilość możliwych kluczy była na tyle duża aby nie było możliwe sprawdzenie ich wszystkich metodą siłową w akceptowalnym czasie.

UWAGA: Efektywna możliwość sprawdzenia wszystkich kluczy w akceptowalnym czasie ulega zmianom wraz z rozwojem techniki.

Niestety wciąż obowiązuje zasada, że wybranemu znakowi zawsze odpowiada ten sam zamiennik. Cecha ta pozwala efektywnie łamać szyfry tego rodzaju dzięki analizie częstotliwościowej występowania znaków.


Wniosek 5.1
Dokument zaszyfrowany nie powinien zawierać w sposób jawny (czytelny) żadnej charakterystyki dokumentu jawnego.


Enigma

Charakterystykę dokumentu jawnego ukryjemy, gdy jeden znak tekstu jawnego będzie zastępowany różnymi znakami w zależności od miejsca występowania znaku w tekście i znaków go poprzedzających. Ten sam znak występujący na przykład trzykrotnie po sobie powinien być zawsze szyfrowany jako trzy różne znaki.

Przyjrzyjmy się następującemu przykładowi.

Podstawienie utworzone powyżej w oparciu o wyrażenie kluczowe START_WARS

zakoduje tekst DDD jako RRR. W tym podstawieniu na przykład litera D zastępowana jest oddaloną od niej o 14 pozycji na prawo (pisać będziemy +14) literą R a litera R zastepowana jest oddaloną od niej o 5 na lewo (pisać będziemy -5) literą M. Skrótowo będziemy to zapisywać jako D+14=R, R-5=M. Stąd podstawienie to możemy zapisać w innej równoważnej postaci jako

Jesli teraz po każdym wprowadzonym znaku dokonamy przesunięcia oddalenia o 1 wówczas będziemy otrzymywać następujące warianty podstawienia

  • Krok 1: oddalenia w pozycji wyjściowej (nieprzesunięte)

    Pozwoli to zakodować pierwszą literę D jako R.

    Ponieważ wiemy, że będziemy kodować znak D, dlatego w praktyce wystarczy znaleźć zamiennik tylko dla D, czyli policzyć D+14. Pozostałe zamienniki podane zostały tylko dla celów ilustracyjnych.

  • Krok 2: oddalenia przesunięte o 1 w prawo w stosnku do Kroku 1

    Pozwoli to zakodować drugą literę D jako B. Podobnie jak poprzednio, wstarczy policzyć D+(-2).

  • Krok 3: oddalenia przesunięte o 1 w prawo w stosnku do Kroku 2

    Pozwoli to zakodować trzecią literę D jako V. Podobnie jak poprzednio, wstarczy policzyć D+18.

Tak więc ciąg DDD został zakodowany jako RBV. Jak więc widać sama procedura szyfrowania nie stała się dużo bardziej złożona od poprzednich. Deszyfrowanie (przy znajomości klucza, a więc oddalenia z Kroku 1) jest jak najbardziej wykonalne, choć wymaga więcej czasu, gdyż należy przeprowadzić proces odwrotny, a więc trzeba wyszukać w zamiennikach zaszyfrowany znak co pozwoli wyznaczyć odpowiadający jemu znak jawny.


Aby móc wykorzystać tą samą procedurę do szyfowania i deszyfrowania musimy wprowadzić pewne drobne usprawnienie całego procesu. Zauważmy, że zawsze mamy zależność

Wprowadźmy teraz odwracacz łączący w pary każde kolejne dwie litery (nie muszą to być dwie kolejne litery -- pary mogą stanowić znaki niesąsiadujące bezpośrednio ze sobą; tutaj robimy tak aby ułatwić zrozumienie idei):

i szyfrujmy tekst w następujący sposób

znak+oddalenie=zamiennik_1

znajdź parę w której wystepuje zamiennik_1
znajdź w zamiennikach drugi element pary i nazwij go zamiennik_2

zamiennik_2-oddalenie=znak_zaszyfrowany

Spróbujmy teraz zaszyfrować ciąg DDD

  • Krok 1: oddalenia w pozycji wyjściowej (nieprzesunięte)

    Pozwoli to zakodować pierwszą literę D jako V. Zauważmy, że przeprowadzając tę procedurę dla V (czyli tak, jak gdybyśmy chcieli zaszyfrować V) otrzymujemy znak D:
  • Krok 2: oddalenia przesunięte o 1 w prawo w stosnku do Kroku 1

    Pozwoli to zakodować drugą literę D jako F.
  • Krok 3: oddalenia przesunięte o 1 w prawo w stosnku do Kroku 2

    Pozwoli to zakodować trzecią literę D jako W.

Tak więc ciąg DDD został zakodowany jako VFW. Choć pozornie po wprowadzonej modyfikacji mamy więcej pracy, to jednak zrealizowana w oparciu o te założenia fizyczna maszyna szyfrująca okazuje się być prostsza w przypadku przeprowadzania deszyfrowania wiadomości.

Na zmodyfikowanej wersji tej metody, opisanej w ramce "informacyjnej" powyżej, oparta była niemiecka maszyna szyfrująca Enigma. Jednak ona także posiadała słabe punkty i została złamana na początku lat 30-tych ubiegłego wieku przez Marian Rejewski oraz Henryka Zygalskiego i Jerzego Różyckiego.

Amerykański historyk i dziennikarz David Kahn napisał (David Kahn, Łamacze kodów. Tajemnice kryptologii, Barbara Kołodziejczyk (tłum.), Warszawa: WNT, 2004), że rozwiązanie tej zagadki było oszałamiającym osiągnięciem, które wyniosło Rejewskiego do panteonu największych kryptoanalityków wszech czasów.

Jak czytamy w Księdze szyfrów (Simon Singh, Księga szyfrow, Wydawnictwo Albatros A. Kuryłowicz, Warszawa 2001)

Jego [Rejewskiego] atak na Enigmę był jednym z największych osiągnięć w historii kryptoanalizy. Musiałem tu streścić jego pracę na kilku stronach, dlatego pominąłem wiele szczegółów matematycznych i wszystkie ślepe zaułki. Enigma jest bardzo złożoną maszyną szyfrującą i złamanie niemieckeigo szyfru wymagało ogromnej siły intelektu. Moje uproszczenia nie powinny nikogo skłonić do zlekceważenia ogromnego osiągnięcia Rejewskiego. [s. 171]

Srategia Rejewskiego polegała na wykorzystaniu faktu, że powtórzenie jest wrogiem bezpieczeństwa: powtórzenia prowadzą do regularności, a tego właśnie trzeba kryptoanalitykom. [s. 165]


Wniosek 5.2
Sposób szyfrowania nie powinien dopuszczać tworzenia powtórzeń.


XOR

Wszystkie dotychczas opisane metody, jak i wiele innych używanych współcześnie, mają jedną zasadniczą wadę: możliwe są do odszyfrowania jeśli tylko będziemy mieć wystarczająco dużo czasu. Potrzebny czas może być bardzo duży, ale zawsze będzie skończony.

Istnieje jednak pewna metoda, która ukrywa sekret na zawsze bez możliwości jego ujawnienia w przypadku niedysponowania kluczem. Co może dziwić, metoda ta jest bardzo prosta.

Najpierw nadajmy każdemu znakowi numer równy pozycji znaku w ciagu znaków dopuszczalnych (alfabecie).

Na przykład A ma numer 0, K ma numer 10 a X ma numer 23. Teraz każdy numer zapiszmy jako ciąg dwójkowy 5-bitowy (zbiór dopuszczalnych symboli, ze względów technicznych, musiał zostać rozszerzony do wielkości $2^5=32$; dodane zostały symbole 1, 2, 3, 4 oraz 5)

Następnie na każdym ciagu dwójkowym odpowiadajacym znakowi tekstu jawnego oraz ciągu dwójkowym klucza przeprowadzamy pewnego rodzaju operację dodawania według poniższych reguł:

  • Jeśli odpowiednie bity tekstu jawnego i klucza są jednakowe (to znaczy oba mają wartość 0 albo oba mają wartość 1), to w tekście zaszyfrowanym stawiamy 0.
  • Jeśli odpowiednie bity tekstu jawnego i klucza są różne (to znaczy jeden z nich ma wartość 0 a drugi wartość 1), to w tekście zaszyfrowanym stawiamy 1.

Taka operacja nazwyana jest w informatyce operacja XOR. Przeprowadzając ją na bitach tekstu jawnego TEKST_JAWNY i klucza DK_SERK_QCV otrzymamy tekst zaszyfrowany. Co istone, w tym przypadku klucz nie musi być permutacją (wymieszaniem) zbioru dopuszczalnych symboli, ale może być dowolną ich kombinacją

Tak więc tekst jawny TEKST_JAWNY przy pomocy klucza DK_SERK_QCV został zaszyfrowwany jako QOQAXLD_GPN

Deszyfrowanie przebiega dokładnie analogicznie. Spróbujmy odszyfrować tekst QEYLSHXRL5CEVJBZJOK wiedząc, że został zaszyfrowany kluczem DKCG_DNCLVKAP_QNKDO.

Zauważmy jednak, iż w tej metodzie szyfrowania nie ma możliwości siłowego znalezienia poprawnego klucza metodą próbowania wszystkich możliwych kluczy i eliminowania wiadomości bezsensownych. Problem polega na tym, że wykonując próby, otrzymamy wszystkie możliwe wiadomości jakie dają się zapisać na liczbie znaków równej liczbie znaków szyfrogramu (w naszym przypadku 19). Poniżej dla wiadomości QEYLSHXRL5CEVJBZJOK podaję kilka kluczy wraz z wynikiem "deszyfrowania"

Jak widać, każda z tych wiadomości ma sens i nie wiadomo, która jest prawdziwa.

Ostania metoda wydaje się być idealną metodą szyfrowania -- jest bardzo prosta i nie daje szans na odczytanie wiadomości. Jedyny problem z nią związany dotyczy samego klucza -- aby, zgodnie z wnioskiem 5.2 ten sposób szyfrowania nie dopuszczał do tworzenia powtórzeń, klucz powinien być długości równej długości szyfrowanego tekstu. W ten oto sposób natrafiamy na zagadnienie bezpiecznego sposobu dystrybucji (przekazywania) kluczy, które jednakże samo w sobie jest zupełnie inną historią wymagającą osobnej opowieści.