Automatentheorie und Kryptologie 001

Ju¨rgen Ecker Automatentheorie und Kryptologie Computer– und Mediensicherheit, FHS Hagenberg

Skriptum zu den Vorlesungen in den Wintersemestern 2002/2003 und 2003/2004 und im Sommersemester 2003

ii

Inhaltsverzeichnis 1 Caesar, Vigen` ere und Feistel

1

1.1

Caesar . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2

2

1.3

Vigen`ere’s chiffre indechiffrable“ . . . . . . . . . . . . . . . . . . . . . . . . . ” Scherbius . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4

Feistel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

1.5

Die Erfindung der asymmetrischen Verschl¨ usselung . . . . . . . . . . . . . . .

4

2 Rivest, Shamir und Adleman

7

2.1

Auf den Spuren Euklids . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

2.2

Falsch rechnen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

2.2.1

Noch einmal Caesar . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.3

Diophantastisch . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

14

2.4

Endliche K¨orper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.5

Das RSA-Verschl¨ usselungsverfahren . . . . . . . . . . . . . . . . . . . . . . .

19

2.5.1

Die Eulersche ϕ-Funktion . . . . . . . . . . . . . . . . . . . . . . . . .

19

2.5.2

Das RSA-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . .

20

2.6

Der chinesische Restsatz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

22

2.7

Attacken auf RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.7.1

Repeated Encryption . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.7.2

Gleiche Moduln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

2.7.3

Die Low Exponent Attacke . . . . . . . . . . . . . . . . . . . . . . . .

25

Faktorisieren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

26

2.8.1

. . . . . . . . . . . . . . . . . . . . . . .

26

Lineare Gleichungssysteme u ¨ ber endlichen K¨orpern . . . . . . . . . . .

27

Das quadratische Sieb . . . . . . . . . . . . . . . . . . . . . . . . . . .

27

Zufallszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.9.1

Test auf Zuf¨alligkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

2.9.2

Der BBS-Zufallszahlengenerator . . . . . . . . . . . . . . . . . . . . .

33

2.10 Erzeugung von Primzahlen . . . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.8

2.8.2 2.8.3 2.9

Die Pollard-(p − 1)-Methode

iii

iv

INHALTSVERZEICHNIS 2.10.1 Es gibt viele Primzahlen . . . . . . . . . . . . . . . . . . . . . . . . . .

34

2.10.2 Primzahltests . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

Probedivision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

Der Fermat–Test . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

Der Miller–Rabin–Test . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

2.10.3 Erzeugung von starken Pseudoprimzahlen . . . . . . . . . . . . . . . .

38

3 Diffie und Hellman 3.1

39

Gruppen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

3.1.1

Primitivwurzeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

3.2

Polynome . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

43

3.3

Polynome u ¨ ber Zp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

47

3.4

Shared Keys . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

3.4.1

Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

48

3.4.2

Chinesischer Restsatz . . . . . . . . . . . . . . . . . . . . . . . . . . .

50

3.5

Faktorisieren in Zp [x] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

51

3.6

Endliche K¨orper . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

54

3.7

Diffie-Hellman-Key-Exchange . . . . . . . . . . . . . . . . . . . . . . . . . . .

57

3.8

DL- und DH-public-key Systeme . . . . . . . . . . . . . . . . . . . . . . . . .

60

3.8.1

Das Massey-Omura-Kryptosystem . . . . . . . . . . . . . . . . . . . .

60

3.8.2

Das ElGamal-Kryptosystem . . . . . . . . . . . . . . . . . . . . . . . .

60

Berechnung diskreter Logarithmen – Der Index Calculus Algorithmus . . . .

61

3.10 Andere public-key Systeme . . . . . . . . . . . . . . . . . . . . . . . . . . . .

64

3.10.1 Das Knapsack-Problem . . . . . . . . . . . . . . . . . . . . . . . . . .

64

3.10.2 Das Merkle-Hellman-Kryptosystem . . . . . . . . . . . . . . . . . . . .

65

3.10.3 Das Chor-Rivest-Kryptosystem . . . . . . . . . . . . . . . . . . . . . .

66

3.9

4 ElGamal 4.1

4.2

69

Hashfunktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

69

4.1.1

Stark kollisionsresistente Kompressionsfunktionen . . . . . . . . . . . .

70

4.1.2

Von Kompressionsfunktionen zu Hashfunktionen . . . . . . . . . . . .

71

Digitale Signaturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

72

4.2.1

RSA-Signaturen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

4.2.2

ElGamal Signaturen . . . . . . . . . . . . . . . . . . . . . . . . . . . .

73

Attacken auf ElGamal Signaturen . . . . . . . . . . . . . . . . . . . .

74

4.3

Zero-Knowledge-Protokolle

. . . . . . . . . . . . . . . . . . . . . . . . . . . .

75

4.4

Oblivious transfer channels . . . . . . . . . . . . . . . . . . . . . . . . . . . .

77

INHALTSVERZEICHNIS 5 Moore, Mealy und Vernam

v 79

5.1

Das Vernam One Time Pad . . . . . . . . . . . . . . . . . . . . . . . . . . . .

79

5.2

Automaten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

80

5.2.1

Angewandte Automaten . . . . . . . . . . . . . . . . . . . . . . . . . .

82

Linear feedback shift registers . . . . . . . . . . . . . . . . . . . . . . . . . . .

83

5.3

6 Koblitz und Miller

87

6.1

Elliptische Kurven u ¨ ber R . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

88

6.2

Elliptische Kurven u ¨ ber GF(q) . . . . . . . . . . . . . . . . . . . . . . . . . .

94

6.2.1

Quadratwurzeln in endlichen K¨orpern . . . . . . . . . . . . . . . . . .

94

6.2.2

Der Satz von Hasse . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

95

6.3

Kryptosysteme mit elliptischen Kurven . . . . . . . . . . . . . . . . . . . . . .

97

6.4

Faktorisieren mit elliptischen Kurven . . . . . . . . . . . . . . . . . . . . . . .

98

vi

INHALTSVERZEICHNIS

Abbildungsverzeichnis 5.1

Die einfache Mausefalle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

81

5.2

Die Mausefalle mit Speck . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

82

x5

+

x2

5.3

Das LFSR

+ 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

85

6.1

Elliptische Kurven u ¨ ber R . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

89

6.2

Addition der Punkte P und Q . . . . . . . . . . . . . . . . . . . . . . . . . . .

90

6.3

Verdopplung von P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

91

6.4

Die Addition von Punkten auf EC ist assoziativ . . . . . . . . . . . . . . . . .

93

vii

viii

ABBILDUNGSVERZEICHNIS

Vorwort Dies ist ein Skriptum zur Vorlesung Automatentheorie und Kryptographie“ an der Fach” hochschule Hagenberg. Die Vorlesung folgt in weiten Teilen [Buc99] und [Kob94]. Genaue Beschreibungen vieler Algorithmen finden sich in [MvOV97], das auch online gelesen werden kann (siehe Literaturverzeichnis), und in [Sch96]. Detailliertere mathematische Grundlagen finden Sie in [Bun92] und eine Sammlung von zahlentheoretischen Algorithmen in [Coh93]. F¨ ur eine intensivere Besch¨aftigung mit endlichen K¨orpern empfehle ich [LN84]. Eine detailliertere Behandlung von elliptischen Kurven in der Kryptographie, die immer noch sehr leicht lesbar ist, finden Sie in [Wer02]. Eine sehr genaue historische Behandlung der Kryptologie fast bis in die ’70er Jahre finden Sie in [Kah67]. Etwas unterhaltsamer und auch f¨ ur’s Nachtkasterl geeignet ist [Sin00].

ix

x

ABBILDUNGSVERZEICHNIS Die Kryptographie verfolgt im Wesentlichen die folgenden Ziele: Vertraulichkeit (confidentiality, secrecy, privacy): seit altersher das wichtigste Ziel

der Kryptographie. Kommunikation soll vertraulich, also geheim, erfolgen. Kein Dritter soll die Kommunikation abh¨oren k¨onnen. Integrit¨ at (data integrity): die Manipulation von Daten zwischen dem Sender und dem Empf¨anger durch unbefugte Dritte soll verhindert werden. Authentifizierung (authentication): zwei Parteien, die miteinander kommunizieren, wollen sicherstellen, das sie wirklich mit dem jeweils anderen zu tun haben, und nicht mit einem Dritten, der sich als jemand anderer ausgibt. Nichtzuru ¨ ckweisung“ (non-repudiation): unterschreibt jemand einen Vertrag soll ” sichergestellt werden, dass er sp¨ater nicht sagen kann, die Unterschrift sei nicht von ihm gewesen. F¨ ur jeden dieser Punkte werden wir mathematische Methoden entwickeln. Viel Vergn¨ ugen!

Kapitel 1

Caesar, Vigen` ere und Feistel 1.1

Caesar

Die mit Abstand am l¨angsten verwendete Methode zur Verschl¨ usselung ist die monoalphabetische Substitution. Dabei werden einfach Zeichen durch andere Zeichen ersetzt. Das kann geschehen, indem man einfach Buchstaben durch andere Buchstaben ersetzt, oder indem man u usselten ¨ berhaupt neue Symbole erfindet. Der eingeweihte Empf¨anger der verschl¨ Nachricht, der weiß, wie die Nachricht verschl¨ usselt wurde, dreht den Verschl¨ usselungsvorgang um und liest die Nachricht. Die wahrscheinlich bekannteste (und mit Abstand einfachste) Variante der monoalphabetischen Substitution tr¨agt den Namen von Julius Caesar. Bei dieser Substitution wird beispielsweise A durch E, B durch F, C durch G, usw. ersetzt, es ist aber jeder andere Buchstabe als E genauso m¨oglich. Wenn man erst einmal weiß, dass mit einem Caesar verschl¨ usselt wurde, ist es sehr einfach, einen verschl¨ usselten Text zu entschl¨ usseln. Versuchen Sie’s mit AIVMQ KPEWL EYWWM XDXWS PPRMG LXWXI MRIRA IVJIR Im schlimmsten Fall muss man alle 26 M¨oglichkeiten durchprobieren, bis man zu einer sinnvollen Nachricht kommt. (Alle W¨orter einfach aneinander zu schreiben und dann F¨ unfergruppen zu bilden, hat sich sehr bald wegen der gr¨oßeren Sicherheit eingeb¨ urgert.) F¨ ur Caesar’s Zeit mag dieses Verfahren ausgereicht haben. Bald jedoch brauchte man bessere Verfahren. Die monoalphabetische Substitution in allgemeiner Form bietet weit mehr M¨oglichkeiten. Es gibt 26! = 2 · 3 · 4 · · · 25 · 26 = 4 · 10 26 M¨oglichkeiten, irgendwie die 26

Buchstaben des Alphabets durch andere zu ersetzen. Da d¨ urfte es ziemlich schwierig werden. Versuchen Sie sich an GIRTV SRDST DUROZ YSHFO RDRDB RTGSJ 1

` KAPITEL 1. CAESAR, VIGENERE UND FEISTEL

2

TRMSI DHRTR OVJZJ SNRMN SAFKR FPVJN TSIVJ ZRYSM NRDDR TRBRT GSJTR MFORY PMPSA QJSNR ZODVJ RDIND ZOZIZ OPMOM SAAHR YROMR TGPTY NORZR ZEROZ YRJTY PRHAO VJLRO ZRMCC. Sehr sicher ist das trotzdem nicht. Bald kam man dahinter, dass gewisse Buchstaben viel h¨aufiger auftreten als andere. 1000 Buchstaben in einem durchschnittlichen deutschen Text verteilen sich in etwa folgendermaßen (Quelle: [Bau95]):

A

B

C

D

E

F

G

H

I

J

K

L

M

65

19

27

48

175

17

31

42

77

3

15

35

26

N

O

P

Q

R

S

T

U

V

W

X

Y

Z

98

30

10

0

75

68

61

42

9

1

0

1

11

In einem halbwegs langen Text sind die Verh¨altnisse ¨ahnlich.1 Das Symbol, das am h¨aufigsten vorkommt, wird wahrscheinlich f¨ ur E stehen, usw. So schaffen Sie den verschl¨ usselten Text von oben jetzt aber spielend. Fortgeschrittene Kryptanalytiker sehen sich auch die H¨aufigkeiten von Buchstabenkombinationen von 2 oder 3 Buchstaben an, den sogenannten Bigrammen und Trigrammen. Eine ausf¨ uhrliche Behandlung dieses Themas finden Sie in [Bau95]. Die Kryptographen versuchten sich zu sch¨ utzen, indem sie f¨ ur h¨aufige Buchstaben mehrere verschiedene Symbole, sogenannte Homophone, verwendeten, die sie abwechselnd verwendeten, weiters f¨ ullten sie die Kryptogramme mit sogenannten Nullen, das sind Symbole, die keine Bedeutung haben und nur den Kryptanalytiker verwirren sollen. Kurz und gut, zur Zeit des 30-j¨ahrigen Krieges lasen Kryptanalytiker in der Wiener schwarzen Kammer“ t¨aglich die sorgf¨altig verschl¨ usselte Korrespondenz der Botschafter der ” europ¨aischen L¨ander, all diese Verbesserungen der monoalphabetischen Substitution waren nicht gut genug.

1.2

Vigen` ere’s chiffre indechiffrable“ ”

Viel schwieriger wurde es f¨ ur kurze Zeit, als man von der monoalphabetischen zur polyalphabetischen Substitution wechselte. 200 Jahre, nachdem Vigen´ere sein Ver1

Hier ist vom statistischen Durchschnitt die Rede, keineswegs h¨ alt sich jeder lange Text an diese Werte.

Im Anhang von [Sin00] k¨ onnen Sie die erste Seite eines Romans lesen, der ganz ohne den Buchstaben e“ ”

auskommt.

1.3. SCHERBIUS

3

schl¨ usselungssystem vorgestellt hatte, wurde es endlich verwendet. Lange schon war die monoalphabetische Substitution nutzlos, aber man hatte nicht zu dem etwas aufwendigeren System wechseln wollen. Das Vigen´ere-System verwendet mehr als eine Substitution zum Verschl¨ usseln, sondern mehrere. Nun wird der erste Buchstabe mit der ersten Substitution verschl¨ usselt, der zweite mit der zweiten, der dritte mit der dritten, usw. Hat man alle Substitutionen durch, so beginnt man wieder mit der ersten. Besonders gerne wurden als Substitutionen einfache Caesar-Substitutionen verwendet. Die Abfolge der verschiedenen Substitutionen merkte man sich mit einem Schl¨ usselwort. Zum Beispiel w¨ urde das Schl¨ usselwort PLUTO bedeuten, dass der erste Buchstabe gem¨aß A → P , der zweite gem¨aß A → L, schließlich der f¨ unfte gem¨aß A → O, der sechste wieder wie der erste Caesar-verschl¨ usselt wird. Zum Entschl¨ usseln braucht man nur das Schl¨ usselwort. Aus PICKNICK w¨ urde dann (mit dem Schl¨ usselwort PLUTO) ETWDBXNE Wie man sieht, sieht man nichts. Gleiche Buchstaben werden verschieden verschl u ¨ sselt, verschiedene Buchstaben zuweilen gleich, eine H¨aufigkeitsanalyse macht hier keinen Sinn. Es dauerte leider nur ein paar Jahre, bis ein deutscher General auch dieses System knackte. Er fand heraus, dass man relativ leicht herausfinden kann, wie lang das verwendete Schl u ¨ sselwort ist. Hat man herausgefunden, dass das Schl¨ usselwort z.B. sieben Buchstaben lang ist, dann weiß man, dass der erste, der achte, der f¨ unfzehnte, usw. Buchstabe mit dem selben Alphabet, also monoalphabetisch verschl¨ usselt wurden, und man kann die einzelnen monoalphabetischen Substitutionen einzeln wie fr¨ uher analysieren.

1.3

Scherbius

Im Lauf des 19. Jahrhunderts kamen mehr und mehr mechanische Hilfsmittel zum Ver- und Entschl¨ usseln in Gebrauch. Am Beginn des 20. Jahrhunderts wurden schließlich die ersten Patente f¨ ur vollmechanische Verschl¨ usselungsmaschinen vergeben. Mit Ihnen wurde es m¨oglich, sehr bequem polyalphabetische Substitution mit tausenden Alphabeten durchzuf u ¨ hren. Scherbius konnte seine Maschine dem deutschen Milit¨ar anbieten. Die von der deutschen Enigma verschl¨ usselten Texte konnte nur mit sehr großem Aufwand und vor allem Dank der Nachl¨assigkeit der Verschl¨ ussler von britischen Kryptanalytikern gelesen werden. In [Sin00] und [Kah67] findet man eine nette Beschreibung der sehr komplexen Geschichte rund um die Enigma.

` KAPITEL 1. CAESAR, VIGENERE UND FEISTEL

4

1.4

Feistel

Moderne Verschl¨ usselungsverfahren arbeiten nicht mit einzelnen Zeichen. Auf Computern sind Daten in der Form von Bitfolgen gespeichert. Es bietet sich daher an, beim Verschl u ¨ sseln mit Bits oder mit Bitfolgen, sogenannten Bl¨ocken zu operieren. Als Beispiel sehen wir uns eines der ¨altesten Verfahren an, den Data Encryption Standard (DES), der bis 2000 der amerikanische Verschl¨ usselungsstandard war. Im Jahr 2000 wurde DES abgel¨ost vom Advanced Encryption Standard (AES), der als wesentlich sicherer gilt. Nach wie vor wird DES aber (vor allem in der Variante 3DES) verwendet. Außerdem werden nach wie vor Verschl¨ usselungsverfahren teilweise oder ganz nach dem Vorbild des DES mit ein paar Verbesserungen entwickelt. Der DES und allgemeine Feistelchiffren sind in [Buc99] ausgezeichnet beschrieben. Der AES wird uns sp¨ater besch¨aftigen, wenn wir mathematisch vorbereitet sind.

1.5

Die Erfindung der asymmetrischen Verschlu ¨ sselung

Viele Verschl¨ usselungssysteme, oft auch viel verwendete, bezogen ihre Sicherheit aus der Geheimhaltung des Verfahrens. Auch heute noch gibt es Verschl¨ usselungsprogramme, deren einzige Sicherheit darin liegt, dass man das Verschl¨ usselungsverfahren nicht kennt. Das prominenteste Beispiel sind die GSM-Verschl¨ usselungsalgorithmen A3, A5 und A8. Hierbei handelt es sich aber nicht wirklich um Sicherheit, denn das Verschl¨ usselungsverfahren kann nicht geheim gehalten werden. Verschl¨ usselungsmaschinen und -software kann gestohlen werden, Software kann analysiert werden, Verr¨ater k¨onnen das Verfahren bekannt geben. Tats¨achlich sind die GSM-Algorithmen l¨angst geknackt. Ein vern¨ unftiges Verschl¨ usselungsverfahren ist ein ¨offentlich bekanntes, das einzig Geheime ist der Schl¨ ussel. Alle Verschl¨ usselungsverfahren, die wir bisher kennen gelernt haben, geh¨oren zu den symmetrischen Verfahren. Zum Entschl¨ usseln einer Nachricht muss man das verwendete Verschl¨ usselungsverfahren und den verwendeten Schl¨ ussel kennen. Dann dreht man das Verschl¨ usselungsverfahren einfach um und kann so den Klartext wieder erhalten. Wir versuchen es ein bisschen mathematischer:

Definition 1.1. Ein Verschl¨ usselungsverfahren ist ein Quintupel (P, C, K, E, D) mit fol-

genden Eigenschaften:

1. P ist die Menge aller Klartexte, der Klartextraum. 2. C ist die Menge aller verschl¨ usselten Texte oder Chiffretexte. 3. K ist die Menge aller m¨oglichen Schl¨ ussel.

¨ 1.5. DIE ERFINDUNG DER ASYMMETRISCHEN VERSCHL USSELUNG

5

4. E = {Ek | k ∈ K} ist die Menge der Verschl¨ usselungsfunktionen Ek : P → C. 5. D = {Dk | k ∈ K} ist die Menge der Entschl¨ usselungsfunktionen Dk : C → P. 6. Zu jedem e ∈ K gibt es ein d ∈ K, so dass f¨ ur jeden Klartext p ∈ P gilt:

Dd (Ee (p)) = p. (Also: zu jedem Schl¨ ussel zum Verschl¨ usseln gibt es einen Schl¨ ussel zum Entschl¨ usseln.)

¨ Ublicherweise sind P, C, K, E und D bekannt, nur e ist geheim. Wer aber e kennt, kann

auch d schnell finden.

Mitte der ’70er Jahre fanden Mathematiker und Informatiker wie Diffie, Hellman ([DH76]), Rivest, Shamir und Adleman ([RSA77]) eine M¨oglichkeit zur asymmetrischen Verschl¨ usselung. Bei so einem Verfahren reicht es nicht aus, den zur Verschl¨ usselung verwendeten Schl¨ ussel und das verwendete Verfahren zu kennen, um die Verschl¨ usselung r¨ uckg¨angig machen zu k¨onnen. Man kennt also e und kriegt nicht heraus, was das dazugeh¨orige d ist. Praktisch bedeutet das sogar, dass man den Schl¨ ussel ¨offentlich bekanntmachen kann, so dass ihn jeder zum Verschl¨ usseln verwenden kann, trotzdem wird niemand anderer entschl¨ usseln k¨onnen. Tats¨achlich macht man das auch so. Den ¨offentlichen Schl¨ ussel nennen wir public key (daher nennt man asymmetrische Verschl¨ usselungssysteme auch public-key Systeme). Neben diesem Schl¨ ussel muss es aber auch einen Schl¨ ussel zum Entschl¨ usseln geben, den sogenannten private key. Dass es so ein asymmetrisches Verschl¨ usselungssystem tats¨achlich gibt, war Anfang der ¨ ’70er eine große Uberraschung. In K¨ urze werden wir wissen, wie das geht.

6

` KAPITEL 1. CAESAR, VIGENERE UND FEISTEL

Kapitel 2

Rivest, Shamir und Adleman In den folgenden Kapiteln spazieren wir durch die Welt der Zahlen. Manche Probleme, die auf den ersten Blick kompliziert aussehen, werden sich ganz leicht l¨osen lassen. Andere werden ganz leicht aussehen, sich aber als ganz schwierig herausstellen. Aus diesen Problemen machen wir Verschl¨ usselungsverfahren.

2.1

Auf den Spuren Euklids

Im Folgenden besch¨aftigen wir uns nur“ mit ganzen Zahlen. Die Menge der ganzen Zahlen ” bezeichnen wir mit Z. Die Menge der positiven ganzen Zahlen, also der nat¨ urlichen Zahlen bezeichnen wir mit N, die Menge der positiven Zahlen inklusive 0 mit N 0 . Wir erinnern uns kurz an die gute alte Zeit, als es noch keine Br¨ uche gab. Wollte man damals eine ganze Zahl durch eine andere teilen, so ging das nicht immer, manchmal blieb ” ein Rest“. Wir beschreiben das exakt.

Satz 2.1. Es seien a und b zwei beliebige ganze Zahlen. Dann gibt es zwei eindeutig bestimmte Zahlen q (Quotient) und r (Rest), so dass a = bq + r

und

0≤r
Manchmal geht sich die Division allerdings aus. Wir sagen, b teilt a und schreiben b | a,

wenn es eine ganze Zahl q gibt, so dass a = bq.

Beispiel 2.2.

7

8

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

• Die Teiler von 18 sind ±1, ±2, ±3, ±6, ±9 und ±18. • Die Teiler von −4 sind ±1, ±2 und ±4. • Jede ganze Zahl ist Teiler von 0. Die Zahlen ±1 und ±a sind nat¨ urlich immer Teiler von a. Ist a positiv und es gibt keine

weiteren Teiler, so heißt a Primzahl. Wir vereinbaren, dass 1 keine Primzahl ist. Die Menge aller Primzahlen bezeichnen wir mit P. Es liegt schon in der Luft, was jetzt kommt:

Satz 2.3 (Eindeutigkeit der Primfaktorzerlegung). Jede ganze Zahl n l¨asst sich in der Form n = ±pe11 · pe22 · · · perr darstellen, wobei p1 , p2 , . . . , pr ∈ P, e1 , e2 , . . . , er ∈ N und alle pi (1 ≤ i ≤ r) verschieden sind. Diese Darstellung als Produkt von Potenzen von Primzahlen ist eindeutig.

Die Primzahlen die in der Primfaktorzerlegung von n vorkommen, nennt man Primfaktoren von n. Eine Primfaktorzerlegung kann man zumindest f¨ ur kleine Zahlen so wie in der Mittelschule ausrechnen. Wir erinnern uns: 240

2

120

2

60

2

30

2

15

3

5

5

also ist 240 = 24 · 3 · 5.

1 Kennt man die Primfaktorzerlegung einer Zahl, so kennt man bereits alle Teiler.

Satz 2.4. Es sei n = pe11 · · · perr die Primfaktorzerlegung von n ∈ Z. Dann sind die

Teiler von n genau die Zahlen t = pt11 · · · ptrr , wobei t1 , . . . , tr ∈ N0 und t1 ≤ e1 , . . . , tr ≤ er .

2.1. AUF DEN SPUREN EUKLIDS

9

Sind a, b ∈ Z, so nennen wir die gr¨oßte ganze Zahl, die sowohl a als auch b teilt, den

gr¨oßten gemeinsamen Teiler von a und b. Wir schreiben daf¨ ur ggT(a, b). Ist ggT(a, b) = 1, so nennen wir a und b relativ prim oder teilerfremd.

Beispiel 2.5. Der gr¨oßte gemeinsame Teiler von 18 und 60 ist 6.

Zu einer gegebenen Zahl n ∈ Z andere Teiler als ±1 und ±n zu finden, ist f¨ ur große

n sehr schwierig. Das RSA-Verschl¨ usselungsverfahren beruht auf dieser Schwierigkeit. Allein herauszufinden, ob es weitere Teiler gibt oder ob es sich um eine Primzahl handelt, ist außer-

ordentlich schwierig. ¨ Uberraschenderweise ist es jedoch sehr einfach, den gr¨oßten gemeinsamen Teiler zweier Zahlen a und b zu finden. Die Methode, die einem zuerst einf¨allt, ist, zun¨achst die Primfaktorzerlegungen von a und von b zu bestimmen, und daraus den gr¨oßten gemeinsamen Teiler zu berechnen.

Beispiel 2.6. F¨ ur a = 21168 = 24 · 33 · 72 und b = 12600 = 23 · 32 · 52 · 7 ist ggT(a, b) = 23 · 32 · 7 = 504.

Offenbar ist das aber zumindest genauso schwierig, wie das Finden aller Teiler von a. Der Euklidsche Algorithmus erledigt das schneller. Er beruht auf den folgenden Beobachtungen:

Satz 2.7. Es seien a, b, c ∈ Z, c | a und c | b. Dann gilt: 1. ggT(a, b) = ggT(b, a), 2. c | a + b, 3. c | a − b, 4. c | a · b und 5. ggT(a, b) = ggT(r, b), wobei r der Rest bei der Division von a durch b ist (vgl.Satz 2.1).

Wir formulieren den Euklidschen Algorithmus anhand eines Beispiels:

10

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

Beispiel 2.8 (Euklidscher Algorithmus). Wir berechnen ggT(112, 203). ggT(112, 203) =(1) ggT(203, 112) =(5) ggT(91, 112) =(1) =(1) ggT(112, 91) =(5) ggT(21, 91) =(1) =(1) ggT(91, 21) =(5) ggT(7, 21) =(1) =(1) ggT(21, 7) =(5) ggT(0, 7) = 7

Der Euklidsche Algorithmus l¨asst sich noch etwas kompakter gestalten und etwas erweitern. Was dabei herauskommt, ist der erweiterte Euklidsche Algorithmus, der uns wieder an lineare Gleichungssysteme erinnert. Das selbe Beispiel nochmal: Beispiel 2.9.

203

112

I

203

1

0

II

112

0

1

III

91

1

-1

IV

21

-1

2

IV=II-III

V

7

5

-9

V=III-4IV

VI

0

III=I-II

VI=IV-3V

Von Interesse ist die Zeile V. Wir lesen ab, dass ggT(112, 203) = 7. Die erste Zeile k¨onnen wir lesen als 203 = 1·203+0·112, die zweite Zeile als 112 = 0·203+1·112, es handelt sich also wirklich um Gleichungen. Insbesondere d¨ urfen wir die Zeile V lesen als 7 = 5·203+(−9)·112.

Wir halten fest:

Satz 2.10. Der ggT zweier ganzer Zahlen l¨asst sich stets als Linearkombination der beiden Zahlen schreiben. Genauer: Seien a und b zwei ganze Zahlen. Dann gibt es ganze Zahlen x und y, so dass ggT(a, b) = ax + by

11

2.2. FALSCH RECHNEN

und der erweiterte Euklidsche Algorithmus berechnet die Zahlen x und y.

2.2

Falsch rechnen

Steht man um 7.00 fr¨ uh auf und arbeitet 8 Stunden, so ist man um 15.00 fertig, klar 7+8=15. Spielt man nun 8 Stunden Tennis, so kann man um 23.00 zu Bett gehen, auch klar 15+8=23. Schl¨aft man jetzt 8 Stunden, dann kann man um 7.00 wieder aufstehen. Hoppla, 23+8=7! In diesem Kapitel kl¨aren wir dieses Ph¨anomen auf. Wir w¨ahlen eine Zahl n ∈ N .

F¨ ur beliebige Zahlen a, b ∈ Z schreiben wir a ≡n b genau dann, wenn n | a − b

und sagen dann, a und b sind kongruent modulo n.

Beispiel 2.11. Je zwei gerade Zahlen sind kongruent modulo 2. Je zwei ungerade Zahlen sind kongruent modulo 2. Modulo 4 gilt 7 ≡ 4 3 und 2 ≡5 7 ≡5 −3.

Offenbar sind 2 Zahlen genau dann kongruent modulo n, wenn sie bei Division durch n den selben Rest ergeben. Das erkl¨art schon viel, denn 23 + 8 = 31, aber 31 und 7 sind kongruent modulo 24. Wir bilden Mengen von kongruenten Elementen modulo n. F¨ ur k ∈ Z sei [k]n die Menge

aller ganzen Zahlen, die kongruent zu k modulo n sind. [0]n := {0, ±n, ±2n, ±3n, . . .}

[1]n := {1, ±n + 1, ±2n + 1, ±3n + 1, . . .} [2]n := {2, ±n + 2, ±2n + 2, ±3n + 2, . . .} .. . [n − 1]n := {n − 1, ±n + (n − 1), ±2n + (n − 1), ±3n + (n − 1), . . .} [n]n = [0]n Diese Mengen heißen Restklassen modulo n.

12

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

Beispiel 2.12. Die Restklassen modulo 4 sind: [0]4 := {0, ±4, ±8, ±12, . . .} [1]4 := {. . . , −11, −7, −3, 1, 5, 9, 13, . . .} [2]4 := {. . . , −10, −6, −2, 2, 6, 10, 14, . . .} [3]4 := {. . . , −9, −5, −1, 3, 7, 11, 15, . . .}

Wir schreiben ein paar einfache Beobachtungen auf:

Satz 2.13. Es sei n ∈ N, a, b ∈ Z. Dann gilt 1. a kommt in genau einer der Restklassen [0] n , [1]n , . . . , [n − 1]n vor. 2. Falls a ≡n b, dann ist [a]n = [b]n , und umgekehrt.

Es wird noch schlimmer. Anstatt mit ganzen Zahlen rechnen wir jetzt mit den Restklassen, also mit unendlich großen Mengen. N¨amlich folgendermaßen:

Definition 2.14. Es seien n, k ∈ N , a, b ∈ Z. Dann definieren wir [a]n + [b]n := [a + b]n [a]n − [b]n := [a − b]n [a]n · [b]n := [a · b]n [a]kn := [ak ]n

Beispiel 2.15.

• [6]12 + [7]12 = [13]12 = [1]12 • [3]9 · [7]9 = [21]9 = [3]9 • [2]5 − [7]5 = [−5]5 = [0]5

13

2.2. FALSCH RECHNEN

Wir werden, wenn m¨oglich, die Restklassen als Restklassen m¨oglichst kleiner nichtnegativer Zahlen schreiben, also [1]12 statt [13]12 , [4]5 statt [−1]5 und [0]4 statt [−328]4 . Die Rechnerei mit Restklassen k¨onnte eine Gefahr bergen. Wenn wir [a] n + [b]n berechnen, rechnen wir [a + b]n aus. Wir k¨onnten die Restklassen aber auch als [a 0 ]n und [b0 ]n schreiben, indem wir einfach irgendein anderes a 0 ≡n a und b0 ≡n b w¨ahlen. Das Ergebnis wird dann

[a0 + b0 ]n sein. Wenn nun [a + b]n 6= [a0 + b0 ]n , dann wissen wir nicht, was nun das richtige

Ergebnis ist. Dieses Problem tritt aber gl¨ ucklicherweise nicht auf, weder bei der Addition, noch bei der Subtraktion, der Multiplikation oder beim Potenzieren. Das kl¨art der folgende

Satz 2.16. Es seien n, k ∈ N, a, b, a0 , b0 ∈ Z, so dass a ≡n a0 und b ≡n b0 . Dann gilt 1. a + b ≡n a0 + b0 , 2. a − b ≡n a0 − b0 , 3. a · b ≡n a0 · b0 und 4. ak ≡n (a0 )k .

Rechnen modulo n heißt also rechnen mit Restklassen. F¨ ur die Menge der Restklassen modulo n schreiben wir ab sofort Zn , also ist Zn = {[0]n , [1]n , . . . , [n − 1]n }. Die Elemente der Menge Zn sind Mengen, weil wir damit aber rechnen k¨onnen, nennen wir sie auch Zahlen in Zn . Der Trick mit den Uhrzeiten ist also ganz einfach. Wir rechnen anstatt mit ganzen Zahlen einfach mit den Restklassen modulo 24. Weil die Schreibweise mit den Restklassen auf die Dauer etwas umst¨andlich wird, vereinbaren wir die

Notation 2.17. F¨ ur n, k ∈ N, a, b, c ∈ Z verwenden wir nach Belieben eine der folgenden

Schreibweisen:

Restklassen

Kongruenz

alternative Schreibweise

[a]n + [b]n = [c]n

a + b ≡n c

a + b = c mod n

a · b ≡n c

a · b = c mod n

[a]n − [b]n = [c]n [a]n · [b]n = [c]n [a]kn = [c]n

a − b ≡n c

a − b = c mod n

ak ≡n c

ak = c mod n

14

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

2.2.1

Noch einmal Caesar

Eine kryptographische Anwendung des Rechnens mit Restklassen kennen wir schon, Caesar’s Verschl¨ usselungssystem. Wir stellen uns die Buchstaben von A-Z durch die Zahlen A = 0, B = 1, . . . , Z = 25 dargestellt vor. Die Caesar-Substitution A → U l¨asst sich nun einfach durch die Formel x 7→ x + 20 mod 26 beschreiben. Allgemein sind x 7→ x + e mod 26 (0 ≤ e ≤ 25)

alle Caesar-Substitutionen, e ist der Schl¨ ussel, der zum Verschl¨ usseln verwendet wird, d = −e mod 26 ist der dazugeh¨orige Schl¨ ussel zum entschl¨ usseln. Das Entschl¨ usseln funktioniert genau gleich wie das Verschl¨ usseln mit der Formel x 7→ x + d mod 26. Es handelt sich um ein symmetrisches Verfahren, denn wer e kennt, kann auch d ohne viel M¨ uhe berechnen.

2.3

Diophantastisch

Beispiel 2.18. Eine Firma kauft Workstations um 46810 . Darunter sind welche um 1990 /Stk. und solche um 2740 /Stk. Wie viele Computer von welcher Sorte wurden gekauft? Wir machen den Ansatz x . . . Anzahl der Workstations um 1990 y . . . Anzahl der Workstations um 2740 und erhalten die Gleichung 1990x + 2740y = 46810 ¨ also eine Gleichung in 2 Unbekannten. Uber R erhalten wir unendlich viele L¨osungen. Wir sind aber nur an positiven ganzzahligen L¨osungen interessiert.

Gleichungen der Form ax + by = c

mit a, b, c ∈ Z und x, y ∈ Z

(2.1)

heißen lineare Diophantische Gleichungen. Es sei d = ggT(a, b). Die Gleichung ax + by = c hat mit Sicherheit keine ganzzahligen L¨osungen, wenn d kein Teiler von c ist, denn d ist Teiler von a und von b, also (wegen Satz 2.7) auch von ax und von by und damit von ax + by. Da ax + by = c ist, muss d also c teilen. Nehmen wir im Folgenden an, d teile c (sonst gibt es sowieso keine L¨osungen). Dann l¨asst sich die Gleichung durch d dividieren und wir erhalten eine Gleichung a 0 x + b0 y = c0 , bei der nun ggT(a0 , b0 ) = 1 gilt. Ab nun gehen wir davon aus, dass die Koeffizienten der Gleichung relativ prim zueinander sind.

15

2.3. DIOPHANTASTISCH

Mit dem erweiterten Euklidschen Algorithmus erh¨alt man ganze Zahlen x0 , y0 , so dass gilt ax0 + by0 = 1

(2.2)

Wir multiplizieren (2.2) mit c und erhalten a( x0 c ) + b( y0 c ) = c |{z} |{z}

(2.3)

x = x1 + bk,

(2.4)

y = y1 − ak.

(2.5)

=x1

=y1

Damit haben wir bereits eine L¨osung (x1 , y1 ) von (2.1) gefunden. Sei nun k ∈ Z und

Setzt man (2.4) in (2.1) ein, so erh¨alt man a(x1 + bk) + b(y1 − ak) = ax1 + abk + by1 − abk = c Also ist f¨ ur jedes beliebige k ∈ Z das Paar (x, y) aus (2.4) eine L¨osung von (2.1). Tats¨achlich

findet man so alle ganzzahligen L¨osungen.

Beispiel 2.19 (Fortsetzung). Die Diophantische Gleichung lautet 1990x + 2740y = 46810

(2.6)

Wir berechnen den ggT: 2740

1990

2740

1

0

1990

0

1

750

1

-1

490

-2

3

260

3

-4

230

-5

7

30

8

-11

20

-61

84

d = 10

69

-95

0 Wir erhalten d = 10 und besch¨aftigen uns nur mehr mit der Gleichung 199x + 274y = 4681.

(2.7)

16

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

Wir haben bereits berechnet, dass 199 · (−95) + 274 · 69 = 1

(2.8)

und wir erhalten die ersten L¨osungen durch Multiplikation mit 4681: x1 = (−95) · 4681 = −444695 y1 = 69 · 4681 = 322989

(2.9) (2.10)

Nun sind alle ganzzahligen L¨osungen gegeben durch x = −444695 + 274k y = 322989 − 199k,

(2.11) wobei k ∈ Z

(2.12)

Von diesen unendlich vielen ganzzahligen L¨osungen interessieren uns im speziellen Fall wieder nur die positiven L¨osungen (negative St¨ uckzahlen gibt es nicht). Wie m¨ ussen wir k ∈ Z w¨ahlen, damit x und y gleichzeitig positiv werden?

x wird positiv, wenn x = −444695 + 274k ≥ 0, also wenn k ≥ 1622, 97. y wird positiv,

wenn y = 322989 − 199k ≥ 0, also wenn k ≤ 1623, 06. In diesem Fall kommt also nur ein

einziges k in Frage, n¨amlich k = 1623. Mit diesem k erhalten wir x = 7 und y = 12. Dies

ist die einzige m¨ogliche L¨osung.

Eine wichtige Anwendung der Diophantischen Gleichungen kommt ganz unerwartet beim F¨alschen digitaler Signaturen. Dort wird es darum gehen, eine Gleichung“ ax = b mod n zu ” l¨osen. Das folgende Beispiel erkl¨art, warum das einerseits nicht so einfach, andererseits aber auch nicht schwierig ist.

Beispiel 2.20. Die Gleichung 12x = 27 besitzt keine ganzzahlige L¨osung. Die Gleichung“ ” 12x = 27 mod 105 besitzt aber 3 L¨osungen, 11, 46 und 81.

Wie findet man alle L¨osungen der Gleichung“ ” ax = b

mod n?

Wir schreiben (2.13) um in eine echte Diophantische Gleichung ax + ny = b und l¨osen die Gleichung.

(2.13)

¨ 2.4. ENDLICHE KORPER

2.4

17

Endliche K¨ orper

Das Rechnen mit Restklassen ist nicht viel schwieriger als das Rechnen mit ganzen Zahlen. Die von den ganzen Zahlen bekannten Rechenregeln gelten weiterhin. Divisionen machen typischerweise Probleme in Z, woraus sich der Siegeszug der rationalen Zahlen erkl¨art. Wie sieht’s mit dem Dividieren modulo n aus?

Beispiel 2.21. In Z l¨asst sich

5 6

nicht (ohne Rest) berechnen. Wie sieht es mit den Rest-

klassen modulo n aus? • n = 7:

[5]7 = [2]7 , denn [6]7 · [2]7 = [5]7 . [6]7

• n = 11:

[5]11 = [10]11 , denn [6]11 · [10]11 = [5]11 . [6]11

• n = 9: [6]9 · [0]9 = [0]9 , [6]9 · [1]9 = [6]9 , [6]9 · [2]9 = [3]9 , [6]9 · [3]9 = [0]9 , [6]9 · [4]9 = [6]9 , [6]9 · [5]9 = [3]9 , [6]9 · [6]9 = [0]9 , [6]9 · [7]9 = [6]9 , [6]9 · [8]9 = [3]9 .

Geht nicht!

Manchmal l¨asst sich also mit Restklassen besser“ dividieren, manchmal aber auch nicht. ” Bringen wir etwas Ordnung in dieses Durcheinander.

Satz 2.22. Es sei n ∈ N und k ∈ Z. Ist ggT(n, k) = 1, dann gibt es eine Zahl q ∈ Z,

so dass [1]n = [k]n · [q]n . Ist ggT(n, k) > 1, so ist dies nicht der Fall. (Mit anderen

Worten: Sind n und k relativ prim, dann hat k modulo n einen Kehrwert, sonst nicht.)

Falls ggT(n, k) = 1, so schreiben wir f¨ ur die Restklasse [q]n mit [1]n = [k]n · [q]n auch [k]−1 n

oder etwas mutiger [k −1 ]n und nennen [k]−1 n den Kehrwert von [k]n .

Besitzt k einen Kehrwert modulo n, dann l¨asst sich modulo n jede Zahl durch k dividieren gem¨aß der Rechenregel

[a]n [k]n

= [a]n ·

[1]n [k]n

(oder k¨ urzer

a k

=a·

1 k

mod n.

18

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN Nat¨ urlich hat [0]n nie einen Kehrwert. Alle anderen Restklassen k¨onnten einen Kehrwert

haben. Dies ist genau dann der Fall, wenn jede Zahl 0 < k < n relativ prim zu n ist.

Satz 2.23. In Zn l¨asst sich genau dann durch jede Zahl außer [0] n dividieren, wenn n eine Primzahl ist.

Mengen von Zahlen“, die sich beliebig addieren, subtrahieren, multiplizieren und (mit ” Ausnahme der 0) dividieren kann, nennen wir K¨orper. (In K¨ urze werden wir genau definieren, was ein K¨orper ist.) Die Mengen Zp (p ∈ P) sind also K¨orper. Die K¨orper Zp sind

außergew¨ohnlich, denn sie enthalten nur p verschiedene Elemente. Daher nennt man sie auch

endliche K¨orper. Neben Zp gibt es noch weitere endliche K¨orper, wir werden noch alle kennen lernen. Unendliche K¨orper gibt es viele, z.B. R, Q, C und unz¨ahlige andere. F¨ ur unendliche K¨orper werden wir uns nicht interessieren.

−1 −1 −1 Beispiel 2.24. Die Kehrwerte modulo 5. [1] −1 5 = [1]5 , [2]5 = [3]5 , [3]5 = [2]5 , [4]5 =

[4]5 . Damit l¨asst sich weiter rechnen:

3 4

=3·

1 4

= 3 · 4 = 2 mod 5.

Es w¨are sch¨on, wenn sich Kehrwerte modulo n auch schnell ausrechnen ließen, Durchprobieren ist eine schlechte L¨osung, wenn n sehr groß ist. Wir denken kurz an Euklid und atmen erleichtert auf: Besitzt k einen Kehrwert modulo n, dann ist ggT(n, k) = 1. Wegen Satz 2.10 gibt es Zahlen x, y ∈ Z, so dass kx + ny = 1. Betrachten wir diese Gleichung modulo n, so erhalten wir kx + 0 = 1

mod n.

Das heißt aber, dass x der gesuchte Kehrwert von k modulo n ist. Danke, Euklid!

Beispiel 2.25. Wir berechnen den Kehrwert von 12 modulo 17.

¨ 2.5. DAS RSA-VERSCHLUSSELUNGSVERFAHREN

17

12

I

17

1

0

II

12

0

1

III

5

1

-1

IV

2

-2

3

IV=II-2III

V

1

5

-7

V=III-2IV

VI

0

19

III=I-II

VI=IV-2V

Tats¨achlich ist ggT(17, 12) = 1. Weiters ist 1 = 17 · 5 + 12 · (−7) Modulo 17 ist also 1 = 12 · (−7) und der Kehrwert von 12 modulo 17 ist −7 = 10. Zur Probe berechnen wir 12 · 10 = 120 = 1 mod 17.

Es f¨allt auf, dass eine Spalte im erweiterten Euklidschen Algorithmus gar nicht ben¨otigt

wird. Tats¨achlich h¨atten wir die 17er-Spalte nicht mitrechnen m¨ ussen und so etwas Arbeit gespart.

2.5

Das RSA-Verschlu ¨ sselungsverfahren

An dieser Stelle bietet sich — gleichsam als Motivationsschub — ein Ausblick in die moderne Kryptographie an. Dazu m¨ ussen wir nur noch ein paar Kleinigkeiten in Erfahrung bringen.

2.5.1

Die Eulersche ϕ-Funktion

Wie viele Zahlen in Zn haben einen Kehrwert? Wie viele Zahlen zwischen 0 und n−1 sind relativ prim zu n? Das war zweimal die selbe Frage, und diese Frage wollen wir jetzt beantworten. Wir beginnen mit einer

Definition 2.26. Es sei n ∈ N. Dann heißt die Funktion ϕ(n) = #{k ∈ Z | 0 ≤ k < n und ggT(n, k) = 1} Eulersche ϕ–Funktion.

20

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

Satz 2.27. Der Wert ϕ(n) l¨asst sich berechnen, wenn man die Primfaktorzerlegung von n kennt, denn es gilt: 1. Ist p ∈ P, dann ist

ϕ(p) = p − 1.

2. Ist p ∈ P und d ∈ N, dann ist ϕ(pd ) = pd−1 (p − 1). 3. Sind m, n ∈ N und ggT(m, n) = 1, dann ist ϕ(m · n) = ϕ(m) · ϕ(n). 4. Ist n = pe11 · · · perr die Primfaktorzerlegung von n, dann ist ϕ(n) = n(1 −

1 1 ) · · · (1 − ). p1 pr

Bevor es losgeht noch ein Hammer (demn¨achst werden Sie diesen Satz auf einem ¨ Ubungsblatt finden und selbst beweisen).

Satz 2.28 (Euler). Sind z, n ∈ N und ist ggT(z, n) = 1 dann gilt z ϕ(n) = 1

mod n

Remark 2.29. F¨ ur den Fall, dass n eine Primzahl ist, wurde dieser Satz schon fr¨ uher von Fermat bewiesen. In dieser Version ist er auch als kleiner Satz von Fermat bekannt.

2.5.2

Das RSA-Verfahren

Bob m¨ochte Alice eine Nachricht schicken, niemand außer Alice soll die Nachricht lesen k¨onnen, also m¨ochte er sie verschl¨ usseln. Alice w¨ahlt zwei große Primzahlen p und q und berechnet n = pq. Weiters berechnet Alice ϕ(n) = (p − 1)(q − 1) (vgl. Satz 2.27). Nun w¨ahlt sie zuf¨allig eine Zahl e relativ prim zu ϕ(n).

Das Paar (n, e) ist ihr public key, den sie Bob schickt.

¨ 2.5. DAS RSA-VERSCHLUSSELUNGSVERFAHREN

21

Weiters berechnet Alice den Kehrwert d von e modulo ϕ(n) mit dem erweiterten Euklidschen Algorithmus. Die beiden Primzahlen p und q h¨alt sie geheim, das Tripel (p, q, d) stellt ihren private key dar. Bob hat seine Nachricht als Folge von Zahlen kleiner als n kodiert (vgl. Kapitel 1) kodiert. Um eine Zahl m zu verschl¨ usseln, berechnet er c = me

mod n.

Um die Nachricht zu entschl¨ usseln, muss die e-te Wurzel modulo n gezogen werden. Die e-te Wurzel modulo n zu ziehen ist sehr schwierig, wenn man die Primfaktoren p und q nicht kennt. Wir sehen gleich, dass das Wurzelziehen aber einfach ist, wenn man p und q kennt. Alice hat den Kehrwert d von e modulo ϕ(n) berechnet, d.h. ed = 1

mod ϕ(n)

bzw.

(2.14)

ed = 1 + v · ϕ(n) f¨ ur ein passendes v ∈ Z (2.15) Sie berechnet nun (modulo n) cd = (me )d = med = m1+vϕ(n)

wegen (2.14)

= m · mϕ(n)v = m · (mϕ(n) )v = m · 1v

=m

wegen Satz 2.28

mod n

und erh¨alt auf diese Weise die urspr¨ ungliche Nachricht m. ¨ urlich viel zu klein, in den Ubungen Beispiel 2.30. Die Zahlen in diesem Beispiel sind nat¨ werden wir uns an gr¨oßere Zahlen heran wagen. Alice w¨ahlt p = 7 und q = 5, also n = 35 und ϕ(35) = 6 · 4 = 24. Nun w¨ahlt sie e = 5

und sendet Bob ihren public key (n, e) = (35, 5). Weiters berechnet sie den Kehrwert von 5 modulo 24. 5 24

0

5

1

4

-4

1

5

0 Der private key von Alice ist (p, q, d) = (7, 5, 5).

22

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

Bob verschl¨ usselt die Nachricht m = 4, er berechnet c = m e = 45 = 9

mod 35

und schickt Alice c = 9. Alice entschl¨ usselt m = cd = 95 = 4 mod 35.

Ein weiteres Problem ergibt sich. Um mit einer sehr großen Zahl zu potenzieren sind sehr viele Multiplikationen mit sehr großen Zahlen notwendig, dazwischen wird man oft modulo n reduzieren m¨ ussen. Hier kann man sich mit zwei Tricks helfen. 1. Der Exponent darf modulo ϕ(n) reduziert werden (das hilft aber nur dem Entschl u ¨ ssler, denn nur er kann ϕ(n) berechnen). ¨ 2. Die Square-And-Multiply–Methode zum Potenzieren, die Sie in den Ubungen kennen lernen.

2.6

Der chinesische Restsatz

Das Rechnen modulo n hat unter Anderem den Vorteil, dass man immer mit kleinen Zahlen rechnen kann, weil man ja immer den Rest modulo n (bzw. den Rest modulo ϕ(n) im Exponenten) nehmen darf, wenn man will. Das Ergebnis erf¨ahrt man daf¨ ur aber auch nur modulo n. Das a¨ndern wir jetzt.

Beispiel 2.31. Wir wollen 13 · 4 berechnen. Das k¨onnen wir in Z machen, genauso gut

aber in Z60 , kein Unterschied. Wir machen es aber modulo 3, modulo 4 und modulo 5. So erhalten wir: 13 · 4 ≡3 1 · 1 ≡3 1 13 · 4 ≡4 1 · 0 ≡4 0 13 · 4 ≡5 3 · 4 ≡5 2 Daraus k¨onnen wir schließen, dass x = 13 · 4 eine Zahl ist, die die folgenden Kongruenzen

erf¨ ullt:

x ≡3 1 x ≡4 0 x ≡5 2

23

2.6. DER CHINESISCHE RESTSATZ

Schon wieder ein schwieriges Problem. M¨ ussen wir hier probieren? Nein, hier hilft der chinesische Restsatz.

Algorithmus 2.32 (Chinesischer Restsatz). Es seien n 1 , n2 , . . . , ns paarweise relativ prime nat¨ urliche Zahlen. Weiters seien x1 , x2 , . . . , xs ganze Zahlen. Dann erh¨alt man eine L¨osung des Restklassengleichungssystems x ≡ n1 x 1 x ≡ n2 x 2 .. . x ≡ ns x s auf folgende Weise: 1. Berechne n = n1 ·n2 · · · ns . Modulo n ist die L¨osung des Restklassengleichungssystems eindeutig.

2. Berechne f¨ ur i = 1, . . . , s die Zahlen qi :=

n ni

3. Jedes qi ist relativ prim zu ni (wieso?), und besitzt daher ein inverses Element modulo ni . Berechne f¨ ur i = 1, . . . , s das inverse Element ri von qi modulo ni (mit dem erweiterten Euklidschen Algorithmus). 4. Berechne x = x 1 q1 r1 + x 2 q2 r2 + · · · + x s qs rs

mod n.

Dieses x ist die eindeutige L¨osung des Restklassengleichungssystems. Betrachten wir dazu die Gleichung modulo ni . Wir erhalten x = x1 · q1 ·r1 + · · · + xi · qi ri + · · · + xs · qs ·rs |{z} |{z} |{z} =0

= xi

mod ni

=1

=0

mod ni

24

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

Beispiel 2.33 (Fortsetzung). Wir l¨osen das Restklassengleichungssystem x ≡3 1 x ≡4 0 x ≡5 2 1. n1 = 3, n2 = 4 und n3 = 5, also ist n = 3 · 4 · 5 = 60. 2. q1 = 20, q2 = 15, q3 = 12. −1 −1 −1 −1 −1 3. [q1 ]−1 3 = [2]3 = [2]3 , [q2 ]4 = [3]4 = [3]4 und [q3 ]5 = [2]5 = [3]5 , also ist r1 = 2,

r2 = 3 und r3 = 3. 4. x = 1 · 20 · 2 + 0 · 15 · 3 + 2 · 12 · 3 = 112 = 52 mod 60.

Wir werden den chinesischen Restsatz gleich benutzen, um Primzahlen zu erzeugen und das RSA-Verfahren zu knacken. Bleiben Sie dran.

2.7

Attacken auf RSA

2.7.1

Repeated Encryption

Die erste Attacke, die wir betrachten ist nicht speziell auf das RSA-Verfahren zugeschnitten, vielmehr auf alle public-key Systeme, bei denen Ver- und Entschl¨ usselung mit der selben Funktion und verschiedenen Schl¨ usseln funktioniert. Ausgehend von der verschl¨ usselten Nachricht c berechnet man die doppelt verschl¨ usselte Nachricht c1 = ce mod n, dann verschl¨ usselt man ein weiteres Mal und erh¨alt c2 = ce1 = 2

(ce )e = ce , usw. Angenommen, beim k-ten Mal erh¨alt man wieder die urspr¨ ungliche verschl¨ usselte Nachricht c, also ck = c. Dann muss ck−1 der Klartext gewesen sein, denn c = ck = cek−1 mod n. Zuf¨allig gew¨ahlte Exponenten e garantieren beim RSA-Verfahren bereits, dass man viel zu oft verschl¨ usseln m¨ usste, um wieder zu c zu gelangen.

2.7.2

Gleiche Moduln

Wird die selbe Nachricht mit zwei Schl¨ usseln (n, e1 ) und (n, e2 ) (gleiches n) verschl¨ usselt, so kann die urspr¨ ungliche Nachricht entschl¨ usselt werden, falls ggT(e1 , e2 ) = 1 ist.

25

2.7. ATTACKEN AUF RSA Nehmen wir an, die verschl¨ usselten Texte sind c 1 = m e1

mod n

c 2 = m e2

und

mod n.

Dann berechnet man einfach ganze Zahlen a und b mit ae1 + be2 = 1. Genau eine der beiden Zahlen ist negativ (warum?). Nehmen wir an, dies ist a. Ist ggT(c 1 , n) > 1, so hat man einen Teiler von n gefunden, der Schl¨ ussel ist vollst¨andig geknackt. Ist ggT(c1 , n) = 1, so kann man den Kehrwert c−1 von c1 modulo n berechnen. Nun berechnet man −a (c−1 · (c2 )b 1 )

mod n.

Das Ergebnis ist (c1 )a (c2 )b = (me1 )a (me2 )b = me1 a+e2 b = m mod n, die Nachricht im Klartext.

2.7.3

Die Low Exponent Attacke

Um den Aufwand beim Verschl¨ usseln im RSA-Verfahren klein zu halten — das ist sehr interessant, wenn man beispielsweise mit einer Smartcard verschl¨ usseln m¨ochte — k¨onnte man kleine Verschl¨ usselungsexponenten verwenden, da diese ja ohnehin o¨ffentlich bekannt sind. Die Low Exponent Attacke zeigt, wie ein Angreifer in diesem Fall die verschl¨ usselte Nachricht entschl¨ usseln kann. Angenommen,

die

selbe

Nachricht

m

wird

mit

den

¨offentlichen

Schl¨ usseln

(n1 , e), (n2 , e), . . . (ne , e) verschl¨ usselt. (Tats¨achlich muss die Nachricht mit e verschiedenen ¨offentlichen Schl¨ usseln mit dem selben Exponenten e verschl¨ usselt werden. Daher funktioniert diese Attacke auf keinen Fall, wenn e groß ist.) Dann l¨asst sich aus den e verschl¨ usselten Nachrichten der Klartext m berechnen. Man kennt dann m e ≡ n1 c 1

m e ≡ n2 c 2 .. . m e ≡ ne c e

Die Zahlen n1 , . . . , ne sind h¨ochstwahrscheinlich paarweise relativ prim. (Was kann man tun, wenn dies nicht der Fall ist?) Nach dem chinesischen Restsatz gibt es modulo n 1 · n2 · · · ne genau ein c, das diese Rest-

klassengleichungen erf¨ ullt. F¨ ur dieses c gilt also c = me mod n1 · n2 · · · ne . Da m kleiner ist

26

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

als jedes ni , ist me kleiner als n1 · n2 · · · ne , also gilt c = me . Nun kann man die e-te Wurzel

ganz normal (in Z) ziehen.

ussel seien (143, 3), (391, 3) und (899, 3). Beispiel 2.34. Es sei e = 3, die ¨offentlichen Schl¨ Verschl¨ usselt man die Nachricht m = 135, so erh¨alt man c1 = 60, c2 = 203 und c3 = 711. Mit dem chinesischen Restsatz erh¨alt man daraus c = mk = 2460375. Daraus zieht man nun die dritte Wurzel und erh¨alt m = 135.

2.8

Faktorisieren

Wir haben gesehen, dass das RSA-Verfahren gebrochen werden kann, wenn man in der Lage ist, eine große Zahl n, die das Produkt zweier großer Primzahlen p und q ist, zu faktorisieren. Die erste Methode, die einem einf¨allt, ist die Methode der Probedivision, also einfach durch alle Zahlen (beginnend mit 2) zu dividieren und dies solange, bis man einen Faktor gefunden hat. Wir betrachten im Folgenden zwei Methoden zur Faktorisierung großer Zahlen, die Pollard-(p − 1)-Methode und das quadratische Sieb.

2.8.1

Die Pollard-(p − 1)-Methode

Mit dieser Methode ist es m¨oglich, einen Primfaktor p einer Zahl n zu finden, wenn in der Primfaktorzerlegung von p − 1 nur kleine Primzahlpotenzen vorkommen.

Angenommen, die Zahl n habe einen Primfaktor p, so dass alle Primzahlpotenzen, die in

der Primfaktorzerlegung von p − 1 vorkommen, kleiner oder gleich B sind, wobei B eine nicht

allzu große Zahl ist. (Bemerkung: Nat¨ urlich kennen wir p nicht. Wir vertrauen blind darauf, dass p − 1 die gew¨ unschte Eigenschaft besitzt. Ist dies nicht der Fall, werden wir keinen Erfolg haben.)

Wir bilden zun¨achst das kleinste gemeinsame Vielfache E aller Zahlen, die kleiner oder gleich B sind. Somit ist E sicher ein Vielfaches von p − 1 (warum?), also E = v(p − 1) f u ¨ r ein passendes v ∈ Z.

Nach dem kleinen Satz von Fermat (Satz 2.28) gilt: ap−1 = 1 also

mod p,

aE = av(p−1) = (ap−1 )v = 1v = 1

mod p,

d.h. p | aE − 1 Also ist aE −1 ein Vielfaches von p. Falls aE −1 kein Vielfaches von n ist, dann ist ggT(a E −1, n) ein echter Teiler von n.

27

2.8. FAKTORISIEREN

Wir brauchen also nur aE − 1 modulo n zu berechnen und dann ggT(a E − 1, n). (Warum

reicht es hier, aE − 1 modulo n zu berechnen?) Die Parameter a und B sind hier frei w¨ahlbar, a kann zuf¨allig gew¨ahlt werden, B muss groß genug sein.

Hat man bei dieser Methode keinen Erfolg (a E − 1 ist ein Vielfaches von n), dann w¨ahlt

man ein anderes a, haben mehrere a nicht funktioniert, muss man wahrscheinlich ein gr¨oßeres B w¨ahlen.

Beispiel 2.35. Wir faktorisieren n = 1241143 und w¨ahlen a = 2, B = 13. Dann ist E = 23 · 32 · 5 · 7 · 11 · 13.

Wir erhalten 2E − 1 = 861525 mod n und ggT(861525, 1241143) = 547. Schon haben wir einen Teiler von n gefunden. Tats¨achlich ist 547 − 1 = 2 · 3 · 7 · 13.

2.8.2

Lineare Gleichungssysteme u orpern ¨ber endlichen K¨

F¨ ur die n¨achste Faktorisierungsmethode m¨ ussen wir ein lineares Gleichungssystem modulo p l¨osen k¨onnen. Wir wissen bereits, wie man lineare Gleichungsssysteme u ur das ¨ ber R l¨ost. F¨ Weitere beruhigt uns der

Satz 2.36. Alles, was wir u ¨ber Vektorr¨aume u ¨ ber R wissen, u ¨ bertr¨agt sich auf endliche K¨orper.

(Nat¨ urlich stimmt dieser Satz so nicht, aber er stimmt so weit, dass wir so tun k¨onnen, als w¨ urde er stimmen.)

2.8.3

Das quadratische Sieb

Die Pollard-(p − 1)-Methode ist f¨ ur nicht allzu große Zahlen eine einfache Faktorisierungs-

methode, die allerdings schnell an ihre Grenzen gelangt. Die dritte Methode ist noch besser, daf¨ ur brauchen wir aber noch ein bisschen mehr Mathematik. Dem quadratischen Sieb liegt folgende Beobachtung zu Grunde: Hat man ganze Zahlen x und y mit x2 = y 2

mod n und

(2.16)

x 6= ±y

mod n

(2.17)

28

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

dann kennt man auch schon einen Teiler von n, denn n | x2 − y 2 = (x + y)(x − y) n - x + y, n - x − y Berechnet man nun ggT(n, x − y), so hat man einen Teiler von n. Nun geht es nur noch darum, die Zahlen x und y zu finden. √ Sei m = b nc1 und f (x) = (x + m)2 − n. Bemerkung: Ist x klein, so ist auch f (x) klein.

Beispiel 2.37. Wir beginnen bescheiden und faktorisieren n = 3277, also m = 57. Zun¨achst berechnen wir die Werte f (−2) = 552 − 3277 = −252 = (−1) · 22 · 32 · 7 f (−1) = 562 − 3277 = −141 = (−1) · 3 · 47 f (0) = 572 − 3277 = −28 = (−1) · 22 · 7 f (1) = 582 − 3277 = 87 = 3 · 29

f (2) = 592 − 3277 = 204 = 22 · 3 · 17 Daraus lesen wir (unter anderem) 552 ≡3277 (−1) · 22 · 32 · 7

und

572 ≡3277 (−1) · 22 · 7

Multipliziert man die beiden Gleichungen, so erh¨alt man 552 · 572 = (−1) · 22 · 32 · 7 · (−1) · 22 · 7

bzw.

(55 · 57)2 = (−1)2 · 24 · 32 · 72 = (22 · 3 · 7)2

mod 3277

Wir w¨ahlen also x = 55 · 57 und y = 22 · 3 · 7 = 84. Tats¨achlich sind die Gleichungen (2.16) und (2.17) erf¨ ullt. Wir berechnen x − y = 3051 und ggT(3051, 3277) = 113, ein Teiler von

n ist gefunden.

So einfach geht’s nicht immer, hier haben wir Gl¨ uck gehabt. Im Allgemeinen muss man ein bisschen mehr tun. Auf der linken Seite steht immer ein Quadrat, wenn man Gleichungen multipliziert. Es stellt sich die Frage, welche Gleichungen (m¨oglicherweise mehr als zwei) multipliziert werden 1

F¨ ur x ∈

bezeichnet man mit bxc die gr¨ oßte ganze Zahl, die kleiner oder gleich x ist.

29

2.8. FAKTORISIEREN

m¨ ussen, damit sich auch auf der rechten Seite ein Quadrat ergibt. Manchmal kann man raten, meistens jedoch muss man rechnen, wir setzen unser Beispiel fort.

Beispiel 2.38 (Fortsetzung). Die rechten Seiten sind (−1) · 22 · 32 · 7, (−1) · 4 · 47, (−1) · 22 · 7, 3 · 29 und 22 · 3 · 17. Wir definieren nun λi = 1, wenn die i-te Gleichung verwendet werden soll und sonst λ i = 0. Multipliziert man nun die Gleichungen, so erh¨alt man auf der rechten Seite

· (3 · 29)λ4


λ1

· ((−1) · 3 · 47)λ2 · (−1) · 22 · 7
λ · 22 · 3 · 17 5

(−1) · 22 · 32 · 7


λ3

Wir sortieren das Ergebnis nach den Basen und erhalten

(−1)λ1 +λ2 +λ3 · 22λ1 +2λ3 +2λ5 · 32λ1 +λ2 +λ4 +λ5 · 7λ1 +λ3 · 17λ5 · 29λ4 · 47λ2

Damit ein Quadrat herauskommt, m¨ ussen alle Exponenten kongruent 0 modulo 2 (also gerade) sein, d.h. λ1 + λ 2 + λ 3 = 0

mod 2

2λ1 + 2λ3 + 2λ5 = 0

mod 2

2λ1 + λ2 + λ4 + λ5 = 0

mod 2

λ1 + λ 3 = 0

mod 2

λ5 = 0

mod 2

λ4 = 0

mod 2

λ2 = 0

mod 2

Es ergibt sich ein lineares Gleichungssystem u ¨ ber dem K¨orper Z2 , welches sich wie gewohnt l¨osen l¨asst. Besitzt das lineare Gleichungssystem neben dem Nullvektor eine weitere L¨osung, so wissen wir, welche Gleichungen multipliziert werden m¨ ussen. In diesem Fall ergibt sich λ1 = λ3 = 1 und λ2 = λ4 = λ5 = 0. Den Rest kennen wir ja schon.

30

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

2.9

Zufallszahlen

Ein zentrales Element jedes kryptographischen Systems ist der Zufallszahlengenerator. Ein RSA-Schl¨ ussel muss selbstverst¨andlich zuf¨allig erzeugt sein, sonst k¨onnte ein Angreifer ihn m¨oglicherweise einfach reproduzieren. Wir werden noch andere Verfahren kennen lernen, die vor allem auf einen guten Zufallszahlengenerator vertrauen. Was heißt nun guter Zufallszahlengenerator“? Der beste Zufallszahlengenerator ist der ” Zufall selbst (falls es so etwas gibt), also ein Prozess, der v¨ollig unvorhersehbar ist, solange man ihn auch beobachtet. Eine M¨oglichkeit einen guten Zufallszahlengenerator zu bauen ist nun, einen nat¨ urlichen zuf¨alligen Prozess zu beobachten. So gibt es Zufallszahlengeneratoren, die den Zerfall radioaktiven Materials beobachten (ein Prozess, von dem man glaubt, dass er ganz zuf¨allig passiert). F¨ ur das eigene Notebook begn¨ ugt man sich in der Regel mit Algorithmen, die zuf¨allige Zahlen produzieren, die sich nur sehr schwer von wirklich zuf¨allig erzeugten Zahlen unterscheiden lassen.

2.9.1

Test auf Zuf¨ alligkeit

Wir sehen uns kurz ein paar Tests an, mit denen sich feststellen l¨asst, ob eine Folge von Bits nicht zuf¨allig ist (siehe auch [MvOV97, Abschnitt 5.4]). Wir werden uns nicht eingehender mit Statistik besch¨aftigen, sondern begn¨ ugen uns mit einem Crashkurs. Um die Zuf¨alligkeit einer Bitfolge zu u ufen, berechnet man bestimmte Kennzahlen ¨ berpr¨ der Bitfolge, sogenannte Statistiken. Diese Statistiken haben bei zuf¨alligen Folgen Werte in einem bestimmten Bereich, bei nicht zuf¨alligen Folgen k¨onnen die Werte der Statistik außerhalb dieser Bereiche liegen. Damit l¨asst sich entscheiden, ob die Bitfolge zuf¨allig ist. Nat¨ urlich kann der Wert einer Statistik auch zuf¨allig“ außerhalb des erwarteten Bereichs ” liegen, allerdings nur mit geringer Wahrscheinlichkeit. Das Ergebnis eines statistischen Tests ist somit stets eine Aussage der Art: Die untersuchte Bitfolge ist nicht zuf¨allig. Die Wahrscheinlichkeit, dass der Wert der Statistik zuf¨allig so extrem war, betr¨agt nur . . . %. Liegt die berechnete Wahrscheinlichkeit unter einer vorgegebenen Schranke α (dem sogenannten Signifikanzniveau), dann kann man ziemlich sicher sein, dass die Bitfolge nicht zuf¨allig ist. Wie groß α gew¨ahlt wird, h¨angt davon ab, wie sicher man sein will, u ur ¨ blich sind 10% f¨ unkritische Anwendungen bis zu 0.05% f¨ ur hochsensible Anwendungen. Die Statistiken in den im Folgenden beschriebenen Tests sind allesamt χ 2 -verteilt. Die erwarteten Bereiche f¨ ur die Statistiken in der Form von Quantiltabellen angegeben. Eine solche Quantiltabelle ist Tabelle 2.1.

31

2.9. ZUFALLSZAHLEN

df

0.10

0.05

0.025

0.02

0.01

0.005

0.0025

0.001

0.0005

1

2.71

3.84

5.02

5.41

6.63

7.88

9.14

10.83

12.12

2

4.61

5.99

7.38

7.82

9.21

10.60

11.98

13.82

15.20

3

6.25

7.81

9.35

9.84

11.34

12.84

14.32

16.27

17.73

4

7.78

9.49

11.14

11.67

13.23

14.86

16.42

18.47

20.00

5

9.24

11.07

12.83

13.33

15.09

16.75

18.39

20.51

22.11

6

10.64

12.53

14.45

15.03

16.81

13.55

20.25

22.46

24.10

7

12.02

14.07

16.01

16.62

18.48

20.28

22.04

24.32

26.02

8

13.36

15.51

17.53

18.17

20.09

21.95

23.77

26.12

27.87

9

14.68

16.92

19.02

19.63

21.67

23.59

25.46

27.83

29.67

10

15.99

18.31

20.48

21.16

23.21

25.19

27.11

29.59

31.42

11

17.29

19.68

21.92

22.62

24.72

26.76

28.73

31.26

33.14

12

18.55

21.03

23.34

24.05

26.22

28.30

30.32

32.91

34.82

13

19.81

22.36

24.74

25.47

27.69

29.82

31.88

34.53

36.48

14

21.06

23.68

26.12

26.87

29.14

31.32

33.43

36.12

38.11

15

22.31

25.00

27.49

28.26

30.58

32.80

34.95

37.70

39.72

16

23.54

26.30

28.85

29.63

32.00

34.27

36.46

39.25

41.31

17

24.77

27.59

30.19

31.00

33.41

35.72

37.95

40.79

42.88

18

25.99

28.87

31.53

32.35

34.81

37.16

39.42

42.31

44.43

19

27.20

30.14

32.85

33.69

36.19

38.58

40.88

43.82

45.97

20

28.41

31.41

34.17

35.02

37.57

40.00

42.34

45.31

47.50

21

29.62

39.67

35.48

36.34

38.93

41.40

43.78

46.80

49.01

22

30.81

33.92

36.78

37.66

40.29

42.80

45.20

48.27

50.51

23

32.01

35.17

38.08

38.97

41.64

44.18

46.62

49.73

52.00

24

33.20

36.42

39.36

40.27

42.98

45.56

48.03

51.18

53.48

25

34.38

37.65

40.65

41.57

44.31

46.93

49.44

52.62

54.95

26

35.56

38.89

41.92

42.86

45.64

48.29

50.83

54.05

56.41

27

36.74

40.11

43.19

44.14

46.96

49.64

52.22

55.48

57.86

28

37.92

41.34

44.46

45.42

48.28

50.99

53.59

56.89

59.30

29

39.09

42.56

45.72

46.69

49.59

52.34

54.97

58.30

60.73

30

40.26

43.77

46.98

47.96

50.89

53.67

56.33

59.70

62.16

40

51.81

55.76

59.34

60.44

63.69

66.77

69.70

73.40

76.09

50

63.17

67.50

71.42

72.61

76.15

79.49

82.66

86.66

89.56

60

74.40

79.08

83.30

84.58

88.38

91.95

95.34

99.61

102.7

80

96.58

101.9

106.6

108.1

112.3

116.3

120.1

124.8

128.3

100

118.5

124.3

129.6

131.1

135.8

140.2

144.3

149.4

153.2

Tabelle 2.1: In dieser Quantiltabelle findet sich in der Spalte 0.01 in der Zeile 9 die Zahl 21.67. Das bedeutet, dass die Wahrscheinlichkeit, dass eine mit 9 Freiheitsgraden χ 2 -verteilte Zahl mit einer Wahrscheinlichkeit von 1% gr¨oßer oder gleich 21.67 ist.

32

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN Sehen wir uns die wichtigsten Tests kurz an.

H¨ aufigkeitstest In einer zuf¨alligen Bitfolge der L¨ange n kommen 0 und 1 ungef¨ahr gleich oft vor. Sei n0 die Anzahl der 0en und n1 die Anzahl der 1en in der Bitfolge. Die Zahl (n0 − n1 )2 n 2 ist dann n¨aherungsweise χ -verteilt mit 1 Freiheitsgrad, falls n ≥ 10. T1 =

Zwei-Bit-Test Die Paare 00, 01, 10 und 11 kommen in einer zuf¨alligen Bitfolge ungef¨ahr gleich oft vor. Es seien n00 , n01 , n10 und n11 die Anzahl der Paare 00, 01, 10 und 11 in der Bitfolge. Dann ist die Zahl 4 2 T2 = (n200 + n201 + n210 + n211 ) − (n20 + n21 ) + 1 n−1 n n¨aherungsweise χ2 -verteilt mit 2 Freiheitsgraden, falls n ≥ 21.

Pokertest Dieser Test ist eine Verallgemeinerung des Zwei-Bit-Tests. Es sei m eine Zahl mit n c ≥ 5 · 2m . Man teilt die Bitfolge irgendwie in k nicht u k := b m ¨ berlappende Teile der

L¨ange m. Jeder dieser Teile ist die Bin¨ardarstellung einer Zahl i mit 0 ≤ i < 2 m . Nun

sei ni die Anzahl der Teile, welche die Zahl i darstellen. Dann ist die Zahl 2m −1

2m X 2 T3 = ( ni ) − k k i=0

n¨aherungsweise

χ2 -verteilt

mit

2m

− 1 Freiheitsgraden.

Runs-Test Ein Run ist eine Teilfolge einer Bitfolge aus lauter gleichen Symbolen. Der RunTest untersucht, ob die Anzahl der Runs bestimmter L¨ange der erwarteten Anzahl in einer zuf¨alligen Bitfolge entspricht. Die erwartete Anzahl von Runs von 0en (oder 1en) der L¨ange i in einer Bitfolge der L¨ange n ist ei = (n − i + 3)/2i+2 . Nun sei k die gr¨oßte

Zahl i, f¨ ur die ei ≥ 5. Nun z¨ahlen wir f¨ ur 1 ≤ i ≤ k Oi , die Anzahl der Runs von 0en

der L¨ange i, und Ii , die Anzahl der Runs von 1en der L¨ange i. Dann ist die Zahl T4 =

k X (Oi − ei )2 i=1

ei

+

k X (Ii − ei )2 i=1

ei

n¨aherungsweise χ2 -verteilt mit 2k − 2 Freiheitsgraden.

Autokorrelationstest Mit diesem Test wird untersucht, ob es einen Zusammenhang zwischen der Bitfolge und der um d Stellen verschobenen Bitfolge gibt. Es sei s i das i-te Pn−d−1 Bit der Bitfolge und d eine Zahl mit 1 ≤ d ≤ b n2 c. Weiters sei A(d) = i=0 si ⊕ si+d

(⊕ steht f¨ ur XOR). Dann ist die Zahl

n−d 2 ) /(n − d) 2 n¨aherungsweise χ2 -verteilt mit 1 Freiheitsgrad, falls n − d ≥ 10. T5 = 4(A(d) −

2.9. ZUFALLSZAHLEN

33

Beispiel 2.39. Wir untersuchen die Bitfolge der L¨ange n = 160, die entsteht, wenn man die Bitfolge 1110001100010001010011101111001001001001 vier mal hintereinander schreibt. 1. (H¨aufigkeitstest) n0 = 84, n1 = 76, T1 = 0.4. Die Wahrscheinlichkeit, dass T 1 ≥ 0.4 ist, ist gr¨oßer als 10%. Test bestanden.

2. (Zwei-Bit-Test) n00 = 44, n01 = 40, n10 = 40, n11 = 35, T2 = 0.625. Die Wahrscheinlichkeit, dass T2 ≥ 0.625 ist, ist gr¨oßer als 10%. Test bestanden. 3. (Pokertest f¨ ur m = 3) k = 53, n0 = 5, n1 = 10, n2 = 6, n3 = 4, n4 = 12, n5 = 3, n6 = 6, n7 = 7, T3 = 9.64. Die Wahrscheinlichkeit, dass T 3 ≥ 9.64 ist, ist gr¨oßer als 10%. Test bestanden.

4. (Runs-Test) e1 = 20.25, e2 = 10.06, e3 = 5, k = 3, O1 = 8, O2 = 20, O3 = 12, I1 = 25, I2 = 4, I3 = 5, T4 = 31.79. Die Wahrscheinlichkeit, dass T 4 ≥ 31.79 ist, ist

kleiner als 0.05%. Diese Bitfolge ist nicht zuf¨allig.

5. (Autokorrelationstest f¨ ur d = 8) A(8) = 100, T5 = 15.13. Die Wahrscheinlichkeit, dass T5 ≥ 15.13 ist, ist kleiner als 0.05%. Die Bitfolge ist nicht zuf¨allig.

2.9.2

Der BBS-Zufallszahlengenerator

Definition 2.40. Ein (Pseudo-)Zufallszahlengenerator (pseudo random number generator, PRNG) ist ein deterministischer Algorithmus, der eine Bitfolge erzeugt, die sich durch die statistischen Tests aus Abschnitt 2.9.1 nicht von einer zuf¨alligen Bitfolge unterscheiden l¨asst.

Es gibt viele M¨oglichkeiten, Pseudozufallszahlen zu erzeugen (siehe [MvOV97] und [Sch96]). Wir sehen uns einen der bekanntesten PRNGs an, den Blum-Blum-Shub-PRNG 2 , benannt nach seinen Erfindern. Er ben¨otigt zwei große (geheime) Primzahlen p und q, beide kongruent 3 modulo 4. 2

Die genaue Beschreibung samt Beweis f¨ ur seine Unvorhersagbarkeit finden Sie in [BBS86].

34

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

Algorithmus 2.41 (Blum-Blum-Shub-PRNG).

1. Es sei n = pq. 2. W¨ahle eine zuf¨allige Zahl s mit 1 ≤ s ≤ n − 1 relativ prim zu n und berechne x 0 = s2 mod n.

3. Berechne xi = x2i−1 mod n. 4. Wiederhole Schritt (3).

Der Algorithmus ist vollkommen deterministisch, sobald die Zahl s, der sogenannte seed ¨ gew¨ahlt ist. Ublicherweise wird ein seed bestimmt, indem man gewisse Daten des Computers (Systemzeit, Register- und Speicherinhalte, Userinput u ¨ ber das Keyboard, Mausbewegungen, Netzwerkdaten, . . . ) ausliest und daraus eine zuf¨allige Zahl macht. Von den berechneten xi verwendet man jeweils nur das letzte Bit bzw. die letzten j Bits, wobei j in der Gr¨oßenordnung von ln ln n liegt, also auch f¨ ur sehr große n nicht mehr als 10.

2.10

Erzeugung von Primzahlen

Die klassische Methode zur Primzahlerzeugung ist, eine zuf¨allige Zahl zu erzeugen, und dann zu u ufen, ob es sich um eine Primzahl handelt. Diese Methode funktioniert aus zwei ¨ berpr¨ Gr¨ unden sehr gut: 1. Die Wahrscheinlichkeit, dass eine zuf¨allig gew¨ahlte Zahl eine Primzahl ist, ist nicht sehr klein, d.h. nach nicht allzu vielen Versuchen ist die Zahl eine Primzahl. 2. Es ist m¨oglich, in vern¨ unftiger Zeit zu u ufen, ob eine Zahl Primzahl ist. ¨ berpr¨ Beides ist nicht unmittelbar klar. Wir gehen dem nach.

2.10.1

Es gibt viele Primzahlen

Wir beginnen ganz harmlos:

Satz 2.42. Es gibt unendlich viele Primzahlen.

35

2.10. ERZEUGUNG VON PRIMZAHLEN

Dieses sch¨one Resultat sagt uns zumindest, dass uns die Primzahlen nie ausgehen. F¨ ur unsere Zwecke brauchen wir aber etwas mehr. Den folgenden Satz haben zwei Mathematiker unabh¨angig voneinander bewiesen, nachdem das Problem 100 Jahre lang ungel¨ost war. Wir begn¨ ugen uns mit einer sehr ungenauen Formulierung.

Satz 2.43 (Hadamard (1896) und de la Vall´ ee Poussin (1896)). Es sei π(x) die Anzahl der Primzahlen, die kleiner sind als x ∈ N. Dann gilt f¨ ur x ≥ 17 x x < π(x) < 1.25506 · . ln x ln x

Dieser Satz sagt insbesondere etwas dar¨ uber aus, wie viele Primzahlen es in etwa in der Umgebung von x gibt. Wir berechnen einfach, wie sehr sich die Anzahl der Primzahlen bei x ¨andert, also einfach die Steigung von π(x) an der Stelle x. 3 Es ergibt sich π 0 (x) ≈

ln x−1 ln2 x

≈

1 ln x .

Das bedeutet, dass in der Gegend von x in etwa jede ( ln1x )-te Zahl eine Primzahl ist. Anders

ausgedr¨ uckt: Man muss im Durchschnitt ln x Zahlen in der Gegend von x testen, bis man eine Primzahl findet. Da ln x eine sehr langsam wachsende Funktion ist, braucht man selbst bei großen x noch nicht allzu lange probieren.

2.10.2

Primzahltests

Wir u ufen kann, ob eine ganze ¨ berlegen uns in diesem Kapitel, ob und wie man schnell u ¨ berpr¨ Zahl n eine Primzahl ist. Probedivision Eine einfache M¨oglichkeit, festzustellen, ob n prim ist, ist probeweise durch alle (Prim-)Zahlen, √ die kleiner sind als n, zu dividieren. Findet man dabei einen Teiler von n, so ist n keine √ Primzahl. Findet man keinen Teiler, dann ist n prim. (Warum muss nur bis n probiert werden?) Diese Methode erfordert sehr viele Probedivisionen. F¨ ur das RSA-Verfahren brauchen wir aber zwei sehr große Primzahlen. Sehen wir uns zwei weitere Methoden an. Der Fermat–Test Der kleine Satz von Fermat (Satz 2.28) besagt, dass f¨ ur alle 0 < a < n gilt: an−1 = 1 3

mod n,

¨ Es sei angemerkt, dass diese analytischen Uberlegungen nat¨ urlich nicht g¨ ultig sind, sie beschreiben aber

sehr anschaulich, was hier passiert.

36

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN

falls n eine Primzahl ist. Und sonst? Sehen wir uns ein paar Beispiele an.

Beispiel 2.44.

n

a

an−1 mod n

prim?

14

2

2

nein

341

2

1

???

341

3

56

nein

561

2

1

???

561

3

1

???

561

4

1

???

Tats¨achlich lassen sich zusammengesetzte Zahlen mit diesem einfachen Test enttarnen. 14 ist sofort als nicht prim identifiziert, 341 besteht den ersten Test mit Basis 2, scheitert aber beim zweiten Test mit Basis 3, 561 ist noch hartn¨ackiger, besteht den Test f¨ ur die Basen 2, 3 und 4. Falls n den Fermat–Test mit Basis a besteht, so nennen wir n eine Pseudoprimzahl zur Basis a. Im obigen Beispiel ist also 341 Pseudoprimzahl zur Basis 2, aber nicht zur Basis 3, 561 ist Pseudoprimzahl zu den Basen 2, 3 und 4. Nach dem kleinen Satz von Fermat ist jede Primzahl p Pseudoprimzahl zu jeder Basis a mit ggT(a, p) = 1. Lassen sich alle zusammengesetzten Zahlen ertappen oder gibt es zusammengesetzte Zahlen n, die Pseudoprimzahlen zu jeder Basis a mit ggT(a, n) = 1 sind? Die bedr¨ uckende Antwort ist ja“. Solche Zahlen heißen Carmichaelzahlen. Die zehn kleinsten Carmichaelzahlen ” sind 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841 und 29341. Remark 2.45. Falls der Fermat–Test ergibt, dass es sich bei n nicht um eine Primzahl handelt, so kennt man noch keinen Teiler von n, der Fermat–Test ist also nicht als Faktorisierungsmethode zu gebrauchen. Faktorisieren ist also schwieriger, als Primalit¨at zu testen. Der Fermat–Test kann also schnell belegen, dass eine Zahl zusammengesetzt ist, Carmichaelzahlen sind allerdings zusammengesetzte Zahlen, die der Fermat–Test immer f u ¨ r Primzahlen h¨alt. Wir m¨ ussen uns noch ein bisschen mehr anstrengen. Der Miller–Rabin–Test Um den Fermat–Test zu verbessern, verbessern wir einfach den kleinen Satz von Fermat.

37

2.10. ERZEUGUNG VON PRIMZAHLEN

Satz 2.46. Es sei n > 2 eine Primzahl. Dann l¨asst sich n − 1 eindeutig als n − 1 = 2s k

schreiben, wobei k ∈ N ungerade und s ∈ N ist. Weiters sei 0 < a < n. Dann gilt

entweder

ak = 1

mod n

(2.18)

oder es gibt eine Zahl r ∈ {0, 1, . . . , s − 1} mit a2

rk

= −1

mod n

(2.19)

Diesen leicht modifizierten Test, den Miller–Rabin–Test, besteht auch keine Carmichaelzahl mehr f¨ ur jede Basis a. Eine Basis a, f¨ ur die n den Miller–Rabin–Test nicht besteht nennen wir einen Zeugen gegen die Primalit¨at von n.

Satz 2.47. Erf¨ ullt n die Bedingungen (2.18) oder (2.19) f¨ ur jedes 0 < a < n, so ist n eine Primzahl.

Beispiel 2.48. Die erste Carmichaelzahl n = 561 besteht den Miller–Rabin–Test f u ¨r a = 2 nicht: wir erhalten 561 − 1 = 24 · 35, also s = 4 und d = 35. Wir berechnen 2 35 = 263 mod 561, also ist (2.18) nicht erf¨ ullt. Weiter erhalten wir 22

mod 561 und

3 22 ·35

1 ·35

= 166 mod 561, 22

2 ·35

= 67

= 1 mod 561, nie ist das Ergebnis −1, also ist auch (2.19) nicht erf¨ ullt.

Somit ist 561 keine Primzahl.

Die Situation ist jetzt also viel besser, allerdings muss man sehr viele Basen durchprobieren, um sicher sein zu k¨onnen, dass n tats¨achlich eine Primzahl ist. Das geht wieder nicht. Eine letzte Rettung bietet der folgende Satz.

urliche Zahl, dann gibt es h¨ochstens Satz 2.49. Ist n eine zusammengesetzte nat¨

n−1 4

Zahlen zwischen 1 und n−1, die zu n relativ prim und keine Zeugen gegen die Primalit¨at von n sind.

38

KAPITEL 2. RIVEST, SHAMIR UND ADLEMAN Daraus ergibt sich der folgende

Algorithmus 2.50 (Miller–Rabin–Test). Gegeben ist eine nat¨ urliche Zahl n ≥ 3. 1. W¨ahle zuf¨allig eine Zahl a, mit 2 ≤ a ≤ n − 1. 2. Schreibe n − 1 als n − 1 = 2s k schreiben, wobei k ∈ N ungerade und s ∈ N ist. 3. Berechne ak , a2k , . . . , a2

s−1 k

und u ufe (2.18) bzw. (2.19). ¨ berpr¨

4. Ist n zusammengesetzt, so findet man in Schritt 4. mit einer Wahrscheinlichkeit von mindestens 75% einen Zeugen gegen die Primalit¨at. 5. Wiederhole den Test mit einem neuen a. Nach t Tests, bei denen kein Zeuge gefunden wurde, ist die Wahrscheinlichkeit, dass n zusammengesetzt ist, h¨ochstens ( 14 )t .

Eine Zahl, die 10 Testrunden besteht ist mit einer Wahrscheinlichkeit von h¨ochstens ( 41 )10

= 9.5 · 10−7 zusammengesetzt. Nach 15 Runden ist die Wahrscheinlichkeit h¨ochstens

9.3 · 10−10 , nach 20 Runden 9.1 · 10−13 . Im Vergleich dazu ist die Wahrscheinlichkeit f¨ ur einen Lottosechser mit 1.2 · 10−7 schon ziemlich groß. Es sind also nicht sehr viele Runden notwen-

dig, um mit großer Sicherheit sagen zu k¨onnen, ob eine Zahl prim ist. Sobald mehr als

n−1 4

Basen durchprobiert sind, kann man sogar sicher sein, dass n prim ist. Praktisch ist das f u ¨r große n aber nicht m¨oglich. Man begn¨ ugt sich mit Zahlen, die sehr wahrscheinlich prim sind. Auch solche Primzahlen werden gelegentlich Pseudoprimzahlen genannt.

2.10.3

Erzeugung von starken Pseudoprimzahlen

F¨ ur das RSA-Verfahren reicht es nicht, zwei große Primzahlen p und q zu finden. Wie schon die Pollard–(p − 1)–Faktorisierungsmethode zeigt, m¨ ussen p − 1 und q − 1 große Primfaktoren ¨ enthalten. Ahnliche Methoden zeigen, dass selbst das noch nicht reicht. Pseudoprimzahlen, die wirklich sicher“ sind, nennen wir starke Pseudoprimzahlen. Eine starke Pseudoprimzahl ” p erf¨ ullt folgende Bedingungen: • p + 1 besitzt einen großen Primfaktor, • p − 1 besitzt einen großen Primfaktor r und • r − 1 besitzt einen großen Primfaktor. ¨ Uberraschend ist, dass starke Pseudoprimzahlen nicht schwieriger zu erzeugen sind als irgendwelche Primzahlen. Details erfahren Sie in [Gor85].

Kapitel 3

Diffie und Hellman In diesem Kapitel erarbeiten wir uns die Grundlagen f¨ ur eine zweites schwieriges mathematisches Problem, das Problem, diskrete Logarithmen zu berechnen.

3.1

Gruppen

Egal, in welchem K¨orper (R, Zp ) wir rechnen, die Rechenregeln, die wir von den reellen Zahlen her kennen, d¨ urfen wir immer verwenden. Wir gehen dem nach.

Definition 3.1. Eine Gruppe ist ein Quadrupel (G, ◦, −1 , 1), wobei G irgendeine Menge

ist, ◦ eine Funktion von G × G nach G,

−1

die folgenden Gesetze erf¨ ullt sind:

eine Funktion von G nach G und 1 ∈ G, und

1. F¨ ur alle a, b, c ∈ G gilt: (a ◦ b) ◦ c = a ◦ (b ◦ c). 2. F¨ ur jedes a ∈ G gilt: a ◦ a−1 = 1 = a−1 ◦ a. 3. F¨ ur jedes a ∈ G gilt: 1 ◦ a = a ◦ 1 = a.

Gilt außerdem a ◦ b = b ◦ a f¨ ur alle a, b ∈ G, so nennen wir die Gruppe abelsch. Wir werden

uns ausschließlich mit abelschen Gruppen besch¨aftigen. Wenn klar ist, was mit ◦, gemeint ist, schreiben wir statt

(G, ◦, −1

, 1) einfach G.

Beispiel 3.2. Wir kennen schon eine ganze Reihe von abelschen Gruppen. • (Z, +, −, 0) ist eine abelsche Gruppe. 39

−1

und 1

40

KAPITEL 3. DIFFIE UND HELLMAN

• (R, +, −, 0) ist eine abelsche Gruppe. • (Zn , +, −, [0]n ) ist eine abelsche Gruppe. • (R \ {0}, ·,−1 , 1) ist eine abelsche Gruppe. • (Zp \ {[0]p }, ·,−1 , [1]p ) ist eine abelsche Gruppe. • Es sei Z∗n = {[r]n ∈ Zn | ggT(r, n) = 1}. Dann ist (Z∗n , ·,−1 , [1]n ) eine abelsche Gruppe.

Auch nicht abelsche Gruppen kennen wir. • Es sei M die Menge aller invertierbaren 2 × 2-Matrizen. Dann ist ! 1 0 (M, ·,−1 , ) 0 1 eine nicht abelsche Gruppe.

Die Beispiele charakterisieren auch fast schon K¨orper, es fehlt nur noch eine Regel f¨ ur das Ausmultiplizieren.

Definition 3.3. Ein K¨orper ist ein Septupel (K, +, −, 0, ·, −1 , 1), wobei K irgendeine

Menge ist und die folgenden Gesetze erf¨ ullt sind: 1. (K, +, −, 0) ist eine abelsche Gruppe. 2. (K \ {0}, ·,−1 , 1) ist eine abelsche Gruppe.

3. f¨ ur alle a, b, c ∈ K gilt: (a + b) · c = (a · c) + (b · c)

Ein paar Begriffe aus der Gruppentheorie brauchen wir noch.

Definition 3.4. Besitzt eine Gruppe unendlich viele Elemente (wie z.B. (Z, +, −, 0)),

so nennen wir sie eine unendliche Gruppe. Andernfalls heißt die Gruppe endlich. Ist (G, ◦,−1 , 1) eine endliche Gruppe so bezeichnen wir mit |G| die Anzahl der Elemente der Gruppe und nennen |G| die Ordnung von G.

41

3.1. GRUPPEN

Ist g ein Element der Gruppe (G, ◦,−1 , 1), so schreiben wir g k statt g ◦ g ◦ · · · ◦ g . | {z } k mal

Die kleinste nat¨ urliche Zahl n, so dass g n = 1 nennen wir (sofern es so eine Zahl gibt) die Ordnung von g. Gibt es keine solche Zahl, so sagen wir, die Ordnung von g ist unendlich. Es sei (G, ◦,−1 , 1) eine Gruppe und U eine Teilmenge von G. Dann nennen wir (U, ◦, −1 , 1)

eine Untergruppe von (G, ◦,−1 , 1), falls 1. 1 ∈ U und 2. falls a, b ∈ U , dann auch a ◦ b−1

Untergruppen werden uns jetzt auf dem Weg zum Satz von Fermat begleiten.

Satz 3.5. Es sei U eine Untergruppe von G. Dann teilt die Ordnung von U die Ordnung von G.

Nehmen wir ein Element g aus einer Gruppe (G, ·, −1 , 1), und suchen wir die

kleinstm¨ogliche Untergruppe U von G, die g enth¨alt, dann beobachten wir folgendes: • U enth¨alt 1. • U enth¨alt g 2 , g 3 , g 4 , . . .. • U enth¨alt g −1 (warum?), g −2 , g −3 , . . .. • U enth¨alt keine weiteren Elemente.

Wir nennen diese Untergruppe U die von g erzeugte Untergruppe von G. Ist n die Ordnung von g, so sind die Elemente der von g erzeugten Untergruppe {g, g 2 , . . . , g n−1 = g −1 , g n = 1}. Die Ordnung der erzeugten Untergruppe ist also gleich der Ordnung ihres Erzeugers, und sie teilt die Ordnung der Gruppe, also

42

KAPITEL 3. DIFFIE UND HELLMAN

Satz 3.6. Ist (G, ·,−1 , 1) eine endliche Gruppe, so teilt die Ordnung jedes Elements der

Gruppe die Ordnung der Gruppe. Insbesondere gilt f¨ ur jedes g ∈ G: g |G| = 1

Es kann passieren, dass ein Element einer Gruppe die gesamte Gruppe erzeugt. In diesem Fall heißt die Gruppe zyklische Gruppe. Im folgenden Abschnitt u ¨ berlegen wir uns noch kurz, dass die multiplikative Gruppe eines endlichen K¨orpers zyklisch ist.

3.1.1

Primitivwurzeln

Definition 3.7. Es sei K ein K¨orper. Eine Primitivwurzel von K ist ein Element g von K, so dass sich jedes Element von K als Potenz von g schreiben l¨asst.

Es sei (K, +, −, 0, ·,−1 , 1) ein K¨orper. Die Gruppe K ∗ := (K \{0}, ·,−1 , 1) heißt multiplikative Gruppe des K¨orpers K. Eine Primitivwurzel ist also ein Element der multiplikativen Gruppe

eines K¨orpers, das den gesamten K¨orper (ohne die 0) erzeugt. Wir beweisen, dass es viele solcher Primitivwurzeln in endlichen K¨orpern gibt. Mit anderen Worten: Die multiplikative Gruppe eines endlichen K¨orpers ist zyklisch.

Lemma 3.8. Sei n ∈ N. Dann ist n=

X

ϕ(d)

0
Satz 3.9. Es sei K ein K¨orper mit q Elementen, also |K ∗ | = q−1. Es sei d ein positiver

Teiler von q − 1. Dann gibt es genau ϕ(d) Elemente der Ordnung d in K ∗ . Insbesondere gibt es also genau ϕ(q − 1) Primitivwurzeln in K.

43

3.2. POLYNOME

Gut, es gibt Primitivwurzeln, aber welche Elemente eines K¨orpers sind Primitivwurzeln? Die schlechte Nachricht ist: Keine Ahnung!“. Die gute Nachricht ist: Macht nix!“, denn ” ”

Satz 3.10. Falls n ≥ 5, so ist ϕ(n) ≥ n/(6 ln ln n).

W¨ahlt man also zuf¨allig ein Element eines K¨orpers mit n Elementen, so ist die Wahrscheinlichkeit, dabei eine Primitivwurzel zu erwischen

1 6 ln ln(n−1) .

Ist n eine Zahl mit 7.5 Millionen

Stellen, so ist diese Wahrscheinlichkeit noch immer ca. 1%, so dass man in diesem Fall im Schnitt etwa 100 mal probieren muss, um eine Primitivwurzel zu finden. Aber wie u uft ¨ berpr¨ man eigentlich, ob ein Element g eine Primitivwurzel ist?

Satz 3.11. Sei g ein Element der Gruppe (G, ◦, −1 , 1) und n ∈ N. Ist g n = 1 und ist n

g p 6= 1 f¨ ur jeden Primfaktor p von n, dann ist n die Ordnung von g.

Wenn man also die Primfaktoren von q − 1 kennt, l¨asst sich relativ schnell u ufen, ob ¨ berpr¨

man eine Primitivwurzel gefunden hat.

3.2

Polynome

Unter einem Polynom verstehen wir einen Ausdruck der Form a n xn + · · · + a1 x + a0 . Als

Koeffizienten kommen ganze, rationale und reelle Zahlen, aber auch Restklassen in Frage. Wir werden gleich genauer. Es sei K ein K¨orper. Die Menge aller Polynome u ¨ ber dem K¨orper K ist {an xn + · · · + a1 x + a0 | n ∈ N0 und ai ∈ K f¨ ur alle 0 ≤ i ≤ n} und wird mit K[x] bezeichnet. Mit Polynomen kann man rechnen wie mit ganzen Zahlen. Es gilt: (an xn + · · · + a1 x + a0 ) + (bm xm + · · · + b1 x + b0 ) = an xn + · · · + am+1 xm+1 +

+ (am + bm )xm + · · · + (a1 + b1 )x + (a0 + b0 )

44

KAPITEL 3. DIFFIE UND HELLMAN

und (an xn + · · · + a1 x + a0 ) · (bm xm + · · · + b1 x + b0 ) = cn+m xn+m + · · · + c1 x + c0 ,

wobei ck = a0 bk + a1 bk−1 + · · · + ak b0 .

Das war noch l¨angst nicht alles. Wir k¨onnen uns von den ganzen Zahlen noch viel mehr abschauen. Wie in Z kann man auch in K[x] mit Rest dividieren.

Definition 3.12. Der Grad des Polynoms a n xn + · · · + a1 x + a0 ∈ K[x] ist n, falls

an 6= 0. Der Grad des Polynoms 0 sei −∞. Der Koeffizient a n heißt f¨ uhrender Koeffizient des Polynoms. Ist der f¨ uhrende Koeffizient = 1, so heißt das Polynom normiert.

Satz 3.13. Sind f und g Polynome, dann ist Grad(f + g) ≤ max(Grad(f ), Grad(g)) Grad(f · g) = Grad(f ) + Grad(g)

Der n¨achste Satz erinnert schon stark an Z (vgl. Satz 2.1):

Satz 3.14 (Division mit Rest in K[x]). Es sei K ein K¨orper und f, g ∈ K[x]. Dann gibt es zwei eindeutig bestimmte Polynome q (Quotient) und r (Rest) u ¨ ber K, so dass f =g·q+r

und

Grad(r) < Grad(g)

Die Polynome q und r erh¨alt man durch Polynomdivision. Ein kurzes Beispiel frischt unsere Erinnerung auf:

45

3.2. POLYNOME

Beispiel 3.15. Wir w¨ahlen K = R, f = 2x3 − 4x2 + 1 und g = x − 1. 2x3 − 4x2

+ 1 : x − 1 = 2x2 − 2x − 2

−2x3 ∓ 2x2

− 2x2

∓ 2x2 ±2x −2x + 1 ∓2x ± 2 − 1 Rest

Also ist q = 2x2 − 2x − 2 und r = −1. Weiters ist Grad(r) = 0 und Grad(g) = 1, passt.

Ist r = 0, so sagen wir g teilt f (g | f ). Wie in Z gibt es auch wieder einen gr¨oßten gemeinsamen Teiler, denn

ur alle f, g ∈ K[x] gibt es genau ein normiertes Polynom d ∈ K[x] gr¨oßten Satz 3.16. F¨

Grades, das sowohl f als auch g teilt.

Wieder l¨asst sich der ggT als Linearkombination“ darstellen, d.h. ”

ur alle f, g ∈ K[x] gibt es Polynome s, t ∈ K[x], so dass Satz 3.17. F¨ ggT(f, g) = s · f + t · g

Ausrechnen l¨asst sich all das genau wie in Z. Ein Beispiel zur Illustration.

Beispiel 3.18 (Der erweiterte Euklidsche Algorithmus f u ¨ r Polynome). Was ist ggT(x3 + 2x2 + x + 2, 2x2 + x − 6)?

46

KAPITEL 3. DIFFIE UND HELLMAN

x3 + 2x2 + x + 2

2x2 + x − 6

x3 + 2x2 + x + 2

1

2x2 + x − 6

0

1

1

− 12 x

13 4 x

+

13 2

0

0

−

3 4

Nebenrechnungen: 9 1 x3 + 2x2 +x + 2 : 2x2 + x − 6 = x + 2 4 1 2 3 −x ± x ∓3x 2 3 2 x +4x + 2 2 3 3 9 − x2 ± x ∓ 2 4 2 13 13 x+ Rest 4 2 2x2 + x −6 :

13 13 8 12 x+ = x− 4 2 13 13

−2x2 ± 4x − 3x

−6

∓ 3x

∓6 0 Rest

Der ggT ist definiert als normiertes Polynom, wir m¨ ussen also

13 4 x

+

13 2

noch normieren,

das heißt dividieren durch den f¨ uhrenden Koeffizienten. Wir erhalten ggT(x3 + 2x2 + x + 2, 2x2 + x − 6) = (

13 13 4 x+ )· =x+2 4 2 13

Weiters l¨asst sich der ggT darstellen als 4 1 3 · [1 · (x3 + 2x2 + x + 2) + (− x − ) · (2x2 + x − 6)] 13 2 4 1 4 3 2 ·(x + 2x + x + 2) + = · (−2x − 3) ·(2x2 + x − 6) 13 13 |{z} {z } |

x+2 =

=s

=t

¨ 3.3. POLYNOME UBER ZP

3.3

47

Polynome u ¨ ber Zp

Alles, was wir mit Polynomen u ¨ ber R bisher angestellt haben, h¨atten wir genauso gut mit Polynomen u ¨ ber irgendeinem anderen K¨orper machen k¨onnen.

Beispiel 3.19. Wir w¨ahlen p = [2]3 x4 + [1]3 x3 + [0]3 x2 + [1]3 x + [2]3

und

q = [1]3 x4 + [0]3 x3 + [0]3 x2 + [1]3 x + [2]3 . Das ist umst¨andlich, wir schreiben lieber p = 2x4 + x3 + x + 2

und

q = x4 + x + 2 und merken uns, dass wir in Z3 [x] rechnen. Es ergibt sich (Achtung: die Koeffizienten sind aus Z 3 !) p + q = 3x4 + x3 + 2x + 4 = x3 + 2x + 1, p · q = 2x8 + x7 + x5 + 2x4 + 2x5 + x4 + x2 + 2x + 4x4 + 2x3 + 2x + 4 = 2x8 + x7 + x4 + 2x3 + x2 + x + 1

Wir berechnen noch schnell den ggT. 2x4 + x3 + x + 2

x4 + x + 2

1

0

+x+2

0

1

+ 2x + 1

1

1

x2 + 2

2x

2x4 + x3 + x + 2 x4 x3

1

1+

x2

1 + 2x 1 + 2x + x2

0 Also ist ggT(2x4 + x3 + x + 2, x4 + x + 2) = 1 und 1 = (1 + x2 ) · (2x4 + x3 + x + 2) + (1 + 2x + x2 ) · (x4 + x + 2)

48

KAPITEL 3. DIFFIE UND HELLMAN

3.4

Shared Keys

Inzwischen wissen wir genug, um uns mit dem folgenden Problem zu besch¨aftigen. An n Personen sind Schl¨ ussel zu verteilen, so dass jede Kombination von mindestens k Schl¨ usseln gemeinsam sperren, weniger als k Schl¨ ussel jedoch nicht. Im Informationszeitalter heißt das: an n Personen werden Zahlen e 1 , . . . , en verteilt. Jeder Kombination von k Personen ist es m¨oglich, daraus den geheimen Schl¨ ussel e zu berechnen, weniger als k Personen jedoch nicht. Praktisch sind solche Shared Keys notwendig, wenn Entscheidungen nicht von Einzelpersonen getroffen werden d¨ urfen, aber z.B. von beliebigen drei Personen gemeinsam. Wir sehen uns zwei Realisierungen eines Shared-Key-Systems an.

3.4.1

Interpolation

Man w¨ahlt eine große Primzahl p, die jedenfalls gr¨oßer als e und n ist und ein Polynom f = e + a1 x + a2 x2 + · · · + ak−1 xk−1 vom Grad k − 1 aus Zp [x]. Die Koeffizienten a1 , . . . , ak−1

k¨onnen zuf¨allig gew¨ahlt werden. Die Teilnehmer erhalten die Teilschl¨ ussel (1,e1 = f (1)) (2,e2 = f (2)) .. . (n,en = f (n))

usseln l¨asst sich e rekonstruieren, aus weniger Behauptung 3.20. Aus je k Teilschl¨ jedoch nicht.

Beweis: Es sind die Koeffizienten a1 , . . . , ak−1 und e unbekannt, das sind k Unbekannte. Aus jedem Teilschl¨ ussel (i, ei ) erh¨alt man eine Gleichung ei = f (i), also ei = e + a1 i + a2 i2 + · · · + ak−1 ik−1 . Insgesamt erhalten wir so ein lineares Gleichungssystem mit k Gleichungen und k Unbekannten, welches eindeutig l¨osbar ist. Fehlt auch nur ein Teilschl¨ ussel, so ist das Gleichungssystem nicht mehr eindeutig l¨osbar und es gibt dann zumindest p verschiedene L¨osungen. Ist p eine große Primzahl, so m¨ usste man sehr viele M¨oglichkeiten durchprobieren, das ist hoffnungslos. Das Polynom f l¨asst sich gl¨ ucklicherweise auch etwas einfacher aus den Teilschl¨ usseln berechnen, es hilft der

49

3.4. SHARED KEYS

Satz 3.21 (Lagrangesches Interpolationspolynom). Gegeben seien k

Punkte

(x1 , y1 ), . . . , (xk , yk ). Sind alle xi verschieden, so gibt es genau ein Polynom f vom Grad k − 1, f¨ ur welches gilt: f (x1 ) = y1 , . . . , f (xk ) = yk . Dieses Polynom lautet f = y1 · L1 (x) + y2 · L2 (x) + · · · + yk · Lk (x), wobei Li (x) =

(x − x1 )(x − x2 ) · · · (x − xi−1 )(x − xi+1 ) · · · (x − xk ) (xi − x1 )(xi − x2 ) · · · (xi − xi−1 )(xi − xi+1 ) · · · (xi − xk )

Ein Beispiel wird n¨otig.

Beispiel 3.22. n = 5, k = 3, e = 9. Wir w¨ahlen p = 17, f = 9 + x + 2x2 ∈ Z17 [x]. Es ergibt sich

e1 = f (1) = 9 + 1 + 2 = 12 e2 = f (2) = 9 + 2 + 8 = 2 e3 = f (3) = 13 e4 = f (4) = 11 e5 = f (5) = 13

Die Teilschl¨ ussel lauten (1, 12), (2, 2), (3, 13), (4, 11) und (5, 13). Sehen wir uns an, wie aus dem zweiten, dritten und f¨ unften Teilschl¨ ussel e rekonstruiert wird. (x − 3)(x − 5) = 6(x − 3)(x − 5) (2 − 3)(2 − 5) (x − 2)(x − 5) L3 (x) = = 8(x − 2)(x − 5) (3 − 2)(3 − 5) (x − 2)(x − 3) = 3(x − 2)(x − 3) L5 (x) = (5 − 2)(5 − 3) L2 (x) =

50

KAPITEL 3. DIFFIE UND HELLMAN

f = 2 · L2 (x) + 13 · L3 (x) + 13 · L5 (x) = 9 + x + 2x2

3.4.2

Chinesischer Restsatz

Man sucht paarweise relativ prime Zahlen r 1 , . . . , rn , so dass n. An die n Personen verteilt man dann die Schl¨ ussel

√ k e ≤ ri <

√ e f¨ ur alle 1 ≤ i ≤

k−1

(r1 , e1 = e mod p1 ) (r2 , e2 = e mod p2 ) .. . (rn , en = e mod pn ). Nun k¨onnen k Personen e mit Hilfe des chinesischen Restsatzes berechnen, denn Sie erhalten √ √ √ ein Ergebnis modulo r1 · r2 · · · rk ≥ k e · · · k e = ( k e)k = e, also das richtige Ergebnis. k − 1 √ √ √ Personen allerdings k¨onnen e nur modulo r1 · r2 · · · rk−1 < k−1 e · · · k−1 e = ( k−1 e)k−1 = e berechnen und k¨onnen daher keine eindeutige L¨osung finden.

Beispiel 3.23. Wir nehmen wieder n = 5 und k = 3. Diesmal sei e = 200. Wir suchen 5 √ √ paarweise relativ prime Zahlen zwischen 200 = 14.1 und 3 200 = 5.8. r1 = 7, r2 = 8, r3 = 9, r4 = 11, r5 = 13 Die Teilschl¨ ussel lauten (7, 200 mod 7) = (7, 4) (8, 200 mod 8) = (8, 0) (9, 200 mod 9) = (9, 2) (11, 200 mod 11) = (11, 2) (13, 200 mod 13) = (13, 5). Aus den Teilschl¨ usseln 2, 3 und 5 l¨asst sich e rekonstruieren, indem man das Restklassengleichungssystem e ≡8 0 e ≡9 2 e ≡13 5

3.5. FAKTORISIEREN IN ZP [X]

51

l¨ost. Man erh¨alt die L¨osung e = 200 modulo 8 · 9 · 13 = 936. Die zwei Personen mit dem

vierten und f¨ unften Teilschl¨ ussel k¨onnen die L¨osung nur modulo 11 · 13 = 143 bestimmen

und m¨ ussen dann raten.

3.5

Faktorisieren in Zp [x]

Wie in Z gibt es auch in K[x] Elemente, die sich in Produkte zerlegen lassen und andere, die dies nicht erlauben. Ein Polynom p ∈ K[x] heißt reduzibel, wenn es Polynome f und

g gibt, so dass p = f · g und die Grade der Polynome f und g sind kleiner als der Grad von p. Andernfalls nennen wir p irreduzibel. Die irreduziblen Polynome sind sozusagen die Primzahlen in K[x]. Wie in Z ist auch in K[x] eine eindeutige Primfaktorzerlegung (vgl. Satz 2.3) m¨oglich.

Satz 3.24. Jedes Polynom p ∈ K[x] l¨asst sich in der Form p = a · pe11 · pe22 · · · perr darstellen, wobei p1 , . . . , pr verschiedene normierte irreduzible Polynome vom Grad ≥ 1

sind und a der f¨ uhrende Koeffizient von p ist. Diese Darstellung ist bis auf die Reihenfolge eindeutig.

Endlich gibt es einen Unterschied zwischen Z und K[x] (allerdings nur f¨ ur die K¨orper Zp ): in Zp [x] kann man faktorisieren. Der folgende Algorithmus beschreibt, wie das funktioniert.

Algorithmus 3.25 (Berlekamp). Sei f ∈ Z p [x] vom Grad n. 1. Zun¨achst sucht man mehrfache Faktoren, indem man d = ggT(f, f 0 ) berechnet (wozu?). 2. Man berechnet die Reste von 1, xp , x2p , . . . , x(n−1)p bei Division durch f . Dann

52

KAPITEL 3. DIFFIE UND HELLMAN

schreibt man die Reste in der Form Rest von 1 = q0,0 + q0,1 x + · · · + q0,n−2 xn−2 + q0,n−1 xn−1

Rest von xp = q1,0 + q1,1 x + · · · + q1,n−2 xn−2 + q1,n−1 xn−1 .. . Rest von x(n−1)p = qn−1,0 + qn−1,1 x + · · · + qn−1,n−2 xn−2 + qn−1,n−1 xn−1 auf und bildet die n × n-Matrix 

q0,0 · · ·  . .. . Q= .  . qn−1,0 · · ·

 q0,n−1  ..  . 

qn−1,n−1

3. Die L¨osungsmenge des homogenen linearen Gleichungssystems (Q − E) · x = 0

(E ist die n × n-Einheitsmatrix)

ist ein Unterraum des (Zp )n der Dimension r. Man berechne eine Basis v 1 , . . . , vr des L¨osungsraums. Dann hat f r verschiedene irreduzible Faktoren. 4. Ist r = 1, so ist f irreduzibel. Sonst bildet man die Polynome hi = hvi , (1, x, x2 , . . . , xn−1 )T i Unter den ggT(f, hi + c), mit c ∈ Zp und 1 ≤ i ≤ r findet man alle Primfaktoren von

f.

Beispiel 3.26. Wir zerlegen f = x7 + x5 + x3 + x2 + x + 1 ∈ Z2 [x] in irreduzible Faktoren. 1. f 0 = x6 + x4 + x2 + 1 und d = ggT(f, f 0 ) = x2 + 1. Damit haben wir schon einen Teiler. Wir dividieren

f d

= x5 + x + 1 und erhalten f = (x2 + 1)(x5 + x + 1). Lassen

sich die beiden Faktoren weiter zerlegen? x2 +1 = (x+1)(x+1) = (x+1)2 , das war leicht, außerdem ist x+1 sicher irreduzibel. Mit f = x5 + x + 1 geht’s weiter.

3.5. FAKTORISIEREN IN ZP [X]

53

2. Wir berechnen die Reste Rest von 1 = 1 · 1+0 · x + 0 · x2 +0 · x3 + 0 · x4

Rest von x2 = 0 · 1+0 · x + 1 · x2 +0 · x3 + 0 · x4

Rest von x4 = 0 · 1+0 · x + 0 · x2 +0 · x3 + 1 · x4

Rest von x6 = 0 · 1+1 · x + 1 · x2 +0 · x3 + 0 · x4

Rest von x8 = 0 · 1+0 · x + 0 · x2 +1 · x3 + 1 · x4

Somit ergibt sich  1  0   Q = 0  0  0

 0   0 0 0     0 1 und Q − E = 0   0 0 0   0 1 1

0 0 0 0 0 1 0 0 1 1 0 0



0 0 0 0



 1 1 0 0   0 1 0 1  1 1 1 0  0 0 1 0

3. Wir l¨osen das lineare Gleichungssystem (Q−E)·x = 0 und erhalten die Basisvektoren     1 0     0 1         v1 = 0 und v2 = 1 .     0 0     0 1 Also gibt es zwei irreduzible Faktoren.

4. Wir berechnen h1 = hv1 , (1, x, x2 , . . . , xn−1 )T i = 1

und

h2 = hv2 , (1, x, x2 , . . . , xn−1 )T i = x + x2 + x4

Unter den ggT’s finden wir x3 +x2 +1 und durch Division den zweiten Faktor x 2 +x+1. Beide sind irreduzibel, denn f besitzt nur zwei irreduzible Faktoren. Wir erhalten also x7 + x5 + x3 + x2 + x + 1 = (x + 1)2 (x2 + x + 1)(x3 + x2 + 1).

Im Kapitel u ¨ ber Automaten werden wir wieder Polynome brauchen. Wir definieren schon jetzt:

54

KAPITEL 3. DIFFIE UND HELLMAN

Definition 3.27. Jedes irreduzible Polynom f vom Grad n in Z p [x] teilt das Polynom xp

n −1

− 1. Die kleinste positive ganze Zahl e, so dass f | x e − 1, heißt Exponent von f .

Der Exponent von f ist stets ein Teiler von p n − 1. Ist der Exponent gleich pn − 1, so heißt f maximalperiodisch.

Beispiel 3.28. In Z2 [x] sind die Polynome 1 + x + x2 , 1 + x3 + x4 und 1 + x + x2 + x4 + x5 maximalperiodisch. Das Polynom 1 + x + x 2 + x3 + x4 ist zwar irreduzibel, aber nicht maximalperiodisch.

3.6

Endliche Ko ¨rper

In diesem Abschnitt u ¨ berlegen wir, ob nicht auch die Sache mit den Restklassen in K[x] funktioniert. Wir nehmen uns dazu ein letztes Mal R[x] vor. Wir definieren (diesmal f¨ ur f, g, p ∈ K[x]): f ≡p g genau dann, wenn p | f − g

(3.1)

Wirklich stellt sich heraus, dass Satz 2.16 mutatis mutandis wieder gilt, d.h. auch hier ¨ darf wieder mit Restklassen gerechnet werden. Ahnlich wie bei Z schreiben wir f¨ ur die Menge der Restklassen modulo p jetzt K[x]/p. Bevor es weitergeht, sehen wir uns das einmal an.

Beispiel 3.29. Das Polynom p = x2 + 1 ist irreduzibel in R[x]. Wir rechnen in R[x]/(x 2 + 1). Addition [(4 + 3x)]p + [(3 − x)]p = [4 + 3x + 3 − x]p = [7 + 2x]p . Multiplikation [(4 + 3x)]p · [(3 − x)]p = [(4 + 3x)(3 − x)]p = [12 + 5x − 3x2 ]p . Hier passiert etwas, wir k¨onnen den Rest bei Division durch p berechnen. Also −3x2 + 5x+12 : x2 + 1 = −3 ∓3x2

∓3 5x

+15 Rest

Also ist [(4 + 3x)]p · [(3 − x)]p = [5x + 15]p .

¨ 3.6. ENDLICHE KORPER

Division

[4+3x]p [3−x]p

55

¨ =?. Auch keine Uberraschung, erweiterter Euklidscher Algorithmus wie

in Zp . x2 + 1 x2

3−x

+1

1

3−x

0

1

1

3+x

10

0

0 1 Gut, der ggT ist 1 und [3 − x]−1 p = [ 10 (3 + x)]p . Also ist 9 x)]p = . . . = [ 10 +

13 10 x]p .

[4+3x]p [3−x]p

1 (3 + = [(4 + 3x)]p · [ 10

Das Berechnen der Rest ist etwas m¨ uhsam, es geht auch bequemer, wie, das wissen wir schon l¨angst. Schaut man genauer hin, so bemerkt man, dass wir hier C, den K¨orper der komplexen Zahlen, konstruiert haben. Wir brauchen statt x lediglich i zu schreiben. Rechnet man modulo p, so ist x2 + 1 ≡p 0, oder mit i, i2 + 1 = 0 mod p, bzw. i2 = −1 mod p. Jetzt ist alles klar.

Man kann es auch so sehen: wir haben einen neuen K¨orper konstruiert, indem wir zu R einfach ein neues Element i hinzugef¨ ugt haben. Man schreibt daher auch oft R(i) f¨ ur diesen K¨orper und nennt R(i) Erweiterungsk¨orper von R. In R(i) ist p nicht mehr irreduzibel, denn nun ist x2 + 1 = (x + i)(x − i), also zerf¨allt p jetzt in Linearfaktoren, weswegen der K¨orper R(i) auch Zerf¨allungsk¨orper von p genannt wird.

So wie sich aus Z die K¨orper Zp konstruieren ließen, so l¨asst sich der K¨orper C aus R[x] konstruieren.

Man erh¨alt so wirklich immer K¨orper.

Satz 3.30. Ist K ein K¨orper und p ein irreduzibles Polynom in K[x], dann ist K[x]/p ein K¨orper.

Das Gleiche versuchen wir jetzt mit anderen K¨orpern K.

Beispiel 3.31. Diesmal versuchen wir K = Z 2 . Das Polynom p = x2 +x+1 ist irreduzibel in Z2 [x]. Wie vorher rechnen wir am bequemsten, indem wir eine fiktive L¨osung α der

56

KAPITEL 3. DIFFIE UND HELLMAN

Gleichung x2 + x + 1 = 0 zu Z2 hinzuf¨ ugen, wir erhalten den K¨orper Z2 (α) = Z2 [x]/(x2 + x + 1). Sehen wir uns diesen K¨orper an. Wir verzichten gleich auf die Schreibweise als Restklassen und verwenden α. Welche Elemente gibt es in Z2 (α)? 0, 1, α, α + 1 Das waren schon alle Elemente, Z2 (α) ist ein K¨orper mit 4 Elementen. H¨ohere Potenzen von α treten nicht auf, denn α ist eine L¨osung von x2 + x + 1 = 0, und daher ist α2 = α + 1 ¨ (man beachte vor allem die Ahnlichkeit zu C). In Z2 (α) rechnet man wie folgt: +

0

1

α

α+1

0

0

1

α

α+1

1

1

0

α+1

α

α

α+1

α+1

α+1

α

·

0

1

α

α+1

0

0

0

0

0

α

1

0

1

α

α+1

0

1

α

0

α

α+1

1

1

0

α+1

0

α+1

1

α

Ein drittes Beispiel Beispiel 3.32. In diesem Beispiel w¨ahlen wir K = Z5 und p = x3 + 3x + 2. Wir erhalten den K¨orper Z5 (α) = Z5 [x]/(x3 + 3x + 2). In diesem K¨orper gilt α3 = 2α + 3. Wie viele Elemente hat dieser K¨orper? Jetzt sind alle Elemente von der Form a + bα + cα2 , a, b, c ∈ Z5 , denn h¨ohere Potenzen von α werden wir wieder los. So ist α3 = 2α + 3 α4 = α · α3 = α(2α + 3) = = 2α2 + 3α

α5 = α2 · α3 = α2 (2α + 3) =

= 2α3 + 3α2 = 2(2α + 3) + 3α2 = = 3α2 + 4α + 6

usw. Diesmal ergeben sich 5 · 5 · 5 = 125 verschiedene Elemente. Auf die beschriebene Art kann man aus einem K¨orper Zp einen K¨orper Zp [x]/p basteln. Ist

3.7. DIFFIE-HELLMAN-KEY-EXCHANGE

57

p ein irreduzibles Polynom vom Grad n, so hat der K¨orper Zp [x]/p genau pn Elemente. Wir haben also K¨orper mit pn Elementen gefunden. Dazu brauchen wir aber irreduzible Polynome. Es dr¨angt sich die Frage auf, ob es in jedem Z p [x] irreduzible Polynome von jedem beliebigen Grad n gibt. Die u ¨ berraschende Antwort ist

Satz 3.33. Ja. F¨ ur jedes p ∈ P und jedes n ∈ N gibt es genau einen endlichen K¨orper

mit pn Elementen. Wir nennen diesen K¨orper GF(pn ), das Galoisfeld mit pn Elementen.

Das sind alle endlichen K¨orper.

3.7

Diffie-Hellman-Key-Exchange

F¨ ur public-key Systeme ist es erforderlich, sogenannte Trapdoor-Funktionen zu kennen. Von einer Trapdoor-Funktion t verlangt man dreierlei: • y = t(x) soll einfach berechnet werden k¨onnen • x = t−1 (y) soll nur sehr schwer berechnet werden k¨onnen • x = t−1 (y) soll einfach berechnet werden k¨onnen, wenn man noch einen (geheimen) Hinweis bekommt.

Beispiel 3.34. Im Fall des RSA-Verfahrens ist es einfach, c = m e mod n zu berechnen. √ Umgekehrt ist es sehr schwer, m = e c mod n zu bestimmen. Mit dem geheimen Hinweis n = p · q ist es dann wieder einfach, die e-te Wurzel zu ziehen. Das RSA-Verfahren verl¨asst

sich allerdings darauf, dass tats¨achlich ein geheimer Hinweis n = p · q erforderlich ist, dass

n also nicht einfach in Primfaktoren zerlegt werden kann.

Allerdings ist nicht bewiesen, dass das Faktorisierungsproblem wirklich schwierig ist, es hat einfach noch niemand geschafft. Daher ist es eine gute Idee, mehr als nur eine Art von Trapdoor-Funktionen zur Verf¨ ugung zu haben. Wir besch¨aftigen uns nun mit einer TrapdoorFunktion, die – soviel man weiß – nichts mit dem Faktorisierungsproblem zu tun hat. Die in weiterer Folge besprochenen Verfahren beruhen auf dem Diffie-Hellman-Problem bzw. auf dem diskreten Logarithmusproblem. Das diskrete Logarithmusproblem (DLP) lautet: Gegeben: eine Gruppe (G, ◦,−1 , 1) und g, A ∈ G

Gesucht: eine Zahl a, so dass A = g a , falls es so eine Zahl gibt.

58

KAPITEL 3. DIFFIE UND HELLMAN

Die Zahl a wird aus naheliegenden Gr¨ unden diskreter Logarithmus (DL) von A zur Basis g genannt. Ganz ¨ahnlich lautet das Diffie-Hellman-Problem (DHP): Gegeben: eine Gruppe (G, ◦,−1 , 1), g ∈ G und g a und g b , nicht aber a und b

Gesucht: g ab .

Ganz klar, wer das DLP l¨ost, kann auch das DHP l¨osen. Ob das umgekehrt auch so ist, weiß niemand. Die beiden Probleme gelten bislang – wie das Faktorisierungsproblem – als nicht l¨osbar (in sehr großen Gruppen). Ein Großteil der Verfahren in diesem Kapitel beruht auf dem DHP oder dem DLP. Als Gruppe werden wir (zumindest in diesem Kapitel) die multiplikative Gruppe eines endlichen K¨orpers verwenden also entweder (Zp \ {0}, ·,−1 , [1]p ) oder (GF(pn ) \ {0}, ·,−1 , 1).

Im Kapitel 6 werden wir schließlich auch andere Gruppen (elliptische Kurven) verwenden.

Wir tasten uns vorsichtig an die Materie heran. Das erste Verfahren, das auf dem DHP-Problem beruht, wurde von Diffie und Hellman vorgeschlagen, es handelt sich dabei um ein Schl¨ usselaustauschsystem. Mit so einem System k¨onnen sich zwei Personen auf einen gemeinsamen Schl¨ ussel einigen, der dann beispielsweise f¨ ur ein symmetrisches Verschl¨ usselungsverfahren verwendet werden kann.

Algorithmus 3.35 (Diffie-Hellman-Schl u ¨ sselaustausch nach [DH76]).

1. Alice und Bob einigen sich auf eine Primzahl p und auf eine Primitivwurzel g in Z ∗p . 2. Alice w¨ahlt zuf¨allig a ∈ Z∗p . Bob w¨ahlt zuf¨allig b ∈ Z∗p .

3. Alice schickt Bob A = g a mod p Bob schickt Alice B = g b mod p. 4. Alice berechnet K = B a mod p Bob berechnet K = Ab mod p. Beide haben die selbe Zahl K berechnet, denn B a = (g b )a = g ab und Ab = (g a )b = g ab . Eine Angreiferin Eve kennt p, g, g a und g b , nicht aber a und b. Um daraus g ab zu berechnen, muss sie das DHP l¨osen.

Remark 3.36. Den Diffie-Hellman-Schl¨ usselaustausch kann man nat¨ urlich mit jeder multi¨ plikativen Gruppe durchf¨ uhren, wir besch¨aftigen uns in den Ubungen damit.

3.7. DIFFIE-HELLMAN-KEY-EXCHANGE

59

Eine lauschende Angreiferin hat also praktisch keine Chance, den vereinbarten Schl u ¨ ssel K herauszubekommen. Eine aktive Angreiferin allerdings schon. Wir sehen uns eine (wo)man in the middle Attacke an. Hier ist es erforderlich, dass die Angreiferin Eve nicht nur die Kommunikation zwischen Alice und Bob abh¨oren kann, sie muss in der Lage sein, die Daten, die die beiden u ¨ bertragen, zu modifizieren.

Algorithmus 3.37 (Woman in the middle).

1. Eve w¨ahlt zuf¨allig e in Z∗p und berechnet E = g e mod p. 2. Eve empf¨angt A von Alice und schickt statt dessen E weiter an Bob. Eve empf¨angt B von Bob und schickt stattdessen E weiter an Alice. 3. Somit einigt sich Eve mit Alice auf den Schl¨ ussel KA = Ae = E a = g ae und mit Bob auf den Schl¨ ussel KB = B e = E b = g be . 4. Alice und Bob k¨onnen nicht erkennen, dass sie nicht direkt miteinander kommunizieren, und Eve liest mit und kann bei Bedarf die Nachrichten auch weiter modifizieren.

Um solche Angriffe zu verhindern muss das Schl¨ usselaustauschverfahren modifiziert werden. Wir sehen uns eine der nach Matsumoto, Takashima und Imai benannten Varianten an:

Algorithmus 3.38 (MTI/A0-Protokoll). Zun¨achst einigen Alice und Bob sich wieder auf eine Primzahl p und eine Primitivwurzel g in Z∗p . Bevor die beiden das Verfahren das erste Mal benutzen, erzeugen die beiden ihre statischen Schl¨ usselpaare: • Alice w¨ahlt zuf¨allig sA ∈ Z∗p und berechnet σA = g sA . • Bob w¨ahlt zuf¨allig sB ∈ Z∗p und berechnet σB = g sB . Die beiden tauschen σA und σB u ¨ ber einen sicheren Kanal aus, z.B. indem sie sich treffen. Das modifizierte Schl¨ usselaustauschverfahren sieht nun folgendermaßen aus: 1. Alice w¨ahlt zuf¨allig a ∈ Z∗p . Bob w¨ahlt zuf¨allig b ∈ Z∗p .

60

KAPITEL 3. DIFFIE UND HELLMAN 2. Alice schickt Bob A = g a mod p Bob schickt Alice B = g b mod p. 3. Alice berechnet K = B sA · (σB )a mod p. Bob berechnet K = AsB · (σA )b mod p.

Wieder erzeugen beide den selben Schl¨ ussel K (warum?). Diesmal hat Eve aber keine Chance, wenn die statischen Schl¨ ussel erst einmal sicher ausgetauscht sind.

3.8

DL- und DH-public-key Systeme

3.8.1

Das Massey-Omura-Kryptosystem

Die Teilnehmer einigen sich auf eine (¨offentlich bekannte) Gruppe (G, ◦,−1 , 1) (z.B. die multiplikative Gruppe eines endlichen K¨orpers GF(q) oder Zp ).

Alice w¨ahlt ein (geheimes) eA zuf¨allig, so dass 2 ≤ eA ≤ |G| und ggT(eA , |G|) = 1, und

berechnet dessen inverses Element d A = (eA )−1 mod |G|. Bob w¨ahlt analog eB und dB .

Will Alice Bob die Nachricht m an Bob schicken, so schickt sie ihm m eA (in G). Bob kann damit nichts anfangen, denn er kennt weder e A noch dA . Er schickt Alice (meA )eB zur¨ uck. Alice schickt Bob (((meA )eB ))dA . Bob entschl¨ usselt nun die Nachricht, indem er mit d B potenziert. Er erh¨alt ((((meA )eB )dA )dB = meA eB dA dB = meA dA eB dB = m1·1 = m (im Exponenten darf ja modulo |G| gerechnet werden). Dabei wurden die folgenden Nachrichten u ¨ bermittelt: meA ,

meA eB und meB . Da sowohl eA als auch eB geheim sind, lassen sich daraus weder m noch

eA oder eB berechnen. Um beispielsweise aus m eA und (meA )eB eB zu bestimmen, muss man das DL-Problem l¨osen. Selbst Bob ist es nicht m¨oglich, eA zu bestimmen auch er m¨ usste das DL-Problem l¨osen. Interessant ist, dass es in diesem Kryptosystem gar keine ¨offentlichen Schl¨ ussel gibt. Nat¨ urlich ist auch bei diesem System die Gefahr eines Man-in-the-middle-Angriffs gegeben. Es muss hier separat sichergestellt werden, dass sich die Benutzer gegenseitig authentifizieren.

3.8.2

Das ElGamal-Kryptosystem

Wieder wird eine Gruppe (G, ◦,−1 , 1) ausgemacht, weiters ein Element g mit großer Ordnung

in G (z.B. eine Primitivwurzel im endlichen K¨orper). Alice w¨ahlt eine Zahl a, so dass 2 ≤

a ≤ ord(g) − 1. Dies ist ihr private key. Als public key gibt Alice das Element A = g a (in G) bekannt.

3.9. BERECHNUNG DISKRETER LOGARITHMEN – DER INDEX CALCULUS ALGORITHMUS61 Will Bob Alice die Nachricht m u ¨ bermitteln, so w¨ahlt er zuf¨allig eine Zahl k und schickt Alice das Paar (B, c) = (g k , m ◦ Ak ). Will Alice die verschl¨ usselte Nachricht lesen, so berechnet sie x = B a und dessen inverses Element x−1 in G. Schließlich berechnet sie c ◦ x −1 . Das ist die Nachricht, denn c ◦ x−1 = m ◦ Ak ◦ (B a )−1 = m ◦ (g a )k ◦ ((g k )a )−1 = m ◦ g ak ◦ (g ak )−1 = m.

Wer das DHP l¨osen kann, kann aus dem ¨offentlich bekannten A = g a und dem B = g k aus

der verschl¨ usselten Nachricht g ak berechnen und damit wie Alice die Nachricht entschl¨ usseln. Eine bessere Methode ist nicht bekannt. Hier wird – anders als im Massey-Omura-Verfahren – stets der gleiche Schl¨ ussel verwendet. Hier sorgt das zuf¨allig gew¨ahlte k daf¨ ur, dass die selbe Nachricht jedes Mal anders verschl¨ usselt wird.

3.9

Berechnung diskreter Logarithmen – Der Index Calculus Algorithmus

Diskrete Logarithmen lassen sich in manchen Gruppen leichter berechnen als in anderen.

Beispiel 3.39. Diskrete Logarithmen in der Gruppe (Z n , +, −, 0) lassen sich sehr einfach berechnen. Das DLP lautet hier:

Gegeben seien g, A ∈ Zn . Gesucht ist ein a ∈ Z, so dass a · g = A.

Eine L¨osung findet man, indem man g −1 in Z∗n berechnet (warum existiert der Kehrwert?),

dann ist a = g −1 ·A. Wir haben also in Abschnitt 2.4 von Kapitel 2 das DLP in der Gruppe (Zn , +, −, 0) gel¨ost.

In den Gruppen (Z∗p , ·,−1 , 1) und (GF(q)∗ , ·,−1 , 1) ist das DLP wesentlich schwieriger, aber

auch hier gibt es M¨oglichkeiten, DL zu berechnen.

Wir sehen uns f¨ ur (Z∗p , ·,−1 , 1) eine Methode an, die sich zu Nutze macht, dass es in Z

eine eindeutige Primfaktorzerlegung gibt, den Index Calculus Algorithmus.

Es sei p ∈ P, g Primitivwurzel modulo p. Wir m¨ochten DLen zur Basis g modulo p

berechnen.

Zun¨achst w¨ahlen wir eine Zahl B und die dazugeh¨orige Faktorbasis F(B) = {p ∈ P | p ≤

B}. Eine Zahl z nennen wir B-glatt, falls alle Primfaktoren von z in F(B) liegen, also ≤ B sind.

Wir bestimmen nun die DLen aller Primzahlen in der Faktorbasis, also f¨ ur jedes q ∈ F(B)

ein xq mit q = g xq mod p.

62

KAPITEL 3. DIFFIE UND HELLMAN Um dann den DL von a zu berechnen, suchen wir einen Exponenten y, so dass a · g y

B-glatt ist. Dann ist

a · gy =

Y

q eq =

q∈F (B)

=g a = g(

q∈F (B)

P

g xq ·eq

q∈F (B)

q∈F (B) xq ·eq

Also ist der DL von a zur Basis g gleich (

Y

mod p,

xq ·eq )−y

q∈F (B)

mod p.

xq · eq ) − y (mod p − 1).

Zur¨ uck zur Bestimmung der DLen der Faktorbasiselemente. Dazu berechnet man g z f¨ ur viele Zahlen z und merkt sich diejenigen, die B-glatt sind. Hat man viele solche Zahlen gefunden, kann man die DLen der Faktorbasiselemente berechnen.

Beispiel 3.40. Wir demonstrieren die Methode f¨ ur p = 2027, g = 2 und B = 11. Nach langem Probieren finden wir z.B. z

gz

1593

33

983

385

1318

1408

293

63

1918

1600

in F(B) 3 · 11

5 · 7 · 11 27 · 11 32 · 7

2 6 · 52

Wir suchen Zahlen x2 , x3 , x5 , x7 , x11 , so dass 2 = 2x2 , 3 = 2x3 , 5 = 2x5 , 7 = 2x7 , 11 = 2x11

mod 2027

Also (wieder modulo 2027) 21593 = 3 · 11 = (2x3 ) · (2x11 ) = 2x3 +x11

2983 = 5 · 7 · 11 = (2x5 ) · (2x7 ) · (2x11 ) = 2x5 +x7 +x11

21318 = 27 · 11 = (2x2 )7 · (2x11 ) = 27x2 +x11 2293 = 32 · 7 = (2x3 )2 · (2x7 ) = 22x3 +x7

21918 = 26 · 52 = (2x2 )6 · (2x5 )2 = 26x2 +2x5

3.9. BERECHNUNG DISKRETER LOGARITHMEN – DER INDEX CALCULUS ALGORITHMUS63

Es ergibt sich ein lineares Gleichungssystem (modulo p − 1 = 2026) 1593 = x3 + x4 983 = x5 + x7 + x11 1318 = 7x2 + x11 293 = 2x3 + x7 1918 = 6x2 + 2x5 Da 2026 = 2·1013 keine Primzahl ist, l¨asst sich das Gleichungssystem nicht einfach modulo 2026 l¨osen (Z2026 ist kein K¨orper). Man kann das Gleichungssystem aber modulo 2 und modulo 1013 l¨osen (Z2 und Z1013 sind K¨orper). Die L¨osungen modulo 2 und 1013 lassen sich schließlich mit dem chinesischen Restsatz zu einer L¨osung modulo 2026 kombinieren. Sehen wir uns das an. Modulo 2 ergibt sich (x2 = 1 ist klar) x3 + x11 = 1 x5 + x7 + x11 = 1 x2 + x11 = 0 x7 = 1 x2 = 1 Wir l¨osen das Gleichungssystem und erhalten x2 = x5 = x7 = x11 = 1, x3 = 0

(mod 2).

Modulo 1013 ergibt sich x3 + x11 = 580 x5 + x7 + x11 = 983 7x2 + x11 = 305 2x3 + x7 = 293 6x2 + 2x5 = 905 x2 = 1 Wir l¨osen auch dieses Gleichungssystem und erhalten x2 = 1, x3 = 282, x5 = 956, x7 = 742, x11 = 298

(mod 1013).

64

KAPITEL 3. DIFFIE UND HELLMAN

Mit dem chinesischen Restsatz erhalten wir x2 = 1, x3 = 282, x5 = 1969, x7 = 1755, x11 = 1311

(mod 2026).

Nun k¨onnen wir beliebige DL berechnen. Um den DL von 13 zur Basis 2 zu berechnen suchen wir (durch Probieren) nach einer Zahl y, so dass 13 · 2 y B-glatt ist. Wir finden 13 · 21397 = 2 · 5 · 11

mod 2027

13 = 2(1+1969+1311)−1397 = 21884

Der DL von 13 zur Basis 2 modulo 2027 ist also 1884.

3.10

Andere public-key Systeme

Neben den public key Systemen, die auf dem DLP oder DHP beruhen, gibt es noch weitere. Im Folgenden beschreiben wir zwei Verfahren, die auf dem Knapsack-Problem beruhen.

3.10.1

Das Knapsack-Problem

Sie steigen auf einen Berg und k¨onnen h¨ochstens Ckg Gep¨ack in Ihren Rucksack packen. Sie haben Gep¨ackst¨ ucke mit v1 , . . . , vk kg. K¨onnen Sie damit – und wenn ja dann wie – mit einer Auswahl aus diesen Gep¨ackst¨ ucken auf genau Ckg kommen? Mathematisch ausgedr¨ uckt: Knapsack-Problem Gegeben seien v1 , . . . , vk ∈ N und C ∈ N. Gesucht sind Zahlen d1 , . . . , dk ∈ {0, 1}, so dass

C=

k X i=1

falls es solche Zahlen gibt.

di · v i ,

Dieses Problem ist im Allgemeinen sehr schwierig, man muss alle M¨oglichkeiten ausprobieren. Wenn die Gewichte vi allerdings besondere Eigenschaften besitzen, geht’s pl¨otzlich ganz leicht.

ur C w¨ahlen wir 24. Beispiel 3.41. Die Gewichte seien 2, 3, 7, 15 und 31. F¨ • 31 scheidet aus • 15 k¨onnte passen. Weil alle kleineren zusammen weniger als 15 ausmachen, m¨ ussen wir es sogar ausw¨ahlen, es bleiben 9kg

65

3.10. ANDERE PUBLIC-KEY SYSTEME

• 7 k¨onnte passen. Weil alle kleineren zusammen weniger als 7 ausmachen, m¨ ussen wir es ausw¨ahlen, es bleiben 2kg

• 3 ist zu viel und scheidet aus • 2 passt, und wir sind fertig: 24=2+7+15.

Ist jedes Gewicht gr¨oßer als die Summe aller kleineren Gewichte, so spricht man von einem superincreasing Knapsack-Problem. Wie das Beispiel zeigt, ist ein superincreasing Knapsack-Problem ganz leicht zu l¨osen. Auf dieser Beobachtung beruht das Merkle-HellmanKryptosystem.

3.10.2

Das Merkle-Hellman-Kryptosystem

Alice w¨ahlt v1 , . . . , vk ∈ Z superincreasing und eine Zahl m >

Pk

i=1 vi .

Weiters w¨ahlt sie eine

Zahl a relativ prim zu m. Nun berechnet sie w 1 = a·v1 mod m, w2 = a·v2 mod m, usw. Der ussel von Alice ist nun (w1 , w2 , . . . , wk ). Schließlich berechnet Alice b = a −1 ¨offentliche Schl¨ mod m. Ihr privater Schl¨ ussel ist (b, m, v1 , . . . , vk ). Will Bob die Bitfolge (d1 , . . . , dk ) verschl¨ usseln, so berechnet er C=

k X i=1

di · w i

und schickt C an Alice. Will man die Nachricht entschl¨ usseln, steht man vor einem Knapsack-Problem, durch das modulare Multiplizieren ist das Problem nicht mehr superincreasing.

Beispiel 3.42. Alice w¨ahlt (v1 , . . . , v5 ) = (2, 3, 7, 15, 31), m = 61 und a = 17. Sie berechnet b = 17−1 = 18 mod 61. Als public key ergibt sich w1 = 17 · 2 = 34

mod 61

w2 = 17 · 3 = 51

mod 61

w3 = 17 · 7 = 58

mod 61

w4 = 17 · 15 = 11

mod 61

w5 = 17 · 31 = 39

mod 61

Ihr o¨ffentlicher Schl¨ ussel ist (34, 51, 58, 11, 39).

66

KAPITEL 3. DIFFIE UND HELLMAN Alice berechnet C 0 = bC mod m und l¨ost das superincreasing Problem mit v 1 , . . . , vk und

C 0 . Sie erh¨alt die richtige L¨osung, denn C 0 = bC = b

k X

di wi = b

i=1

k X

di avi = ba

i=1

k X i=1

di vi =

k X

di vi

mod m

i=1

Beispiel 3.43 (Fortsetzung). Bob will 01101 senden. Er berechnet C = 0 · 34 + 1 · 51 + 1 · 58 + 0 · 11 + 1 · 39 = 148 Alice berechnet daraus C 0 = 18 · 148 = 41 mod 61. Sie l¨ost das superincreasing Problem 41 =

5 X

di vi

i=1

und erh¨alt die Nachricht 01101.

Im Jahr 1982 zeigte Shamir (lauter bekannte Namen!), wie man dieses System knacken kann. Das Knapsack-Problem, das ein Angreifer zu l¨osen hat, ist zwar nicht superincreasing, aber doch einfacher als ein allgemeines Knapsack-Problem, weil es mit einem superincreasing Problem verwandt“ ist. Das allgemeine Knapsack-Problem kann er nicht l¨osen. ” Die Shamir-Attacke l¨asst sich abwehren, indem man nicht nur einmal mit a modulo m multipliziert, sondern nacheinander mit a 1 modulo m1 , mit a2 modulo m2 , usw. Sonst bleibt das Verfahren aber gleich. Es ist jedoch wahrscheinlich, dass sich auch die Attacke entsprechend anpassen l¨asst. Daher ist das Merkle-Hellman-Verfahren zur Zeit nicht in Verwendung.

3.10.3

Das Chor-Rivest-Kryptosystem

Ein anderes Verfahren, das ebenfalls auf dem Knapsack-Problem beruht, ist bislang ungebrochen, daf¨ ur aber etwas aufw¨andig. Vorgeschlagen wurde es 1988 von Chor und Rivest. Es wird ein endlicher K¨orper GF(q) = Zp (α) (also ist q = pn f¨ ur ein passendes n) so gew¨ahlt, dass q − 1 nur kleine Primfaktoren besitzt.

Alice sucht eine Primitivwurzel g in GF(q) und w¨ahlt zuf¨allig eine ganze Zahl z. Weiters

w¨ahlt sie ein k ∈ N, so dass k < p und k < n. Dann berechnet sie die Zahlen b 0 , . . . , bk−1 , so dass f¨ ur alle j ∈ {0, . . . , k − 1} gilt α + j = g bj , also die DLen zur Basis g im K¨orper GF(q).

Wenn q − 1 nur kleine Primfaktoren besitzt, ist das mit etwas Aufwand m¨oglich, jedenfalls

muss sie das aber nur ein einziges Mal tun. Schließlich w¨ahlt sie eine zuf¨allige Permutation π der Zahlen 0, 1, . . . , k − 1.

Alice berechnet f¨ ur 0 ≤ j ≤ k − 1 die Zahlen vj = bπ(j) + z mod q − 1. Ihr public key ist

(v0 , . . . , vk−1 ).

67

3.10. ANDERE PUBLIC-KEY SYSTEME Will Bob die Bitfolge (d0 , d1 , . . . , dk−1 ) verschl¨ usseln, so berechnet er C=

k−1 X

dj vj

und

j=0

C0 =

k−1 X

dj

j=0

und schickt Alice C und C 0 . Bob muss hier also auch verraten, wie viele 1er in seiner Bitfolge vorkommen. Alice entschl¨ usselt, indem sie M = g C−zC

0

berechnet. Nun ist aber 0

g C−zC = g =

k−1 j=0

k−1 Y j=0

dj vj −z

k−1 j=0

g dj (vj −z) =

dj

k−1 Y j=0

=g

k−1 j=0 (dj vj −zdj )

g dj bπ(j) =

k−1 Y

=g

k−1 j=0

dj (vj −z)

(α + π(j))dj .

j=0

Alice braucht also nur M zu faktorisieren und kann d 0 , . . . , dk−1 ablesen.

68

KAPITEL 3. DIFFIE UND HELLMAN

Kapitel 4

ElGamal Bisher haben wir uns auf ein Ziel der Kryptographie konzentriert, privacy, Verschl u ¨ sselung. In diesem Kapitel sehen wir uns die anderen Einsatzgebiete der Kryptographie an.

4.1

Hashfunktionen

In diesem Abschnitt sei A eine Menge von Zeichen, genannt Alphabet. Oft ist A = {0, 1}, es

k¨onnte aber auch das Alphabet {A, . . . , Z, a, . . . , z} sein. Mit A ∗ bezeichnen wir die Menge

aller beliebig langen Folgen von Zeichen aus dem Alphabet A, die wir auch als W¨orter bezeichnen. Mit Am bezeichnen wir die Menge aller W¨orter, die aus genau m Zeichen bestehen.

Definition 4.1. Es sei A ein Alphabet und m > n ∈ N. Jede Funktion h : A ∗ → An heißt Hashfunktion. Jede Funktion h : A m → An heißt Kompressionsfunktion.

Beim Wort Kompression darf man dabei nicht an Datenkompression denken. Bei Anwendung einer Kompressionsfunktion geht Information verloren.

Definition 4.2. Es seien X und Y zwei beliebige Mengen. Eine Funktion h : X → Y

heißt Einwegfunktion, wenn es praktisch unm¨oglich“ ist, zu einem beliebigen y ∈ Y ein ” x ∈ X zu finden, so dass y = h(x).

Eine Kollision von h ist ein Paar (x1 , x2 ) von Elementen von X, so dass x1 6= x2 , aber h(x1 ) = h(x2 ). Hashfunktionen und Kompressionsfunktionen haben immer Kollisionen (warum?).

69

70

KAPITEL 4. ELGAMAL

Die Funktion h heißt stark kollisionsresistent, wenn es praktisch unm¨oglich ist, eine Kollision von h zu finden. Die Funktion h heißt schwach kollisionsresistent, wenn es praktisch unm¨oglich ist, eine Kollision (x1 , x2 ) von h mit vorgegebenem x1 zu finden.

Nat¨ urlich sind stark kollisionsresistente Funktionen auch schwach kollisionsresistent. Um gekehrt ist das nicht so. Stark kollisionsresistente Funktionen sind Einwegfunktionen.

4.1.1

Stark kollisionsresistente Kompressionsfunktionen

Im Folgenden sehen wir, dass es stark kollisionsresistente Kompressionsfunktionen und Hashfunktionen tats¨achlich gibt. Zun¨achst basteln wir eine Kompressionsfunktion, die so gebaut ist, dass, wer eine Kollision findet, auch diskrete Logarithmen berechnen kann. Sei p eine n-bit Primzahl, so dass auch q =

p−1 2

eine Primzahl ist.1 Weiters sei a eine

Primitivwurzel in Z∗p und b eine zuf¨allig gew¨ahlte Zahl zwischen 1 und p − 1. Dann ist h : {0, . . . , q − 1} × {0, . . . , q − 1} → {1, . . . , p − 1} (α, β) 7→ aα bβ

mod p

eine Kompressionsfunktion von {0, 1} 2n−4 nach {0, 1}n (warum?).

Beispiel 4.3. p = 83, q = 41, a = 13, b = 53. Hier ist n = 7, wir erhalten eine Kompressionsfunktion, die 10-bit-Zahlen in 6-bit-Zahlen komprimiert. Wir komprimieren 0110011010. Dazu wird die Bitfolge in zwei 5-bit-Zahlen zerlegt, n¨amlich in α = (01100)2 = 12 und β = (11010)2 = 26. Dann berechnen wir h(α, β) = 1312 ·5326 = 21 mod 83. Schließlich l¨asst sich 21 als 0010101 schreiben. Wir haben also 0110011010 zu 0010101 komprimiert.

Wer eine Kollision von h finden kann, kann auch diskrete Logarithmen in Z ∗p berechnen. Sei (x1 , x2 ) eine Kollision von h und x1 = (α1 , β1 ), x2 = (α2 , β2 ). Dann ist

1

a α 1 b β1 = a α 2 b β2

mod p bzw.

aα1 −α2 = bβ2 −β1

mod p

Die Primzahl q nennt man in diesem Fall Sophie Germain Primzahl.

71

4.1. HASHFUNKTIONEN

Da a eine Primitivwurzel ist, l¨asst sich b als b = ak schreiben. Wir zeigen nun, dass sich k mit Hilfe der Kollision berechnen l¨asst. aα1 −α2 = ak(β2 −β1 )

mod p

α1 − α2 = k(β2 − β1 )

mod ϕ(p) = p − 1 = 2q

Diese Gleichung hat eine L¨osung, falls d := ggT(β2 − β1 , p − 1) ein Teiler von (α1 − α2 ) ist. | {z } =2q

Es gibt dann genau d verschiedene L¨osungen.2

Da β1 und β2 kleiner als q sind, ist auch |β2 − β1 | < q. Daher kann d nur 1 oder 2 sein.

Ist d = 1, dann gibt es genau eine L¨osung modulo p − 1, diese ist der DL k. Ist d = 2,

dann gibt es 2 L¨osungen. Durch Ausprobieren der beiden L¨osungen findet man das richtige k.

Somit ist der DL gefunden. W¨ahlt man eine Primzahl p, so dass das DLP in Z ∗p schwierig ist, dann ist es zumindest ebenso schwierig, irgendeine Kollision von h zu finden. Remark 4.4. Praktisch finden diese Kompressionsfunktionen keine Verwendung, weil das Berechnen der Funktionswerte zu aufw¨andig w¨are.

4.1.2

Von Kompressionsfunktionen zu Hashfunktionen

Wir sehen uns jetzt eine Methode an, aus einer kollisionsresistenten Kompressionsfunktion eine kollisionsresistente Hashfunktion zu erzeugen. Sei g : {0, 1}m → {0, 1}n eine Kompressionsfunktion und r := m − n. Sei x ∈ {0, 1}∗ , also eine beliebig lange Bitfolge.

1. Zun¨achst werden vorne so viele Nullen angeh¨angt, dass die Bitl¨ange durch r teilbar ist. Dann werden hinten r Nullen angeh¨angt. 2. Jetzt wird die Bin¨ardarstellung der Bitl¨ange des urspr¨ unglichen x bestimmt und an diese hinten so viele Nullen angeh¨angt, dass ihre L¨ange durch r − 1 teilbar ist. An den

Anfang sowie an jeder r-ten folgenden Stelle wird eine 1 eingef¨ ugt. 3. Die zweite Bitfolge wird an die erste angeh¨angt.

4. Die erhaltene Bitfolge wird in t Bl¨ocke x1 , . . . , xt der L¨ange r zerlegt.

Beispiel 4.5. r = 4, x = 100101101. 2

Erinnern Sie sich an Beispiel 2.20?

72

KAPITEL 4. ELGAMAL

1. Die Bitl¨ange von x ist 9. Wir m¨ ussen vorne 3 Nullen anh¨angen und erhalten 000100101101. Hinten werden 4 Nullen angeh¨angt, das ergibt 0001001011010000. 2. Die Bin¨ardarstellung von 9 ist 1001. Ihre L¨ange ist 4, wir m¨ ussen 2 Nullen anh¨angen, damit die L¨ange durch r − 1 = 3 teilbar ist, also erhalten wir 100100. Nun wird an

der ersten und an jeder vierten folgenden Stelle eine 1 eingef¨ ugt, wir erhalten 11001100. 3. Die beiden Bitfolgen werden aneinander geh¨angt. Wir erhalten 000100101101000011001100. 4. Wir erhalten 6 Bl¨ocke der L¨ange 4, n¨amlich 0001 0010 1101 0000 1100 1100.

Der Hashwert wird nun iterativ berechnet: H0 := 00 . . . 0 (L¨ange n) Hi := g(Hi−1 ◦ xi ),

1 ≤ i ≤ t,

wobei mit Hi−1 ◦ xi gemeint ist, dass die beiden Bitfolgen aneinander geh¨angt werden. Der Hashwert h(x) ist dann Ht .

Von der so konstruierten Hashfunktion kann man zeigen (siehe [Buc99]), dass sie stark kollisionsresistent ist, falls g es ist. Damit haben wir eine stark kollisionsresistente Hashfunktion konstruiert. Praktisch begn¨ ugt man sich mit Funktionen, deren Kollisionsresistenz nur empirisch gesichert ist, die daf¨ ur aber viel schneller sind. Wichtige Beispiele sind MDx, RIPEMD-x und SHA-1. Ausf¨ uhrliche Beschreibungen finden Sie z.B. in [MvOV97] und [Sch96].

4.2

Digitale Signaturen

Alice will bei Bob’s Buchversand per email B¨ ucher bestellen. Sie signiert ihre email digital. So eine Signatur soll drei wichtige W¨ unsche von Bob bzw. Alice erf¨ ullen. 1. Bob soll sich davon u ucher bestellt hat, und ¨ berzeugen k¨onnen, dass wirklich Alice die B¨ nicht irgendjemand anderer Alice einen Streich spielt.

4.2. DIGITALE SIGNATUREN

73

2. Alice will sicher sein, dass ihre email auf dem Weg zu Bob nicht ge¨andert werden kann. 3. Bob will sich auf die email berufen k¨onnen, wenn Alice pl¨otzlich behauptet, sie h¨atte gar nichts bestellt. Die digitalen Signaturen, die wir uns ansehen, erf¨ ullen alle diese W¨ unsche.

4.2.1

RSA-Signaturen

Mit einem RSA-Schl¨ usselpaar l¨asst sich ein Signaturverfahren ganz einfach konstruieren. Alice besitzt einen privaten RSA-Schl¨ ussel (n = p · q, d). Will Alice die Nachricht m

signieren, so sendet sie m und zus¨atzlich s = md mod n. Nun kann Bob (und jeder andere, der Alice’s ¨offentlichen Schl¨ ussel (n, e) besitzt) die Unterschrift u ufen, indem er se mod n ¨ berpr¨ berechnet und das Ergebnis mit m vergleicht. Hat wirklich Alice unterschrieben, dann ist se = (md )e = mde = m mod n. Wer den privaten Schl¨ ussel (n, d) nicht kennt, ist jedoch nicht in der Lage, s zu berechnen. Praktisch wird nicht die Nachricht m signiert, sondern nur ein Hashwert der Nachricht, also s = h(m)e mod n und der Empf¨anger vergleicht sd mod n mit h(m). Die verwendete Hashfunktion kann ¨offentlich vereinbart werden. Wie digitale Signaturen auszusehen haben, ist genau geregelt. In [MvOV97] finden Sie eine genaue Erl¨auterung. Um eine Signatur zu f¨alschen, k¨onnte Eve eine Unterschrift von Alice verwenden, z.B. die Unterschrift zur Nachricht m. Dann w¨are s = h(m)d mod n. Eve kennt d nicht, sie kann aber mit dieser Signatur als Alice alle Nachrichten unterschreiben, deren Hashwert der gleiche ist, wie der der Nachricht m. Sie kann also versuchen, eine Nachricht m 0 zu finden, so dass h(m0 ) = h(m). Wenn h aber auch nur schwach kollisionsresistent ist, wird es Eve nicht einmal gelingen, eine sinnlose Nachricht m 0 mit dem selben Hashwert zu finden. Eve k¨onnte auch irgendeine Signatur s nehmen und sehen, ob sie eine Nachricht findet, so dass h(m) = s e mod n (denn dann w¨are s = h(m)d mod n). Das ist aber, wie man sieht, auch nicht einfacher.

4.2.2

ElGamal Signaturen

Diese Signaturvariante ist – wie der Name schon vermuten l¨asst – verwandt mit dem ElGamalVerschl¨ usselungsverfahren. Man nimmt an, dass es n¨otig ist, ein DLP zu l¨osen, um ElGamalSignaturen zu f¨alschen, bewiesen ist allerdings nichts. Zun¨achst wird eine kollisionsresistente Hashfunktion h ¨offentlich vereinbart. Nun w¨ahlt Alice eine große Primzahl p und eine Primitivwurzel g in Z ∗p , weiters eine zuf¨allige Zahl a, so dass 2 ≤ a ≤ p − 1. Sie berechnet A = g a mod p und ver¨offentlicht ihren public-key (p, g, A).

Die Zahl a h¨alt sie geheim.

74

KAPITEL 4. ELGAMAL Um zu signieren, w¨ahlt Alice zuf¨allig eine Zahl k, so dass 2 ≤ k ≤ p−1 und ggT(k, p−1) =

1. Dann berechnet sie die Signatur (r, s) der Nachricht m als r = gk

s = k −1 (h(m) − ar)

mod p,

mod p − 1

Will Bob die Signatur u ufen, so pr¨ uft er: ¨ berpr¨ 1. Ist 1 ≤ r ≤ p − 1? 2. Ist Ar · r s = g h(m) mod p? Attacken auf ElGamal Signaturen Eine g¨ ultige Unterschrift besteht beide Tests, denn Ar · r s = g ar · g ks = g ar+kk

−1 (h(m)−ar)

= g h(m)

mod p

Der scheinbar u ussige Test, ob 1 ≤ r ≤ p − 1 ist, ist ¨außerst wichtig, denn macht man ¨ berfl¨

diesen Test nicht, dann ist es Eve m¨oglich, eine beliebige Nachricht m 0 f¨ ur Alice zu signieren, wenn sie nur eine einzige signierte Nachricht m von Alice kennt. Das geht so: Sei (r, s) Alice’s Signatur der Nachricht m. Angenommen h(m) ist relativ prim zu p − 1.

Dann sei

u := h(m0 ) · h(m)−1

s0 := su mod p − 1

mod p − 1

Weiters berechnet Eve mit Hilfe des chinesischen Restsatzes modulo p · (p − 1) eine Zahl r 0 ,

welche die Gleichungen

r 0 = ru r0 = r

mod p − 1 mod p

und

erf¨ ullt.

Nun ist (r 0 , s0 ) eine g¨ ultige Alice-Signatur von m0 , denn s = k −1 (h(m) − ar)

mod p − 1,

also ist

h(m) = ar + ks

mod p − 1.

Somit ist

r0

A ·r

0 0s

0

= Aru · r su = g aru · g ksu = g u(ar+ks) = g u·h(m) = g h(m ) .

Den einfachen ersten Test besteht die gef¨alschte Signatur jedoch nicht, denn r 0 ≥ p: r0 = r

mod p

r 0 = ru 6= r

mod p − 1,

75

4.3. ZERO-KNOWLEDGE-PROTOKOLLE

denn u 6= 1 mod p − 1 (außer man f¨ande eine Kollision von h). Also ist r 0 6= r, und daher muss r 0 ≥ p sein.

Es ist nicht ratsam, sich Arbeit zu sparen, indem man jedes Mal das selbe k verwendet,

denn werden zwei Nachrichten m1 und m2 mit dem selben k-Wert signiert, so l¨asst sich unter Umst¨anden aus den beiden Signaturen (r, s 1 ) und (r, s2 ) das geheime a berechnen: Es ist s1 − s2 = k −1 (h(m1 ) − ar) − k −1 (h(m2 ) − ar) = k −1 (h(m1 ) − ar − h(m2 ) + ar) = k −1 (h(m1 ) − h(m2 ))

mod p − 1

Falls s1 − s2 und p − 1 relativ prim sind, l¨asst sich s1 − s2 modulo p − 1 invertieren und man

erh¨alt

k = (s1 − s2 )−1 (h(m1 ) − h(m2 ))

mod p − 1.

Andernfalls hat die Gleichung genau ggT(s 1 − s2 , p − 1) verschiedene L¨osungen. Wenn dieser

ggT nicht allzu groß ist, kann man alle L¨osungen durchprobieren. Kennt man k, so l¨asst sich a berechnen aus s1 = k −1 (h(m1 ) − ar) ks1 = h(m1 ) − ar ar = h(m1 ) − ks1

mod p − 1

mod p − 1 mod p − 1.

Falls r relativ prim zu p − 1 ist, so l¨asst sich a daraus direkt berechnen, ist ggT(r, p − 1) > 1,

so gibt es wieder mehrere L¨osungen, und man kann probieren.

Die in der Praxis am meisten benutzte Variante des ElGamal-Signaturverfahrens ist der Digital Signature Algorithm (DSA), lesen Sie in [MvOV97] nach.

4.3

Zero-Knowledge-Protokolle

Nichts wissen“ klingt erst einmal sehr gut, aber zu fr¨ uh gefreut, eigentlich sollte es nichts ” ” verraten“ heißen. Jetzt aber von vorn. Alice weiß etwas, was Bob nicht weiß. Sie m¨ochte ihn davon u ¨ berzeugen, dass sie es weiß, sie m¨ochte es ihm aber nicht verraten. Ein Zero-Knowledge-Protokoll ist ein Weg, das zu erreichen. Wir starten mit einem anschaulichen

76

KAPITEL 4. ELGAMAL

Beispiel 4.6 (Landkarten bemalen). Es ist bei jeder Landkarte m¨oglich, mit vier Farben die L¨ander so zu bemalen, dass benachbarte L¨ander niemals die gleiche Farbe haben. Mit drei Farben geht das nur manchmal und selbst dann ist es ein sehr schwieriges Problem. Alice hat es geschafft, und m¨ochte es Bob beweisen, sie m¨ochte ihm aber nicht verraten, wie sie es gemacht hat, schließlich hat sie sich lange damit herumgeplagt. Die beiden bauen einen Apparat. Es handelt sich um eine riesige Landkarte. In jedem Land sind 3 L¨ampchen montiert, ein rotes, ein gr¨ unes und ein blaues. Alice kann in jedem Land entsprechend ihrer Bemalung einstellen, welches L¨ampchen leuchten soll. Wenn Bob mit dem Finger auf eine Grenze der Landkarte tippt, so gehen in den angrenzenden L¨andern die L¨ampchen an, und er kann sich davon u ¨ berzeugen, dass die Farben verschieden sind. Nachdem er auf eine Grenze getippt hat, dr¨ uckt Alice schnell auf einen Knopf, der folgende Umstellungen ausl¨ost: die Farben werden zuf¨allig durchmischt, es wird z.B. rot zu blau, blau zu gr¨ un und gr¨ un zu rot (die Farben k¨onnen aber auch zuf¨allig unver¨andert bleiben), die Farben ¨andern sich aber in jedem Land gleich. Im n¨achsten Durchgang wird nun anstelle des roten ein blaues L¨ampchen leuchten, und anstelle eines blauen ein gr¨ unes, wo auch immer Bob hintippt. Nun ist Bob wieder dran, er untersucht die n¨achste (oder noch einmal die selbe) Grenze, danach verstellt Alice wieder die Farben. Das geht so lange bis Bob davon u ¨ berzeugt ist, dass Alice die Karte richtig bemalt hat. Bob erf¨ahrt dabei aber nicht, wie Alice die Karte bemalt hat.

Jetzt wird’s etwas praktischer. Wir sehen uns ein Zero-Knowledge-Protokoll f u ¨ r das Wissen um den diskreten Logarithmus eines Elements einer Gruppe. Es sei (G, ·,−1 , 1) eine Gruppe großer Ordnung, b ein fixes Element großer Ordnung der

Gruppe und y ein beliebiges Element der Gruppe. Alice will Bob davon u ¨ berzeugen, dass sie den diskreten Logarithmus von y zur Basis b kennt, also jenes x, so dass y = b x . 1. Alice w¨ahlt zuf¨allig eine Zahl e und schickt Bob B = b e . 2. Bob wirft eine M¨ unze. (a) Bei Kopf muss Alice e bekannt geben und Bob u uft, ob B = be ist. ¨ berpr¨ (b) Bei Zahl muss Alice x + e bekannt geben und Bob u uft, ob y · B = bx+e ist. ¨ berpr¨ 3. Die Schritte (1) und (2) werden wiederholt, bis Bob u ¨ berzeugt ist.

77

4.4. OBLIVIOUS TRANSFER CHANNELS Wenn Alice x nicht kennt, dann kann sie zweierlei tun.

• Sie setzt auf Kopf, w¨ahlt ein e und schickt B = be . F¨allt Kopf, kann sie einfach e schicken, und Bob ist zufrieden. F¨allt aber Zahl, so muss sie x + e schicken und das

kann sie nicht, wenn sie x nicht kennt. • Sie setzt auf Zahl, w¨ahlt ein e, schickt aber B = be · y −1 . F¨allt Zahl, dann schickt sie e (statt x + e) und Bob u uft y · B = bx+e und ist zufrieden. F¨allt aber Kopf, steckt ¨ berpr¨ sie in der Klemme.

In jeder Testrunde hat also Alice eine Chance von 50%, Bob zu betr¨ ugen, wenn sie den diskreten Logarithmus nicht kennt. Nach n Runden ist die Wahrscheinlichkeit, als L u ¨ gner alle Runden zu u ¨ berstehen, nur mehr ( 12 )n . Umgekehrt erf¨ahrt Bob nichts u ¨ ber den diskreten Logarithmus x, weil er entweder e oder x + e aber nicht e erf¨ahrt.

4.4

Oblivious transfer channels

Interaktive Beweise sind m¨ uhsam, weil immer auf die Antwort des anderen gewartet werden muss. Um aus den interaktiven Protokollen nicht-interaktive zu machen, bedient man sich eines oblivious transfer channels.

Definition 4.7. Ein oblivious transfer channel von Alice zu Bob ist ein System, mit dem Alice Bob zwei (verschl¨ usselte) Pakete schicken kann, so dass die folgenden Forderungen erf¨ ullt sind: 1. Bob kann genau eines der beiden Pakete entschl¨ usseln und lesen. 2. Alice weiß nicht, welches der beiden Pakete das ist. 3. Beide k¨onnen sicher sein, dass (1) und (2) erf¨ ullt sind.

Wir studieren einen oblivious transfer channel, der auf dem DHP beruht. Zun¨achst wird ein endlicher K¨orper GF(q) vereinbart, in dem das DHP schwierig zu l¨osen ist, weiters eine Primitivwurzel b von GF(q) und ein Element C des K¨orpers, dessen DL zur Basis b nicht bekannt ist. Schließlich braucht man eine Funktion ψ : GF(q) → {0, 1} n . 1. Bob w¨ahlt ein x, so dass 0 < x < q − 1, und ein i ∈ {1, 2}. Er berechnet βi = b x ,

β3−i = C · b−x

78

KAPITEL 4. ELGAMAL Er gibt Alice seinen public-key (β1 , β2 ), hingegen h¨alt er x und i geheim. Bob kennt x, den DL von βi zur Basis b. W¨ urde er auch den DL x0 von β3−i zur Basis b 0

0

kennen, so w¨ usste er, dass bx+x = bx · bx = βi · β3 − i = bx · C · b−x = C. Also w¨ urde er den DL von C zur Basis b kennen. Da dieser nicht bekannt ist, kann Bob auch x 0 nicht kennen. 2. Alice hat zwei Pakete m1 und m2 . Nehmen wir an, beide Pakete sind Bitfolgen der L¨ange n. Sie w¨ahlt zuf¨allig 0 < y1 , y2 < q − 1 und schickt Bob (a) ε1 = by1 (b) ε2 = by2

(c) α1 = ψ(β1y1 ) ⊕ m1

(d) α2 = ψ(β2y2 ) ⊕ m2

(dabei steht ⊕ f¨ ur bitweises XOR). 3. Bob berechnet ψ(εxi ) ⊕ αi . Bob erh¨alt im letzten Schritt tats¨achlich mi , denn ψ(εxi ) ⊕ αi = ψ((byi )x ) ⊕ ψ(βiyi ) ⊕ mi

= ψ((bx )yi ) ⊕ ψ(βiyi ) ⊕ mi = ψ(βiyi ) ⊕ ψ(βiyi ) ⊕ mi = mi

Bob kann aber m3−i nicht entschl¨ usseln. Dazu m¨ usste er y

0

3−i β3−i = (C · b−x )y3−i = (bx )y3−i = (by3−i )x

0

0

berechnen k¨onnen. Er kennt aber nur bx = β3−i und by3−i = ε3−i , steht also vor einem DHP. Alice kennt i nicht, weiß also nicht, welches Paket Bob lesen kann. Sie kann sich aber davon u ¨ berzeugen, dass er nicht beide Pakete lesen kann. Sie berechnet β 1 · β2 . Hat Bob

seinen o¨ffentlichen Schl¨ ussel nicht ver¨andert, so ergibt sich β1 · β2 = bx · C · b−x = C. K¨onnte Bob den DL von β1 und von β2 berechnen, so auch den von C, das geht aber nicht.

Kapitel 5

Moore, Mealy und Vernam 5.1

Das Vernam One Time Pad

Definition 5.1. Eine Strom-Chiffre verschl¨ usselt eine Bitfolge Bit f¨ ur Bit (im Gegensatz zu Block-Chiffren).

Das Vernam One Time Pad ist eine symmetrische Strom-Chiffre. Der Schl¨ ussel ist eine zuf¨allige Bitfolge (ki ). Die Bitfolge (mi ) wird verschl¨ usselt, indem man Bit f¨ ur Bit, das Nachrichtenbit mit dem entsprechenden Schl¨ usselbit XOR-verkn¨ upft, also ci = m i ⊕ k i . Um die verschl¨ usselte Folge (ci ) wieder zu entschl¨ usseln, berechnet man (wie beim Verschl¨ usseln) Mi = c i ⊕ k i . So einfach dieses Verfahren ist, so sicher ist es. Es handelt sich um eines der wenigen absolut sicheren Verschl¨ usselungsverfahren. Wer den Schl¨ ussel nicht kennt, hat u ¨ berhaupt keinen Hinweis auf den Klartext. Jede Bitfolge ist ein potentieller Klartext. Nat¨ urlich ist dieses Verfahren f¨ ur Known-plaintext-Attacken anf¨allig; wer den Nachrichtentext kennt, kann den Schl¨ ussel berechnen. Es muss also stets ein neuer Schl¨ ussel verwendet werden. Dieser Schl¨ ussel muss sicher ausgetauscht werden, und er ist mindestens so lang wie die Nachricht, die verschl¨ usselt werden soll. F¨ ur die absolute Sicherheit zahlt man hier also mit riesigem Aufwand zum Schl¨ usselaustausch. Um diesen Aufwand zu reduzieren, l¨asst man sich die zuf¨allige Schl¨ usselbitfolge von einem PRNG erzeugen. Man braucht dann bloß die Parameter f¨ ur den PRNG austauschen. Alice und Bob k¨onnen dann beide mit ihren PRNGs die selbe zuf¨allige Schl¨ usselbitfolge erzeugen. 79

80

KAPITEL 5. MOORE, MEALY UND VERNAM Der BBS-PRNG ist, wie wir gesehen haben, rechnerisch sehr aufwendig. Wir entwickeln

in diesem Kapitel einen kleinen Teil der Theorie der Automaten, und verwenden diese, um schnelle PRNGs zu bauen“. ”

5.2

Automaten

Ein Automat ist ein Quintupel (I, O, Z, δ, λ), bestehend aus einer Inputmenge I, einer

Outputmenge O, einer Zustandsmenge Z, einer Zustands¨ uberf¨ uhrungsfunktion δ : Z × I →

Z, und einer Outputfunktion λ : Z × I → O.

Die Mengen und Funktionen sind dabei wie folgt zu interpretieren:

• I ist die Menge aller m¨oglichen Inputs in den Automaten. • Auf jeden Input reagiert der Automat mit einem Output. O ist die Menge aller m¨oglichen Outputs des Automaten.

• Der Output des Automaten h¨angt nicht nur vom Input ab, sondern auch vom Zustand,

in dem sich Automat gerade befindet. Z ist die Menge aller m¨oglichen Zust¨ande des Automaten.

• Befindet sich der Automat im Zustand z ∈ Z so reagiert er auf den Input i ∈ I mit dem Output λ(z, i) ∈ O

• und wechselt in den Zustand δ(z, i) ∈ Z. H¨angt der Output eines Automaten nur vom Zustand, aber nicht vom Input ab, so heißt der Automat auch Moore-Automat. Die Funktionen δ und λ k¨onnen neben dem Zustand und dem Input auch vom Zufall abh¨angen. Man spricht in diesem Fall von einem nichtdeterministischen Automaten, andernfalls von einem deterministischen Automaten. Ein Automat (I, O, Z, δ, λ) heißt endlich oder Mealy-Automat, falls I, O und Z endliche Mengen sind.

Verzichtet man auf die Outputmenge O und die Outputfunktion λ, so spricht man von einem Halbautomaten. Gern gibt man bei einem (Halb-)Automaten einen Anfangszustand z 0 ∈ Z an.

Einfache Automaten mit nicht allzu großen Input- und Zustandsmengen lassen sich sehr sch¨on grafisch veranschaulichen. Dazu zeichnet man f¨ ur jeden Zustand einen kleinen Kreis. Wechselt der Automat beim Input i vom Zustand z in den Zustand z 0 und gibt dabei den Output o aus, so zeichnet man einen Pfeil vom Kreis z zum Kreis z 0 , den man mit i/o beschriftet. Beim Betrachten des n¨achsten Beispiels wird alles klar.

81

5.2. AUTOMATEN

Beispiel 5.2. Als erstes Beispiel betrachten wir eine einfache Mausefalle. Die Mausefalle kann sich zwei Zust¨anden befinden, gespannt“ (G) oder nicht gespannt“ (N). M¨ogliche ” ” Inputs sind Maus tappt in die Falle“ (1) und Maus tappt nicht in die Falle“ (0). ” ” ¨ Ublicherweise hat eine Mausefalle keinen Output, es handelt sich also um einen Halbautomaten. Eine bessere Version der Mausefalle hat als Output 1, wenn soeben eine Maus gefangen wurde und sonst 0. Abbildung 5.1 stellt diesen Automaten dar.

1 0

1 1 G

N

0 0 0 0

Abbildung 5.1: Die einfache Mausefalle

Beispiel 5.3. Sieht man sich eine Mausefalle genauer an, kann man vier Zust¨ande unterscheiden, je nachdem, ob Speck in der Falle ist oder nicht. Nun ergeben sich die Zust¨ande SG: Speck ist in der Falle, die Falle ist gespannt SN: Speck ist in der Falle, die Falle ist nicht gespannt LG: Die Falle ist leer und gespannt LN: Die Falle ist leer und nicht gespannt Abbildung 5.2 zeigt diesen etwas komplizierteren Automaten.

Um Automaten studieren zu k¨onnen, interessiert man sich daf¨ ur, was der Automat macht, wenn man ihm eine Serie von Inputs schickt. Unter einer Folge von Inputs verstehen wir eine Folge i = i1 i2 . . . in , wobei ij ∈ I f¨ ur 1 ≤ j ≤ n. Wir lassen als Inputfolge auch die leere“ ” ∗ Folge i = Λ (kein Input) zu. Mit I bezeichnen wir die Menge aller Inputfolgen. 1 1

Inputfolgen sind also die W¨ orter u ¨ ber dem Alphabet I, so klein ist die Welt der Mathematik.

82

KAPITEL 5. MOORE, MEALY UND VERNAM

0 0

LG

1 1

0 0

SG

0 0

LN

1 1 1 0

0 0

SN

0 0

Abbildung 5.2: Die Mausefalle mit Speck Wir erweitern die Zustands¨ uberf¨ uhrungsfunktion δ zu einer Funktion δ ∗ : Z × I ∗ → Z.

F¨ ur z ∈ Z, i1 , . . . , in ∈ I definieren wir:

δ ∗ (z, Λ) = z δ ∗ (z, i1 ) = δ(z, i1 ) δ ∗ (z, i1 . . . in ) = δ(δ ∗ (z, i1 . . . in−1 ), in ) Die Folge hz, δ ∗ (z, i1 ), δ ∗ (z, i1 i2 ), . . . , δ ∗ (z, i1 . . . in )i nennen wir die Zustandstrajektorie

von z unter der Inputfolge i1 . . . in .

Auf die gleiche Weise l¨asst sich die Outputfunktion λ zu einer Funktion λ ∗ : Z × I ∗ → O

erweitern.

λ∗ (z, Λ) = Λ λ∗ (z, i1 ) = λ(z, i1 ) λ∗ (z, i1 . . . in ) = λ(δ ∗ (z, i1 . . . in−1 ), in )

5.2.1

Angewandte Automaten

Eine klassische Anwendung von Automaten ist die Verwendung als Akzeptoren. Ein Akzeptor ist ein Automat mit zwei m¨oglichen Outputs, akzeptiert“ (A) und nicht akzeptiert“ (N). ” ” Ist der Output A, so hat der Automat, die Inputfolge akzeptiert, sonst ist der Output N.

83

5.3. LINEAR FEEDBACK SHIFT REGISTERS

Ein Akzeptor kann z.B. pr¨ ufen, ob ein Ausdruck syntaktisch korrekt ist. Wir sehen uns als Beispiel einen Automaten an, der pr¨ uft, ob der eingegebene Ausdruck richtig geklammert ist.

Beispiel 5.4. Wir w¨ahlen Z = Z ∪ {π}, I ist der ASCII-Zeichensatz und O = {A, N }.

Als Anfangszustand w¨ahlen wir z0 = 0. Dann definieren wir δ : Z×I →Z   π        z+1   (z, i) 7→ z − 1      π     z

λ: Z×I →Z  A (z, i) 7→ N

, falls z = π , falls z ∈ Z und i =( , falls z ∈ Z und z > 0und i =) , falls z ≤ 0 und i =) , falls i 6∈ {), (}

, falls δ(z, i) = 0 , falls δ(z, i) 6= 0

Akzeptoren sind sozusagen ganz einfache Programme zur Syntaxanalyse. In Netzwerken werden Sie eingesetzt, um die Datenintegrit¨at zu u ufen. Bei hardwarenahen Protokollen ¨ berpr¨ k¨onnen diese Automaten einfach gebaut oder in kleine Prozessoren gebrannt werden. Wir wenden uns der kryptologischen Anwendung von Automaten zu.

5.3

Linear feedback shift registers

Eine spezielle Art von Automaten sind Schieberegister (Linear feedback shift registers, LFSRs).

Definition 5.5. Ein LFSR ist ein Automat (I, O, Z, δ, λ), bei dem I = {1}, O = Z 2

und Z ein Vektorraum u ¨ ber dem K¨orper Z2 ist. Die Funktionen δ und λ h¨angen dann nicht mehr vom Input ab (LFSRs sind also Moore-Automaten). Sie sind von der Form λ((z1 , . . . , zn )T ) = z1

und

δ(z) = A · z,

84

KAPITEL 5. MOORE, MEALY UND VERNAM

wobei A eine sogenannte Begleitmatrix ist. Das ist eine Matrix von der Gestalt 



0

1

0

0

...

0

0

 0  0   A= 0  .. .   0

0

1

0

...

0

0

0

1

...

0

0 .. .

0 .. .

0 .. .

... .. .

0 .. .

0

0

0

...

0

 0  0   0  ..  .   1 an

1 a 2 a3 a4 . . .

an−1

wobei a2 , . . . , an ∈ Z2 .

Der Name LFSR erkl¨art sich von selbst, wenn man sich ansieht, was die Zustands¨ uberf¨ uhrungsfunktion aus dem Zustand z = (z 1 , . . . , zn )T macht.       0 1 0 0 ... 0 0 z2 z1       0 0 1 0 . . .  0 0   z2   z3       0 0 0 1 . . .      0 0   z3   z4         0 0 0 0 . . .      z5 0 0  ·  z4  =     .. ..  .. .. .. . . .. ..   ..   . .      . . . . . .  .           zn 0 1  zn−1   0 0 0 0 . . .  z1 + a 2 z2 + a 3 z3 + . . . + a n zn zn 1 a2 a3 a4 . . . an−1 an

Bei jedem Input wird der Zustandsvektor (eine Bitfolge) um eine Position verschoben, das Bit, das dabei hinausf¨allt, ist der Output. An der letzten Stelle wird ein linearer Feedback nachgeschoben. Ist A ein LFSR mit Begleitmatrix A, dann heißt das Polynom x n +a2 xn−1 +. . .+an x+1 ∈

Z2 [x] Verbindungspolynom (connection polynomial). Ein LFSR ist durch sein Verbindungs-

polynom eindeutig bestimmt. Vereinbart man zus¨atzlich einen Anfangszustand z0 ∈ Z, so sind alle Outputs des LFSR schon bestimmt. Die Dimension des Vektorraums Z nennt man

auch die L¨ange des LFSRs.

Beispiel 5.6. Betrachten wir das LFSR mit dem Verbindungspolynom x 5 + x2 + 1. Das LFSR hat die L¨ange 5. Eine bequeme Art, ein LFSR zu zeichnen, wird in Abbildung 5.3 dargestellt. Wir vereinbaren als Anfangszustand z 0 = (1, 0, 0, 1, 1) ∈ Z52 . Das LFSR erzeugt

dann die Outputfolge

1001101001000010101110 . . .

5.3. LINEAR FEEDBACK SHIFT REGISTERS

85

+

z1

z2

z3

z4

z5

Abbildung 5.3: Das LFSR x5 + x2 + 1. Die Outputfolgen (oi ) (i ∈ N), die ein LFSR erzeugt sind periodisch, d.h. es gibt eine

kleinste Zahl L, die Periode, so dass stets o i+L = oi . Ein LFSR der L¨ange n kann maximal 2n −

1 verschiedene Zust¨ande annehmen. Daher ist die Periode eines LFSR der L¨ange n maximal 2n − 1. Ist die Periode gleich der maximal m¨oglichen, so heißt das LFSR maximalperiodisch. Wir erinnern uns an Kapitel 3. Tats¨achlich gilt

Satz 5.7. Ein LFSR ist genau dann maximalperiodisch, wenn sein Verbindungspolynom maximalperiodisch ist.

Wir k¨onnen also aus Polynomen vom Grad n Bitfolgen mit der Periode 2 n − 1 erzeugen.

Leider kann man aber mit Hilfe des Berlekamp-Massey-Algorithmus 2 aus 2n Bits der Bitfolge

das Verbindungspolynom berechnen. Sobald man also 2n Bits des Schl¨ ussels kennt, kennt man den gesamten Schl¨ ussel. Um LFSRs als kryptographische Zufallszahlengeneratoren verwenden zu k¨onnen, verschaltet man nun einfach mehrere LFSRs mit relativ primen Perioden. Beispiel 5.8. Ein Beispiel, wie es praktisch verwendet wird ist das folgende. Wir w¨ahlen 5 LFSRs R1 , . . . , R5 . Nun sei Ri (j) der j-te Output des LFSR Ri . Wir definieren die Funktion  x , falls s = 0 f (x, y, s) = y , falls s = 1

Nun verwenden wir als j-ten Output

O(j) = f (R1 (j), R2 (j), f (R3 (j), R4 (j), R5 (j))) ⊕ f (R4 (j), R3 (j), R5 (j)). Die so erzeugte Bitfolge besitzt eine sehr lange Periode und der Berlekamp-MasseyAlgorithmus ist nicht mehr direkt anwendbar. Daf¨ ur muss man sich auf 5 Verbindungspolynome einigen. 2

ein.

Dieser Algorithmus ist in [MvOV97] im Kapitel 6 ausf¨ uhrlich beschrieben. Wir gehen nicht n¨ aher darauf

86

KAPITEL 5. MOORE, MEALY UND VERNAM Stromchiffren aus LFSRs bieten in der Regel nicht die Sicherheit, die andere Systeme

bieten k¨onnen. Es ist daf¨ ur aber sehr einfach, sie hardwarem¨aßig zu implementieren und sie sind ungeheuer schnell. Daher sind sie besonders f¨ ur Anwendungen geeignet, in denen Geschwindigkeit besonders wichtig ist und die verschl¨ usselten Daten schnell ihre Wichtigkeit ¨ verlieren, so dass es keinen Sinn mehr macht, die Daten eine Stunde nach der Ubertragung zu entschl¨ usseln.

Kapitel 6

Koblitz und Miller In beinahe 30 Jahren RSA und DH haben sich das Faktorisierungsproblem und das DLP/DHP wie in den Jahrhunderten davor nicht vollst¨andig l¨osen lassen. Allerdings werden immer mehr und bessere Methoden entwickelt, so dass es immer schwieriger wird, sichere Parameter f u ¨r diese Verfahren zu finden.

Beispiel 6.1. F¨ ur das RSA-Verfahren hat man zur Zeit wenigstens 1024 Bit lange starke Primzahlen zu w¨ahlen. Gl¨ ucklicherweise geht das, weil auch das Finden (und Testen) von Primzahlen immer einfacher wird. Es bleibt jedoch das Problem, dass mit immer gr¨oßeren Zahlen gerechnet werden muss, und das halbwegs schnell.

ur DLP-verwandte Verfahren, bei denen als Gruppe Z ∗p verwendet wird, Beispiel 6.2. F¨ muss p ebenfalls wenigstens 1024 Bit lang sein. Auch hier muss man mit sehr großen Zahlen potenzieren, viel Aufwand.

Das gr¨oßte Problem dabei ist, dass die Gruppen Z ∗p und GF(q)∗ sehr gut erforscht sind und viel Struktur aufweisen. Das DLP l¨asst sich aber, wie wir gesehen haben, f¨ ur jede Gruppe formulieren. Wir studieren in diesem Kapitel eine ganz andere Art von Gruppen, elliptische Kurven. 87

88

KAPITEL 6. KOBLITZ UND MILLER

6.1

Elliptische Kurven u ¨ ber R

Definition 6.3. Es sei x3 + ax + b ∈ R[x] ein Polynom, so dass 4a3 + 27b2 6= 0. Mit O bezeichnen wir einen ausgezeichneten Punkt im Unendlichen“. Dann ist ” E = {(x, y) ∈ R2 | y 2 = x3 + ax + b} ∪ {O} eine elliptische Kurve (EC) u ¨ ber R.

Der Einfachheit halber schreiben wir statt der EC nur die Gleichung. Abbildung 6.1 zeigt die Graphen verschiedener elliptischer Kurven u ¨ ber dem K¨orper R. Aus E l¨asst sich eine Gruppe machen. Das sehen wir uns jetzt an. Beispiel 6.4. Wir w¨ahlen E : y 2 = x3 − 36x. Die Punkte P = (−3, 9) und Q = (−2, 8) sind Punkte auf E, wovon man sich durch Einsetzen in die Gleichung schnell u ¨ berzeugt. Wir legen durch P und Q eine Gerade

g : y = kx + d Die Steigung k l¨asst sich schnell berechnen als k=

8−9 = −1. −2 − (−3)

Setzt man nun P in g ein, so erh¨alt man d = y − kx = 9 − (−1)(−3) = 6 Die Geradengleichung lautet also g : y = −x + 6 Wir schneiden g mit E: (−x + 6)2 = x3 − 36x

x2 − 12x + 36 = x3 − 36x

x3 − x2 − 24x − 36 = 0

Die entstehende Gleichung dritten Grades k¨onnen wir leicht l¨osen, weil wir zwei L¨osungen schon kennen (P und Q sind Schnittpunkte): x 1 = −3 und x2 = −2.

¨ 6.1. ELLIPTISCHE KURVEN UBER R

-4

-3

-2

89

4

4

2

2

-1

1

2

3

-4

-3

-3

-2

-1

1

-2

-2

-4

-4

y 2 = x3 + x − 1

-4

-2

4

2

2

1

2

3

-4

-3

-2

-1

1

-2

-2

-4

-4

y 2 = x3 − x + 2

3

2

3

y 2 = x3 + x + 2

4

-1

2

y 2 = x3 − 3x

Abbildung 6.1: Elliptische Kurven u ¨ ber R

90

KAPITEL 6. KOBLITZ UND MILLER 4

P*Q

2

Q

-2

P -1

1

2

3

-2

P+Q

-4

Abbildung 6.2: Addition der Punkte P und Q Wir dividieren x3 − x2 − 24x − 36 durch (x − x1 )(x − x2 ) = x2 + 5x + 6 und erhalten x − 6. Also ist x3 = 6.

Auch der dritte Schnittpunkt liegt auf g, also ist y = −x + 6 = 0 Aus den zwei Punkten P und Q erhalten wir so einen dritten Punkt P ∗ Q = (6, 0).

Beispiel 6.5. Wir w¨ahlen E : y 2 = x3 + 1 und den Punkt P = (2, 3) auf E. Wir legen in P die Tangente an E. Diese ist von der Form t : y = kx + d Die Steigung der Tangente in P ist gerade die Steigung von E in P . Diese l¨asst sich mit

implizitem Differenzieren berechnen:

2y y˙ 0 = 3x2 y0 =

3x2 2y

y 0 (x = 2, y = 3) = 2

¨ 6.1. ELLIPTISCHE KURVEN UBER R

91

Also ist k = 2. Wir setzen P in t ein und erhalten d = y − kx = 3 − 2 · 2 = −1. Wir schneiden t mit E (2x − 1)2 = x3 + 1

4x2 − 4x + 1 = x3 + 1

x3 − 4x2 + 4x = 0

Auch von dieser Gleichung dritten Grades kennen wir zwei L¨osungen, denn die xKoordinate von P als Ber¨ uhrpunkt ist zweifache L¨osung der Gleichung. Wir k¨onnen also ohne Rest durch (x − 2)(x − 2) = x2 − 4x + 4 dividieren und erhalten x. Die dritte L¨osung ist also x3 = 0.

Die y-Koordinate ergibt sich durch Einsetzen in t. Wir erhalten y = 2x − 1 = −1 Aus einem Punkt P auf E erhalten wir einen Punkt P ∗ P = (0, −1) auf der EC.

4

P

2

P+P

-2

-1

1

2

3

P*P

-2

-4

Abbildung 6.3: Verdopplung von P

92

KAPITEL 6. KOBLITZ UND MILLER

Remark 6.6. Man rechnet leicht nach, dass eine EC das Assoziativgesetz (P ∗ Q) ∗ R = P ∗ (Q ∗ R) nicht erf¨ ullt, dass sich so also keine Gruppe aus einer EC machen l¨asst.

Definition 6.7. Es sei E eine EC. Wir definieren: 1. −O = O und f¨ ur jedes P ∈ E sei P + O = O + P = P . (Damit wird O zum neutralen Element.)

2. Ist P = (x, y), dann sei −P = (x, −y). 3. Ist Q = −P , dann sei P + Q = O. 4. P + P = 2P = −(P ∗ P ), wobei P ∗ P der andere Schnittpunkt der Tangente an E in P ist. (siehe Abb. 6.3)

5. Ist P 6= ±Q, dann sei P + Q = −(P ∗ Q), wobei P ∗ Q der dritte Schnittpunkt der Geraden durch P und Q mit E ist. (siehe Abb. 6.2)

Damit wird aus einer EC eine Gruppe.

Satz 6.8. Ist E eine EC, dann ist (E, +, −, O) eine abelsche Gruppe.

Der Beweis, dass jetzt das Assoziativgesetz gilt, ist alles andere als einfach, und viel zu lang f¨ ur uns. Wir begn¨ ugen uns mit einem Blick auf Abbildung 6.4. F¨ ur die Addition von Punkten auf EC lassen sich einfache Formeln angeben, die wir gleich herleiten werden.

Lemma 6.9. Sind x1 , x2 , x3 Nullstellen des Polynoms x3 + Ax2 + Bx + C, dann gilt x1 + x2 + x3 = −A x1 · x2 · x3 = −C.

und

¨ 6.1. ELLIPTISCHE KURVEN UBER R

93 Q*R 7.5

5

2.5 P+Q+R P

-4

P*Q

Q

-2

2

4

P+Q R

P*HQ+RL=HP+QL*R -2.5

-5

-7.5

Q+R

Abbildung 6.4: Die Addition von Punkten auf EC ist assoziativ

Definition 6.10. Es sei K ein K¨orper mit Einselement 1.1 Die kleinste positive ganze Zahl k, f¨ ur die gilt k · 1 = 1| + 1 +{z. . . + 1} = 0, k mal

nennen wir Charakteristik von K (char(K)). Falls es keine solche Zahl gibt, dann definieren wir char(K) = 0.

Satz 6.11. Es sei K ein K¨orper mit char(K) 6= 2, 3. Weiters sei E : y 2 = x3 + ax + b eine EC und P = (x1 , y1 ) und Q = (x2 , y2 ) zwei Punkte auf E. Dann lassen sich die

Koordinaten (x3 , y3 ) von R = P + Q nach folgenden Formeln berechnen. • Falls P = −Q, dann ist R = O.

94

KAPITEL 6. KOBLITZ UND MILLER

• Falls P 6= Q, dann ist  y2 − y 1 2 − x1 − x2 x3 = x2 − x 1   y2 − y 1 y3 = −y1 + (x1 − x3 ) x2 − x 1 

(6.1)

• Falls P = Q, dann ist 2 3x21 + a − 2x1 2y1   2 3x1 + a (x1 − x3 ) y3 = −y1 + 2y1

x3 =

6.2



(6.2)

Elliptische Kurven u ¨ ber GF(q)

Wir haben die Additionsformeln gleich f¨ ur EC u ¨ ber (fast) beliebigen K¨orpern hergeleitet. Wir sehen uns jetzt EC u ¨ ber endlichen K¨orpern an.

6.2.1

Quadratwurzeln in endlichen K¨ orpern

Um einen Punkt auf einer EC u ¨ ber dem K¨orper GF(q) mit gegebener x-Koordinate zu berechnen, setzt man f¨ ur x ein und berechnet dann y, indem man die Quadratwurzel zieht. Wir u ur die K¨orper Zp , wie man Quadratwurzeln zieht. ¨ berlegen uns zumindest f¨ Es sei p ∈ P. Um zu bestimmen, ob [a]p ein Quadrat in Zp ist, ob man also die Quadrat-

wurzel daraus ziehen kann (wir werden das noch brauchen), bedient man sich des sogenannten Legendre-Symbols. Wir definieren:  0      a = 1  p   −1

falls a ≡ 0 mod p falls a ein Quadrat modulo p ist sonst

Das hilft noch nicht weiter, aber es gilt

ur a, b ∈ Z und p, q ∈ P \ {2} gilt Satz 6.12. F¨   • p1 = 1,

¨ 6.2. ELLIPTISCHE KURVEN UBER GF(Q)

• • • •

  a p

=

  ab p

  2 p

  q p



=

a mod p p



95

,

    a b p · p ,

= (−1)(p

2 −1)/8

,

= (−1)(p−1)(q−1)/4 ·

  p q

.

Damit l¨asst sich schnell entscheiden, ob man aus einer Zahl modulo p die Quadratwurzel ziehen kann. Der folgende nette Algorithmus zum Ziehen von Quadratwurzeln modulo p ist von Shanks. Alles was man dazu braucht ist eine Zahl n, die nicht Quadrat modulo p ist.

Algorithmus 6.13 (Shanks). Es sei a ein Quadrat modulo p. Es ist die Quadratwurzel aus a zu ziehen. 1. Stelle p − 1 als 2α · s dar, wobei s ungerade ist. 2. Berechne b = ns mod p. 3. Berechne r = a(s+1)/2 mod p. 4. Berechne (r 2 /a)2

α−2

mod p. Das Ergebnis ist ±1. Ist das Ergebnis 1, dann setze

j0 = 0, sonst setze j0 = 1.

5. Wiederhole die folgenden Schritte f¨ ur k von 1 bis α − 2: (a) Es sei e die Zahl mit der Bin¨ardarstellung (jk−1 jk−2 . . . j1 j0 )2 . (b) Berechne ((be r)2 /a)2

α−k−2

mod p. Das Ergebnis ist ±1. Ist das Ergebnis 1, dann

setze jk = 0, sonst setze jk = 1.

6. Es sei e die Zahl mit der Bin¨ardarstellung (jk jk−1 . . . j1 j0 )2 . Dann ist be r eine Quadratwurzel von a modulo p.

6.2.2

Der Satz von Hasse

Wie viele Punkte liegen auf einer EC u ¨ ber einem endlichen K¨orper?

96

KAPITEL 6. KOBLITZ UND MILLER In GF(q) gibt es q verschiedene x-Koordinaten. Setzt man eine x-Koordinate in die Glei-

chung der EC ein, und zieht die Quadratwurzel, so erh¨alt man zwei y-Koordinaten, oder keine. Es gilt

Lemma 6.14. Ist GF(q) ein K¨orper der Charakteristik 6= 2, dann sind genau

Elemente von GF(q) Quadrate und aus den restlichen

q−1 2

q+1 2

Elementen kann man keine

Quadratwurzel ziehen.

Also d¨ urfen wir im Schnitt mit etwa q Punkten auf der EC rechnen. Tats¨achlich gilt

Satz 6.15 (Hasse). Es sei N die Anzahl der Punkte auf einer EC ¨ uber GF(q). Dann ist

√ √ (q + 1) − 2 q ≤ N ≤ (q + 1) + 2 q.

(D.h. die Anzahl der Punkte auf der EC ist von der selben Gr¨oßenordnung wie die √ Gr¨oße des K¨orpers, denn q hat nur halb so viele Stellen wie q.)

Somit ist eine EC u ¨ ber GF(q) eine abelsche Gruppe, deren Ordnung in etwa q ist. Ausnahmsweise ist diese Gruppe einmal nicht zyklisch, so etwas wie Primitivwurzeln gibt es also nicht. Es gibt keine Formel, mit der sich die Ordnung dieser Gruppe berechnen ließe. Es gibt allerdings Algorithmen, so z.B. den Algorithmus von Schoof ([Sch85]) und zahlreiche Varianten davon. Um sichere Kryptographie mit EC zu treiben, sollte sichergestellt sein, dass die Ordnung der Gruppe einen großen Primfaktor besitzt. Wenn man eine EC w¨ahlt wird man also nicht um das (etwas m¨ uhsame) Berechnen der Ordnung herumkommen.

Beispiel 6.16. Es sei p = x2 + 2 ein irreduzibles Polynom u ¨ ber Z5 und α eine Nullstelle von p. Dann ist Z5 (α) = Z5 [x]/p = GF(25) der endliche K¨orper mit 25 Elementen. Wir rechnen mit der EC E : y 2 = x3 + (α + 1)x + 4α + 3 u ¨ ber diesem K¨orper. Liegt der Punkt P = (2α, 2) auf E?

Wir berechnen x3 + (α + 1)x + 4α + 3 f¨ ur x = 2α und erhalten als Ergebnis 4. Dann berechnen wir y 2 f¨ ur y = 2 und erhalten ebenfalls 4. Also liegt P auf E.

6.3. KRYPTOSYSTEME MIT ELLIPTISCHEN KURVEN

97

Wie lauten die Koordinaten von 3 · P ?

Wir berechnen zun¨achst 2·P = P +P gem¨aß der Formel (6.2) und erhalten 2P = (2, 3α+1). Nun berechnen wir 3P = 2P + P gem¨aß der Formel (6.1) und erhalten 3P = (4, 3α + 3).

6.3

Kryptosysteme mit elliptischen Kurven

Das DLP sieht f¨ ur EC so aus: Gegeben E . . . EC u ¨ ber GF(q), P, Q ∈ E Gesucht k ∈ N, so dass k · P = Q, falls es so ein k gibt Zur Berechnung von k·P l¨asst sich wieder das Square-And-Multiply-Verfahren verwenden. Jetzt heißt square“ verdoppeln und multiply“ heißt addieren. ” ” ¨ In den Ubungen sehen wir uns als Beispiel den DH-Key-Exchange mit EC an. Um das DLP in Z∗p schwierig zu machen, sollte p zumindest eine 1024-Bit Zahl sein. Um die gleiche Schwierigkeit beim DLP u ¨ ber EC zu bekommen, sollte die Ordnung der EC etwa eine 160-Bit Zahl sein, es sollte also eine EC u ¨ ber Zp sein, wobei p eine 160-Bit Zahl ist. Man kann also mit wesentlich kleineren K¨orpern rechnen und verliert nichts an Sicherheit. Noch ein paar Kleinigkeiten. Wie kommt man zu einer EC und einem Punkt 6= O darauf ? Zun¨achst w¨ahlt

man einen endlichen K¨orper GF(q) der Charakteristik > 3. Dann w¨ahlt man zuf¨allig x, y, a ∈

GF(q). Damit der Punkt (x, y) auf y 2 = x3 + ax + b liegt, w¨ahlt man b = y 2 − x3 − ax.

Ist 4a3 + 27b2 6= 0, so hat man eine EC mit einem Punkt (x, y) darauf. Andernfalls w¨ahlt man neue x, y, a. Nun kann man die Ordnung der EC berechnen und gegebenenfalls ganz von

vorne beginnen. Wie macht man aus einer Zahl m (der Nachricht) einen Punkt P m auf der EC E? 1. W¨ahle t ∈ N so groß, dass 2−t als Wahrscheinlichkeit, dass es nicht gelingt einen passenden Punkt zu finden, klein genug ist. (Praktisch w¨ahlt man t zwischen 30 und 50.)

2. Sind die m¨oglichen Nachrichten als Zahlen zwischen 0 und M kodiert, so w¨ahle eine EC u ¨ ber GF(q) = Zp (α), wobei q = pr > M · t ist. 3. Jedes Element a ∈ {0, 1, . . . , M · t} besitzt eine eindeutige Darstellung a → a0 + a1 p + a2 p2 + . . . + ar−1 pr−1 , 0 ≤ ai < p.

98

KAPITEL 6. KOBLITZ UND MILLER Wir stellen a als a → a0 + a1 α + a2 α2 + . . . + ar−1 αr−1 ∈ Zp (α) dar. 4. Um die Nachricht m (0 ≤ m < M ) zu einem Punkt auf der EC zu machen, stelle man

nacheinander f¨ ur j = 1, 2, . . . , t die Zahl m · t + j gem¨aß (3) als Element des endlichen

K¨orpers dar. Dieses Element setze man f¨ ur x in y 2 = x3 + ax + b ein und versuche die

Quadratwurzel zu ziehen. Das gelingt mit Wahrscheinlichkeit 1/2. Hat man Erfolg, so hat man einen Punkt Pm gefunden. Andernfalls probiert man das n¨achste j. Somit hat man t Versuche und die Wahrscheinlichkeit, t mal zu scheitern ist nur ( 21 )t = 2−t . 5. Hat man umgekehrt einen Punkt auf der EC, dann nimmt man seine x-Koordinate. Diese ist von der Form x = a0 + a1 α + . . . + ar−1 αr−1 . Daraus macht man a = a0 + a1 p + . . . + ar−1 pr−1 Nun ist die urspr¨ ungliche Nachricht m = b a−1 t c.

6.4

Faktorisieren mit elliptischen Kurven

EC lassen sich auch verwenden, um große Zahlen zu faktorisieren. Wir sehen uns eine Methode von Lenstra an. Diese Methode beruht darauf, dass man Vielfache von Punkten auf einer EC u ¨ ber Zn berechnet. Da Zn kein K¨orper ist, geht das mit einer gewissen Wahrscheinlichkeit schief. Diese Wahrscheinlichkeit ist bei passenden Vielfachen sehr groß.

Algorithmus 6.17 (Lenstra). Die Zahl n ist zu faktorisieren. 1. W¨ahle (zuf¨allig) eine EC E : y 2 = x3 + ax + b u ¨ ber Zn und einen Punkt P = (x, y) auf E.

2. W¨ahle zwei nat¨ urliche Zahlen B und C. 3. Setze k=

Y

l αl ,

l≤B, l∈

wobei αl die gr¨oßte ganze Zahl ist, f¨ ur die lαl ≤ C ist.

6.4. FAKTORISIEREN MIT ELLIPTISCHEN KURVEN

99

4. Berechne k · P . Dabei muss modulo n invertiert werden (Nenner). Das funktioniert

nicht, wenn der Nenner nicht relativ prim zu n ist. In diesem Fall berechnet der erweiterte Euklidsche Algorithmus einen Teiler von n.

5. Ist alles gut gegangen, w¨ahle neue E und P .

Beispiel 6.18. Will man eine 10-stellige Zahl n faktorisieren, w¨ahlt man etwa B = 20 und C = 100700. Dann ergibt sich k = 216 · 3 · 57 · 75 · 114 · 134 · 174 · 193 .

Diese Faktorisierungsmethode ist in etwa so schnell wie das quadratische Sieb. Sie ist aber schneller, wenn n einen sehr kleinen Primfaktor besitzt. Außerdem haben wir gesehen, dass das quadratische Sieb einen sehr großen Speicherbedarf hat, es m¨ ussen ja riesige Gleichungssysteme gel¨ost werden. Dieses Problem hat diese Methode nicht. Schließlich kann man hier mehr Parameter w¨ahlen (B, C und E), nat¨ urlich kann man dann mit verschiedenen Parametern parallel an der Faktorisierung arbeiten.

Die Faktorisierungsmethode mit EC hat gezeigt, dass das Faktorisierungsproblem noch lange nicht vollst¨andig untersucht ist. Die relativ einfache Methode f¨ uhrt zu einem sehr schnellen Faktorisierungsalgorithmus (lediglich der Beweis, dass diese Methode wirklich eine schnelle Faktorisierungsmethode ist, ist sehr schwierig). So haben EC auch auf diesem Weg dazu gef¨ uhrt, dass mehr u ¨ ber Alternativen zu RSA nachgedacht wird.

100

KAPITEL 6. KOBLITZ UND MILLER

Literaturverzeichnis [Bau95]

F. Bauer. Entzifferte Geheimnisse. Springer, 1995.

[BBS86]

L. Blum, M. Blum, and M. Shub. A simple unpredictable pseudo-random number generator. SIAM J. Comput., 15(2), 1986.

[Buc99]

Johannes Buchmann. Einf¨ uhrung in die Kryptographie. Springer Verlag, 1999.

[Bun92]

Peter Bundschuh. Einf¨ uhrung in die Zahlentheorie. Springer-Verlag, Berlin, second edition, 1992.

[Coh93]

Henri Cohen. A course in computational algebraic number theory. Springer-Verlag, Berlin, 1993.

[DH76]

Whitfield Diffie and Martin E. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):644–654, 1976.

[Gor85]

John Gordon. Strong primes are easy to find. In Advances in cryptology (Paris, 1984), pages 216–223. Springer, Berlin, 1985.

[Kah67]

David Kahn. The Codebreakers. Macmillan Publishing Company, 1967.

[Kob94]

Neal Koblitz. A Course in Number Theory and Cryptography. Springer, 2nd edition, 1994.

[LN84]

Rudolf Lidl and Harald Niederreiter. Finite Fields, volume 20 of Encyclopedia of Mathematics and Its Applications. Addison–Wesley Pub Co, 1984.

[MvOV97] A.J. book

Menezes, of

P.C.

Applied

van

Ooorschot,

Cryptography.

and 1997.

S.A.

Vanstone. Online

Hand-

erh¨altlich

auf

http://www.cacr.math.uwaterloo.ca/hac/. [RSA77]

R. L. Rivest, A. Shamir, and L. M. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Technical Report MIT/LCS/TM-82, 1977. 101

102 [Sch85]

LITERATURVERZEICHNIS R. Schoof. Elliptic curves over finite fields and the computation of square roots mod p. Math. Comp., 44:483–494, 1985.

[Sch96]

Bruce Schneier. Angewandte Kryptographie. Addison-Wesley, 1996.

[Sin00]

Simon Singh. Geheime Botschaften. Die Kunst der Verschl¨ usselung von der Antike bis in die Zeiten des Internet. dtv, 2000.

[Wer02]

Annette Werner. Elliptische Kurven in der Kryptographie. Springer, 2002.