Kryptologia Wyklad 4.pdf

Marek Grajek KURS KRYPTOLOGII

Podstawienia polialfabetyczne

W wykładzie poświęconym szyfrom podstawieniowym milcząco zakładaliśmy, że

w trakcie szyfrowania znaki alfabetu jawnego przechodzą nieodmiennie w znaki

jednego i tego samego alfabetu szyfrowego. Poznaliśmy także główną słabość tego

systemu szyfrowego, którą stanowi wrażliwość na analizę częstotliwości występo-

wania znaków. Kryptolodzy od kilku stuleci byli świadomi tej słabości, jak rów-

nież faktu, że propozycje zwiększenia odporności szyfru na atak wysuwane do po-

łowy XVI wieku miały połowiczną naturę. W 1553 roku Giovanni Belaso opublikował

książkę, w której zaproponował, by każda kolejna litera tekstu jawnego była

szyfrowana z użyciem innego alfabetu szyfrowego, a wybór konkretnego alfabetu

szyfrowego spośród wielu dostępnych miał być podyktowany kolejnymi literami

słowa kluczowego. Jego idea została podchwycona przez wielu kryptologów, ale

najtrwalszy był wpływ Giovanniego Battisty Porta, który zaledwie 10 lat po wy-

daniu książki Belaso publikował własny, systematyczny opis znanych ówcześnie

technik kryptograficznych pod tytułem „ De Furtivis Literarum Notis ”. Nawiasem

mówiąc, książka stała się przedmiotem jednego z najwcześniejszych znanych naru-

szeń prawa autorskiego - w 1591 roku wyszło jej londyńskie, pirackie wydanie.

W 1586 roku wyszła drukiem książka Blaise de Vigenère’a pod tytułem „ Traicté

des Chiffres ”, w którym pojawiło się m.in. miłe każdemu kryptologowi zdanie

„każda rzecz tego świata stanowi szyfr”. Vigenère opisał w swojej książce sys-

temy utajniania informacji znane w jego czasach, jak również zaproponował kilka

nowych, interesujących rozwiązań. Nieco paradoksalnie, współcześnie kryptolodzy

posługują się określeniem „tablica Vigenère’a” w odniesieniu do czegoś, co sta-

nowi uproszczenie jego prawdziwych pomysłów. Ponieważ jednak tablica (lub z

francuska tableau ) Vigenère’a jest traktowana współcześnie jako sztandarowy

przykład użycia podstawień polialfabetycznych, musimy się z nią zapoznać. Kon-

struujemy tablicę alfabetów szyfrowych, w której każdy kolejny wiersz jest

przesunięty w stosunku do poprzedniego o jedną pozycję, 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 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

F 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 E

G G H I J K L M N O P Q R S T U V W X Y Z A B C D E F

H H I J K L M N O P Q R S T U V W X Y Z A B C D E F G

I I J K L M N O P Q R S T U V W X Y Z A B C D E F G H

J J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

K K L M N O P Q R S T U V W X Y Z A B C D E F G H I J

L L M N O P Q R S T U V W X Y Z A B C D E F G H I J K

M M N O P Q R S T U V W X Y Z A B C D E F G H I J K L

N N O P Q R S T U V W X Y Z A B C D E F G H I J K L M

O O P Q R S T U V W X Y Z A B C D E F G H I J K L M N

P P Q R S T U V W X Y Z A B C D E F G H I J K L M N O

Q Q R S T U V W X Y Z A B C D E F G H I J K L M N O P

R R S T U V W X Y Z A B C D E F G H I J K L M N O P Q

S S T U V W X Y Z A B C D E F G H I J K L M N O P Q R

T T U V W X Y Z A B C D E F G H I J K L M N O P Q R S

U U V W X Y Z A B C D E F G H I J K L M N O P Q R S T

V V W X Y Z A B C D E F G H I J K L M N O P Q R S T U

W W X Y Z A B C D E F G H I J K L M N O P Q R S T U V

X X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

