Kryptologia Wyklad 5.pdf

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

©Ł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

©Ł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.

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.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: