Marek Grajek KURS KRYPTOLOGII
Szyfry przestawieniowe
Poprzedni wykład poświęciliśmy szyfrom podstawieniowym, w którym w miejsce
poszczególnych znaków alfabetu jawnego podstawia się odpowiadające im znaki
alfabetu szyfrowego. Dzisiaj zajmiemy się drugą podstawową kategorią szyfrów -
szyframi przestawieniowymi. Ponieważ przestawienie bywa uczenie określane
mianem transpozycji, szyfry przestawieniowe sÄ… alternatywnie nazywane szyframi
transpozycyjnymi. Na zakończenie wykładu przekonamy się, że obie kategorie
przekształceń - podstawienia i przestawienia - bywają do dnia dzisiejszego
używane i wzajemnie kombinowane w konstrukcji szyfrów wykorzystywanych w
codziennym życiu, m.in. w transakcjach finansowych.
Przejdz
my od razu do przykładu. Załóżmy, że pragniemy zaszyfrować depeszę o
treści:
TRZECIAKOMPANIAATAKUJEWZGORZEJEDENDWACZTERYPOCZATEKNATARCIAGODZINAZEROCZTERYZER
OZEROPIERWSZAKOMPANIAJAKODRUGIRZUTNATARCIADRUGAKOMPANIAWREZERWIE
a uzgodnione na dany dzień słowo kluczowe brzmi KRYPTOANALITYK.
Aby zaszyfrować powyższy tekst szyfrem przedstawieniowym tworzymy tabelę o tylu
kolumnach, ile znaków liczy słowo kluczowe po wyeliminowaniu zeń powtarzających
się znaków. W nagłówku każdej kolumny wpisujemy kolejne litery słowa
kluczowego, w następnie w wierszach tabeli tekst jawny depeszy, jak poniżej.
K R Y P T O A N L I
T R Z E C I A K O M
P A N I A A T A K U
J E W Z G O R Z E J
E D E N D W A C Z T
E R Y P O C Z A T E
K N A T A R C I A G
O D Z I N A Z E R O
C Z T E R Y Z E R O
Z E R O P I E R W S
Z A K O M P A N I A
J A K O D R U G I R
Z U T N A T A R C I
A D R U G A K O M P
A N I A W R E Z E R
W I E X X X X X X X
W niektórych wypadkach szyfrant uzupełniał ostatni, niekompletny wiersz,
wpisując konieczną liczbę znaków niezwiązanych z treścią szyfrogramu - jak
łańcuch znaków X w przykładzie. Następnie zawartość tabeli (z pominięciem
nagłówka) odczytujemy w kolumnach, biorąc jednak kolumny nie po kolei, lecz w
alfabetycznej kolejności słów słowa kluczowego, tj. najpierw kolumnę pod literą
A, następnie I, K, L, N, O, P, R, T i Y, otrzymując szyfrogram:
ATRAZCZZEAUAKEXMUJTEGOOSARIPRXTPJEEKOCZZJZAAWOKEZTARRWIICMEXKAZCAIEERNGROZXIAOW
CRAYIPRTARXEIZNPTIEOOONUAXRAEDRNDZEAAUDNICAGDOANRPMDAGWXZNWEYAZTRKKTRIE
©A
AMACZE SZYFRÓW 1 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Skąd dowiemy się, że szyfrogram został zaszyfrowany szyfrem przestawieniowym? Z
pomocą przychodzi ponownie, jak w poprzednim wykładzie, wykres częstości
występowania znaków w szyfrogramie. Zauważmy, że przestawienie zmienia
położenie znaku, ale nie zmienia jego wartości. Zatem, pomijając
zniekształcenie wprowadzone przez znaki dopełniające ostatni wiersz, struktura
częstotliwości występowania znaków w szyfrogramie powinna odpowiadać strukturze
charakterystycznej dla tekstu jawnego. Czy jest tak w rzeczywistości?
Struktura częstotliwości różni się od zapamiętanej z przykładu szyfru
podstawieniowego - ale przecież mamy do czynienia z szyfrogramem napisanym w
języku polskim! Co więcej, specyficzne, polskie znaki zostały w nim zastąpione
przez ich łacińskie odpowiedniki, a próbka tekstu liczy sobie zaledwie 150
znaków, co także znajduje odbicie w strukturze wykresu. Porównując wartości na
rysunku z teoretycznymi wartościami częstotliwości występowania znaków w języku
polskim dochodzimy do wniosku, że ich struktura jest zbliżona, a zatem
prawdopodobnie mamy do czynienia z szyfrem przestawieniowym.
Wydaje się, że sposób odczytania szyfrogramu przez jego odbiorcę jest na tyle
oczywisty, że nie sensu poświęcać mu czasu. Dla nas bardziej interesującym
wyzwaniem jest metodologia złamania szyfru. Zaczynamy pracę od odrobiny
obliczeń. Wiedząc, że szyfrogram liczy sobie 150 znaków, usiłujemy określić
możliwe rozmiary tablicy, w jakiej został zapisany (przyjmujemy przy tym dla
ułatwienia, że ostatni wiersz tablicy był wypełniony). Zważywszy, że braliśmy
pod uwagę tylko niepowtarzające się znaki słowa kluczowego, jego największa
długość wynosi 26 znaków. Z drugiej strony, czym mniejsza długość słowa
kluczowego, tym łatwiejsze złamanie szyfru. Możemy zatem założyć, że rozsądny
szyfrant nie użyje słowa kluczowego krótszego niż 5 znaków. W zakresie pomiędzy
5 i 26 znaków długość szyfrogramu dzieli się bez reszty przez 5, 6, 10, 15 i
25. Przygotowujemy zatem tabele o rozmiarach 5x30, 6x25, 10x15 i 25x6, wpisujÄ…c
do nich zawartość szyfrogramu w kolejnych kolumnach. Tak przygotowane tabele
rozcinamy pionowo na poszczególne słupki i przystępujemy do ataku na szyfr
metodą określaną wśród kryptoanalityków mianem anagramowania. Anagramowanie, to
nic innego, jak zestawianie ze sobą poszczególnych słupków tak, by uzyskać w
powstałych wierszach fragmenty sensownego tekstu jawnego. Zilustrujmy tę
czynność na przykładzie.
©A
AMACZE SZYFRÓW 2 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Załóżmy, że przeanalizowaliśmy już tabele o rozmiarach 5x30, 6x25 i 10x15 nie
odnajdując przy żadnym wzajemnym ustawieniu ich kolumn wystarczająco długich
fragmentów sensownego tekstu. Przystępujemy do analizy tabeli o rozmiarach
15x10, jak poniżej:
A M T O K I E R C Z
T U P K A A I A A N
R J J E Z O Z E G W
A T E Z C W N D D E
Z E E T A C P R O Y
C G K A I R T N A A
Z O O R E A I D N Z
Z O C R E Y E Z R T
E S Z W R I O E P R
A A Z I N P O A M K
U R J I G R O A D K
A I Z C R T N U A T
K P A M O A U D G R
E R A E Z R A N W I
X X W X X X X I X E
Założyliśmy, że tekst jawny szyfrogramu został napisany w języku polskim, zatem
warto poszukać wierszy z parami znaków, z których da się ułożyć częste w języku
polskim bigramy CH, SZ i CZ. Już w pierwszym wierszu odnajdujemy parę CZ,
jednak w innych wierszach w tych samych kolumnach występują niespotykane w
języku polskim pary znaków AA, NZ, OY, MK, co sugeruje, że występujące w tym
wierszu litery C i Z są niezależne, nie tworzą poszukiwanego bigramu. W
czwartym wierszu także spotykamy parę CZ, zaś zestawiając we właściwej
kolejności kolumny, w których występują tworzące ją litery, otrzymujemy
(zapisując w nagłówkach numery kolumn):
5 4
K O
A K
Z E
C Z
A T
I A
E R
E R
R W
N I
G I
R C
O M
Z E
X X
W powstałych wierszach brak par, których wystąpienie w języku polskim jest mało
prawdopodobne, a dwukrotne powtórzenie bigramu ER czyni zestawienie obu kolumn
prawdopodobnym. Zestawienia znaków CZ występują także w piątym i ósmym wierszu
tabeli. ZestawiajÄ…c odpowiadajÄ…ce im kolumny otrzymujemy:
©A
AMACZE SZYFRÓW 3 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
6 1 3 8
I A T R
A T P A
O R J E
W A E D
C Z E R
R C K N
A Z O D
Y Z C Z
I E Z E
P A Z A
R U J A
T A Z U
A K A D
R E A N
X X W I
W otrzymanych parach także brak kombinacji mało prawdopodobnych w języku
polskim, przyjmujemy więc hipotezy dotyczące zestawienia wszystkich trzech par.
W następnej kolejności szukamy kolumn, w których wierszach można ułożyć inny
częsty w języku polskim bigram - CI. Odpowiednie pary znaków występują w
wierszach pierwszym, szóstym i dwunastym. Zestawiając odpowiednie kolumny
otrzymujemy następujące pary:
9 6 1 5 4 2
C I A K O M
A A T A K U
G O R Z E J
D W A C Z T
O C Z A T E
A R C I A G
N A Z E R O
R Y Z E R O
P I E R W S
M P A N I A
D R U G I R
A T A R C I
G A K O M P
W R E Z E R
X X X X X X
W drugim wierszu pierwszej pary kolumn z lewej występuje para AA, którą
niedawno uznaliśmy za niezbyt częstą w języku polskim. Może to jednak wynikać z
zestawienia dwóch wyrazów, kończącego się i rozpoczynającego od A; pozostałe
pary w obu kolumnach są zgodne z logiką języka polskiego, zatem podtrzymujemy
założenie dotyczące kolumn 9 i 6.
Podsumujmy uzyskaną dotąd wiedzę; jeżeli przyjęte przez nas założenia są
poprawne, po kolumnie 1 następuje kolumna 5, po kolumnie 5 następuje 4, po 4 -
2, kolumna 1 następuje po 6, a kolumna 8 następuje po 3. Uzyskaliśmy wzajemne
uporządkowanie znacznej części kolumn, które składa się łącznie na łańcuch 9 -
6 - 1 - 5 - 4 - 2 oraz niezależną parę 3 - 8. Uporządkujmy kolumny należące do
zidentyfikowanego łańcucha, otrzymując następujący fragment tabeli szyfru:
©A
AMACZE SZYFRÓW 4 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
C I A K O M
A A T A K U
G O R Z E J
D W A C Z T
O C Z A T E
A R C I A G
N A Z E R O
R Y Z E R O
P I E R W S
M P A N I A
D R U G I R
A T A R C I
G A K O M P
W R E Z E R
X X X X X X
Wynik wygląda obiecująco - rysują się w nim bez wątpienia fragmenty słów języka
polskiego. W dziesiątym wierszu bez wątpienia mamy końcówkę słowa KOMPANIA,
poszukujemy zatem wśród niewykorzystanych do tej pory kolumn takich, które w
dziesiątym wierszu mają znaki K oraz O (kolumny 10 i 7), dołączając je we
właściwej kolejności przed powyższym fragmentem tabeli. Otrzymujemy:
Z E C I A K O M
N I A A T A K U
W Z G O R Z E J
E N D W A C Z T
Y P O C Z A T E
A T A R C I A G
Z I N A Z E R O
T E R Y Z E R O
R O P I E R W S
K O M P A N I A
K O D R U G I R
T N A T A R C I
R U G A K O M P
I A W R E Z E R
E X X X X X X X
Wiemy, że kolumny 3 i 8 występują obok siebie, a na opisanym etapie pracy jest
już oczywiste, że należy dołączyć je przed zrekonstruowanym do tej pory
fragmentem tabeli, otrzymujÄ…c:
T R Z E C I A K O M
P A N I A A T A K U
J E W Z G O R Z E J
E D E N D W A C Z T
E R Y P O C Z A T E
K N A T A R C I A G
O D Z I N A Z E R O
C Z T E R Y Z E R O
Z E R O P I E R W S
Z A K O M P A N I A
J A K O D R U G I R
©A
AMACZE SZYFRÓW 5 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Z U T N A T A R C I
A D R U G A K O M P
A N I A W R E Z E R
W I E X X X X X X X
Jednocześnie stwierdziliśmy, że kolumny pierwotnej tabeli należało przestawić
(transponować) w kolejności: 3 - 8 - 10 - 7 - 9 - 6 - 1 - 5 - 4 - 2. Przy
odrobinie wysiłku i wyobraz
ni można na tej podstawie wydedukować słowo
kluczowe, choć w większości przypadków otrzymane rozwiązanie nie będzie
jednoznaczne.
Jak widać, proces anagramowania, to raczej rzemiosło, niż sztuka. Metoda
łamania szyfrów przestawieniowych jest powszechnie znana od wielu lat, mimo
tego szyfry oparte na opisanej zasadzie były powszechnie wykorzystywane jeszcze
w czasach II wojny światowej. Wykorzystywano je w bardziej wyrafinowanych
wariantach, wśród których warto wymienić szyfr z podwójną transpozycją lub
szyfr transpozycyjny ze znakiem pustym. W szyfrze podwójnej transpozycji, jak
łatwo się domyślić, dysponujemy dwoma słowami kluczowymi, a wynik pierwszego
przestawienia poddajemy kolejnej transpozycji korzystając z drugiego słowa
kluczowego. W szyfrze ze znakiem pustym klucz obejmuje oprócz słowa kluczowego
także liczbę n. Przed wypełnieniem tabeli transpozycji wykreślamy z niej co n-
ty znak (por. przykład poniżej), co zakłóca naturalny układ fraz języka tekstu
jawnego. Na potrzeby przykładu załóżmy, że n = 7; przed wpisaniem do tabeli
tekstu jawnego wykreślamy z niej co 7 znak, wstawiając w tabeli X:
K R Y P T O A N L I
T R Z E C I X A K O
M P A X N I A A T A
X K U J E W Z X G O
Sposoby łamania obu wspomnianych rodzajów szyfru przestawieniowego w poglądowy
sposób opisał w swoich wspomnieniach Marian Rejewski, główny autor sukcesu
polskich kryptologów w ataku na szyfry Enigmy (wspomnienia Rejewskiego są
dostępne w Internecie pod adresem www.spybooks.com/pl/enigma.html, dokument o
nazwie  Wspomnienia z mej pracy w Biurze Szyfrów... ). Wspomnienia Mariana
Rejewskiego potwierdzają jednoznacznie, że jeszcze w okresie II wojny światowej
szyfry przedstawieniowe były wykorzystywane operacyjnie. Przyczyną ich użycia
był zapewne stosunkowo duży nakład pracy i długi czas niezbędny dla złamania
klucza. We współczesnej kryptologii nie dąży się zazwyczaj do osiągnięcia
absolutnego bezpieczeństwa informacji, lecz spełnienia warunku, by korzyść
przeciwnika ze złamania szyfru była znacznie mniejsza, niż włożony weń wysiłek
lub alternatywnie - by czas złamania szyfru był dłuższy, niż czas w którym
zabezpieczana nim informacja zachowuje swoją użyteczność.
We wstępie do dzisiejszego wykładu powiedzieliśmy, że kombinacja dwóch
podstawowych operacji kryptograficznych - podstawienia i przestawienia - do
chwili obecnej stanowi fundament konstrukcji szyfrów. A
ączność większości
bankomatów w świecie z centralami ich banków jest zabezpieczana przez szyfr o
nazwie 3DES. Konstrukcja tego szyfru, to nic innego, jak kaskada kilkunastu
stosowanych naprzemiennie operacji podstawienia i przestawienia.
Po tych ciekawostkach czas na dzisiejsze zadania. Przejęliśmy szyfrogram;
podejrzewamy, że jego tekst jawny został napisany w języku polskim a przeciwnik
posłużył się szyfrem przestawieniowym. Należy:
©A
AMACZE SZYFRÓW 6 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
1. Zaszyfrować pierwsze 52 litery zdania, które rozpoczyna się od słów Biuro
Szyfrów WP z działu "O akcji - Nieco historii". Jako klucza użyć nazwiska
matematyka, który pierwszy złamał kod Enigmy. Uwaga! Zgodnie z zasadami
przedstawionymi w wykładzie liczba liter szyfrogramu może ulec zwiększeniu w
stosunku do tekstu pierwotnego.
2. Przejęliśmy szyfrogram; podejrzewamy, że jego tekst jawny został napisany w
języku polskim a przeciwnik posłużył się szyfrem przestawieniowym. Należy
odczytać pierwszych 50 znaków szyfrogramu. Oto szyfrogram:
ACEJRTSANUDCJWOZOICPWDUSPZCDEXYDSYOSDPYRNCGOXKIWSZOTLIN
ZWKNNEAYJZECHAJLURIXILNEDIICZCCSPLXTAIEAOYILMWSUORNEAZA
WKACIIYIAYAJZIZGZZEAAOZLBRPZOCEOZASCAEIXPSDNIWHUPIANZNX
3. Podać możliwe słowo kluczowe użyte przy szyfrowaniu tekstu z zadania nr 2,
przy założeniu, że zostało ono zaczerpnięte spośród pojęć kryptologicznych
podanych w dotychczasowych wykładach i że zostały z niego usunięte
powtarzajÄ…ce siÄ™ litery.
Dla ułatwienia pracy poniżej podajemy rozkład częstotliwości znaków w
szyfrogramie.
Powodzenia.
©A
AMACZE SZYFRÓW 7 www.lamaczeszyfrow.pl