Szyfry strumieniowe.pdf

(2041 KB) Pobierz
Szyfry strumieniowe_K_Mackowiak
Politechnika Poznaıska
Wydziaþ Informatyki i ZarzĢdzania
Krzysztof Maękowiak
Szyfry strumieniowe
Praca dyplomowa magisterska wykonana
w Instytucie Automatyki i InŇynierii Informatycznej
Politechniki Poznaıskiej pod kierownictwem
dr hab. inŇ. J. Stokþosy, prof. P. P.
Poznaı, 2005 r.
Spis treĻci
Spis treĻci ..................................................................................................................................2
Wstħp.........................................................................................................................................4
1. Wprowadzenie do kryptologii.............................................................................................7
2. Algorytmy kryptograficzne Î wprowadzenie ....................................................................8
2.1 Algorytmy symetryczne...................................................................................................9
2.2 Algorytmy asymetryczne ...............................................................................................10
3. Algorytmy strumieniowe ...................................................................................................11
4. Podstawowe elementy szyfrw strumieniowych..............................................................14
4.1 Rejestry...........................................................................................................................14
4.1.1 Rejestry przesuwajĢce ze sprzħŇeniem zwrotnym (FSR) .......................................14
4.1.2 Liniowe rejestry przesuwajĢce ze sprzħŇeniem zwrotnym (LFSR)........................18
4.1.3 Nieliniowe rejestry przesuwajĢce ze sprzħŇeniem zwrotnym (NFSR)...................20
4.1.4 Rejestr FCSR...........................................................................................................21
4.2 Generatory kluczy..........................................................................................................23
4.2.1 Oglna postaę generatorw.....................................................................................24
4.2.2 Liniowe generatory kongruencyjne.........................................................................25
4.2.3 Generator BBS ........................................................................................................26
4.2.4 Generator Bluma-Micaliego....................................................................................27
4.2.5 Generator RSA........................................................................................................27
4.2.6 Generatory addytywne ............................................................................................28
4.3 Testy statystyczne ..........................................................................................................29
5. Metody budowy szyfrw strumieniowych........................................................................35
5.1 Budowa szyfrw strumieniowych z szyfrw blokowych ..............................................35
5.1.1 Tryb sprzħŇenia zwrotnego (CFB)..........................................................................35
5.1.2 Tryb sprzħŇenia zwrotnego wyjĻciowego (OFB)....................................................37
5.2 Szyfry oparte na rejestrach przesuwajĢcych ze sprzħŇeniem zwrotnym........................39
5.2.1 Budowa szyfrw strumieniowych opartych na LFSR.............................................39
5.2.2 Przykþadowe generatory oparte na LFSR................................................................40
5.2.3 ýĢczenie szyfrw strumieniowych..........................................................................43
5.3 Szyfry oparte na rejestrach przesuwajĢcych z przeniesieniem w sprzħŇeniu zwrotnym43
6. PrzeglĢd algorytmw strumieniowych.............................................................................46
6.1 RC4.................................................................................................................................47
6.2 A5...................................................................................................................................49
6.3 SEAL..............................................................................................................................52
6.4 Szyfr wykorzystywany w PKZIP...................................................................................53
6.5 WAKE............................................................................................................................54
6.6 Variably Modified Permutation Composition (VMPC).................................................56
6.6.1 Funkcja jednokierunkowa VMPC...........................................................................56
6.6.2 Szyfr strumieniowy VMPC.....................................................................................59
6.7 BMGL ............................................................................................................................61
6.8 SNOW............................................................................................................................63
6.9 SOBER...........................................................................................................................65
6.9.1 SOBER-t16..............................................................................................................65
6.9.2 SOBER-t32..............................................................................................................67
6.10 LEVIATHAN...............................................................................................................70
6.11 LILI-128.......................................................................................................................73
6.12 Helix.............................................................................................................................75
2
6.13 E0 .................................................................................................................................77
6.14 SCOP............................................................................................................................79
6.15 SN3...............................................................................................................................82
6.16 Szyfr Bluma-Goldwassera............................................................................................83
6.17 Algorytmy skompromitowane......................................................................................85
6.17.1 Generator I/p .........................................................................................................85
6.17.2 Generator crypt(1).................................................................................................85
6.17.3 Generator V. Pless.................................................................................................85
6.17.4 Generator wykorzystujĢcy automaty komrkowe.................................................86
6.18 Kryptografia DNA........................................................................................................87
6.18.1 Podstawowe pojħcia biologiczne ..........................................................................87
6.18.2 Budowa czĢsteczki DNA ......................................................................................87
6.18.3 Reakcja þaıcuchowa polimerazy...........................................................................90
6.18.4 Sekwencjonowanie................................................................................................90
6.18.5 Informatyka DNA .................................................................................................91
6.18.6 Komputer DNA.....................................................................................................92
6.18.7 Komputery DNA a komputery PC........................................................................92
6.18.8 Kodowanie DNA a kodowanie binarne ................................................................93
6.18.9 Kryptografia DNA.................................................................................................94
6.18.10 DNA a ochrona danych.......................................................................................97
7. Kryptoanaliza .....................................................................................................................98
7.1 Kryptoanaliza algorytmw historycznych ...................................................................100
7.2 Kryptoanaliza rŇnicowa..............................................................................................105
7.3 Ataki algebraiczne........................................................................................................106
7.4 Kryptoanaliza liniowa ..................................................................................................106
7.5 Atak algorytmiczny......................................................................................................107
7.6 Ataki na implementacje sprzħtowe algorytmw kryptograficznych............................108
7.6.1 Atak na czas wykonywania...................................................................................108
7.6.2 Metoda rŇnicowej analizy bþħdw.......................................................................108
7.6.3 Metoda akustyczna................................................................................................108
7.6.4 Analiza poboru mocy............................................................................................108
8. Metody kryptoanalizy szyfrw strumieniowych ...........................................................111
8.1 Proste ataki na algorytmu strumieniowe......................................................................111
8.1.1 Atak korelacyjny (dziel i zwyciħŇaj).....................................................................111
8.1.2 Atak wstawieniowy...............................................................................................111
8.1.3 Atak powtrzeniowy.............................................................................................112
8.1.4 Atak odrŇniajĢcy .................................................................................................112
8.1.5 Ataki okresowe......................................................................................................112
8.2 Ataki na wybrane algorytmy strumieniowe.................................................................112
8.2.1 Atak na algorytm XOR z krtkim hasþem.............................................................112
8.2.2 Atak czasowo-pamiħciowy na algorytm LILI-128 ...............................................117
8.2.3 Ataki kryptoanalityczne na rodzinħ algorytmw A5 ............................................119
8.2.4 Atak na algorytm E0 .............................................................................................124
8.3 Implementacja algorytmw a ich bezpieczeıstwo.......................................................125
8.4 Oprogramowanie CrypTool .........................................................................................132
Podsumowanie......................................................................................................................141
Wykaz symboli i oznaczeı...................................................................................................142
Sþownik..................................................................................................................................143
Akronimy ..............................................................................................................................149
Literatura..............................................................................................................................151
3
Wstħp
Umotywowanie wyboru tematu
W dobie rozwoju technologii informatycznych najcenniejszĢ wartoĻciĢ wielu organizacji staje
siħ informacja. Jej ujawnienie, zniszczenie lub nieautoryzowana modyfikacja prowadzi do
wymiernych strat. Straty naleŇy postrzegaę nie tylko jako straty finansowe, lecz takŇe jako
utratħ zaufania klientw czy teŇ przerwħ w ciĢgþoĻci dziaþania systemu. WþaĻciwe
zabezpieczenie informacji moŇe mieę wpþyw na zachowanie pozycji na rynku,
konkurencyjnoĻci, pþynnoĻci finansowej, a takŇe na pozytywny wizerunek organizacji. W celu
zapewnienia poufnoĻci informacji wykorzystuje siħ mechanizmy kryptograficzne, w tym
rwnieŇ szyfry strumieniowe. AktualnoĻę tych tematw oraz rozwj badaı w tym kierunku
stanowi jedno z podstawowych uzasadnieı do napisania pracy na temat szyfrw
strumieniowych.
TematykĢ kryptologii interesujħ siħ osobiĻcie od kilku lat. Moje zainteresowania, praca
zawodowa, a takŇe obroniona juŇ praca inŇynierska zwiĢzane sĢ takŇe z tym tematem. Od
ponad roku mam przyjemnoĻę prowadzię internetowy serwis kryptologiczny
www.kryptografia.com. Kilka tematw z dziedziny kryptologii miaþem moŇliwoĻę
zaprezentowaę na seminariach oraz konferencji ENIGMA 2004. W zwiĢzku z tymi
zainteresowaniami przygotowywaþem rwnieŇ artykuþy do czasopisma Software 2.0
[MAC204], [MAC304]. Chħę rozwoju w tym kierunku jest bez wĢtpienia gþwnym powodem
wyboru takiego tematu pracy magisterskiej. SzukajĢc tematu swojej pracy braþem rwnieŇ
pod uwagħ fakt, iŇ w literaturze, szczeglnie w jħzyku polskim brakuje pozycji, ktra w peþni
obejmowaþaby zakres zwiĢzany z szyframi strumieniowymi. Dlatego teŇ mojĢ pracħ po
obronie chciaþbym udostħpnię publicznie szerokiemu gronu ludzi zainteresowanych
kryptologiĢ, aby mogþa dla nich stanowię bogate Ņrdþo wiedzy.
Szeroki zakres tematyki szyfrw strumieniowych w przyszþoĻci daje moŇliwoĻę dalszego
rozwoju i prowadzenia badaı w ramach pracy doktorskiej.
Cel i zakres pracy
Podstawowym celem niniejszej pracy magisterskiej jest dokonanie przeglĢdu szyfrw
strumieniowych wraz z metodami ich kryptoanalizy oraz wþaĻciwe udokumentowanie tego
przeglĢdu.
4
PowyŇsze zaþoŇenia przedstawiþem w oĻmiu rozdziaþach, ktre obejmujĢ nastħpujĢce
elementy:
Rozdziaþ 1 Î Wprowadzenie do kryptologii Î to krtki wprowadzajĢcy rozdziaþ
wyjaĻniajĢcy podstawowe pojħcia takie jak: kryptografia, kryptoanalizy czy teŇ steganografia.
Rozdziaþ 2 Î Algorytmy kryptograficzne Î wprowadzenie Î przedstawia podziaþ
historyczny algorytmw szyfrowania na algorytmy podstawieniowe oraz przestawieniowe,
jak rwnieŇ podziaþ najnowszych algorytmw na algorytmu szyfrowania symetrycznego i
asymetrycznego. Podziaþ ten obejmuje rwnieŇ krtki opis kaŇdej z wydzielonych klas
algorytmw.
Rozdziaþ 3 Î Algorytmy strumieniowe Î wprowadza w tematykħ szyfrw strumieniowych,
ich dziaþanie oraz sposb przetwarzania tekstu jawnego, jednoczeĻnie dokonujĢc podziaþu
tych algorytmw na strumieniowe szyfry synchroniczne i samosynchronizujĢce.
Rozdziaþ 4 Î Podstawowe elementy szyfrw strumieniowych Î zawiera opis podstawowych
elementw wykorzystywanych do budowy szyfrw strumieniowych takich jak: podstawowe
typy rejestrw (rejestry liniowe, rejestry nieliniowe, rejestry FCSR), generatory ciĢgw
pseudolosowych, opis przykþadowych testw statystycznych i pakietw oprogramowania,
ktre mogĢ byę wykorzystywane do testowania ciĢgw wygenerowanych przez generatory
ciĢgw pseudolosowych.
Rozdziaþ 5 Î Metody budowy szyfrw strumieniowych Î omawia przykþadowe metody
budowy szyfrw strumieniowych takie jak: budowa szyfrw strumieniowych z szyfrw
blokowych czy teŇ budowa szyfrw strumieniowych z wykorzystaniem rejestrw.
Rozdziaþ 6 Î PrzeglĢd algorytmw strumieniowych Î jest jednym z gþwnych rozdziaþw
mojej pracy, w ktrym przedstawiam najbardziej popularne szyfrw strumieniowe. Opisujħ
ponad 15 najczħĻciej wykorzystywanych algorytmw takich jak: RC4, ktry wykorzystywany
jest m.in. do szyfrowania transmisji danych w sieciach bezprzewodowych wykorzystujĢcych
protokþ WEP, E0 wykorzystywany w transmisji Bluetooth, A5 stosowany w procesie
szyfrowania w sieciach komrkowych GSM, SEAL, WAKE, VMPC, PKZIP, BMGL,
SNOW, LEVIATHAN, SOBER, SCOP, SN3, LILI-128, Blooma-Goldwassera, a takŇe kilka
5

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin