krypt_zlam_szyfr.pdf

Złam szyfr i odkryj tajemnic ę

Krzysztof Ma ć kowiak

www.centrum.bezpieczenstwa.pl

Od wieków toczy się walka pomiędzy twórcami szyfrów a tymi, których zadaniem jest ich łamanie.

W ten sposób powstała dziedzina wiedzy i badań zwana kryptoanalizą, która zajmuje się metodami

łamania szyfrów. Szyfry odgrywały znaczącą rolę w konfliktach zbrojnych a odkrycie tajemnicy

decydowało w wielu przypadkach o przebiegu wojen i losach imperiów. Przykładem z historii I

wojny światowej moŜe być odszyfrowanie telegramu Zimmermanna, w którym to Niemcy

proponują Meksykowi przymierze w przypadku, gdyby Stany Zjednoczone nie utrzymały

neutralności. Odszyfrowany telegram przyczynił się do podjęcia decyzji o zaangaŜowaniu się

Stanów Zjednoczonych w wojnę. Szyfry wykorzystywane były takŜe do mniej znaczących spraw np.

w słynnym dziele “Kamasutra” zaleca się kobietom poznanie 64 sztuk, takich jak gotowanie,

ubieranie się, masaŜ, przygotowanie perfum, wróŜbiarstwo, introligatorstwo, stolarka a takŜe jako

pozycja numer 45 -- mlecchita- vikalpa , czyli sztuka posługiwania się tajnym pismem, która miała

pomóc kobietom w ukrywaniu swoich związków.

Mając wgląd w historię metody skutecznego ukrywania danych oraz sposoby ich łamania były na

wagę złota. Wiele państw, w tym takŜe Watykan, tworzyło specjalne zespoły kryptologów zwane

tajnymi kancelariami.

W VIII/IX wieku, kiedy to Europa tkwiła w intelektualnych ciemnościach, uczeni arabscy wynaleźli

metodę łamania monoalfabetycznego szyfru podstawieniowego, polegającego na zastępowaniu

poszczególnych liter innymi znakami lub symbolami zgodnie z określoną zasadą lub stworzoną

tablicą podstawieniową. Szyfr ten wydawał się być wystarczający do ukrywania tajemnicy. To

właśnie tam szukać naleŜy początku tej fascynującej dziedziny nauki jaką jest kryptoanaliza.

Arabowie odkryli metodę częstości występowania poszczególnych liter w szyfrogramie (zostanie

ona omówiona w dalszej części artykułu), dzięki rozwojowi w takich dziedzinach nauki jak

matematyka, statystyka oraz lingwistyka.

Szyfry historyczne

Bezpieczeństwo szyfrów historycznych jest z reguły niskie. W większości przypadków z

wykorzystaniem komputerów szyfrogramy mogą zostać odszyfrowane w czasie krótszym niŜ 1

sekunda.

Najprostsze monoalfabetyczne szyfry podstawieniowe jak np. szyfr Cezara, powstają przez zamianę

kaŜdej litery alfabetu na inną, która w alfabecie połoŜona jest o określoną liczbę miejsc dalej.

Przykładowo Cezar w swoim szyfrze zamieniał literę A na D, B na E itd. (przesunięcie o 3 pozycje).

W celu odszyfrowania tekstu wystarczy przesunąć kaŜdą literę o trzy pozycje w lewo (lub dla

alfabetu o długości 26 o 23 (26-3) pozycje w prawo). Choć szyfr jest bardzo prosty do złamania

stosowany był jeszcze w 1915 roku w armii rosyjskiej, gdyŜ tylko tak prosty szyfr wydawał się być

zrozumiały dla sztabowców. Następca Cezara -- Oktawian August -- był jeszcze bardziej leniwy i

stosował przesunięcie zaledwie o 1 pozycję w alfabecie. NaleŜy zwrócić uwagę, Ŝe wielokrotne

wykonanie szyfrowania w tym przypadku nie zwiększa bezpieczeństwa. Gdy zaszyfrujemy tekst

jawny z przesunięciem o 3 a następnie wynik ponownie zaszyfrujemy z przesunięciem o 5 to

otrzymamy identyczny tekst tajny, jaki powstaje przez zaszyfrowanie tekstu jawnego z

przesunięciem o 8. Ogólna metoda łamania tego typu szyfrów polega na zamianie kaŜdej litery w

kolejnych krokach o wszystkie moŜliwe pozycje. Następnie z otrzymanego zbioru tekstów

wyszukujemy ten, który ma sens. W ten sposób moŜemy odszyfrować szyfrogramy, które powstały

z wykorzystaniem szyfrów: Cezara czy ROT-13. Atak taki nazywamy atakiem brutalnym, gdyŜ

polega on na przeszukaniu całej przestrzeni klucza. W przypadku tak prostego szyfru mamy do

sprawdzenia zaledwie 25 moŜliwości (dla alfabetu składającego się z 26 liter). Prosty algorytm

prezentujący atak brutalny przedstawiony jest na Listungu 1.

Listing 1. Kryptoanaliza prostych szyfrów podstawieniowych.

#include <stdio.h>

#include <iostream.h>

#include <math.h>

void main()

{

FILE *we, *wy;

char c; //znak odczytany z pliku

char plainfile[20]; //nazwa pliku z tekstem jawnym

char cipherfile[20]; //nazwa pliku z tekstem zaszyfrownym

int offset; //wartosc przesuniecia

cout<<"Podaj nazwe pliku zawierajacego tekst zaszyfrowany: ";

cin>>cipherfile;

cout<<"Podaj nazwe pliku,w ktorym zapisany ma byc tekst odszyfrowany: " ;

cin>>plainfile;

if((wy=fopen(plainfile,"wb"))!=NULL) //otwieranie pliku do zapisu

{

for (offset=1;offset<27;offset++)

{

if((we=fopen(cipherfile,"rb"))!=NULL) //otwieranie pliku do odczytu

{

while((c=getc(we))!=EOF)

{

//Kazdy odczytywany znak wg kodów ASCII nale Ŝ y do jednej z 3 grup:du Ŝ e litery, małe litery, cyfry

if ((c>=65)&&(c<=90))

{

c-=65;

c-=offset;

if (c<0)

c=26-fabs(c);

c+=65;

putc(c,wy);

}

else if ((c>=97)&&(c<=122))

{

c-=97;

c-=offset;

if (c<0)

c=26-fabs(c);

c+=97;

putc(c,wy);

}

else if ((c>=48)&&(c<=57))

{

c-=48;

if (offset<=10)

c-=offset;

else if (offset<=20)

{

offset-=10;

c-=offset;

}

else

{

offset-=20;

c-=offset;

}

if (c<0)

c=10-fabs(c);

c+=48;

putc(c,wy);

}

c=*"endl";

putc(c,wy);

fclose(we);

}

fclose(wy);

}

cout<<"Deszyfrowanie zostalo zakonczone";

return;

}

W przypadku współczesnych algorytmów atak taki jest z reguły nieskuteczny, gdyŜ zakładając

odpowiednią długość klucza, nie jesteśmy w stanie korzystając z dostępnych zasobów

komputerowych i czasowych, złamać takich algorytmów, próbując wszystkich moŜliwych

kombinacji klucza. Algorytmy takie nazywamy bezpiecznymi obliczeniowo. JuŜ dla prostego szyfru

podstawieniowego, gdzie kaŜdą literę zamieniamy na inną, zgodnie z przygotowaną tablicą (nie

występuje tutaj zasada, Ŝe litera leŜy o określoną pozycję dalej w alfabecie) ilość moŜliwości

wynosi 26! czyli około 403291461126605635584000000, co stanowi 10 rzędów wielkości więcej

niŜ zakres kluczy algorytmu DES. Arabscy naukowcy odkryli inny sposób łamania szyfrów

podstawieniowych, bez sprawdzania wszystkich moŜliwych kombinacji, metoda ta zwana jest

analizą częstości występowania poszczególnych liter.

Analiza cz ę sto ś ci wyst ę powania poszczególnych liter

Metoda ta nadaje się do kryptoanalizy monoalfabetycznych szyfrów podstawieniowych. Między

innymi do łamania takich algorytmów jak szyfr Cezara czy ROT-13, ale nie tylko. Do szyfrów

monoalfabetycznych zaliczamy równieŜ szyfry, w których poszczególne litery zamieniane były na

inne znaki, symbole i litery zgodnie z określoną tablicą podstawieniową, która była podstawą

bezpieczeństwa tych algorytmów i musiała pozostać w tajemnicy a jednocześnie musiała być znana

obu stroną biorącym udział w przesyłaniu szyfrogramu. Metoda ta wykorzystuje fakt, Ŝe w kaŜdym

języku róŜne znaki występują z róŜną charakterystyczną dla siebie częstotliwością. Wiadomo, Ŝe w

języku polskim częściej występuje np. litera a niŜ ź i tak dalej. Podstawą tej metody jest tabela

częstości, która powstaje poprzez przeanalizowanie reprezentacyjnej próbki tekstów w wybranym

języku, zliczenie ilości występowania kaŜdego znaku i podzieleniu tej liczby przez ilość wszystkich

znaków w tekście. Podobnie postępujemy z tekstem zaszyfrowanym -- zliczamy ilość wystąpień

poszczególnych znaków, symbolów i tworzymy drugą tabelę częstości, tym razem dla tekstu

zaszyfrowanego. W celu obliczenia statystyk występowania poszczególnych znaków w tekście

moŜna skorzystać z programu dostępnego pod adresem

http://www.wiw.pl/modelowanie/prog/poe/zip/poe.zip lub teŜ oprogramowania CrypTool,

prezentowanego w dalszej części artykułu. W ostatnim kroku porównujemy dwie tabele i na

podstawie analizy określamy jakie litery tekstu jawnego mogą odpowiadać znakom, symbolom w

tekście zaszyfrowanym. Najczęściej wnioskujemy 3 lub 4 znaki i dokonujemy ich zastąpienia w

tekście zaszyfrowanym. Czytając taki zmodyfikowany tekst zaszyfrowany próbujemy znaleźć

słowa, gdzie brakuje niewielu liter i na podstawie dedukcji odkrywamy kolejne odpowiedniki

znaków. W tej drugiej fazie z pomocą mogą nam przyjść programy pisane z myślą o

krzyŜówkowiczach ( http://republika.pl/programyaionela/ , http://www.crosswordman.com/tea.html ,

http://www.mopsik.pl/ ). Tekst zaszyfrowany w tym przypadku powinien być dość długi, gdyŜ przy

krótkich tekstach moŜe się zdarzyć, Ŝe nie zostanie zachowana charakterystyka języka naturalnego.

Podobnie postępujemy w przypadku szyfrów przestawieniowych, czyli takich w których wszystkie

znaki tekstu jawnego występują w niezmienionej formie w szyfrogramie, tylko w innej kolejności.

Przykładowo mamy jakąś figurę i wpisujemy do niej tekst wierszami a następnie odczytujemy

kolumnami i w ten prosty sposób otrzymujemy tekst zaszyfrowany. W przypadku takich szyfrów

zamiast analizy częstości występowania poszczególnych liter, zliczamy ilość występowania

digramów (par liter) lub trigramów (trójek liter). Podobnie jak w przypadku pojedynczych liter

tworzymy tablicę rozkładu częstotliwości dla zwykłego tekstu i tekstu zaszyfrowanego a następnie

dokonujemy porównań i wnioskujemy w jaki sposób została zamieniona kolejność znaków

względem tekstu jawnego.

Bardziej zaawansowaną metodą dla szyfrów podstawieniowych jest algorytm relaksacyjny. Metoda

ta polega na wyznaczeniu dla kaŜdej litery tekstu jawnego x oraz kryptogramu y

prawdopodobieństwa P[f( x )= y ]. Tak obliczone prawdopodobieństwa są następnie iteracyjnie

aktualizowane na podstawie częstości występowania trigramów.

Mimo znanych metod kryptoanalizy proste szyfry monoalfabetyczne stosowano do utajnienia

tekstów tajnych i poufnych przez wiele wieków. Jeszcze w czasie II wojny światowej szyfry te były

wykorzystywane (czasami z elementami szyfrów homofonicznych), takŜe przez AK na terenach

polskich.

W celu uniemoŜliwienia zastosowania tych metod stworzono szyfry homofoniczne. Ich głównym

celem jest zatarcie informacji związanej z częstością wystąpienia poszczególnych znaków. W

szyfrach tych litery, które w danym języku występują częściej zastępowane są przez kilka

odpowiedników. Ilość znaków odpowiadających literom tekstu jawnego ściśle związana jest z

tablicą częstości występowania poszczególnych liter. W ten sposób kaŜdy znak tekstu

zaszyfrowanego powinien występować tyle samo razy.

Szyfry wieloalfabetowe

Utrudnieniem dla kryptoanalityka moŜe być zastosowanie kilku alfabetów w procesie szyfrowania.

Przykładowo zamiast stosować przesunięcia o trzy pozycje moŜemy wykonywać na zmianę

przesunięcia np. o dwie i sześć pozycji. W ten sposób analizowanie częstości występowania

poszczególnych liter dla całego tekstu nie da poŜądanych efektów. NaleŜy zauwaŜyć jednak, Ŝe

zastosowanie metody częstości osobno dla znaków nieparzystych (przesunięcie o dwie pozycje)

oraz parzystych (przesunięcie o sześć pozycji) da nam moŜliwość odszyfrowania tekstu. Dla

utrudnienia moŜemy korzystać z wielu alfabetów a ich wybór i kolejność określić przez hasło.

Przykładowo stosując hasło DOM – stosujemy kolejno przesunięcie o 3, 14 oraz 12 pozycji. Na

takiej podstawie działa szyfr Vigenera stworzony w XVI wieku przez Blaise de Vigenera. Przez

ponad 300 lat uchodził on za szyfr niemoŜliwy do złamania. Jednak w roku 1863 oficer armii

pruskiej Friedrich Kasisky dokonał jego udanej kryptoanalizy. Głównym problemem jest w tym

przypadku odkrycie długości zastosowanego klucza (ilości róŜnych alfabetów -- przesunięć). Znając

tą długość moŜemy zastosować metodę częstości występowania poszczególnych liter dla znaków

szyfrogramu powstałych poprzez przesunięcie o taką samą ilość miejsc -- przykładowo dla hasła o

długości 3 te same przesunięcie będą miały znaki 1,4,7,...; 2,5,8,...; 3,6,9,....

Metoda Kasiskiego analizuje powtórzenia tych samych ciągów znaków. W kaŜdym języku

naturalnym występują charakterystyczne trójki, czwórki znaków -- dla języka angielskiego moŜe to

być słowo the , dla języka polskiego końcówki -anie lub czwórka szcz . W przypadku, gdy dwa takie

same ciągi znajdują się między sobą w odległości równej długości klucza, kaŜda z liter w obu tych

ciągach będzie przesuwana o tą samą pozycję i w szyfrogramie będą one miały taką samą postać i

takie same połoŜenia. Kasisky zauwaŜył tą zaleŜność i na tej podstawie złamał szyfr

wieloalfabetowy. Chcąc skorzystać z metody Kasiskiego w pierwszej kolejności wyszukujemy w

tekście zaszyfrowanym powtarzające się ciągi znaków a następnie analizujemy odstępy między

takimi samymi ciągami. Przykładowo w tekście znaleźliśmy 7 wystąpień trójki fad a odstępy

między nimi wynoszą odpowiednio 24, 12, 20, 16, 35, 44 i 92. MoŜemy zauwaŜyć, Ŝe sześć z

siedmiu wartości, reprezentujących długość odstępu, podzielnych jest przez 4 -- zatem moŜemy

przyjąć, Ŝe długość klucza wynosi 4 lub 2. Wartość 35 mogła być związana z przypadkowym

zaszyfrowaniem innego tekstu z innymi przesunięciami i w ten sposób otrzymaliśmy ten sam tekst

zaszyfrowany.

Inną metodą wyznaczającą długość hasła dla szyfrów polialfabetycznych jest indeks koincydencji.

Metoda ta zaproponowana została przez Williama Friedmana w 1920 roku. Polega na obliczeniu

wartości indeksu koincydencji dla tekstu według zadanego wzoru:

∑ ∈ B F F 1

N N 1

IC =

F - liczba wystąpień litery β z alfabetu B w tekście o długości N.

Zgodnie ze wzorem obliczamy liczbę wystąpień wszystkich znaków, zliczamy długość tekstu i

podstawiamy do wzoru, otrzymując wartość indeksu koincydencji (IC). Następnie korzystając z

Tabeli 1. określamy długość zastosowanego hasła.

Tabela 1. Odwzorowanie wartości in deksu na długość zastosowanego hasła.

Długość

0,066

0,052

0,047

0,045

0,044

0,041

bardzo duŜe

0,038

Przykładowo, gdy otrzymamy wartość indeksu zbliŜoną do 0,06 moŜemy przypuszczać, Ŝe długość

hasła (ilość zastosowanych alfabetów) wynosi 1 czyli zastosowano prosty szyfr monoalfabetyczny.

W literaturze moŜemy znaleźć równieŜ inną postać tej metody. Polega ona na zliczaniu ilości

znaków pokrywających się w obu tekstach. Teksty przesuwamy względem siebie o kolejne pozycje

i zliczamy liczbę pokrywających się znaków. Po przesunięciu tekstów o wielokrotną długość

klucza, uzyskujemy największą liczbę pokrywających się znaków. Dla dłuŜszych tekstów ilość

pokrywających się znaków powinna wynosić w przypadku języka angielskiego około 6,5-6,9%.

Przykładowo na Rysunku 1. widoczny jest wykres przedstawiający ilości pokrywających się znaków

w stosunku do przesunięcia tekstów względem siebie. Dwa zdania z tego artykułu zostały

zaszyfrowane algorytmem Vigenera z kluczem KOD. Jak widać na wykresie wartości największe

otrzymaliśmy dla przesunięcia będącego wielokrotnością liczby 3, czyli zgodnie z naszymi

oczekiwaniami.

Rysunek 1. Indeks koincydencji.

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: