Marek Grajek KURS KRYPTOLOGII

Nakładanie Kerckhoffsa

W dzisiejszym wykładzie skupimy uwagę na drugiej z technik ataku
zaproponowanych przez Kerckhoffsa - nakładaniu. We wszystkich poprzednich

wykładach i zadaniach atakowaliśmy stosunkowo długi, liczący kilkaset znaków
fragment szyfrogramu. Teoria i doświadczenie są zgodne, że skuteczne podjęcie

ataku statystycznego na fragment szyfrogramu zaszyfrowany jednym kluczem wymaga
posiadania próbki o minimalnej długości bliskiej liczbie znaków w alfabecie

szyfrowym; przy krótszym tekście wzorce częstości występowania znaków są zbyt
zniekształcone. Jak łatwo obliczyć, przy próbie złamania szyfru

polialfabetycznego o kluczu długości 4 znaków metodą analizy częstości
występowania znaków potrzebujemy co najmniej około 100 znaków tekstu

zaszyfrowanego. Oczywiście autorzy systemów szyfrowych byli świadomi tego
wymogu i często zastrzegali, by szyfrowane depesze były możliwie krótkie i nie

dostarczały kryptoanalitykowi przeciwnika materiału wystarczającego do podjęcia
skutecznego ataku.

Kerckhoffs zwrócił uwagę na fakt, że materiał użyty przez kryptoanalityka nie
musi pochodzić z jednego szyfrogramu pod warunkiem, że teksty pochodzące z

różnych szyfrogramów można uporządkować wzajemnie tak, by stało się możliwe
porównywanie znaków różnych szyfrogramów zaszyfrowanych przy pomocy tego samego

alfabetu szyfrowego. Takie uporządkowanie wzajemne szyfrogramów określane jest
w kryptologii mianem wyrównania fazowego. W przypadku szyfrogramów

zaszyfrowanych tym samym kluczem wyrównanie fazowe jest trywialne; wystarczy
zapisać szyfrogramy jeden pod drugim, by w kolumnach otrzymać znaki

zaszyfrowane tym samym podstawieniem monoalfabetycznym. Problem w tym, że
należało zidentyfikować depesze szyfrowane tym samym kluczem w strumieniu wielu

depesz wysyłanych przez przeciwnika. Identyfikacja różnych depesz
zaszyfrowanych tym samym kluczem rodziła problemy w czasach Kerckhoffsa, który

dysponował jedynie metodą Kasiskiego.
Współcześnie jesteśmy w lepszym położeniu, dysponując indeksem koincydencji. W

jednym z poprzednich wykładów wykorzystywaliśmy go do identyfikacji okresu
klucza szyfru polialfabetycznego, obliczając wartość indeksu dla różnych

wartości wzajemnego przesunięcia tego samego tekstu. Ale przecież możemy
wyznaczyć wartość indeksu koincydencji także dla dwóch różnych tekstów; jeżeli

zostały one zaszyfrowane tym samym alfabetem szyfrowym, jego wartość będzie
znacznie większa, niż dla tekstów przypadkowych. Weźmy przykładowo trzy

szyfrogramy poniżej:

YMHVJBDBWMHJUSTAEP
MVXKVBDBJEXKUEZ

VQSITGUYRJIMIQTQ

Zauważmy, że pierwsze dwa zawierają po cztery koincydencje (odpowiadające
znakowi U oraz trygramowi BDB - wystąpienie koincydencji dotyczącej nie

oddzielnych znaków, lecz całego trygramu jest prawie pewnym sygnałem tożsamości
użytego klucza). Pomiędzy pierwszym i trzecim oraz drugim i trzecim

szyfrogramem brak koincydencji. Wynika stąd, że pierwszy i drugi szyfrogram
zostały prawdopodobnie zaszyfrowane wspólnym kluczem, a trzeci - innym od

pozostałych dwóch.
Nakładanie Kerckhoffsa można zrealizować także w odniesieniu do szyfrogramów,

które nie zostały zaszyfrowane explicite tym samym kluczem, kiedy jesteśmy w

©ŁAMACZE SZYFRÓW

1

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

stanie określić prawidłowe wzajemne przesunięcie tekstów oraz zakres nakładania
klucza. Zapiszmy pod sobą fragmenty szyfrogramów zaszyfrowanych częściowo

