Kryptologie: Algebraische Methoden und Algorithmen

3834808849......Page 1
Kryptologie......Page 3
Vorwort......Page 5
Inhalt......Page 6
1.1 Worum geht’s?......Page 9
1.2 Monoalphabetische Chiffrierung......Page 10
1.2.2 Mathematische Modellierung......Page 11
1.2.3 Substitutions-Chiffren......Page 12
1.3.1 Das Kerckhoffs’sche Prinzip......Page 14
1.3.2 Angriffsarten......Page 15
1.5 Kryptosysteme......Page 16
1.6 Polyalphabetische Chiffrierung......Page 18
1.6.1 Die Vigenère-Chiffre......Page 19
1.6.2 Die Kryptoanalyse der Vigenère-Chiffre......Page 21
1.7 Affine Chiffren und ihre Kryptoanalyse *......Page 26
1.7.2 Affine Abbildungen......Page 27
1.7.3 Affine und lineare Chiffren......Page 28
1.7.4 Die Kryptoanalyse affiner Chiffren......Page 29
2.1.1 Strom-Chiffren......Page 31
2.1.2 Das Verfahren......Page 32
2.2 ElementareWahrscheinlichkeitsrechnung......Page 33
2.2.1 Wahrscheinlichkeitsverteilung und Wahrscheinlichkeitsfunktion......Page 34
2.2.2 Bedingte Wahrscheinlichkeit......Page 35
2.3.1 Perfekt sichere Kryptosysteme......Page 36
2.3.2 Kennzeichnung perfekt sicherer Systeme......Page 38
3 Block-Chiffren – AES und DES......Page 41
3.1.2 Polynome......Page 42
3.1.3 Division mit Rest......Page 44
3.1.4 Restklassen in Polynomringen......Page 45
3.1.5 Der ggT von Polynomen......Page 46
3.1.6 Irreduzible Polynome......Page 47
3.1.7 Körper......Page 48
3.1.8 Konstruktion endlicher Körper......Page 49
3.1.9 Der AES-Körper......Page 50
3.2.1 Zur Geschichte des DES- und AES-Verfahrens *......Page 52
3.2.2 Design-Kriterien......Page 53
3.2.4 Die Rundenschlüssel......Page 54
3.2.6 Die Rundenfunktionen......Page 55
3.3 Feistel-Chiffren *......Page 58
3.3.2 DES......Page 59
3.4 Betriebsmodi *......Page 61
3.4.2 Cipher Block Chaining Mode – CBC......Page 62
3.4.4 Output Feedback Mode – OFB......Page 63
3.5 Differentielle und lineare Kryptoanalyse *......Page 64
4.1 Komplexität......Page 65
4.1.1 Die Ordnung von Funktionen......Page 66
4.1.2 Die Laufzeit von Algorithmen......Page 67
4.1.3 Multiplikation von Polynomen......Page 68
4.1.4 Addition und Multiplikation ganzer Zahlen......Page 69
4.1.5 Division mit Rest......Page 70
4.1.6 Komplexitätsklassen......Page 71
4.1.7 Algorithmische Äquivalenz......Page 72
4.2.2 Der erweiterte euklidische Algorithmus......Page 73
4.3.1 Einheiten in Zn......Page 79
4.3.2 Lineare Kongruenzgleichungen......Page 80
4.3.3 Invertieren modulo n......Page 82
4.4 Einwegfunktionen und Hashfunktionen......Page 83
4.4.1 Einwegfunktionen......Page 84
4.4.2 Hashfunktionen......Page 85
4.4.4 Anwendungen......Page 86
5.1 Message Authentication Code......Page 89
5.1.1 Das Prinzip des MAC......Page 90
5.1.2 Ein Beispiel und Varianten......Page 91
5.2.1 Möglichkeiten zum Betrug......Page 92
5.3.2 Die affine Ebene AG(2,F)......Page 95
5.3.3 Netze......Page 96
5.3.4 Netze liefern perfekte kartesische Systeme......Page 98
5.3.5 Perfekte kartesische Systeme liefern Netze......Page 99
5.4 Ausblick: Mehrfach perfekte Systeme *......Page 100
6.1.1 Ordnungen von Gruppenelementen......Page 101
6.1.2 Der Satz von Lagrange......Page 104
6.1.3 Untergruppen zyklischer Gruppen......Page 105
6.1.5 Der Satz von Cauchy......Page 106
6.1.6 Die Sätze von Euler und Fermat......Page 107
6.1.7 Die Gruppen Z×psind zyklisch......Page 108
6.1.8 Die Gruppen Z×pν , p = 2, sind zyklisch......Page 109
6.2.1 Das Pohlig-Hellman-Verfahren in Z×p......Page 110
6.2.3 Zur Sicherheit des Pohlig-Hellman-Verfahrens......Page 111
6.2.4 Zur Wahl der Gruppe......Page 112
6.2.5 Zusammenfassung und ein Beispiel......Page 113
6.3 Schnelle Exponentiation......Page 115
7.1 Das Verfahren von Rivest, Shamir und Adleman......Page 119
7.1.1 Das Kryptosystem......Page 120
7.1.4 Die Entschlüsselung......Page 122
7.1.5 Hybridverfahren......Page 123
7.1.6 Zur Sicherheit von RSA......Page 124
7.2.1 Der chinesische Restsatz......Page 125
7.2.2 Lösen eines Systems von Kongruenzgleichungen......Page 126
7.2.3 Produktdarstellung der primen Restklassengruppen......Page 128
7.2.4 Optimierung des Entschlüsselns mit dem chinesischen Restsatz......Page 129
7.3.1 Kenntnis von p und q liefert d......Page 130
7.3.2 Kenntnis von d liefert p und q......Page 131
7.4 Wahl der Parameter p, q, e und d bei RSA......Page 133
7.4.2 Die Wahl von e......Page 134
7.5 Kettenbrüche *......Page 136
7.5.1 Kettenbruchdarstellungen......Page 137
7.5.2 Existenz und Eindeutigkeit von Näherungsbrüchen......Page 138
7.5.3 Ermittlung der Näherungsbrüche......Page 139
7.5.5 Abschätzungen......Page 141
7.5.6 Charakterisierung von Näherungsbrüchen......Page 142
7.6 DerWiener-Angriff *......Page 145
8 Primzahltests......Page 149
8.1.2 Probedivision für große Zahlen......Page 150
8.2 Der Fermat-Test......Page 151
8.2.1 Der Test......Page 152
8.2.2 Pseudoprimzahlen und Zeugen für Zusammengesetztheit......Page 153
8.2.3 Carmichael-Zahlen......Page 154
8.3.1 Das Verfahren......Page 155
8.3.2 Starke Pseudoprimzahlen......Page 157
8.4.1 Ideale in Ringen......Page 160
8.4.2 Die Idee des AKS-Tests......Page 162
8.4.3 Der AKS-Algorithmus......Page 164
8.4.4 Introspektive Zahlen......Page 166
8.4.5 Die Korrektheit des AKS-Algorithmus......Page 169
8.5 Vergleich der Primzahltests......Page 172
9.1 Der Diffie-Hellman-Schlüsselaustausch......Page 174
9.1.1 Der Schlüsselaustausch nach Diffie-Hellman......Page 175
9.1.3 Der Mann in der Mitte......Page 176
9.1.4 Weitere Gruppen für das Diffie-Hellman-Verfahren......Page 177
9.2.2 Verschlüsselung......Page 178
9.2.4 Zur Sicherheit des ElGamal-Verfahrens......Page 179
9.3.1 Quadratwurzeln modulo n......Page 180
9.3.3 Das Verfahren......Page 182
9.3.4 Zur Sicherheit des Rabin-Verfahrens......Page 184
10.1.1 Der diskrete Logarithmus......Page 186
10.2.1 Das Verfahren......Page 187
10.3 Pollards -Methode *......Page 188
10.3.1 Das Verfahren......Page 189
10.3.2 Modifikation des zweiten Schrittes......Page 191
10.4.1 Reduktion auf Primzahlpotenzordnung......Page 193
10.4.2 Reduktion auf Primzahlordnung......Page 195
10.4.3 Volle Reduktion......Page 197
11.1 Prinzipielles Vorgehen......Page 198
11.2.2 Konstruktion der Zahlen x und y......Page 200
11.3.1 Die Methode......Page 201
11.3.2 Glatte Zahlen......Page 202
11.3.3 Der Algorithmus......Page 203
11.4.2 Die gemeinsame Idee der Kettenbruchmethode, des quadratischenSiebs und weiterer Verfahren......Page 204
11.4.3 Die Kongruenzen......Page 205
11.4.4 Die Faktorbasis......Page 206
11.5.1 Die Kettenbruchentwicklung von √N......Page 208
11.6 Das quadratische Sieb......Page 211
11.6.2 Das Sieb......Page 212
12.2 Das RSA-Signaturverfahren......Page 216
12.2.3 Angriffe......Page 217
12.2.4 Wie man’s richtig macht......Page 218
12.3.2 Das Signaturverfahren nach ElGamal......Page 219
12.3.3 Angriffe......Page 221
12.4 Digital Signature Standard – DSS......Page 222
12.4.1 Das Signaturverfahren DSS......Page 223
12.4.3 Signaturverfahren nach Schnorr *......Page 224
13.1 Projektive Ebenen......Page 226
13.1.2 Die projektive Ebene PG(2,F)......Page 227
13.1.3 Jede projektive Ebene liefert viele affine Ebenen......Page 229
13.1.4 Die unendlich ferne Gerade......Page 230
13.2 Definition elliptischer Kurven......Page 231
13.2.2 Affine Darstellung elliptischer Kurven......Page 232
13.2.3 Beliebige Charakteristik – die Weierstraß-Gleichung – Singularitäten......Page 234
13.3 Tangenten......Page 235
13.3.1 Projektive Beschreibung der Tan......Page 236
13.3.2 Affine Beschreibung der Tangente......Page 238
13.4.1 Schnittpunkte von Geraden mit E......Page 239
13.4.2 Eine Verknüpfung auf E......Page 240
13.5.2 Die Sekanten-Tangenten-Konstruktion......Page 244
14.1.2 Verschlüsselung......Page 247
14.2 Das Signaturverfahren ECDSA......Page 248
14.3.1 Elliptische Kurven über dem Ring ZN......Page 250
14.3.3 Der Algorithmus ECM......Page 252
14.4 Zur Anzahl der Punkte einer Kurve......Page 253
14.4.1 Der Satz von Hasse......Page 254
14.4.2 Zur Existenz elliptischer Kurven mit vorgegebener Ordnung......Page 255
14.4.4 Erweiterungskörper und der Frobenius......Page 256
14.4.5 Der Algorithmus von Schoof......Page 258
Literaturverzeichnis......Page 261
Index......Page 263