Y Y Z A B C D E F G H I J K L M N O P Q R S T U V W X

Z Z 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

Blaise de VIGENÈRE

i tablica Vigenère'a

©ŁAMACZE SZYFRÓW 1 www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

Oczywiście wiersze tablicy Vigenère’a można równie dobrze konstruować z wyko-

rzystaniem alfabetów szyfrowych, w których poszczególne znaki nie są uporządko-

wane w kolejności alfabetycznej. W szczególności możliwy jest sposób konstruk-

cji alfabetu szyfrowego oparty na słowie kluczowym, zaprezentowany w jednym z

poprzednich wykładów. Istotne jest, że poszczególne wiersze tablicy są kolejno

przesunięte o jedną pozycję, dając w efekcie inny alfabet szyfrowy. Sposób po-

sługiwania się tablicą jest względnie prosty. Załóżmy, że dysponujemy słowem

kluczowym VIGENR (utworzonym z nazwiska renesansowego kryptologa) i tekstem

jawnym BLAISE (równoważnym jego imieniu). Bierzemy pierwszy znak tekstu jawnego

i pierwszy znak klucza: B i V . Wybieramy w tablicy wiersz rozpoczynający się od

litery V i znajdujemy w nim szyfrowy odpowiednik litery B - jest nim litera W .

Następnie bierzemy kolejny znak tekstu jawnego - L i kolejny znak klucza - I .

Znajdujemy odpowiednik litery L w wierszu tablicy rozpoczynającym się od litery

I ; jest nim T . Postępujemy w opisany sposób aż do wyczerpania liter klucza, po

czym powracamy do litery V i kontynuujemy szyfrowanie, otrzymując szyfrogram o

treści WTGMFV .

Zauważmy, że w procesie szyfrowania kolejnych znaków tekstu jawnego używamy

tylu różnych alfabetów szyfrowych, ile różnych liter liczy słowo kluczowe. Dla

odróżnienia tej sytuacji od znanego nam szyfru podstawieniowego z jednym alfa-

betem szyfrowym, tamten prosty wariant otrzymał nazwę podstawienia monoalfabe-

tycznego, a system opisywany w niniejszym wykładzie jest określany mianem pod-

stawienia polialfabetycznego. Zastosowanie różnych alfabetów szyfrowych w trak-

cie szyfrowania tego samego tekstu jawnego musi prowadzić do zatarcia staty-

stycznych właściwości tekstu jawnego i szyfrogramu, m.in. do spłaszczenia

struktury wykresu częstości. Sprawdźmy, jak to oczekiwanie potwierdza się w

praktyce, szyfrując kluczem VIGENR tekst jawny

PROBKATESKTUJAWNEGOWJEZYKUPOLSKIMZASTOSOWANADLADEMONSTRACJICECHSZYFRUPODSTAWIEN

IAPOLIALFABETYCZNEGOWEDLUGSYSTEMUVIGENERAOCZEKIWANYMSKUTKIEMUZYCIASZYFRUVIGENER

AJESTZAKLOCENIECZESTOTLIWOSCIWYSTEPOWANIAZNAKOWWSTOSUNKUDOSZYFRUPODSTAWIENIAMON

OALFABETYCZNEGO

otrzymując szyfrogram w postaci

KZUFXROMYOGLEICRRXJEPIMPFCVSYJFQSDNJOWYSJRIIJPNUZUURFKMIINVTZKNWMPAZATBUNBGAVVI

QGTBCDIRJNSZBEGMEZOUARUGCMWLJOMSYIZBMTIERJKFIXZRITCZJFCZOVVHCFCPZVAFCSIPDOKREZZ

GNRJOHGOYFXMTMRTUMYXBKGQCSFTDEEWGVKWCEAZVHTEXFREYXBJPVQYQFNHEJELKWJWGRRQKRVRHWT

SNCAIHIGPXHTITF

i wyznaczając diagram częstości występowania znaków w szyfrogramie (poniżej).

©ŁAMACZE SZYFRÓW 2 www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

