Dane szczegółowe książki
Kody korekcyjne i kryptografia / Mochnacki, Władysław
Autorzy
Tytuł
Kody korekcyjne i kryptografia
Wydawnictwo
Wrocław: Oficyna Wydawnicza Politechniki Wrocławskiej, 2000
Numer wydania
2 popr.
ISBN
837085480X
Hasła przedmiotowe
Informacje dodatkowe
Książka bez numeracji stron
Spis treści
pokaż spis treści
Wstęp.........................................................................................................................7
Część 1. Elementy algebry ciał skończonych..............................................................9
1.1. Wprowadzenie....................................................................................................9
1.1.1. Systemy algebraiczne.................................................................................9
1.1.2. Kongruencje i arytmetyka modularna ......................................................10
1.1.3. Funkcja Eulera .........................................................................................12
1.2. Ciała proste.......................................................................................................13
1.2.1. Konstrukcja ciała prostego .......................................................................13
1.2.2. Przykłady ciał prostych ............................................................................13
1.2.3. Rząd multyplikatywny elementów ciała ..................................................14
1.2.4. Charakterystyka ciała ...............................................................................15
1.3. Algebra wielomianów i przestrzeń wektorowa ................................................16
1.3.1. Wielomiany nad ciałami skończonymi ....................................................16
1.3.2. Wielomiany nierozkładalne i pierwotne...................................................17
1.3.3. Tablice wielomianów nierozkłdalnych nad ciałami prostymi..................19
1.3.4. Przestrzeń wektorowa ..............................................................................20
1.4. Sekwencje okresowe nad ciałami prostymi......................................................22
1.4.1. Generowanie sekwencji okresowych .......................................................22
1.4.2. Generatory sekwencji okresowych ..........................................................23
1.4.3. Właściwości binarnych sekwencji pseudolosowych................................24
1.5. Konstrukcja i struktura ciał rozszerzonych ......................................................28
1.5.1. Ciała rozszerzone .....................................................................................28
1.5.2. Konstrukcja rozszerzonych ciał skończonych..........................................29
1.5.3. Elementy ciała skończonego w postaci macierzy ....................................30
1.5.4. Elementy ciała skończonego w postaci wektorów ...................................31
1.5.5. Elementy ciała skończonego w postaci wielomianów .............................32
1.5.6. Ciała rozszerzone nad niebinarnymi ciałami prostymi ............................33
1.5.7. Wielomiany minimalne elementów ciała .................................................35
1.5.8. Struktura ciał rozszerzonych ....................................................................38
1.6. Sekwencje okresowe i rozszerzenia ciał nad ciałami rozszerzonymi..............41
1.6.1. Wielomiany i sekwencje okresowe nad ciałami rozszerzonymi .............41
1.6.2. Właściwości sekwencji pseudolosowych nad ciałami rozszerzonymi .....42
1.6.3. Rozszerzenia ciał nad ciałami rozszerzonymi..........................................44
1.7. Realizacja działań w ciałach skończonych.......................................................47
1.7.1. Logarytmy Zecha .....................................................................................47
1.7.2. Programowa realizacja działań w ciałach skończonych..........................50
1.7.3. Układy mnożenia i dzielenia wielomianów .............................................52
1.7.4. Układy realizujące działania arytmetyczne w ciałach rozszerzonych......55
Część 2. Kody korekcyjne ..........................................................................................59
2.1. Elementy transmisji danych .............................................................................59
4 Spis treści
2.1.1. System transmisji danych.........................................................................59
2.1.2. Zakłócenia i błędy w kanałach transmisyjnych........................................61
2.1.3. Model binarnego kanału transmisji danych .............................................62
2.2. Charakterystyka kodów....................................................................................64
2.2.1. Typy kodów korekcyjnych.......................................................................64
2.2.2. Struktura kodu blokowego .......................................................................64
2.2.3. Zdolność detekcyjna i korekcyjna kodu...................................................68
2.2.4. Geometryczna interpretacja kodu.............................................................70
2.2.5. Syndrom ...................................................................................................71
2.3. Kody liniowe ....................................................................................................72
2.3.1. Definicja kodu liniowego .........................................................................72
2.3.2. Macierzowy opis kodu liniowego ............................................................74
2.3.3. Kodowanie informacji..............................................................................76
2.3.4. Dekodowanie ciągów odebranych ...........................................................77
2.3.5. Liniowe kody Hamminga.........................................................................79
2.4. Kody cykliczne.................................................................................................83
2.4.1. Charakterystyka kodów cyklicznych .......................................................83
2.4.2. Wielomiany generujące kody cykliczne ..................................................85
2.4.3. Algorytm kodowania................................................................................86
2.4.4. Uproszczony algorytm dekodowania .......................................................88
2.5. Macierzowy opis kodów cyklicznych ..............................................................92
2.5.1. Wyznaczanie macierzy generującej na podstawie wielomianu
generującego kod ..........................................................................................92
2.5.2. Wyznaczenie macierzy kontrolnej na podstawie wielomianu
generującego kod dualny...............................................................................94
2.5.3. Definicja kodu cyklicznego za pomocą pierwiastków wielomianu
generującego kod ..........................................................................................96
2.5.4. Kodowanie i dekodowanie kodów cyklicznych.......................................99
2.6. Realizacja techniczna koderów i dekoderów kodów cyklicznych .................102
2.6.1. Realizacja kodera ...................................................................................102
2.6.2. Realizacja dekodera................................................................................104
2.6.3. Dekodowanie z łowieniem błędów ........................................................107
2.7. Przegląd binarnych kodów cyklicznych.........................................................110
2.7.1. Cykliczne kody Hamminga....................................................................110
2.7.2. Kody maksymalnej długości ..................................................................111
2.7.3. Kody Bose-Chaudhuri-Hocquenghema .................................................111
2.7.4. Tablica kodów cyklicznych....................................................................116
2.8. Kody cykliczne korygujące błędy grupowe ...................................................118
2.8.1. Błędy grupowe .......................................................................................118
2.8.2. Kody Reeda-Solomona ..........................................................................118
2.8.3. Realizacja techniczna kodów Reeda-Solomona.....................................121
2.8.4. Rozszerzone kody Reeda-Solomona......................................................122
Spis treści 5
Część 3. Kryptografia...............................................................................................125
3.1. Elementy kryptologii......................................................................................125
3.1.1. Ochrona danych .....................................................................................125
3.1.2. Systemy i algorytmy kryptograficzne ....................................................126
3.1.3. Właściwości informacyjne języka..........................................................127
3.1.4. Kryptoanaliza .........................................................................................130
3.2. Systemy kryptograficzne................................................................................132
3.2.1. System kryptograficzny z kluczem tajnym............................................132
3.2.2. System kryptograficzny z kluczem jawnym ..........................................134
3.2.3. Ocena systemów kryptograficznych ......................................................136
3.3. Szyfry podstawieniowe i przestawieniowe ....................................................137
3.3.1. Podział szyfrów podstawieniowych .......................................................137
3.3.2. Proste szyfry podstawieniowe................................................................137
3.3.3. Szyfry podstawieniowe homofoniczne ..................................................141
3.3.4. Szyfry podstawieniowe wieloalfabetowe...............................................142
3.3.5. Szyfry podstawieniowe poligramowe ....................................................146
3.3.6. Szyfry przestawieniowe .........................................................................147
3.4. Szyfry kaskadowe ..........................................................................................148
3.4.1. Charakterystyka szyfrów kaskadowych.................................................148
3.4.2. Maszyny rotorowe..................................................................................148
3.4.3. Algorytm Lucifer ...................................................................................149
3.4.4. Standard szyfrowania danych DES........................................................150
3.5. Klucze kryptograficzne ..................................................................................157
3.5.1. Charakterystyka kluczy kryptograficznych............................................157
3.5.2. Generatory nieliniowe kluczy binarnych ...............................................158
3.5.3. Łamanie kluczy kryptograficznych........................................................161
3.5.4. Zarządzanie kluczami.............................................................................162
3.6. Szyfry z kluczem jawnym..............................................................................167
3.6.1. Charakterystyka algorytmów z kluczem jawnym..................................167
3.6.2. Algorytm Merklego-Hellmana...............................................................167
3.6.3. Algorytm ElGamala ...............................................................................171
3.6.4. Algorytm RSA .......................................................................................173
3.7. Techniki szyfrowania i implementacje...........................................................177
3.7.1. Szyfry strumieniowe ..............................................................................177
3.7.2. Szyfry blokowe ......................................................................................179
3.7.3. Uwierzytelnianie użytkownika...............................................................181
3.7.4. Podpisy cyfrowe.....................................................................................182
3.7.5. Kryptografia w sieciach komputerowych...............................................183
3.7.6. Szyfrowanie plików ...............................................................................184
Literatura ...............................................................................................................186
Indeks ....................................................................................................................188
Część 1. Elementy algebry ciał skończonych..............................................................9
1.1. Wprowadzenie....................................................................................................9
1.1.1. Systemy algebraiczne.................................................................................9
1.1.2. Kongruencje i arytmetyka modularna ......................................................10
1.1.3. Funkcja Eulera .........................................................................................12
1.2. Ciała proste.......................................................................................................13
1.2.1. Konstrukcja ciała prostego .......................................................................13
1.2.2. Przykłady ciał prostych ............................................................................13
1.2.3. Rząd multyplikatywny elementów ciała ..................................................14
1.2.4. Charakterystyka ciała ...............................................................................15
1.3. Algebra wielomianów i przestrzeń wektorowa ................................................16
1.3.1. Wielomiany nad ciałami skończonymi ....................................................16
1.3.2. Wielomiany nierozkładalne i pierwotne...................................................17
1.3.3. Tablice wielomianów nierozkłdalnych nad ciałami prostymi..................19
1.3.4. Przestrzeń wektorowa ..............................................................................20
1.4. Sekwencje okresowe nad ciałami prostymi......................................................22
1.4.1. Generowanie sekwencji okresowych .......................................................22
1.4.2. Generatory sekwencji okresowych ..........................................................23
1.4.3. Właściwości binarnych sekwencji pseudolosowych................................24
1.5. Konstrukcja i struktura ciał rozszerzonych ......................................................28
1.5.1. Ciała rozszerzone .....................................................................................28
1.5.2. Konstrukcja rozszerzonych ciał skończonych..........................................29
1.5.3. Elementy ciała skończonego w postaci macierzy ....................................30
1.5.4. Elementy ciała skończonego w postaci wektorów ...................................31
1.5.5. Elementy ciała skończonego w postaci wielomianów .............................32
1.5.6. Ciała rozszerzone nad niebinarnymi ciałami prostymi ............................33
1.5.7. Wielomiany minimalne elementów ciała .................................................35
1.5.8. Struktura ciał rozszerzonych ....................................................................38
1.6. Sekwencje okresowe i rozszerzenia ciał nad ciałami rozszerzonymi..............41
1.6.1. Wielomiany i sekwencje okresowe nad ciałami rozszerzonymi .............41
1.6.2. Właściwości sekwencji pseudolosowych nad ciałami rozszerzonymi .....42
1.6.3. Rozszerzenia ciał nad ciałami rozszerzonymi..........................................44
1.7. Realizacja działań w ciałach skończonych.......................................................47
1.7.1. Logarytmy Zecha .....................................................................................47
1.7.2. Programowa realizacja działań w ciałach skończonych..........................50
1.7.3. Układy mnożenia i dzielenia wielomianów .............................................52
1.7.4. Układy realizujące działania arytmetyczne w ciałach rozszerzonych......55
Część 2. Kody korekcyjne ..........................................................................................59
2.1. Elementy transmisji danych .............................................................................59
4 Spis treści
2.1.1. System transmisji danych.........................................................................59
2.1.2. Zakłócenia i błędy w kanałach transmisyjnych........................................61
2.1.3. Model binarnego kanału transmisji danych .............................................62
2.2. Charakterystyka kodów....................................................................................64
2.2.1. Typy kodów korekcyjnych.......................................................................64
2.2.2. Struktura kodu blokowego .......................................................................64
2.2.3. Zdolność detekcyjna i korekcyjna kodu...................................................68
2.2.4. Geometryczna interpretacja kodu.............................................................70
2.2.5. Syndrom ...................................................................................................71
2.3. Kody liniowe ....................................................................................................72
2.3.1. Definicja kodu liniowego .........................................................................72
2.3.2. Macierzowy opis kodu liniowego ............................................................74
2.3.3. Kodowanie informacji..............................................................................76
2.3.4. Dekodowanie ciągów odebranych ...........................................................77
2.3.5. Liniowe kody Hamminga.........................................................................79
2.4. Kody cykliczne.................................................................................................83
2.4.1. Charakterystyka kodów cyklicznych .......................................................83
2.4.2. Wielomiany generujące kody cykliczne ..................................................85
2.4.3. Algorytm kodowania................................................................................86
2.4.4. Uproszczony algorytm dekodowania .......................................................88
2.5. Macierzowy opis kodów cyklicznych ..............................................................92
2.5.1. Wyznaczanie macierzy generującej na podstawie wielomianu
generującego kod ..........................................................................................92
2.5.2. Wyznaczenie macierzy kontrolnej na podstawie wielomianu
generującego kod dualny...............................................................................94
2.5.3. Definicja kodu cyklicznego za pomocą pierwiastków wielomianu
generującego kod ..........................................................................................96
2.5.4. Kodowanie i dekodowanie kodów cyklicznych.......................................99
2.6. Realizacja techniczna koderów i dekoderów kodów cyklicznych .................102
2.6.1. Realizacja kodera ...................................................................................102
2.6.2. Realizacja dekodera................................................................................104
2.6.3. Dekodowanie z łowieniem błędów ........................................................107
2.7. Przegląd binarnych kodów cyklicznych.........................................................110
2.7.1. Cykliczne kody Hamminga....................................................................110
2.7.2. Kody maksymalnej długości ..................................................................111
2.7.3. Kody Bose-Chaudhuri-Hocquenghema .................................................111
2.7.4. Tablica kodów cyklicznych....................................................................116
2.8. Kody cykliczne korygujące błędy grupowe ...................................................118
2.8.1. Błędy grupowe .......................................................................................118
2.8.2. Kody Reeda-Solomona ..........................................................................118
2.8.3. Realizacja techniczna kodów Reeda-Solomona.....................................121
2.8.4. Rozszerzone kody Reeda-Solomona......................................................122
Spis treści 5
Część 3. Kryptografia...............................................................................................125
3.1. Elementy kryptologii......................................................................................125
3.1.1. Ochrona danych .....................................................................................125
3.1.2. Systemy i algorytmy kryptograficzne ....................................................126
3.1.3. Właściwości informacyjne języka..........................................................127
3.1.4. Kryptoanaliza .........................................................................................130
3.2. Systemy kryptograficzne................................................................................132
3.2.1. System kryptograficzny z kluczem tajnym............................................132
3.2.2. System kryptograficzny z kluczem jawnym ..........................................134
3.2.3. Ocena systemów kryptograficznych ......................................................136
3.3. Szyfry podstawieniowe i przestawieniowe ....................................................137
3.3.1. Podział szyfrów podstawieniowych .......................................................137
3.3.2. Proste szyfry podstawieniowe................................................................137
3.3.3. Szyfry podstawieniowe homofoniczne ..................................................141
3.3.4. Szyfry podstawieniowe wieloalfabetowe...............................................142
3.3.5. Szyfry podstawieniowe poligramowe ....................................................146
3.3.6. Szyfry przestawieniowe .........................................................................147
3.4. Szyfry kaskadowe ..........................................................................................148
3.4.1. Charakterystyka szyfrów kaskadowych.................................................148
3.4.2. Maszyny rotorowe..................................................................................148
3.4.3. Algorytm Lucifer ...................................................................................149
3.4.4. Standard szyfrowania danych DES........................................................150
3.5. Klucze kryptograficzne ..................................................................................157
3.5.1. Charakterystyka kluczy kryptograficznych............................................157
3.5.2. Generatory nieliniowe kluczy binarnych ...............................................158
3.5.3. Łamanie kluczy kryptograficznych........................................................161
3.5.4. Zarządzanie kluczami.............................................................................162
3.6. Szyfry z kluczem jawnym..............................................................................167
3.6.1. Charakterystyka algorytmów z kluczem jawnym..................................167
3.6.2. Algorytm Merklego-Hellmana...............................................................167
3.6.3. Algorytm ElGamala ...............................................................................171
3.6.4. Algorytm RSA .......................................................................................173
3.7. Techniki szyfrowania i implementacje...........................................................177
3.7.1. Szyfry strumieniowe ..............................................................................177
3.7.2. Szyfry blokowe ......................................................................................179
3.7.3. Uwierzytelnianie użytkownika...............................................................181
3.7.4. Podpisy cyfrowe.....................................................................................182
3.7.5. Kryptografia w sieciach komputerowych...............................................183
3.7.6. Szyfrowanie plików ...............................................................................184
Literatura ...............................................................................................................186
Indeks ....................................................................................................................188