pokrywającymi się kluczami KOREFERAT I REFERAT, wraz z powtórzeniami słowa
kluczowego.

KOREFERATKOREFERATKOREFERATKOREFER

DCGVECBLTNCNCXDPFKYUIEROVRVUVFJKWR
KSUVQYDCEISNYLQCKVFGKRQPIICDYSKJJA

REFERATREFERATREFERATREFERATREFERA

Zauważmy, że możemy dopasować fazowo oba szyfrogramy odpowiednio przesuwając
dolną parę wierszy i wstawiając odstępy w miejsca nienakładających się znaków

klucza.

KOREFERATKOREFERATKOREFERATKOREFER
DCGVECBLTNCNCXDPFKYUIEROVRVUVFJKWR

KSUVQYD CEISNYL QCKVFGK RQPII
REFERAT REFERAT REFERAT REFER

Idąc jeszcze dalej w tym samym kierunku, można dopasowywać fazowo szyfrogramy,

których klucze nie zawierają wspólnych fragmentów. Jeżeli na przykład
przejęliśmy szyfrogramy zaszyfrowane kluczami RONDO oraz ULICA (których

oczywiście a priori nie znamy), możemy próbować dopasować wzajemnie n-te znaki
pierwszego szyfrogramu i (n+3)-cie drugiego, bowiem pierwsza litera drugiego

klucza jest przesunięta w tablicy alfabetów szyfrowych o trzy pozycje w
stosunku do pierwszej litery pierwszego klucza,itd. Dla każdej hipotezy

dotyczącej wzajemnej pozycji znaków klucza obliczamy indeks koincydencji
określając, czy hipotetyczne dopasowanie fazowe jest poprawne, czy też nie.

Prześledźmy naszkicowany proces na przykładzie. Przejęliśmy następującą paczkę

szyfrogramów, których językiem jawnym jest język polski, a język z którego
wzięto słowa – klucze, określające kolejność użytych alfabetów szyfrowych to

angielski. Nie wiemy, które z nich zostały zaszyfrowane tym samym kluczem.

1. EDWUSILSUPYVKRGSUIPUULMXPWYVYPYEKRGSCDWXBSUUJIQLYAWEKKYRXEARXIEGXEIDKHSHBE

AQCXMH

2. UIPUULMXPWMYVSQAVWUGTIXSCEBQUVWHDSJGQMGOUWGSJGCGZYZDSOMOKRCBGHXAOAGWDRYKDC

KOSIIMCXMH

3. CCKWDVGSZSXQMNGCOVACRSDXCEHWCXNGNIHKMMCEKPRWBRYLIALQWAMTOGYFKPGRIGXWCXMKMM

UQCXCHYAYFSEXFKOMOCXMH

4. XEIDKHYFSIGKIQYLOVGSZSXQMNGCOVACRSDXCEQLYWSBOQWVYPYEKRGSCDWXBSUHYPGSVJYTOX

WUJRWURWRGZ

5. JEQSNEQQWIRJSMNGJCABSOCJMOFGPJQSWSXWLCAMJCUSXEJSMDLAODXSCEBSXEIDKHYFSEQLYT
6. ZSBKDEUGGCKHBSZDOQCEGRYCVEBSXMSCOVACRSDXCEHWCXNJKAGVVSUWGCPGGRYFSIDSJSUWCD

WXBSEJKQMOCXMH

7. XEIDKHYFSIIWBGIZYJDKKYKGJPGOSEJSWELAOHCHOWXRLCRCBSRCSGFTIQMRVMUQLCJTODNGCV

CVXMYLKOQLYT

Warto rozpocząć pracę od obliczenia indeksu koincydencji dla różnych wartości
wzajemnego przesunięcia tego samego szyfrogramu. Uzyskamy w ten sposób

informację dotyczącą długości kluczy, którymi poszczególne szyfrogramy zostały
zaszyfrowane. Dla szyfrogramów o numerach 1 i 5 wartość indeksu koincydencji

wskazuje jednoznacznie na klucz o długości 4 znaków, dla szyfrogramów o

©ŁAMACZE SZYFRÓW

2

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

numerach 2, 3 i 7 wartość indeksu koincydencji nie daje jednoznacznej
informacji o długości klucza, wskazując na klucze o długości 3 lub 4

(szyfrogramy 2 i 7) oraz 2 lub 4 znaków (szyfrogram 3). Dla szyfrogramów o
numerach 4 i 6 indeks koincydencji wskazuje na klucze o długości 7 i 9 znaków.

Dla stosunkowo krótkich depesz, z jakimi mamy do czynienia, wyniki badania
indeksu koincydencji rzadko dają jednoznaczny wynik. Ponieważ dla kilku

szyfrogramów badanie wskazuje na klucz o 4 znakach, a dla innych ta sama
długość klucza jest prawdopodobna, przyjmijmy ją jako hipotezę dla dalszych

badań, zestawiając odpowiednie szyfrogramy. Uwaga! Samo stwierdzenie, że
szyfrogramy zostały zaszyfrowane przy użyciu klucza o tej samej długości nie

stanowi potwierdzenia, że w każdym wypadku użyto tego samego klucza. W zasadzie
należałoby przeprowadzić np. badanie indeksów koincydencji pomiędzy

poszczególnymi parami. Jednak powtórzenia długich fragmentów tekstów w
pierwszych dwóch parach szyfrogramów (sekwencja UIPU ULMX) oraz liczne

koincydencje znaków pozwalają nam zaryzykować założenie, że wszystkie
szyfrogramy zostały zaszyfrowane tym samym kluczem.

EDWUSILSUPYVKRGSUIPUULMXPWYVYPYEKRGSCDWXBSUUJIQLYAWEKKYRXEARXIEGXEIDKHSHBEAQCXM

H
UIPUULMXPWMYVSQAVWUGTIXSCEBQUVWHDSJGQMGOUWGSJGCGZYZDSOMOKRCBGHXAOAGWDRYKDCKOSII

MCXMH
CCKWDVGSZSXQMNGCOVACRSDXCEHWCXNGNIHKMMCEKPRWBRYLIALQWAMTOGYFKPGRIGXWCXMKMMUQCXC

HYAYFSEXFKOMOCXMH
JEQSNEQQWIRJSMNGJCABSOCJMOFGPJQSWSXWLCAMJCUSXEJSMDLAODXSCEBSXEIDKHYFSEQLYT

XEIDKHYFSIIWBGIZYJDKKYKGJPGOSEJSWELAOHCHOWXRLCRCBSRCSGFTIQMRVMUQLCJTODNGCVCVXMY
LKOQLYT

Dalsze prace nad grupą depesz prowadzimy przy założeniu, że tekstem jawnym

początku drugiego szyfrogramu jest słowo KERCKHOFFS. Otrzymujemy dzięki niemu
następujący fragment tabeli 4 użytych alfabetów szyfrowych:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

1 P U
2 I L W

3 M P
4 U X

Uzupełniając tabelę w oparciu o zasadę symetrii pozycji otrzymujemy:

ABCDEFGHIJKLMNOPQRSTUVWXYZ
1 M P U X

2 I L W
3 M P U X

4 U X M P

Dysponując znajomością części alfabetów szyfrowych wpisujemy pod tekstami

szyfrogramu znane znaki jawne, dzięki czemu uzyskujemy fragmenty tekstu jawnego
pozwalające nam odgadnąć słowo UZYCIE na początku pierwszego szyfrogramu i

NAKLADANIE na początku ostatniego. Uzupełniając tabelę alfabetów szyfrowych o
nowe znaki otrzymujemy:

©ŁAMACZE SZYFRÓW

3

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

ABCDEFGHIJKLMNOPQRSTUVWXYZ
1 LM P S U WX DE I

2 E I LM P S U WX D
3 DE I LM P S U WX

4 S U WX DE I LM P

Proces znany z poprzedniego wykładu można kontynuować formułując kolejne
hipotezy, jednak rzut oka na powyższą tabelę alfabetów szyfrowych pozwala

odgadnąć, że znaki występują w niej w naturalnej kolejności alfabetycznej; mamy
do czynienia z klasyczną tablicą Vigenere’a, bez słowa kluczowego. Uzupełnienie

tabeli i całkowite odczytanie szyfrogramów jest w tej sytuacji zadaniem
trywialnym. Na zakończenie przykładu warto dodać, że szyfrogramy, które

odrzuciliśmy z racji innej długości klucza, sygnalizowanej przez wartość
indeksu koincydencji, w rzeczywistości zostały zaszyfrowane tym samym kluczem,

co pozostałe. Należy pamiętać, że test indeksu koincydencji ma charakter
statystyczny, a statystyka zawodzi tym bardziej, im mniejsza próbka (czytaj -

długość badanego tekstu). Na szczęście okazało się, że pozostałe szyfrogramy
były zupełnie wystarczające dla odnalezienia rozwiązania. Podkreślmy także, że

punktem wyjścia dla analizy był tym razem stosunkowo krótki tekst jawny.

Czas na praktyczne zastosowanie nakładania Kerckhoffsa. Przejęliśmy następującą
paczkę szyfrogramów, których językiem tekstu jawnego jest język polski.

OSZCHSZNEAWGESLQTIVYTEPOVRESAVVMUEYWPPWNASHIORECHICCHWYVZHQGESLDCSONPSVSKAKZPRE

SYEQNJGESCIVSCAOHZT

OSSHKBODIPOFESEVWRKOXHGGCDPEGGZTSNNRDXGTHLDXDIDEZWOXCQZWITFPKICBSNXYCBQWTKGTBNE
SLBGEZHZHKBAEIKIAVSLRQUDXDI

OSPFKIYWPNGCXTWBTMOHZTQHCDUALGHWYMACMVKBJWPCASPFKIYWPNVSCSVSCSKRPVSONWESZHJWPTN

NJNWQTIHODXKDZHSFZXJOOVQULPEBTIOHZT

OSHSHNMYHMCCCDTVWJFHTKNRYMTPHELORBSBCKPGWMLGYBGGZTLRHEKCBTQQZXGSSPTIYSSEZDTKCFE
SEICFTPZBKQCSSSSFESE

OSZFFKESUOKAAEJWTWPCAXNNPGEOVSIDLREOFXNNJQQXPTKNJGFSDXKDEVVSNMWNPVKNPVKYZRPFFHA

FKIJWPRWXPNLFLAUADONNJHHSDXKD

OSYNHENHPNXOEINWTTNNPGEKFHAFKIJWPDWDWEJCHEJSYEPFKIYWLDAFZDAFZWPCASZFFKESUHVWPWE
SNSCWPRVOASNCHCJIXINRHEVSCSOHZT

OSLWPVSGKIFYZQLOYMEGESLCOHWQAPQHZRNSKINKZAURZHUGASVMNNEHCDAQTIFYZQLOYMEGESLZLGV

BTOKQKIGIUISDFRGQTIVSMVWGESL

OSIKNRNMTCPNEIGBWFESEHUVPROTDBCSLRBNHDVHFMPXGSMMPVDLWROIBGOJLPPHUATSLTDVPGBBBHE
WIHDCZXTFCTTICGSXLNPVMFESE

Nasłuch radiowy twierdzi, że szyfrogramy mogą pochodzić z różnych sieci

łączności, a przez to - być zaszyfrowane różnymi kluczami. Teksty szyfrogramów
mogą zawierać stereotypowe początki i zakończenia, o czym świadczą identyczne

dwie pierwsze litery wszystkich szyfrogramów. Z wcześniejszego doświadczenia
wiemy, że jednostki przeciwnika rozpoczynają każdy szyfrogram od formuły DO, po

której następuje oznaczenie jednostki, do której szyfrogram jest kierowany

©ŁAMACZE SZYFRÓW

4

www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

(DOPIERWSZEGOBATALIONU, DOSZTABU, DODOWODZTWA itd.). Wiemy także, że zdania w
tekstach jawnych kończone są frazą STOP, zastępującą kropkę. Zakładamy, że

szyfrogram o pierwszych literach OSPF zaczyna się od tekstu jawnego DOTRZECIEJ.

Polecenia:

1. Stwórz tablicę alfabetów szyfrowych za pomocą słowa lamacze i zaszyfruj

opisany poniżej tekst słowem kluczowym szyfrow. Podaj zaszyfrowany
tekst. Tekst do zaszyfrowania to imiona i nazwiska trzech wykładowców

kursu kryptologicznego opisanych na naszej stronie, ułożone w kolejności
alfabetycznej (analogicznie do podobnych poprzednich zadań)

2. Na którą godzinę dowództwo zaplanowało przeciwuderzenie? Odpowiedzi należy

udzielić cytując określenie godziny zawarte w szyfrogramie.

3. Podaj najkrótszy klucz użyty do szyfrowania analizowanych szyfrogramów.

POWODZENIA

©ŁAMACZE SZYFRÓW

5

www.lamaczeszyfrow.pl