Bez wątpienia statystyczna struktura tekstu w języku polskim uległa poważnemu

zniekształceniu. Najczęściej występujący w języku polskim znak A występuje w

szyfrogramie z częstotliwością poniżej 3%, widoczne jest także oczekiwane

spłaszczenie struktury wykresu. Nadzieje autorów szyfru podstawienia polialfa-

betycznego zostały spełnione - klasyczny atak metodą częstości występowania

znaków jest wobec niego bezskuteczny. W czasach Vigenère’a nie znano innych me-

tod ataku na szyfry, zatem podstawienie polialfabetyczne zyskało nieco chełpli-

we określenie „ le chiffre indéchiffreable ” - szyfru nie do złamania. W później-

szych czasach wielu kryptografów określało takim samym mianem zaprojektowane

przez siebie systemy; prawie bez wyjątku były one łamane w krótkim czasie. Ale

trzeba przyznać, że chiffre indéchiffreable dość długo musiał czekać na swojego

pogromcę.

W 1863 roku urodzony w Człuchowie Friedrich Kasiski (miejsce urodzenie i nazwi-

sko sugerują polskie korzenie) opublikował książeczkę pod tytułem „Die Geheim-

schriften und die Dechiffrierkunst”, poświęcając większą część jej treści po-

szukiwaniu metody łamania szyfrów polialfabetycznych. Pamiętamy, że w podsta-

wieniu polialfabetycznym szyfrant używa kolejno tylu różnych alfabetów szyfro-

wych, ile znaków liczy sobie słowo kluczowe, po czy powraca do pierwszego uży-

tego alfabetu i kontynuuje swoje działanie. Kasiski zauważył, że w treści depe-

szy często występują powtarzające się fragmenty. Jeżeli ich wystąpienia wypadną

w tych samych punktach powtórzonego cyklu klucza, zostaną zaszyfrowane w iden-

tyczny sposób. Zaszyfrujmy frazę cipheringanddeciphering kluczem KASISKI,

otrzymując:

mihpwbqxgsvvnmmihpwbqxg

Otrzymaliśmy w szyfrogramie powtórzenie tekstu (zaznaczone podkreśleniem) o

znaczącej długości. Oczywiście tak ewidentny przykład nałożenia klucza i tekstu

jawnego w szyfrogramie należy do rzadkości. Zgodnie z oryginalną metodologią

Kasiskiego należało wyszukać wszelkie powtórzenia grup znaków w szyfrogramie,

niezależnie od ich długości, zliczyć odległości pomiędzy początkami powtórzeń

tej samej grupy znaków i przystąpić do określenia przypuszczalnej długości klu-

cza metodą rozkładu otrzymanych odległości na czynniki. Załóżmy, że otrzymali-

śmy następującą sekwencję odległości pomiędzy powtórzeniami tekstu w szyfrogra-

mie: 84, 114 i 198 znaków. Przytoczone liczby można rozłożyć na czynniki w na-

stępujący sposób:

84 = 2·2·3·7

114 = 2·3·19

198 = 2·3·3·11

Wartości 2 i 3 są zbyt małe, jak dla długości klucza. Ale wspólny czynnik roz-

kładów w postaci 2·3 = 6 znaków jest dobrą hipotezą.

Przybliżamy się do celu całej gimnastyki związanej z określaniem prawdopodobnej

długości klucza szyfru. Weźmy dwa dowolne powtórzenia w szyfrogramie, które po-

służyły nam do wyznaczenia długości klucza. Pierwsze litery obu powtórzeń zo-

stały zaszyfrowane z wykorzystaniem tego samego alfabetu szyfrowego. Drugie li-

tery - innego, ale też identycznego alfabetu. Podobnie trzecie, czwarte itd.

Wyznaczenie długości klucza pozwala nam podzielić szyfrogram na grupy znaków,

które zostały zaszyfrowane tym samym alfabetem szyfrowym, czyli przy użyciu

