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. Wez
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
©A
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śledz
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
©A
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:
©A
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
©A
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
©A
AMACZE SZYFRÓW 5 www.lamaczeszyfrow.pl