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.

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)
  • Wojna sześciodniowa - historyczny sukces Izraela
  • Wojna szesciodniowa - jak to bylo mozliwe...?
• 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.
  • Indiański szyfr, którego nie złamali Niemcy
  • Indiańscy szyfranci
• 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.

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.

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.

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
  
  1 3 5 7 9 1 3 5 7 9 2 4 6 8 0 2 4 6 8

  1 2	1 3 5 7 9 1 3 5 7 9 2 4 6 8 0 2 4 6 8

  
  co dałoby szyfrogram postaci
  
  1 1 1 1 1 1 1 1 1 1 1 3 5 7 9 1 3 5 7 9 2 4 6 8 0 2 4 6 8 N T E U T _ I _ A I _ R D E O E K T N N T E U T _ I _ A I _ R D E O E K T N

  1 2 3 4 5 6

  1 1 1 1 1         1 1 1 1 1 1 3 5 7 9 1 3 5 7 9 2 4 6 8 0 2 4 6 8 N T E U T _ I _ A I _ R D E O E K T N   N T E U T _ I _ A I _ R D E O E K T N

  
  Zatem tekstem oryginalnym musiałoby być:
  
  N_TREDUETO_EIK_TANI

  1	N_TREDUETO_EIK_TANI

• 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
  
  . 2 4 6 8 0 2 4 6 8 1 3 5 7 9 1 3 5 7 9

  1 2	. 2 4 6 8 0 2 4 6 8 1 3 5 7 9 1 3 5 7 9

  
  co dałoby szyfrogram postaci
  
  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 6 8 0 2 4 6 8 1 3 5 7 9 1 3 5 7 9 N T E U T _ I _ A I _ R D E O E K T N . N T E U T _ I _ A I _ R D E O E K T N

  1 2 3 4 5 6

  1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 4 6 8 0 2 4 6 8 1 3 5 7 9 1 3 5 7 9 N T E U T _ I _ A I _ R D E O E K T N   . N T E U T _ I _ A I _ R D E O E K T N

  
  Zatem tekstem oryginalnym musiałoby być:
  
  IN_TREDUETO_EIK_TAN

  1	IN_TREDUETO_EIK_TAN

• 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
  
  1 5 9 3 7 2 4 6 8 0 2 4 6 8 3 7 1 5 9

  1 2 3

  1   5   9   3   7 2 4 6 8 0 2 4 6 8   3   7   1   5   9

  
  co dałoby szyfrogram postaci
  
  1 1 1 1 1 1 1 1 1 1 1 5 9 3 7 2 4 6 8 0 2 4 6 8 3 7 1 5 9 N T E U T _ I _ A I _ R D E O E K T N N T E U T _ I _ A I _ R D E O E K T N

  1 2 3 4 5 6 7

  1 1         1 1 1 1 1     1 1 1 1 5 9 3 7 2 4 6 8 0 2 4 6 8 3 7 1 5 9 N T E U T _ I _ A I _ R D E O E K T N   N   T   E   U   T _ I _ A I _ R D E   O   E   K   T   N

  
  Zatem tekstem oryginalnym musiałoby być:
  
  N_OIT_EAEIK_URTDTEN

  1	N_OIT_EAEIK_URTDTEN

• 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
  
  . 4 8 2 6 1 3 5 7 9 1 3 5 7 9 2 6 0 4 8

  1 2 3

  .   4   8   2   6 1 3 5 7 9 1 3 5 7 9   2   6   0   4   8

  
  co dałoby szyfrogram postaci
  
  1 1 1 1 1 1 1 1 1 1 4 8 2 6 1 3 5 7 9 1 3 5 7 9 2 6 0 4 8 N T E U T _ I _ A I _ R D E O E K T N . N T E U T _ I _ A I _ R D E O E K T N

  1 2 3 4 5 6 7

  1 1           1 1 1 1 1     1 1 1 4 8 2 6 1 3 5 7 9 1 3 5 7 9 2 6 0 4 8 N T E U T _ I _ A I _ R D E O E K T N   .   N   T   E   U T _ I _ A I _ R D E   O   E   K   T   N

  
  Zatem tekstem oryginalnym musiałoby być:
  
  TO_NIE_TAKIE_TRUDNE

  1	TO_NIE_TAKIE_TRUDNE

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.

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.

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.

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.

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)
  
  znaki.......... A B C D E F G H I J K L M N O P Q R S T U V W X Y Z _ oddalenie......+18 +18 -2 +14 +22 +17 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -2 -2 -1 -1 -1 zamiennik...... S T A R _ W B C D E F G H I J K L M N O P Q U V X Y Z

  1 2 3

  znaki..........  A   B  C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z   _ oddalenie......+18 +18 -2 +14 +22 +17  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -2  -2  -1  -1  -1 zamiennik......  S   T  A   R   _   W   B   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   U   V   X   Y   Z

  
  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
  znaki.......... A B C D E F G H I J K L M N O P Q R S T U V W X Y Z _ oddalenie...... -1 +18 +18 -2 +14 +22 +17 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -2 -2 -1 -1 zamiennik...... _ T U B S A X C D E F G H I J K L M N O P Q U V W Y Z

  1 2 3

  znaki..........  A   B  C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z   _ oddalenie...... -1 +18 +18 -2 +14 +22 +17  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -2  -2  -1  -1 zamiennik......  _   T  U   B   S   A   X   C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   U   V   W   Y   Z

  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
  znaki.......... A B C D E F G H I J K L M N O P Q R S T U V W X Y Z _ oddalenie...... -1 -1 +18 +18 -2 +14 +22 +17 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -5 -2 -2 -1 zamiennik...... _ A U V C T B Y D E F G H I J K L M N O P Q U V W X Z

  1 2 3

  znaki..........  A   B  C   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   R   S   T   U   V   W   X   Y   Z   _ oddalenie...... -1  -1 +18 +18 -2 +14 +22 +17  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -5  -2  -2  -1 zamiennik......  _   A  U   V   C   T   B   Y   D   E   F   G   H   I   J   K   L   M   N   O   P   Q   U   V   W   X   Z

  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.

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]

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.