podstawienia monoalfabetycznego. A podstawienia monoalfabetyczne potrafimy ła-

mać metodą analizy częstotliwości występowania znaków! Rysuje się prosta metod

ataku na szyfr polialfabetyczny:

©ŁAMACZE SZYFRÓW 3 www.lamaczeszyfrow.pl

Marek Grajek KURS KRYPTOLOGII

1. Wyznaczyć metodą Kasiskiego prawdopodobną długość klucza.

2. Podzielić tekst szyfrogramu na grupy w liczbie odpowiadającej liczbie zna-

ków w prawdopodobnym słowie kluczowym, zaliczając do każdej grupy (np.

przy hipotetycznej długości słowa kluczowego 6 znaków) wszystkie pierwsze,

drugie, trzecie, ... szóste litery w szyfrogramie.

3. Wewnątrz każdej z tak wyznaczonych grup zastosować niezależnie metodę ana-

lizy częstotliwości występowania znaków.

4. Połączyć rezultaty sześciu operacji z punktu 3.

Cóż jednak uczynić, gdy w szyfrogramie brak powtórzeń, albo też odległości po-

między istniejącymi nie układają się w powtarzalny wzór? Na rozwiązanie takiego

problemu kryptoanaliza musiała czekać aż do 1920 roku, kiedy to amerykański

kryptolog, William Friedman, napisał niewielką pracę zatytułowaną „The Index of

Coincidence and Its Applications in Cryptology”. Opisaną w niej koncepcję in-

deksu koincydencji najłatwiej wyjaśnić na przykładzie. Weźmy dwa fragmenty tek-

stu np. w języku niemieckim i zapiszmy je jeden pod drugim, po czym policzmy

kolumny tekstu, w których pojawiły się identyczne znaki (podkreślając te

znaki).

DIEARBEITDERBRITISCHENMARINEINTELLIGENCEINDENJAHR

INDIESEMBUCHSCHIENDASLETZTEWORTUBERVORHERDISKUTIE

Wśród 50 znaków znaleźliśmy 3 pary identycznych znaków w kolumnach - Friedman

określał takie pary mianem koincydencji. Okazuje się, że relacja liczby koincy-

dencji do długości tekstu jest w przybliżeniu stała dla danego języka i stanowi

równie charakterystyczny parametr, jak częstotliwość występowania znaków. Dla

języka niemieckiego wynosi ona około 8%; wynik zaobserwowany w przykładzie po-

wyżej jest nieco poniżej normy. Oczywiście powstaje pytanie, czy identyczne

zjawisko zachodzi także dla tekstu przypadkowego lub tekstu w różnych językach?

Zestawmy obie niemieckojęzyczne frazy z równej im długości tekstem przypadko-

wym:

DIEARBEITDERBRITISCHENMARINEINTELLIGENCEINDENJAHR

UQSRZUKNUQSIUDQEUQFKABRRUQHSDIBCSZUVTBVUCGOOZVVTW

INDIESEMBUCHSCHIENDASLETZTEWORTUBERVORHERDISKUTIE

UQSRZUKNUQSIUDQEUQFKABRRUQHSDIBCSZUVTBVUCGOOZVVTW

W pierwszej parze nie otrzymaliśmy żadnej koincydencji, w drugiej jedną. Na ra-

zie mechanizm Friedmana działa, a to dopiero początek jego magii. Zaszyfrujmy

obie przykładowe frazy szyfrem Vigenère’a, najpierw tym samym kluczem (np. KO-

WAL ), następnie dwoma różnymi kluczami ( KOWAL i METAL ), po czym zestawmy wyniki

szyfrowania.

NWAACLSETOOFXRTDWOCSOBIACSBAIYDSHLTQSJCPSBZEYTODR

SBZIPCSIBFMVOCSSSJDLCZATKDSSOCDIXECFCNHPBRESVEHEE

NWAACLSETOOFXRTDWOCSOBIACSBAIYDSHLTQSJCPSBZEYTODR

