Podstawy Ochrony Nazwisko: _______________________
Informacji Rok/grupa: _______________________
Zima 2012/2013
Ćwiczenie laboratoryjne I
Kryptoanaliza szyfrów mono- i polialfabetycznych
To jest laboratorium ćwiczeniowe. Nale\
y jest wykonać w czasie trwania zajęć. Zadanie
to nie powinno zająć więcej czasu ni\
czas trwania laboratorium. Jeśli zadanie zostanie
zakończone wcześniej, to mo\
na kontynuować prace dotyczące poprzedniego
laboratorium lub pracy semestralnej.
1. Wstęp
System kryptograficzny nazywamy symetrycznym, gdy dla ka\
dej pary kluczy (e, d)
 obliczeniowo łatwe jest określenie na podstawie znajomości jednego z kluczy z pary,
np.klucza e - drugiego klucza d.
W większości praktycznych rozwiązań algorytmów kryptografii symetrycznej e = d.
Istnieją dwie klasy szyfrów symetrycznych:
" szyfry blokowe
" szyfry strumieniowe
Poniewa\
w trakcie laboratoium będziemy zajmować sie tylko szyframi blokowmi,
dlatego informacje o szyfrach strumieniowych zostały pominięte.
Szyfr blokowy jest takim systemem szyfrującym, w którym tekst jawny dzielony jest na
ciągi równej długości t nad alfabetem AM, zwane blokami , a następnie ka\
dy z bloków
jest kolejno szyfrowany.
Przemiotem ćwiczenia są szyfry blokowe podstawieniowe monoalbabetyczne
i polialfabetyczne (patrz rys. 1).
2. Proste szyfry podstawieniowe (monoalfabetyczne)
Niech A będzie alfabetem zawierającym q symboli, zaś M zbiorem wszystkich ciągów o
A M
A M
A M
długości t nad alfabetem A
A.
A
A
Niech K A
K będzie zbiorem wszystkich permutacji na zbiorze A.
K A
K A
Dla ka\
dego e " K
" K
" K definiuje się przekształcenie szyfrujące:
" K
Ee (m) = ( e(m1) e(m2) e(m3) ... e(mt )) = ( c1 c2 c3 ... ct ) = c
gdzie:
m = ( m1 m2 m3 ... mt ) " M
" M
" M
" M
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 2
Ka\
dy symbol spośród t symboli tworzących blok zastępuje się (podstawia za niego)
innym symbolem ze zbioru A , zgodnie z ustaloną permutacją e. Przekształcenie Ee
A
A
A
nazywa siÄ™ prostym (monoalfabetycznym) szyfrem podstawieniowym.
Kluczem deszyfrujÄ…cym odpowiadajÄ…cym e jest permutacja d = e -1.
Szyfry
blokowe
podstawieniowe
przestawieniowe
monoalfabetyczne
(proste)
homofoniczne
polialfabetyczne
poligramowe
produktowe
(kaskadowe)
Rys. 1 Klasyfikacja blokowych systemów kryptografii symetrycznej
Przekształcenie deszyfrujące:
Dd (c) = ( d(c1) d(c2) d(c3) ... d(ct )) = ( m1 m2 m3 ... mt ) = m
Liczba ró\
nych przekształceń szyfrujących wynosi q! i nie zale\
y od rozmiaru bloku t.
(np. dla alfabetu 26-literowego przestrzeń kluczy M H"
M zawiera 26! H" 4*10 26 elementów).
M H"
M H"
Niestety, szyfry monoalfabetyczne są podatne na atak metodami analizy częstości
występowania znaków w kryptogramie.
Metody zmniejszania skuteczności kryptoanalizy częstotliwościowej
Konfuzja (nieład)
DÄ…\
enie do "wikłania" zale\
ności Ee wią\
ącej klucz przekształcenia szyfrującego z
wiadomością jawną (a w konsekwencji tak\
e zale\
ności Dd wią\
Ä…cej klucz z
kryptogramem).
Rezultat konfuzji : Analiza statystycznych cech kryptogramu nie daje u\
ytecznych
informacji o kluczu szyfrującym przekształcenia.
Dyfuzja (rozproszenie)
"Zacieranie" cech statystycznych tekstu jawnego w trakcie wykonywania przekształcenia
szyfrującego. Stosowane metody dyfuzji sprowadzają się zasadniczo do dwóch metod
postępowania :
" stosowanie przestawień (mimo zachowania częstości występowania pojedynczych
znaków utrudnia się kryptoanalizę dzięki zaburzeniu częstości występowania
digramów, trigramów, etc.
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 3
" uzale\
nienie ka\
dego znaku kryptogramu od jak największej liczby znaków
wiadomości jawnej.
Operacją dodatkową, która mo\
e skutecznie wspomagać operację szyfrowania, jest
wstępna kompresja wiadomości jawnej przed poddaniem jej przekształceniu
szyfrujÄ…cemu.
UWAGA : W tym przypadku odbiorca musi znać metodę dekompresji..
Z reguły w fazie pośredniej odwzorowuje się pierwotny alfabet jawny na zbiór kolejnych
nieujemnych liczb całkowitych, po czym po przeprowadzeniu operacji obliczeniowych
na liczbach i uzyskaniu ciągu liczb odpowiadających wiadomości zaszyfrowanej,
powraca do pierwotnego alfabetu.
Kluczem monoalfabetycznego szyfru podstawieniowego jest pewna permutacja, która w
przypadku du\
ej mocy alfabetu wiadomości jawnych jest  kłopotliwa w zapisie.
Ze względu na łatwość implementacji stosuje się systemy z "mniejszą przypadkowością"
w wyborze klucza szyfrowania, tzw. systemy wielomianowe.
W systemach tych przekształcenie szyfrujące określone jest następująco :
f(m) = ( m t k t + m t-1 k t-1 + ... + m 1 k 1 + k 0 ) mod N
gdzie m jest nieujemną liczbą całkowitą < N , odpowiadającą literze alfabetu jawnego,
zaś zbiór:
{ k t , k t-1 , ... , k 1 , k 0 }
jest kluczem przekształcenia.
Dla wielomianów pierwszego rzędu kluczem jest para liczb k 1 i k 0 , a przekształcenie
nosi nazwę przekształcenia afinicznego.
f(m) = ( m k 1 + k 0 ) mod N
Szczególnymi przypadkami przekształcenia afinicznego są :
" przekształcenie liniowe (tzw. "przerzedzone"): f(m) = m k 1 mod N
" przesunięciowy "szyfr Cezara" : f(m) = ( m + k 0 ) mod N
Przykład szyfru Cezara:
Szyfr Cezara w wersji podstawowej polega na zastÄ…pieniu ka\
dej litery alfabetu literÄ…
znajdujÄ…cÄ… siÄ™ o trzy pozycje dalej (k1 = 1, k0 = 3):
C = E(m) = f(m) = (m+3) mod (26)
C to litera tekstu zaszyfrowanego odpowiadajÄ…ca literze tekstu jawnego o indeksie m
Przesunięcie mo\
e mieć wielkość dowolną, więc ogólna postać algorytmu wygląda
następująco:
C = E(m) = (m+k) mod (26), 0Algorytm deszyfrujący ma postać:
m = D(C) = (C-k) mod (26)
Dla szyfru Cezara (z przesunięciem o 3 znaki) klucz ma postać:
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 4
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
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
Stąd przykładowy szyfrogram ma postać
tekst jawny : szyfr juliusza cezara
tekst zaszyfrowany: VCBIU MXOLXVCD FHCDUD
Dla szyfru Cezara Å‚atwo mo\
na przeprowadzić kryptoanalizę metodą brutalną polegającą
na wypróbowaniu 25 mo\
liwych kluczy k.
W afinicznych systemach kryptograficznych istotny jest właściwy dobór parametrów
klucza.
W szczególności parametr k1 oraz liczba N określająca moc alfabetu wiadomości
jawnych muszą być względnie pierwsze. W przeciwnym przypadku nie istnieje
jednoznaczne przekształcenie deszyfrujące.
Przykład niewłaściwego wyboru klucza :
N = 26 (np. alfabet du\
ych liter łacińskich)
WybierajÄ…c k 1 = 13 i k 0 = 4 uzyskujemy :
f("A") = f(0) = ( 13 . 0 + 4 ) mod 26 = 4 mod 26 = 4 = "E"
f("C") = f(2) = ( 13 . 2 + 4 ) mod 26 = 30 mod 26 = 4 = "E"
Szyfry podstawieniow monalfabetyczne są podane na kryptoanlaizę częstotliwościową.
Dla ka\
dego języka mo\
na bowiem określić względną częstość występowania liter.
Poni\
sza tabela prezentuje procentową częstość względną występowania poszczególnych
liter w tekście angielskim.
Litera Częstość Litera Częstość Litera Częstość
(%) (%)
E 12,75 L 3,75 W 1,50
T 9,25 H 3,50 V 1,50
R 8,50 C 3,50 B 1,25
N 7,75 F 3,00 K 0,50
I 7,75 U 3,00 X 0,50
O 7,50 M 2,75 Q 0,50
A 7,25 P 2,75 Z 0,25
D 4,25 G 2,00
3. Podstawieniowe szyfry polialfabetyczne
Polialfabetycznym szyfrem podstawieniowym jest szyfr blokowy o długości bloku t nad
alfabetem A
A o następujących właściwościach:
A
A
" przestrzeń kluczy K zawiera wszystkie uporządkowane zbiory t permutacji ( p1,
K
K
K
p2, p3, ..., pt ), przy czym ka\
da permutacja pi jest określona na zbiorze A;
A
A
A
" szyfrowanie wiadomości m = ( m1 m2 m3 ... mt ) " M
" M przy pomocy klucza e = ( p1
" M
" M
, p2 , p3 , ..., pt ) " K
" K
" K jest zdefiniowane przez:
" K
Ee (m) = ( p1(m1) p2(m2) p3(m3) ... pt(mt )) = ( c1 c2 c3 ... ct ) = c
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 5
" przekształcenie deszyfrujące:
Dd (c) = (p1 -1 (c1) p2 -1 (c2) p3 -1 (c3) ... pt -1 (ct ))
zaÅ› kluczem deszyfrujÄ…cym d odpowiadajÄ…cym kluczowi e jest uporzÄ…dkowany
zbiór t permutacji odwrotnych:
d = (p1 -1 , p2 -1 , p3 -1 , ..., pt -1) " K
"
"
"
Przykład (szyfr Vigenere a):
Niech A
A = { a, b, c, ..., x, y, z } oraz t = 3. Wybierając jako klucz e zbiór trzech permutacji
A
A
( p1 , p2 , p3 ) takich, \
e p1 przesuwa ka\
dÄ… literÄ™ o 3 pozycje w prawo (szyfr Cezara), p2 -
o 7 pozycji w prawo, zaś p3 - o 10 pozycji w prawo, uzyskuje się z wiadomości jawnej:
m = thi sci phe ris cer tai nly not sec ure
kryptogram:
c = Ee(m) = wos vjs soo upc flb whs qsi qvd vlm xyo
Du\
ym ułatwieniem przy szyfrowaniu I deszyfrowaniu tekstu jest tablica Vigenere a
(patrz ni\
ej). Dla dowolnej litery tekstu jawnego a i dowolnej litery klucza k literÄ…
kryptogramu c jest znak na przecięciu kolumny a i wiersza k. Deszyfrowanie działa
podobnie. Jak?
Szyfry polialfabetyczne sÄ… tak\
e trudniejsze do przełamania od szyfrów
monoalfabetycznych, lecz  odgadnięcie długości bloku t sprowadza kryptoanalizę do
badania t przekształceń monoalfabetycznych, przy czym np. do analizy
częstotliwościowej zestawiane są podzbiory symboli kryptogramu określone zale\
nością:
Ci = { ci , ci+t , ci+2t , ..., ci+nt } (i = 1, 2, ..., t -1)
Test Kasiski ego:
Obserwacja: Powtarzalne fragmenty tekstu jawnego szyfrowane tymi samymi
fragmentami klucza dajÄ… w rezultacie identyczne segmenty kryptogramu.
Wniosek: Odstęp pomiędzy powtarzającymi się segmentami kryptogramu powinien być
wielokrotnością długości klucza t.
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 6
Metodyka: Po wyznaczeniu zbioru liczb, będących odległościami między
powtarzajÄ…cymi siÄ™ segmentami kryptogramu nale\
y wyznaczyć dla nich największy
wspólny podzielnik (gcd - greatest common divisor), który (po odrzuceniu
przypadkowych powtórzeń segmentów w krytpogramie) wska\
e długość bloku (klucza) t.
Indeks koincydencji Friedmana (IC):
IC określa prawdopodobieństwo wystąpienia w kryptogramie dwóch jednakowych liter i
wyliczany jest z zale\
ności :
n-1
fi ( fi -1)
"
i =0
IC =
L(L-1)
gdzie fi jest liczbą wystąpień litery ai w tekście o długości L zaś sumowanie obejmuje
wszystkie litery alfabetu AC.
A
A
A
Tablica 1. Wartości oczekiwanych IC dla długiego tekstu angielskiego (26 symboli w
alfabecie AM)
t 1 2 3 4 5 10
"
"
"
"
IC 0,066 0,052 0,047 0,045 0,044 0,041 0,038
Wartość oczekiwana indeksu koincydencji:
1 L-t t-1 L
E(IC)= º + ºr
p
t L-1 t L-1
gdzie:
L - długość kryptogramu;
t - okres (długość bloku);
kp - miara rozkładu prawdopodobieństwa (częstości) znaków w tekście jawnym (AM
A
A
A
zawiera N symboli):
n
º = pi2
"
p
i=1
Tablica 2. Przykładowe wartości współczynnika kp
Język kp
francuski 0.0778
hiszpański 0.0775
niemiecki 0.0762
włoski 0.0738
angielski 0.0667
rosyjski 0.0529
kr - prawdopodobieństwo pojawienia się określonego symbolu w kryptogramie przy
 idealnie płaskich charakterystykach częstotliwościowych:
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 7
1
º =
r
n
Przykład wykorzystania IC do oszacowania okresu szyfru :
Tekst angielski (du\
e litery bez spacji) po zaszyfrowaniu szyfrem podejrzewanym o to,
\
e jest polialfabetycznym szyfrem okresowym, dał następujący szyfrogram :
"GPSNBMMBOHVBHFTIBWFCFFOQMBZJOHB
GVOEBNFOUBMQPMFJODPNQVUFSTDJFODF"
Długość zaszyfrowanego tekstu L = 63 znaki.
Liczba wystąpień poszczególnych liter w kryptogramie :
FA = FK = FL = FR = 0 FB = FC = FE = FI = FW = FZ = 1
FD = FH = FJ = FN = FP = FQ = FV = 3 FF = 9
FG = FS = FT = FU = 2 FM = 5 FO = 7
Wyliczony na podstawie powy\
szych danych wskaz
nik zgodności :
IC = 0,061
A zatem nale\
y podejrzewać, i\
jest to szyfr monoalfabetyczny. PodstawiajÄ…c d = 1,
I zakładając, i\
litera F o największej liczbie powtórzeń odpowiada literze E o
największej częstotliwości występowania, otrzymuje się natychmiast rozwiązanie (gdy\

k1 = 1) :
"FORMALLANGUAGESHAVEBEENPLAYINGA
FUNDAMENTALROLEINCOMPUTERSCIENCE"
zaś po uzupełnieniu domyślnymi spacjami :
"FORMAL LANGUAGES HAVE BEEN PLAYING A
FUNDAMENTAL ROLE IN COMPUTER SCIENCE"
4. Ćwiczenie
W ramach ćwiczenia dostępne są dwie aplikacje (pracujące w środowisku MS-DOS).
Pierwsza z nich - Afin.exe  słu\
y do krypotanalizy podstawieniowego szyfru
monoalfabetycznego, druga z kolei - Kasiski.exe - do kryptoanalizy szyfru
polialfabetycznego.
Przebieg ćwiczenia
1. Kryptoanaliza szyfru monoalfabetycznego
Dla otrzymanych szyfrogramów nale\
y odgadnąć klucz, a następnie odszyfrować
szyfrogram. Poniewa\
szyfr afiniczny ma postać:
f(m) = ( m k 1 + k 0 ) mod N
stÄ…d nale\
y odgadnąć wartość k1, k0 oraz N. Program Afin.exe umo\
liwia prowadzenie
ataku ze znanym tekstem, tzn. dla podanego znaku lub grupy znaków zwraca odpowiedni
kryptogram. Alfabetem tekstu jawnego oraz szyfrogramu mogą być znaki nale\
Ä…ce do
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 8
podstawowej (regularnej) i rozszerzonej tabeli kodów ASCII (patrz ni\
ej). Pierwszym
znakiem tego alfabetu jest zawsze znak spacji.
2. Kryptoanaliza szyfru Vigenere
W szyfrze Vigenere a klucz tworzy sekwencja liter K = k1 ... kt przy czym ki (i=1, ..., t)
daje liczbę przesunięć w i-tym alfabecie, tj. ka\
dy znak w kolejnych blokach o długości t
znaków jest przekształcany w znak szyfrogramu wg formuły:
fi(m) = (m + ki) mod N
Zadanie polega na odgadnięciu dla otrzymanych szyfrogramów klucza szyfrującego, a
następnie odszyfrowaniu szyfrogramu.
Program Kasiski.exe wspomaga prowadzenie kryptoanalizy, obliczajÄ…c m.in. indeks
(współczynnik) koincydencji Friedmana, histogram oraz zbiór liczb, będących
odległościami między powtarzającymi się segmentami kryptogramu, które po
wyznaczeniu największego wspólnego podzielnik mogą pomóc (po odrzuceniu
przypadkowych powtórzeń segmentów w kryptogramie) w określeniu długości bloku
(klucza) t.
Przykład testowy:
Kryptogram o postaci
zhyme zvelk ojubw ceyin cusml ravsr yarnh ceari ujpgp vardu
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 9
qzcgr nncaw jaluh gjpjr ygegq fulus qffpv eyedq golka lvosj
tfrtr yejzs rvnci hyjnm zdcro dkhcr mmlnr fflfn qgolk alvos
jwmik qkubp sayoj rrqyi nrnyc yqzsy ednca leilx rchug iebko
ythgv vckhc jeqgo lkalv osjed weaks gjhyc llfty igsvt fvpmz
nrzol cyuzs fkoqr yryar zfgki qkrsv ircey uskvt mkhcr myqil
xrcrl gqarz olkhy ksnfn rrncz twuoc jnmkc mdezp irjej w
został uzyskany dla klucza ray i tekstu jawnego:
ihave beent oldby learn edsou rcest hatwh enatr ulygr eatmu
sicia nplay sandh ispla yings ounds sofre eands ponta neous
thatt helis tener hasno ideao fthea mount ofnon spont aneou
swork study schol arshi panal ysisa ndpla nning requi redto
achie vethe sespo ntane ousef fects ishal lnota rguet hepoi
ntion lywis htosa ythat ifiti strue itlea dsmet othea mazin
greal izati ontha tspon tanei tydoe snotc omeby itsel f
Przypomnijmy sobie, \
e w kryptoanalizie nale\
y najpierw oszacować długość klucza
(długość bloku t, w programie Kasiski.exe parametr ten jest oznaczony przez d) - opcja
F2 programu, póz
niej dla wybranej liczby powtórzeń znaków w kryptogramie wykonać
test Kasisiego  opcja F5 programu i w końcu dla wybranej długości hasła t obejrzeć
histogramy (opcja F6 programu) dla ka\
dej sekwencji z poni\
szych:
sekwencja 1: c1, c1+t, c1+2t, ..., c1+nt
sekwencja 2: c2, c2+t, c2+2t, ..., c2+nt
.......................................
sekwencja t: ct, ct+t, ct+2t, ..., ct+nt
Na podstawie uzyskanych t histogramów mo\
na zidentyfikować kolejne znaki hasła.
Na przykład dla przedstawionego powy\
ej szyfrogramu prawdopodobna długość
szyfrogramu wynosi 6 (tak wynika z testu Freedmana, dla którego IC = 0.043, patrz tak\
e
Tabela 1). Testy Kasiskiego pokazujÄ…, \
e najczęstszymi podzielnikami odstępów
pomiędzy powtarzającymi się fragmentami szyfrogramu (o ró\
nych długościach) jest
liczba 3. Przyjmijmy zatem, \
e długość hasła wynosi 3 i obejrzymy po kolei histogramy,
o których wspomniano powy\
ej (opcja F6 programu).
POI Zima, 2012/2013
Ćwiczenie laboratoryjne I strona 10
W histogramie szukamy znaku, który najczęściej występuje w sekwencji pierwszej (jest
to znak v). Poniewa\
w sekwencjach od 1 do t częstość występowania znaków jest taka
sama jak w tekście jawnym, to nale\
y przyjąć, \
e znakom w sekwencji o największej
częstości odpowiada zaszyfrowana literka e (ten znak najczęściej występuje w
anglojęzycznych tekstach jawnych).
StÄ…d na podstawie tabeli Vigenere mo\
na znalez
ć, \
e znakowi e tekstu jawnego i
znakowi v szyfrogramu odpowiada znak r (jest to pierwszy znak klucza). Pozostałe dwa
znaki klucza znajdujemy tak samo.
Uwaga! Czasami częstości wstępowania znaków w kryptogramie są bardzo zbli\
one do
siebie. Wówczas nale\
y znalez
ć odpowiadające im znaki klucza, a następie zbadać
wszystkie mo\
liwe klucze, które są kombinacją tych znaków, a\
do momentu
odszyfrowania szyfrogramu.
Sprawozdanie z ćwiczenia
W trakcie ćwiczenia nale\
y notować wszystkie czynności oraz uzyskiwane wyniki. Po
zakończeniu ćwiczenia nale\
y przygotować sprawozdanie z przebiegu ćwiczenia,
zawierające m.in. krótki opis ćwiczenia, uzyskane wyniki oraz podsumowanie i wnioski
z ćwiczenia.
Sprawozdanie powinno zawierać opis sposobu przeprowadzenia ataku, odgadnięte klucze
oraz odszyfrowany tekst jawny.
Literatura
1. D. E. Robling Denning Kryptografia i ochrona danych, WNT 1982
2. J. Pieprzyk, T. Hardjono, J. Seberry Teoria bezpieczeństwa systemów
komputerowych, Wydawnictwo Helion, 2005.