"Einfuehrung in die Kryptographie 001.ps.gz" - читать интересную книгу автора

Einf"uhrung in die Kryptographie

Prof. Johannes Buchmann

Patrick Theobald

Stefan Neis

16. Oktober 1997

Inhaltsverzeichnis 1 Einleitung 4 2 Grundlagen 6

2.1 Grundbegriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Verschiedene Verschl"usselungsverfahren . . . . . . . . . . . . . . . . . . . . 7 2.3 Public-Key-Verschl"usselung . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.4 Authentifikation in Public-Key-Verfahren . . . . . . . . . . . . . . . . . . . 9 2.5 Signaturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.6 Hashfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.7 Schl"usselverwaltung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.8 Pseudo-Zufallszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.9 Angriffe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Grundlagen aus der Zahlentheorie 13

3.1 Ganze und nat"urliche Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Bin"ardarstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.3 Asymptotische Darstellung . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4 Teilbarkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.5 Division mit Rest . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.6 Komplexit"at arithmetischer Operationen . . . . . . . . . . . . . . . . . . . . 14 3.7 Gr"osster gemeinsamer Teiler . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1

Version 16. Oktober 1997 2

3.8 Euklidischer Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.9 Kongruenz modulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.10 Division im Restklassenring . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.11 (ZZ=mZZ)\Lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 3.12 Kleiner Satz von Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.13 Schnelle Exponentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.14 Berechnungen und Verifizieren von Ordnungen . . . . . . . . . . . . . . . . 23 3.15 Chinesischer Restsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.16 Zerlegung von ZZ=mZZ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.17 Bestimmung der Eulerschen '-Funktion . . . . . . . . . . . . . . . . . . . . 26 3.18 Struktur von (ZZ=pZZ)\Lambda . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

4 Public-Key-Primitive 28

4.1 Nachrichtenkodierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4.2 RSA: Rivest, Shamir, Adleman . . . . . . . . . . . . . . . . . . . . . . . . . 29 4.3 RSA und Faktorisierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.4 Auswahl der RSA-Parameter . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.5 RSA-Signaturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.6 Diffie-Hellman-Schl"usselaustausch . . . . . . . . . . . . . . . . . . . . . . . . 33 4.7 Diffie-Hellman-Verfahren und diskrete Logarithmen . . . . . . . . . . . . . . 34 4.8 Diffie-Hellman-Verfahren in beliebigen Gruppen . . . . . . . . . . . . . . . . 34 4.9 Endliche abelsche Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 4.10 Wahl der Parameter f"ur das Diffie-Hellman-Verfahren . . . . . . . . . . . . 36 4.11 Verschl"usselung nach ElGamal . . . . . . . . . . . . . . . . . . . . . . . . . 37

Version 16. Oktober 1997 3 5 Kryptographische Hashfunktionen 38

5.1 Einf"uhrung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2 Geburtstags-Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.3 Hashfunktionen und diskrete Logarithmen . . . . . . . . . . . . . . . . . . . 40

6 Signaturen 41

6.1 ElGamal-Signatur . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 6.2 DSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42

7 Berechnung diskreter Logarithmen 44 8 Zuf"allige Zahlen und Primzahlen 48