URWIPEIFBFOLLCSUIGDLEPXTKFIPOCFYUECHSKHPDHBSVGXBE

Zauważmy, że szyfrowanie tym samym kluczem (pierwsza para) zachowało nie tylko

liczbę koincydencji w tekście, lecz także ich lokalizacje znane z porównania

tekstów jawnych, natomiast w parach szyfrowanych różnymi kluczami doliczyliśmy

Marek Grajek KURS KRYPTOLOGII

się tylko jednej koincydencji. Zyskaliśmy potężne narzędzie, umożliwiające

stwierdzenie, czy dwa teksty zostały zaszyfrowane tym samym kluczem. Zanim pod-

powiemy, w jakim stopniu koncepcja indeksu koincydencji przybliża nas to do

rozwiązania szyfru polialfabetycznego, zastanówmy się nad przyczynami, dla któ-

rych indeks koincydencji jest wartością charakterystyczną dla danego języka.

Zauważyliśmy wcześniej, że zarówno częstotliwość występowania poszczególnych

znaków w tekście jawnym, jak i liczba koincydencji obserwowanych w tekście w

stosunku do jego długości stanowią wartości charakterystyczne dla danego języ-

ka. Związek pomiędzy nimi nie jest przypadkowy. Dla alfabetu liczącego 26 zna-

ków oraz dla prawdopodobieństwa wystąpienia znaku np. a oznaczonego jako P(a),

prawdopodobieństwo wystąpienia tego samego znaku w jednej kolumnie (czyli koin-

cydencji) jest sumą kwadratów prawdopodobieństw wystąpienia wszystkich znaków

alfabetu:

κ = [P(a)] 2 + [P (b)] 2 + [P(c)] 2 + . . . + [P (z)] 2

podczas, gdy prawdopodobieństwo wystąpienia koincydencji przy całkowicie

losowym rozkładzie znaków (dla tekstu przypadkowego) wynosi:

κ =1/26 ≈ 0,0385

Ustaliliśmy w ten sposób związek pomiędzy częstotliwością występowania poszcze-

gólnych znaków w tekście jawnym w danym języku i charakterystyczną dla tego ję-

zyka wartością indeksu koincydencji. Jeżeli częstotliwość występowania znaków

w danym języku nie ulega zmianie po zaszyfrowaniu tekstu podstawieniem monoal-

fabetycznym, staje się zrozumiałe, dlaczego także liczba koincydencji nie zmie-

nia się po zaszyfrowaniu tekstu.

Otwarte pozostaje pytanie, w jaki sposób indeks koincydencji może nam pomóc w

złamaniu szyfru podstawienia polialfabetycznego? Odpowiedź jest stosunkowo pro-

sta: przecież możemy porównywać tekst z sobą samym przy różnym wzajemnym prze-

sunięciu obu kopii. Jeżeli przedstawiona powyżej teoria jest prawdziwa, przy

wzajemnym przesunięciu obu kopii tekstu równym długości klucza powinniśmy

otrzymać wartość indeksu koincydencji zdecydowanie wyższą od pozostałych kombi-

nacji. Nie zachęcamy do ręcznego obliczania wartości indeksu - to żmudna praca.

Na stronie ŁAMACZE SZYFRÓW, w dziale narzędzia można znaleźć kalkulator indeksu

koincydencji, który będzie świetnym ułatwieniem w pracy adeptów kryptologii.

Korzystając z kalkulatora indeksu koincydencji obliczyliśmy jego wartości dla

tekstu URWIPEIFBFOLLCSUIGDLEPXTKFIPOCFYUECHSKHPDHBSVGXBE z przykładu powyżej i

wzajemnych przesunięć w zakresie od 1 do 9, otrzymując następujące wartości in-

deksu:

i = 1 k = 0.021

i = 2 k = 0.021

i = 3 k = 0.065

i = 4 k = 0.000

i = 5 k = 0.068

i = 6 k = 0.047

i = 7 k = 0.048

i = 8 k = 0.024

i = 9 k = 0.000

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: