Marek Grajek KURS KRYPTOLOGII
Symetria pozycji Kerckhoffsa
W 1883 roku wydrukowano jedno z najważniejszych dzieł w
historii kryptologii, książkę francuskiego naukowca o
flamandzkich korzeniach, Augusta Kerckhoffsa, pod tytułem "La
Criptographie Militaire". Opisane w niej szyfry i metody ich
łamania miały w dużej mierze utracić znaczenie (choć, jak się
przekonamy - nie wszystkie), ale kilka sformułowanych przez
autora ogólnych zasad dotyczących konstrukcji systemów
szyfrowych zachowuje aktualność do dzisiaj. Najważniejszym
dziedzictwem, jakie Kerckhoffs pozostawił kryptologom, to
zasada, zgodnie konstrukcja szyfru winna zapewnić, by
zaszyfrowane nim wiadomości pozostały bezpieczne nawet, jeśli
przeciwnik dysponuje wszystkimi elementami systemu szyfrowego
poza kluczem. Dzisiaj wydaje siÄ™ oczywista, ale przypomnijmy
sobie wykład o podstawieniach monoalfabetycznych i to, jak autorzy szyfrów
wymyślali coraz bardziej fantazyjne alfabety szyfrowe by ukryć istotną naturę
przekształcenia szyfrującego. Istotnie, jeszcze w naszych czasach pojawiają się
propozycje szyfrów, których konstruktorzy ręczą za absolutne bezpieczeństwo,
ale nie zgadzają się na ogłoszenie informacji o ich konstrukcji. Rozsądek
nakazuje trzymanie się od takich szyfrów z daleka.
Ale ogólne zasady konstrukcji systemów szyfrowych nie były jedynym trwałym
elementem w dorobku Kerckhoffsa. Pozostawił także dwie techniki ataku na
szyfry, które po dostosowaniu do współczesnych szyfrów zachowują ważność do
dnia dzisiejszego: metodę symetrii pozycji oraz nakładania. W trakcie
niniejszego wykładu zapoznamy się z pierwszą z nich, a dodatkowo posłużymy się
bodaj najpowszechniej stosowanÄ… metodÄ… ataku kryptoanalitycznego - atakiem ze
znanym lub prawdopodobnym tekstem jawnym. Rozpocznijmy od metody symetrii
pozycji.
Warto, abyśmy przypomnieli sobie początkowy fragment tablicy Vigenere'a z
poprzedniego przykładu:
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
A 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
B 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 A
C C D E F G H I J K L M N O P Q R S T U V W X Y Z A B
D D E F G H I J K L M N O P Q R S T U V W X Y Z A B C
E E F G H I J K L M N O P Q R S T U V W X Y Z A B C D
Alfabety szyfrowe w kolejnych wierszach tablicy powstają z przesunięcia o jedną
pozycję alfabetu w poprzednim wierszu. Oczywiście nie wszystkie systemy
polialfabetyczne opierały się na tablicy Vigenere'a w jej klasycznej postaci,
równie często w wierszach tablicy wykorzystywano alfabety o zakłóconej
strukturze, np. wygenerowane na podstawie słowa kluczowego, jak poniżej:
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
A K L U C Z A B D E F G H I J M N O P Q R S T V W X Y
B L U C Z A B D E F G H I J M N O P Q R S T V W X Y K
C U C Z A B D E F G H I J M N O P Q R S T V W X Y K L
D C Z A B D E F G H I J M N O P Q R S T V W X Y K L U
E Z A B D E F G H I J M N O P Q R S T V W X Y K L U C
©A
AMACZE SZYFRÓW 1 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Niezależnie od tego, czy alfabety szyfrowe mając strukturę regularną, czy
zakłóconą, warto zauważyć szczególną właściwość tabeli utworzonej na bazie
przesuniętych alfabetów szyfrowych: każda jej przekątna biegnąca z prawego
górnego do lewego dolnego narożnika składa się z tych samych liter. W innych
systemach opisana regularność może mieć inny charakter, ale w zaskakująco wielu
systemach polialfabetycznych alfabety szyfrowe sÄ… wzajemnie powiÄ…zane jakÄ…Å›
regułą.
Dla zilustrowania zasady symetrii pozycji Kerckhoffsa posłużymy się przykładem
zaczerpniętym z jego własnej książki. Proszę zignorować fakt, że tekst jawny
analizowanej depeszy będzie w języku francuskim - nie ma to żadnego znaczenia
dla istoty metody. Kerckhoffs analizował następujący szyfrogram:
RBNBJ JHGTS PTABG JXZBG JICEM QAMUW
IVGAG NEIMW REZKZ SUABR RBPBJ CGYBG
JJMHE NPMUZ CHGWO UDCKO JKKBC PVPMJ
NPGKW PWADW CPBVM RBZBH JWZDN MEUAO
JFBMN KEXHZ AWMWK AQMTG LVGHC QBMWE
Podział szyfrogramu na grupy 5-cio wyrazowe można wnioskować, że Kerckhoffs
zakładał lub znał długość klucza wynoszącą 5 znaków (jeśli nie znał, mógł ją
ustalić metodą Kasiskiego lub, gdyby żył kilkadziesiąt lat dłużej, indeksu
koincydencji). Znał także (lub domyślał się) tekst początkowej frazy
szyfrogramu, brzmiący legeneralwolseleytelegraphie (generał Wolseley
telegrafuje). Podpiszmy prawdopodobnÄ… frazÄ™ pod odpowiadajÄ…ce jej litery
szyfrogramu:
RBNBJ JHGTS PTABG JXZBG JICEM QAM
legen eralw olsel eytel egrap hie
Utwórzmy tabelę, w której kolumny odpowiadają kolejnym znakom alfabetu jawnego,
a wiersze - pięciu alfabetom szyfrowym, odpowiadającym pięciu znakom słowa
kluczowego. W tabeli będziemy wpisywać znaki szyfrogramu w wierszach
odpowiadających pozycji, na której wystąpiły oraz kolumnach odpowiadających
literze, z którą tworzą pary w tekście prawdopodobnym. Przykładowo, trzecim
znakiem szyfrogramu jest N, które odpowiada literze g tekstu jawnego. Wpisujemy
zatem znak N w trzecim wierszu tabeli i w kolumnie oznaczonej literÄ… g. Po
przeanalizowaniu pierwszej piątki znaków szyfrogramu powracamy do pierwszego
alfabetu, wpisujÄ…c w odpowiadajÄ…cym mu pierwszym wierszu literÄ™ J (alfabetu
szyfrowego) pod literÄ… e alfabetu jawnego. Powtarzamy opisany proces dla
wszystkich znaków szyfrogramu, których jawne odpowiedniki znamy lub domyślamy
się ich. Pamiętamy, by szyfrowe odpowiedniki wpisywać do właściwych wierszy
tabeli (tj. wierszy o numerze odpowiadajÄ…cym numerowi znaku wewnÄ…trz aktualnie
analizowanej piÄ…tki).
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
1 J Q R P
2 B I A T H X
3 G M N C A Z
4 E B T
5 Z G J M S
©A
AMACZE SZYFRÓW 2 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
Już pierwszy rzut oka na otrzymaną tabelę pozwala wnioskować, że jej drugi i
czwarty wiersz są identyczne (oznacza to, że w użytym słowie kluczowym druga i
czwarta litera są tożsame). Zauważmy też (właśnie w tym miejscu zaczyna działać
zasada symetrii pozycji Kerckhoffsa), że litera J występuje zarówno w
pierwszym, jak i piątym wierszu, przesunięta o 9 pozycji - oznacza to, że cały
piąty wiersz jest przesunięty o 9 pozycji w stosunku do wiersza pierwszego. Aby
zachować przejrzystość wywodu, uzupełnijmy tabelę na razie tylko o wnioski
wynikające z obu powyższych spostrzeżeń:
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
1 G J M Q R S P Z
2 E B I A T H X
3 G M N C A Z
4 E B I A T H X
5 Z G J M Q R S P
Ale powiązane wzajemnie są także wiersze trzeci i piąty (przez literę M, z
przesunięciem o 11 pozycji) oraz drugi i trzeci (przez literę A, także z
przesunięciem o 11 pozycji). Uzupełniając tabelę o wnioski z kolejnych relacji
wiążących wiersze otrzymujemy:
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
1 G H J M Q N X R E S P B I C A Z T
2 E S P B I C A Z T G H J M Q N X R
3 G H J M Q N X R E S P B I C A Z T
4 E S P B I C A Z T G H J M Q N X R
5 I C A Z T G H J M Q N X R E S P B
Dysponując 17 z 26 znaków alfabetów szyfrowych dokonujemy częściowego
dekryptażu szyfrogramu, otrzymując tekst (gwiazdkami oznaczono nieznane
litery):
legen eralw olsel eytel egrap hie**
s*ail iaqu* latte n*seu lemen tq*el
eserv ice*e tra** **r** e**ec ommun
Od tego momentu można podążać do celu jedną z dwóch ścieżek. Pierwszą polecamy
znawcom języka francuskiego: należy podjąć próbę uzupełnienia brakującego
tekstu depeszy. Nawet słaba znajomość języka pozwala rozpoznać w drugim wierszu
zarys frazy "attend seulement que" (czeka tylko na). DysponujÄ…c nowymi znakami
tekstu prawdopodobnego powracamy do uzupełniania tabeli alfabetów szyfrowych,
korzystamy z symetrii pozycji, a jeśli wynik okaże się nadal niewystarczający
do odczytania całego szyfrogramu, powtarzamy oba etapy procesu aż do skutku.
Druga droga ataku prowadzi przez analizę samej tabeli alfabetów szyfrowych.
Przyjrzyjmy się jeszcze raz jej fragmentom, które podkreśliliśmy poniżej.
©A
AMACZE SZYFRÓW 3 www.lamaczeszyfrow.pl
Marek Grajek KURS KRYPTOLOGII
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
1 G H J M Q N X R E S P B I C A Z T
2 E S P B I C A Z T G H J M Q N X R
3 G H J M Q N X R E S P B I C A Z T
4 E S P B I C A Z T G H J M Q N X R
5 I C A Z T G H J M Q N X R E S P B
Wydaje się oczywistym, że podstawowy alfabet szyfrowy został wygenerowany na
podstawie słowa kluczowego RESPUBLICA. Po tym spostrzeżeniu uzupełnienie tabeli
alfabetów szyfrowych i całkowite rozszyfrowanie przejętej depeszy są trywialnym
zadaniem.
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
1 D F G H J K M Q N O X R E S P U B L I C A Z Y T V W
2 E S P U B L I C A Z Y T V W D F G H J K M Q N O X R
3 G H J K M Q N O X R E S P U B L I C A Z Y T V W D F
4 E S P U B L I C A Z Y T V W D F G H J K M Q N O X R
5 L I C A Z Y T V W D F G H J K M Q N O X R E S P U B
Pora na zadanie. Przejęliśmy szyfrogram o treści podanej poniżej. Mamy podstawy
by sądzić, że został on zaszyfrowany podstawieniem polialfabetycznym o
alfabetach przesuniętych (jak w przykładzie powyżej). Co więcej, nasz wywiad
zdołał zdobyć częściowo spalony skrawek notatki szyfranta, na którym zanotował
on słowa KRYPTOLOGIACZYLINAUKA (to zapewne początek szyfrogramu, począwszy od
tego miejsca arkusz jest jednak spalony).
Są pewne przesłanki by sądzić, że przeciwnik dla utrudnienia złamania szyfru
może używać słów kluczowych do szyfrowania bez wykreślenia powtarzającej się
litery.
Szyfrogram:
VOMXQEXLXNRMFYJNHHIDOVPGDKBBJTZBUTRCTSJJRNNMDVVCELJRJOBLEZSKT
SWNSNFYHVCOZHMTPHYLTABOXHMDAXWYIELYRIKSHUNEMQLRGVUEWGTSCNSMIU
Należy:
1. Zrekonstruować metodą symetrii pozycji alfabety szyfrowe użyte do
zaszyfrowania tekstu, określić i podać słowo kluczowe użyte do wygenerowania
alfabetów szyfrowych.
2. Określić słowo kluczowe użyte do szyfrowania za pomocą wygenerowanych
alfabetów szyfrowych, pamiętając że przeciwnik mógł dla łatwiejszego
zapamiętania jako obu słów kluczowych użyć dwóch związanych ze sobą wyrazów.
3. Podać pierwsze 50 znaków tekstu jawnego szyfrogramu.
Powodzenia.
©A
AMACZE SZYFRÓW 4 www.lamaczeszyfrow.pl