Wolfgang Ertel - hs-weingarten.deertel/kryptobuch/kryptobuch-ertel-folien.pdf · 2.1 Terminologie 11 2.1 Terminologie Kryptographie wird verstanden als die Lehre der Absicherung von

1

Prasentationsfolien zum Buch

Angewandte Kryptographie

Wolfgang Ertel

Hanser Verlag, 4. Auflage, 2012

ISBN: 3-446-21549-2

www.fh-weingarten.de/~ertel/kryptobuch.html

Inhaltsverzeichnis

1 Elektronisches Bargeld, ein erstes Beispiel 4

2 Grundlagen 10

3 Klassische Chiffren 35

4 Moderne Blockchiffren 112

5 Public-Key-Kryptographie 163

6 Authentifikation und digitale Signatur 218

7 Public-Key-Infrastruktur 272

8 Public-Key-Systeme 282

INHALTSVERZEICHNIS 3

9 Elektronisches Bargeld 309

10 Elektronische Zahlungssysteme 322

11 Politische Randbedingungen 332

12 Sicherheitslucken in der Praxis 339

13 Das kleine Einmaleins auf endlichen Mengen 344

14 Erzeugen von Zufallszahlen 398

Kapitel 1

Elektronisches Bargeld, ein erstes Beispiel

5

5 DM

Kodierung des Wertes im Klartext als Textdatei

Problem: Fälschung sehr einfach

Wert: 100 DM

Ecash MünzeEcash Münze

Wert: 5 DM

Ecash Münze

Wert: 5 DM

Ecash: 1. Versuch

6 1 Elektronisches Bargeld, ein erstes Beispiel

Bank kodiert mitgeheimem Schlüssel

e9uhfc−)vG$

@1l;5=O>WY7909jt&^3Fq_

5 DM

5 DM

909jt&^3Fq_@1l;5=O>WY7e9uhfc−)vG$5 DM

e9uhfc−)vG$@1l;5=O>WY7909jt&^3Fq_

5 DM


5 DMe9uhfc−)vG$@1l;5=O>WY7909jt&^3Fq_

5 DM


5 DM

Digitale Signatur der Bank:

Problem: Kopieren d. Münzen sehr einfach!

Ecash: 2. Versuch

7

5 DM123456789101

)^g$R#c9oH=P.KY"}3bx>[\0

digitaleSignaturd. Bank

Betrüger

5 DM123456789101


5 DM123456789101


Eindeutige Seriennummer:

Betrug wird erkannt ! kopiert Münze

Bank

Ecash: 3. Versuch

5 DM123456789101

8 1 Elektronisches Bargeld, ein erstes Beispiel

1.1 mogliche Kundendatenbank der E-Bank

Seriennummer Ausgabe Kunde Kto.-Nr. Handler Rucklauf Betrag123456789101 12.2.2001 Maier 7654321 Otto Versand 14.2.2001 50 DM123456789102 12.2.2001 Maier 7654321 Otto Versand 14.2.2001 20 DM123456789103 12.2.2001 Maier 7654321 Otto Versand 14.2.2001 8 DM123456789104 12.2.2001 Maier 7654321 Otto Versand 14.2.2001 0.90 DM123456789105 12.2.2001 Maier 7654321 amazon.de 17.2.2001 20 DM123456789106 12.2.2001 Maier 7654321 amazon.de 17.2.2001 2 DM123456789107 15.2.2001 Huber 0054322 Frisor Kurz 15.2.2001 20 DM123456789108 15.2.2001 Huber 0054322 Frisor Kurz 15.2.2001 20 DM123456789109 15.2.2001 Huber 0054322 Frisor Kurz 15.2.2001 5 DM123456789110 15.2.2001 Huber 0054322 Frisor Kurz 15.2.2001 1 DM123456789111 15.2.2001 Huber 0054322 Tankst. Sprit 16.2.2001 100 DM123456789112 15.2.2001 Huber 0054322 Tankst. Sprit 16.2.2001 2 DM123456789113 15.2.2001 Huber 0054322 Tankst. Sprit 16.2.2001 2 DM

......

......

......

...

1.1 mogliche Kundendatenbank der E-Bank 9

zurück an

mit Ser.Nr.

100 Münzen

99x

1x

5 DM

382644398021

eine Münze

Kunden

Signatur

99 Münzen

anonyme

Signatur

Bank prüft

Anonyme Signatur:

Bank signiert

Ecash: 4. Versuch

5 DM

382644398021

5 DM

Müll

876015769132

Kapitel 2

Grundlagen

2.1 Terminologie 11

2.1 Terminologie

Kryptographie wird verstanden als die Lehre der Absicherung vonNachrichten durch Verschlusseln.

Kryptanalyse ist die Kunst, Chiffretext aufzubrechen, d. h. denKlartext zu reproduzieren, ohne Kenntnis des Schlussels.

Kryptologie vereinigt Kryptographie und Kryptanalyse.

Ein Alphabet A ist eine endliche Menge von Zeichen. n = |A| istdie Machtigkeit des Alphabets.

Der lesbare Text einer Nachricht (message) wird Klartext (plain-

12 2 Grundlagen

text) genannt und mit M bezeichnet. Er wird als Zeichenkette uberdem Alphabet A gebildet.

aaa und abcabbb sind Klartexte uber dem Alphabet {a, b, c}.Geheimtexte oder Chiffretexte sind Zeichenketten uber demgleichen Alphabet A oder einem anderen Alphabet.

Auch die Schlussel sind Zeichenketten.

Verschlusselung oder Chiffrierung bezeichnet das Verfahren, umeine Nachricht unverstandlich zu machen.

Chiffre E (encryption) ist eine invertierbare, d. h. eine umkehrbareAbbildung, welche aus dem Klartext M und einem Schlussel K denGeheimtext C (ciphertext) erzeugt.

Die Umkehrung von E zur Wiederherstellung des Klartextes wird

2.1 Terminologie 13

Entschlusselung genannt und mit D (decryption) bezeichnet.

Es gilt E(M) = C und D(C) = M und

D(E(M)) = M

folgt.

Geheimhaltung: Lesen einer Nachricht fur Unbefugte unmoglichbzw. schwierig machen.

Authentifizierung oder

Authentifikation : Identitatsbeweis des Senders einer Nachrichtgegenuber dem Empfanger

Integritat: Unveranderbarkeit einer Nachricht.

Verbindlichkeit: Der Sender kann spater nicht leugnen, eineNachricht abgeschickt zu haben.

14 2 Grundlagen

2.2 Kryptographische Algorithmen

Kryptographische Algorithmen sind Berechnungsvorschriften,d. h. mathematische Funktionen zur Ver- und Entschlusselung.

Bei symmetrischen Algorithmen wird zum Chiffrieren und zumDechiffrieren immer der gleiche Schlussel K benutzt und es gilt

EK(M) = C

DK(C) = M

DK(EK(M)) = M.

Bei asymmetrischen Algorithmen wird zum Chiffrieren ein Schlussel

2.2 Kryptographische Algorithmen 15

K1 und zum Dechiffrieren ein anderer Schlussel K2 benutzt und esgilt:

EK1(M) = C

DK2(C) = M

DK2(EK1(M)) = M

bei Stromchiffren wird ein Zeichen nach dem anderen verschlusselt.

bei Blockchiffren wird die Nachricht in Blocke (z. B. der Lange64 Bit) zerteilt und dann ein Block nach dem anderen verschlusselt.

Kryptosystem = Algorithmus + Schlussel + verschlusselte Nach-richten.

Nachteile der Geheimhaltung eines (eingeschrankten) Al-gorithmus:

16 2 Grundlagen

• Verlasst eine Person eine Benutzergruppe (z. B. eine Firma),dann muss der Algorithmus geandert werden.

• Eingeschrankte Algorithmen konnen daher nicht an Dritte wei-tergegeben werden. Sie waren dann wertlos.

• Qualitatskontrolle von eingeschrankten Algorithmen ist sehr schwie-rig!

Im 19. Jahrhundert von A. Kerkhoffs [Kah67] gefordert:

Die Sicherheit eines Verschlusselungsverfahrens darf nur von derGeheimhaltung des Schlussels abhangen, nicht jedoch von der Ge-heimhaltung des Algorithmus.

⇒ starke Kryptographie


Beispiele fur die Verletzung von Kerkhoffs’ Prinzip

Online-Magazin der Zeitschrift c’t vom 7.12.991:

Handy-Verschlusselung angeblich geknacktDie beiden israelischen Kryptologen Alex Biryukov und Adi Shamir haben Medienberichtenzufolge den Verschlusselungsalgorithmus geknackt, der GSM-Handy-Telefonate auf der Funk-strecke zur Mobiltelefon-Basisstation schutzt. . . .Eines zeigen die Vorfalle um die GSM-Verschlusselungsalgorithmen A5/1 und A5/2 aberschon jetzt deutlich: Der Versuch, Krypto-Verfahren geheim zu halten, dient nicht derSicherheit. Das hat anscheinend auch die GSM-Association gelernt: Ihr SicherheitsdirektorJames Moran ausserte dem Online-Magazin Wired gegenuber, dass man kunftige Algorithmenvon vorneherein offenlegen will, um der Fachwelt eine Prufung zu ermoglichen. (nl/c’t)

1 Siehe http://www.heise.de/newsticker/data/nl-07.12.99-000/

18 2 Grundlagen

am 15.12.992 an gleicher Stelle die nachste Meldung:

Netscape verschlusselt Passworter unzureichendDer Netscape Navigator legt Passworter fur den Zugriff auf E-Mail-Server nur unzureichendverschlusselt ab. Zwei Mitarbeiter des US-Softwarehauses Reliable Software Technologies(RST) brauchten lediglich acht Stunden, um den Algorithmus zu knacken. . . .Der Algorithmus zerhacke die Passworter zwar, es handle sich jedoch um keine starke Ver-schlusselung, so Gary McGraw von RST. Durch die Eingabe einfacher Passworter wie “a”,“b” und so weiter sei man relativ schnell dahinter gekommen.. . .Der US-Sicherheitsexperte Bruce Schneier wertet die Entdeckung als weiteres Beispiel dafur,wie schadlich proprietare Verschlusselungsverfahren sein konnen. (ad[2]/c’t)

Weiteres aktuelles Beispiel: Verschlusselungsprotokoll WEP (WiredEquivalent Privacy), verwendet bei Funk-Netzwerken (IEEE802.11).Zitat aus [BGW01]:2 Siehe http://www.heise.de/newsticker/data/ad-15.12.99-001/


ConclusionsWired Equivalent Privacy (WEP) isn’t. The protocol’s problems is a result of misunderstan-ding of some cryptographic primitives and therefore combining them in insecure ways. Theseattacks point to the importance of inviting public review from people with expertisein cryptographic protocol design; had this been done, the problems stated here would havesurely been avoided.

20 2 Grundlagen

2.3 Kryptographische Protokolle

Kryptographische Protokolle sind Verfahren zur Steuerung des Ab-laufs von Transaktionen fur bestimmte Anwendungen.

2.4 Public-Key-Algorithmen 21

2.4 Public-Key-Algorithmen

M M

Bob

SD

(M)

Aliceunsicherer Kanal

EP

B

BEPB

Abbildung 2.1: Austausch einer Nachricht mit einem Public-Key-Verfahren. Es werden offentlicherSchlussel PB und geheimer Schlussel SB von Bob benutzt

22 2 Grundlagen

Es muss gelten:

EPB(M) = C

DSB(C) = M

DSB(EPB(M)) = M.

M M

Bob

PD A

Alice

EA

SSE(M, (M))A

Abbildung 2.2: Alice signiert ein Dokument M mit ihrem geheimen Schlussel SA und Bob pruft die Signaturmit Alices offentlichem Schlussel PA

Es ist praktisch unmoglich, aus einem offentlichen Schlussel PA denzugehorigen geheimen Schlussel SA zu berechnen (Kapitel 5).

2.5 Kryptanalyse 23

2.5 Kryptanalyse

Arten von kryptanalytischen Angriffen:

Ciphertext-Only-Angriff: Der Kryptanalytiker verfugt nur ubereine bestimmte Menge Chiffretext.

Known-Plaintext-Angriff: Der Kryptanalytiker kennt zusatz-lich den zum Chiffretext gehorenden Klartext.

Chosen-Plaintext-Angriff: Der Kryptanalytiker kann einenbeliebigen Klartext vorgeben und hat eine Moglichkeit zu die-sem vorgegebenen Text an den Chiffretext zu gelangen. Moglich

24 2 Grundlagen

bei allen Public-Key-Systemen.

Chosen-Ciphertext-Angriff: Der Kryptanalytiker kann einenbeliebigen Chiffretext vorgeben und hat eine Moglichkeit, an denzugehorigen Klartext zu gelangen.

Angriff mit Gewalt: Der Kryptanalytiker bedroht oder folterteine Person mit Zugang zum Schlussel.

Angriff mit gekauftem Schlussel: Der Schlussel wird mittelsBestechung “gekauft”.

2.5 Kryptanalyse 25

Bei den Verfahren der starken Kryptographie stellt meist der Menschals Besitzer des Schlussels die großte Sicherheitslucke dar.

26 2 Grundlagen

Ein Angriff, bei dem alle moglichen Schlussel ausprobiert werden,wird Brute-Force-Angriff genannt.

Definition 2.1 Ein Algorithmus gilt als sicher, wenn

• der zum Aufbrechen notige Geldaufwand den Wert der ver-schlusselten Daten ubersteigt oder

• die zum Knacken erforderliche Zeit großer ist als die Zeit, diedie Daten geheim bleiben mussen, oder

• das mit einem bestimmten Schlussel chiffrierte Datenvolumenkleiner ist als die zum Knacken erforderliche Datenmenge.

Ein Algorithmus ist uneingeschrankt sicher, wenn der Klartextauch dann nicht ermittelt werden kann, wenn Chiffretext in belie-bigem Umfang vorhanden ist.

2.5 Kryptanalyse 27

In Abschnitt ?? werden wir einen uneingeschrankt sicheren Algo-rithmus kennen lernen.

28 2 Grundlagen

Wichtige Großen

Berechnungskomplexitat = Rechenzeit in Abhangigkeit von derSchlussellange.

Speicherplatzbedarf

Datenkomplexitat,

2.6 Sicherheit von Schlusseln 29

2.6 Sicherheit von Schlusseln

Aufwand zum Knacken dieser Schlussel??

30 2 Grundlagen

56 Bit-Schlussel (DES):

Der Schlusselraum hat die Große 256 ≈ 7 · 1016.

Beste bekannte Hardware-Implementierung kann etwa 9·1010 Schlusselpro Sekunde testen.

Kryptanalyseaufwand: ⇒ mittlere Zeit von etwa 3.9 · 105 Se-kunden ≈ 4.5 Tage. ⇒ unsicher

100 Bit-Schlussel:

2100 ≈ 1.3 · 1030 Schlussel.

Aufwand: 7 · 1018 Sekunden ≈ 2 · 1011 Jahre ≈ 20 mal Alter desUniversums (1010 Jahre).

Aufwand bei Schlussel der Lange 1024 Bit??


Einer der 21024 Schlussel mit 1024 Bit

010000101101111010100011101100011111110101001100111100100000110111101

001111110010100000110110001000110100010100100011010110111011011010010

000001100010000100101110111100011111010100001111000011011010001110000

010101001110101101111110111011111011011011001100011110001011110011100

001111110001000000110001011010110010110111110110011100011100110011010

111101101011010101001010100010000101011100100100011000000110010101101

000110100111111000111101000100001110010101000010100001010010000111111

011001010000100010100001011100100000001100010011110100010101110001001

001010110111110001011111010100101011100001000100110101100100111101111

000100010111101000010000010001001101101111100011101110000100010100111

100001101110011111000110011110010111011101101101110001110101001111011

110010101101110001100101101101011100001001010101110001011101010010001

000001101001101110100000110100000000001111110011011000100110101000001

001111110100110001010101001111111101011000111111001011001110111101010

1101111110101001100011110011000101010000010000000100101011

32 2 Grundlagen

Der Schlusselraum, d. h. die Menge, aus der ein Schlussel gewahltwird, sollte moglichst groß sein. Er sollte mindestens so groß sein,dass der Aufwand fur einen Angriff unakzeptabel hoch wird.


Untersetzung pro Zahnrad: 50 : 1

Wie lange lauft der Motor mit 200 Umdr./min., bis es kracht?

Foto aufgenommen im Technorama, Winterthur, Schweiz.

34 2 Grundlagen

Untersetzung gesamt: 5012 ≈ 2.4 · 1020

Foto aufgenommen im Technorama, Winterthur, Schweiz.

Kapitel 3

Klassische Chiffren

Problem: Addition und Multiplikation naturlicher Zahlen auf kei-ner endlichen Teilmenge abgeschlossen.

36 3 Klassische Chiffren

Definition 3.1 Bei einer Transpositionschiffre wird der Ge-heimtext durch eine Permutation der Klartextzeichen erzeugt.Bei einer Substitutionschiffre wird jedes Zeichen des Klartextesdurch ein anderes ersetzt. Die Position bleibt jedoch gleich.Eine Substitutionschiffre heißt monoalphabetisch, wenn jedesKlartextzeichen immer auf das gleiche Geheimtextzeichen abge-bildet wird. Sie heißt polyalphabetisch, wenn sie nicht monoal-phabetisch ist.

Uber dem naturlichen Alphabet (a, b, c, . . . , z) gibt es 26! ≈ 4·1026

monoalphabetische Chiffren.

Beim Verschlusseln von Binardaten gibt es nur zwei monoalphabe-tische Chiffren. Welche?

3.1 Verschiebechiffren 37

3.1 Verschiebechiffren

Julius Caesar (100 bis 44 v. Chr):

Klartext: a b c d e f g h i j k l m n o p q r s t u v w x y zChiffretext: D E F G H I J K L M N O P Q R S T U V W X Y Z A B C.

Klartextzeichen: KleinbuchstabenGeheimtextzeichen: Großbuchstaben


Definition 3.2 Bei einer Verschiebechiffre wird jedes Klartextzei-chen z durch ein um k Zeichen im Alphabet verschobenes Zeichenersetzt. Bei einem Alphabet mit n Zeichen seien die Zeichen durch-nummeriert von 0 bis n− 1. Dann gilt fur eine Verschiebechiffre:

z 7→ (z + k) mod n.

Verschiebechiffren sind sehr leicht zu knacken. Wie?


Buchstabenhaufigkeiten der deutschen Sprache

Buchstabe Haufigkeit [%] Buchstabe Haufigkeit [%]

a 6.51 n 9.78

b 1.89 o 2.51

c 3.06 p 0.79

d 5.08 q 0.02

e 17.40 r 7.00

f 1.66 s 7.27

g 3.01 t 6.15

h 4.76 u 4.35

i 7.55 v 0.67

j 0.27 w 1.89

k 1.21 x 0.03

l 3.44 y 0.04

m 2.53 z 1.13


Beispiel 3.1 Gegeben sei folgender Chiffretext:

GEIWEV LEX MQQIV YQ HVIM ZIVWGLSFIR

Haufigkeitsanalyse

Geheimtext-Alph.: E F G H I L M Q R S V W X Y ZHaufigkeit: 3 1 2 1 5 2 2 3 1 1 4 2 1 1 1Erwartungswerte falls e 7→ I: 2.0 0.6 0.9 1.5 5.2 1.4 2.3 0.8 2.9 0.8 2.1 2.2 1.8 1.3 0.2Klartext-Alphabet: a b c d e h i m n o r s t u v

Hypothese e 7→ IAußerdem erkennt man, dass die zehn haufigsten Buchstaben desAlphabets bei dieser Hypothese (Verschiebung um vier) alle im ent-schlusselten Text vertreten sind. Der Klartext lautet:

caesar hat immer um drei verschoben


Ciphertext-Only-Angriff mit wenig Geheimtext.minimale Datenkomplexitat.Grund??


3.2 Multiplikative Chiffren

Definition 3.3 Bei einer multiplikativen Chiffre uber dem Alpha-bet A wird jedes Klartextzeichen z mit einer Zahl t ∈ {0, . . . , n−1} multipliziert. t und n = |A| mussen teilerfremd sein, d. h. esmuss gelten ggT(t, n) = 1. Die Chiffriervorschrift lautet

z 7→ (z · t) mod n.

Wegen (z · t) mod n = (z mod n) · (t mod n) mod n mussen furt nur Werte aus {0, . . . , n− 1} betrachtet werden. Großere Werte

3.2 Multiplikative Chiffren 43

von t liefern keine neuen Chiffren.

Beispiel 3.2 n = 26 und t = 2

Klartext a b c d . . . l m n o . . .

z 0 1 2 3 . . . 11 12 13 14 . . .

2z mod 26 0 2 4 6 . . . 22 24 0 2 . . .

Geheimtext A C E H . . . V X A C . . .

Chiffre ist nicht injektiv!Fur t = 3 ergibt sich

z 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

3z mod 26 0 3 6 9 12 15 18 21 24 1 4 7 10 13 16 19 22 25 2 5 8 11 14 17 20 23


Hier funktioniert die eindeutige Entschlusselung. Allgemein gilt

Satz 3.1 Zu jeder multiplikativen Chiffre E mit ggT(t, n) = 1gibt es eine multiplikative Dechiffrierfunktion D mit D(E(z)) = zfur alle z ∈ A.

Beweis: Wegen ggT(t, n) = 1 gibt es nach Satz 13.8 ein b ∈ Znmit t · b ≡ 1 mod n. Dieses b ist also invers zu t modulo n undmacht die Multiplikation mit t ruckgangig. Also ist

D : z′ 7→ bz′ mod n

die Dechiffrierfunktion zu E, denn es gilt

D(E(z)) = (b(zt) mod n) mod n = ((bt) mod n · z) mod n =(1z) mod n = z. 2

3.2 Multiplikative Chiffren 45

Mogliche Schlussel t mit ggT(t, 26) = 1 und t < 26:

1, 3, 5, 7, 9, 11, 15, 17, 19, 21, 23, 25

|Schlusselraum| = 12


3.3 Tauschchiffren (Affine Chiffren)

Definition 3.4 Sei ggT(t, n) = 1. Dann wird jede Chiffre E mitz 7→ (zt + k) mod n affine Chiffre oder Tauschchiffre genannt.

3.3 Tauschchiffren (Affine Chiffren) 47

Beispiel 3.3 Sei t = 5, k = 7, n = 26.

z 1 2 3 4 5 6 7 8 9 10 11 12 . . .

z′ = (5z + 7) mod n 12 17 22 1 6 11 16 21 0 5 10 15 . . .

Wie lautet die Dechiffrierfunktion?

Suche multiplikative Inverse b zu 5 in Z26 durch Probieren. Fur bmuss gelten 5 · b ≡ 1 mod 26.

Gesucht: Vielfaches von 5, das bei Division durch 26 den Rest 1ergibt.

Tabelle der Vielfachen von 26:

i 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 . . .

26i 0 26 52 78 104 130 156 182 208 234 260 286 312 338 364 . . .

Zahlen, die um 1 kleiner sind als ein Vielfaches von 5, also Zahlen


die mit den Ziffern 4 oder 9 enden. Wir finden 104, 234, 364 . . .,verwenden davon 104 und berechnen

5b = 105 ≡ 1 mod 26 ⇒ b = 21

z′ = 5z + 7 nach z auflosen:

z′ = 5z + 7

21z′ = 21 · 5 · z + 21 · 7 ≡ (z + 147) mod 26 = (z + 17) mod 26

z ≡ (21z′ − 17) mod 26 ≡ (21z′ + 9) mod 26

Damit kann die Dechiffrierfunktion angewendet werden, um aus z′

wieder z zu berechnen (siehe Tabelle ??).

3.3 Tauschchiffren (Affine Chiffren) 49

z z′ = (5z + 7) mod 26 z = (21z′ + 9) mod 26

1 12 252 + 9 = 18 + 9 = 27 = 12 17 357 + 9 = 19 + 9 = 28 = 23 22 462 + 9 = 20 + 9 = 29 = 34 1 21 + 9 = 30 = 4...

......

12 67 = 15 315 + 9 = 3 + 9 = 12...

......

Siehe auch: Euklidischer Algorithmus


es gibt 26 ·12 = 312 verschiedene Tauschchiffren auf dem Alphabet{a, b, c, . . . , z}.

3.4 Kryptanalyse monoalphabetischer Chiffren 51

3.4 Kryptanalyse monoalphabetischer Chiffren

Gegeben sei folgender monoalphabetisch verschlusselte Chiffretext:

WBO BUVLPH RZWB NHBOB EOHGYVTRQ UVRQY CD GUHRGBU

LBNBTBU QHBYYBU WVB MOVYVTRQBU GOXEYZLOHEQBU UVRQYT

DBMBO WBU IBOTRQKDBTTBKDULTEOZCBTT LBNDTTY

haufigster Buchstabe: “B”

Buchstabenhaufigkeiten:

Buchstabe A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

Haufigkeit 0 22 2 5 4 0 4 6 1 0 2 5 2 3 9 1 7 7 0 12 11 7 4 1 8 3


Hypothesen:

1. B 7→ e, T 7→ n

2. B 7→ e, U 7→ n

Bigramme, d. h. Paare von Buchstaben abzahlen:

Linken Tabelle: en viel haufiger als ne. Daher wird Hypothese 2(U 7→ n) weiterverfolgt. Das vierfache Vorkommen von BO legtO 7→ r nahe.

Die auffallige Haufigkeit von RQ deutet auf ch. Nimmt man dannnoch V und T als die beiden nach e und n haufigsten Buchstabeni und s dazu, so ergibt sich als eine neue Hypothese (neben einerweiteren):


Paarhaufigkeiten in deutschen Texten


Mittlere Haufigkeit vonPaaren in deutschen

Texten

Paar Haufigkeit

en 3.88%er 3.75%ch 2.75 %te 2.26 %de 2.00 %nd 1.99 %ei 1.88 %ie 1.79 %in 1.67 %es 1.52 %

Paarhaufigkeiten im Beispiel

Paar Haufigkeit

WB 3HB 2LB 2TB 2QB 2DB 2NB 1YB 1VB 1MB 1IB 1CB 1LB 1

Paar Haufigkeit

BU 7BO 4BT 3BN 2BY 1BK 1BM 1RQ 5


B 7→ e, U 7→ n, O 7→ r, R 7→ c, Q 7→ h, T 7→ s, V 7→ i

Damit erhalt man:

Wer eniLPH cZWe NHere ErHGYisch nichY CD GnHcGen

LeNesen hHeYYen Wie MriYischen GrXEYZLrHEhen nichYs

DeMer Wen IerschKDesseKDnLsErZCess LeNDssY

Luckentext:

er eni c e ere r isch nich n c en

e esen h e en ie ri ischen r r hen nich s

e er en ersch esse n s r ess e ss


3.5 Polyalphabetische Chiffren

Homophone Chiffren

Homophone Chiffren sind solche, bei denen im Geheimtext jedesZeichen (in etwa) gleich haufig vorkommt.

Homophone Chiffren verschleiern die Haufigkeiten der Klartextzeichen.

Angriffe mit statistischen Methoden moglich.

3.5 Polyalphabetische Chiffren 57

Als Nachfolger der Geheimtextzeichen von c sind z.B. die zu h undk gehorenden Geheimtextzeichen besonders haufig.

⇒

• homophone Chiffren sind schwerer zu knacken als monoalpha-betische Chiffren

• fur die statistische Analyse von Paaren werden mehr Datenbenotigt.


Vigenere-Chiffre

16. Jhd., Blaise de Vigenere

Beispiel 3.4 Das Schlusselwort sei geheim.

Schlusselwort K: geheimgeheimgehei

Klartext P : dieloesunglautetx

Chiffretext C: JMLPWQYYUKTMAXLXF

K = Schlusselwort der Lange k

geheim =(6, 4, 7, 4, 8, 12)

V = Matrix des Vigenere-Quadrats


z = Nummer des zu codierenden Zeichens im Alphabet

i = Position von z im Klartext

n = die Lange des Alphabets

Dann gilt

E(z, i) = (z + Ki mod k) mod n = Vz,Ki mod k,


Klartext a b c d e f g h i j k l m n o p q r s t u v w x y z0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25

Chiffretext 0 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z1 B C D E F G H I J K L M N O P Q R S T U V W X Y Z A2 C D E F G H I J K L M N O P Q R S T U V W X Y Z A B3 D E F G H I J K L M N O P Q R S T U V W X Y Z A B C4 E F G H I J K L M N O P Q R S T U V W X Y Z A B C D5 F G H I J K L M N O P Q R S T U V W X Y Z A B C D E6 G H I J K L M N O P Q R S T U V W X Y Z A B C D E F7 H I J K L M N O P Q R S T U V W X Y Z A B C D E F G8 I J K L M N O P Q R S T U V W X Y Z A B C D E F G H9 J K L M N O P Q R S T U V W X Y Z A B C D E F G H I

10 K L M N O P Q R S T U V W X Y Z A B C D E F G H I J11 L M N O P Q R S T U V W X Y Z A B C D E F G H I J K12 M N O P Q R S T U V W X Y Z A B C D E F G H I J K L13 N O P Q R S T U V W X Y Z A B C D E F G H I J K L M14 O P Q R S T U V W X Y Z A B C D E F G H I J K L M N15 P Q R S T U V W X Y Z A B C D E F G H I J K L M N O16 Q R S T U V W X Y Z A B C D E F G H I J K L M N O P17 R S T U V W X Y Z A B C D E F G H I J K L M N O P Q18 S T U V W X Y Z A B C D E F G H I J K L M N O P Q R19 T U V W X Y Z A B C D E F G H I J K L M N O P Q R S20 U V W X Y Z A B C D E F G H I J K L M N O P Q R S T21 V W X Y Z A B C D E F G H I J K L M N O P Q R S T U22 W X Y Z A B C D E F G H I J K L M N O P Q R S T U V23 X Y Z A B C D E F G H I J K L M N O P Q R S T U V W24 Y Z A B C D E F G H I J K L M N O P Q R S T U V W X25 Z A B C D E F G H I J K L M N O P Q R S T U V W X Y


Kryptanalyse


Der Kasiski-Test

Charles Babbage, engl. Mathematiker, 1854

preussischer Major Friedrich Kasiski, 1863 erstmals veroffent-licht.

Idee:Suche Wiederholungen von Zeichenfolgen mit mindestens drei Zei-chen, messe deren Abstand und bestimme daraus die Schlussellange.


Beispiel 3.5 Gegeben sei folgender Geheimtext:

WGRIS LSTNJ AQSEI WGGEI XOSRV FNFMB GRTEI WBGOE FONHI AQSTV FRLSR

TSCIE VSCPI SLTSJ WZEEE NSCWV FRFNX XWYDV LRPNE WGTSK KSSRL EGEAV

FRWIT ZNFBV VWPNV FWYSS WGZNU WFPDV JGNHC MSDSV DHLUJ UVTSK KSSRR

MTHEE VWRUE VOYFR WZWIX MBODV JGNHC MSDSV DAFSJ WQSTQ MTLEC DWRSV

AB

Zeichenfolge Pos. 1 Pos. 2 Abstand Primfaktoren

ISL 4 65 61 61AQS 11 46 35 5 · 7EIW 14 34 20 225QST 47 207 160 25 · 5VFR 50 80 30 2 · 3 · 5SJW 69 204 135 33 · 5VFR 80 110 30 2 · 3 · 5TSKKSSR 98 158 60 22 · 3 · 5FRW 111 179 68 22 · 17DVJGNHCMSDSVD 139 189 50 2 · 52


Vermutung: Schlussellange = 2 oder 5

Teiltexte bei Schlussellange 2:

Nr. Teiltext

1 WRSSNASIGEXSVNMGTIBOFNIQTFLRSIVCILSWEESWFFXWDLPEGSKSLGAF

WTNBVPVWSWZUFDJNCSSDLJVSKSRTEVREOFWWXBDJNCSSDFJQTMLCWSA

2 GILTJQEWGIORFFBREWGEOHASVRSTCESPSTJZENCVRNXYVRNWTKSREEVR

IZFVWNFYSGNWPVGHMDVHUUTKSRMHEWUVYRZIMOVGHMDVASWSQTEDRVB

Teiltexte bei Schlussellange 5:

Nr. Teiltext

1 WLAWXFGWFAFTVSWNFXLWKEFZVFWWJMDUKMVVWMJMDWMDA

2 GSQGONRBOQRSSLZSRWRGSGRNWWGFGSHVSTWOZBGSAQTWB

3 RTSGSFTGNSLCCTECFYPTSEWFPYZPNDLTSHRYWONDFSLR

4 INEERMEOHTSIPSEWNDNSRAIBNSNDHSUSREUFIDHSSTES

5 SJIIVBIEIVREIJEVXVEKLVTVVSUVCVJKREERXVCVJQCV


Haufigkeiten in den Teiltextenk = 1 k = 2 k = 5

Buchstabe Text 1 Text 2 Text 1 Text 2 Text 3 Text 4 Text 5A 5 3 2 3 1 0 1 0B 5 3 2 0 3 0 1 1C 6 4 2 0 0 3 0 3D 8 5 3 3 0 2 3 0E 15 6 9 1 0 2 6 6F 12 8 4 6 1 4 1 0G 10 4 6 1 7 2 0 0H 5 0 5 0 1 1 3 0I 9 5 4 0 0 0 4 5J 6 4 2 2 0 0 0 4K 4 2 2 2 0 0 0 2L 7 6 1 2 1 3 0 1M 6 2 4 5 0 0 1 0N 11 6 5 1 2 3 5 0O 5 2 3 0 3 1 1 0P 4 2 2 0 0 3 1 0Q 4 2 2 0 3 0 0 1R 14 4 10 0 5 3 3 3S 26 17 9 1 8 6 9 2T 11 5 6 1 2 5 2 1U 4 1 3 1 0 0 2 1V 17 6 11 4 1 0 0 12W 17 10 7 9 5 2 1 0X 4 3 1 2 0 0 0 2Y 3 0 3 0 0 3 0 0Z 4 1 3 1 2 1 0 0


Java-Applets fur den Kasiski-Test sind zu finden unter [Vig01].


Der Friedmann-Test

amerikanischer Kryptologe William Friedmann, 1925

Idee: naherungsweises Bestimmen der Schlussellange nur durchAbzahlen der Buchstabenhaufigkeiten.


Darstellung von Chiffre- und Klartext

C =

C11, C12, . . . C1k,C21, C22, . . . C2k,

... ... ...,Cm

k 1, Cmk 2, . . . Cm

k k,

M =

M11, M12, . . . M1k,M21, M22, . . . M2k,

... ... ...,Mm

k 1, Mmk 2, . . . Mm

k k,

(3.1)

Zeilenlange = SchlusselwortlangeSpalte i entspricht dem i-ten Teiltext


Herleitung der Formel

Buchstaben innerhalb der Teiltexte sind nicht zufallig verteilt

Koinzidenzindex I = Wahrscheinlichkeit dafur, dass zwei zufalliggewahlte Buchstaben mit beliebigem Abstand gleich sind.

m1 = Haufigkeit fur ’a’, m2 = Haufigkeit fur ’b’, . . .m26 = Haufig-keit fur ’z’.

Die Lange m des Textes

m =

26∑i=1

mi.


Gesamtzahl aller Buchstabenpaare

m(m− 1)

2Zahl der Paare a. . . a

m1(m1 − 1)

2.

Gesamtzahl aller Paare aus gleichen Buchstaben26∑i=1

mi(mi − 1)

2.

Koinzidenzindex

I =

∑26i=1mi(mi − 1)

m(m− 1).

Fur lange deutsche Texte gilt I ≈ Id := 0.0762.


Fur zufallig generierte lange Texte mit m1 = m2 = . . . = m26 gilt

I =

∑26i=1mi(mi − 1)

m(m− 1)≈∑26

i=1m2i

m2=

26∑i=1

m2i

m2

=

26∑i=1

(mi

m

)2

=

26∑i=1

(1

26

)2

=1

26≈ 0.0385 =: Ir.

I = 1 fur Text aus lauter gleichen Buchstaben.

Anderer Zugang:zerlege Text in k Teiltexte (k = Schlussellange)

innerhalb der Teiltexte gilt I = Id = 0.0762zwischen verschiedenen Teiltexten gilt I = Ir = 0.0385

Es gibt k Teiltexte mit je etwa m/k Buchstaben.


Zahl der Paare aus Buchstaben innerhalb der Teiltexte:

1

2· mk

(mk− 1)· k =

m(m− k)

2k

Zahl der Paare von Buchstaben aus verschiedenen Teiltexten:

m(m− m

k

)· 1

2=m2(k − 1)

2k

Zahl der Paare aus gleichen Buchstaben im Text

m(m− k)

2k· Id +

m2(k − 1)

2k· Ir.

Wahrscheinlichkeit fur Paare aus gleichen Buchstaben

m(m− k)

m(m− 1)k· Id +

m2(k − 1)

m(m− 1)k· Ir.


muß etwa gleich I sein:

I ≈ (m− k)

(m− 1)k· Id +

m(k − 1)

(m− 1)k· Ir

nach k auflosen:

k ≈ (Id − Ir)m(m− 1)I − Irm + Id

=0.0377m

(m− 1)I − 0.0385m + 0.0762

Ergebnis:

naherungsweise Berechnung der Schlussellange nur durch Abzahlender Haufigkeiten aller Geheimtextzeichen.

Angewendet auf unser Beispiel ergibt sich

I ≈ 0.0499


und

k ≈ 3.29.


Die Enigma

erfunden etwa 1920 vonArthur Scherbius



Verdrahtungsschema der Enigma

entnommen aus dem Enigma Simulator von Ian Noble [Nob96]


Schlusselraum

• Vigenere-Chiffre mit Schlussellange ka = 26 · 26 · 26 = 17 576

• Steckbrett: Bei funf vertauschten Buchstabenpaaren

1

5!

(262

)(242

)(222

)(202

)(182

)= 5 019 589 575 ≈ 5 · 109

unterschiedliche Steckbrettverschaltungen.

• Fur beliebige Zahl p vertauschter Buchstabenpaare:

ks(p) =1

p!

(262

)(242

)· · ·(26− 2(p− 1)

2

)(3.2)

Verschaltungen.


Schlusselraum

• Steckbrett insgesamt:

ks =

13∑p=0

ks(p) = 532 985 208 200 575 ≈ 5 · 1014.

• Schlusselraum gesamt mit 3 fest eingebauten Walzen, Steck-brett und 6 verschiedenen Walzenlagen:

k = 6 · ka · ks = 6 · 17 576 · 532 985 208 200 575

= 56 206 488 115 999 837 200 ≈ 6 · 1019.


Geschichte der Enigma

1923 Erfindung durch Arthur Scherbius zum Gebrauchfur Geschaftsleute.

1925 Deutsche Marine kauft erste Enigmas.

1928 Landstreitkrafte kaufen Enigmas. Polnische Ma-thematiker beginnen mit der Kryptanalyse. Polenknacken die Enigma erstmals ( ⇒ Prinzip vonKerkhoffs).

1930 Verbesserung durch Hinzufugen des Steckbretts.


1933 Einsatz elektromechanischer Computer, Bombegenannt, zum erfolgreichen Knacken der Enigmadurch die Polen.

1938 Enigma wird durch austauschbare Walzen wiedersicher (drei von funf Walzen).

1939 Der Großangriff auf die Enigma in Bletchley Parkbeginnt. Alan Turing baut verbesserte Bomben(erste Computer).

1942 Neue Enigma mit vier Walzen ist wieder sicher.Wird im U-Boot-Krieg eingesetzt.


1943 4-Walzen-Enigma geknackt, u. a. helfen Wetter-meldungen deutscher U-Boote, sog. Menus fur dieBomben bzw. Computer zu erstellen. Colossuskommt zum Einsatz.

1945 Ende des zweiten Weltkriegs. Entschlusseln derEnigma-Codes in Bletchley Park trug bei zum Siegder Alliierten. Ca. 10 000 Personen in drei Schich-ten.


Kryptanalyse

• Marian Rejewski (Polen) analysiertschon fruh die Enigma

Literatur:[Dew89, Har95, Kah67, Kah91]


Kryptanalyse

• Brute-Force-Angriff aussichtslos

• Kasiski-Test und Friedmann-Test nicht sinnvoll anwendbar

• Funktionsweise war den Alliierten schon fruh bekannt

• Fehler bei der Anwendung boten Angriffspunkte

• Standardisiertes militarisches Format der Meldung macht Known-Plaintext-Angriff moglich.

• Taglich neue Anfangsstellung der Walzen wird zweimal nach-einander ubertragen!

• Enigma bildet kein Zeichen auf sich selbst ab. Schrankt Such-raum ein.


• Selbstinverse Eigenschaft der Enigma f 7→ p ⇒ p 7→ f .

• Erbeutete Codebucher machen Angriffe viel leichter.


Zyklen verraten die Walzenstellung

• Steckbrettverschaltung, Walzenlage, Anfangsstellung der Wal-zen fur jeden Tag vorgegeben.

• Funker mussten eigenen Spruchschlussel verwenden.

• Spruchschlussel musste wiederholt werden. Beispiel: ULJULJ 7→LOKTGM

• Rejewski nutzte Zyklen durch wiederholte Spruchschlussel, umdie Walzenstellung zu finden.


Abgefangene Anfangsstucke:

LOKTGM, AXUFMB, GLBCFJ, XOENGD, TFIIYK, ...

Tabelle aller 1. und 4. Zeichen:

1. Ze. A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

4. Ze. F Y Q G B W C O D M E T S U R A Z X H I J L P N K V

Alle Zyklen: Zyklus LangeA-F-W-P-A 4

B-Y-K-E-B 4

C-Q-Z-V-L-T-I-D-G-C 9

S-H-O-R-X-N-U-J-M-S 9


Zyklenlangen sind Fingerabdrucke der Walzenstellung

• Zyklenlangen sind unabhangig von der Steckbrettverschaltung!

• (4, 4, 9, 9) als grober Fingerabdruck von Walzenstellung undWalzenlage.

• gleiche Prozedur fur 2. und 5. Buchstaben.

• gleiche Prozedur fur 3. und 6. Buchstaben.

• Fingerabdruck: ((4, 4, 9, 9), (13, 13), (1, 1, 3, 3, 9, 9))


Tabelle aller Zyklenlangen

Walzen- Zyklenlangenstellung 1.7→4. Zeichen 2.7→5. Zeichen 3.7→6. Zeichen

AAA (13,13) (13,13) (13,13)AAB (13,13) (13,13) (1,1,12,12)AAC (13,13) (1,1,12,12) (13,13)AAD (1,1,12,12) (13,13) (4,4,9,9)AAE (13,13) (4,4,9,9) (1,1,12,12)AAF (4,4,9,9) (1,1,12,12) (13,13). . . . . . . . . . . .AAN (4,4,9,9) (13,13) (2,2,5,5,6,6)AAO (13,13) (2,2,5,5,6,6) (1,1,2,2,3,3,3,3,4,4)AAP (2,2,5,5,6,6) (1,1,2,2,3,3,3,3,4,4) (13,13)AAQ (1,1,2,2,3,3,3,3,4,4) (13,13) (13,13)AAR (13,13) (13,13) (1,1,12,12)AAS (13,13) (1,1,12,12) (2,2,11,11). . . . . . . . . . . .


Tabelle aller Zyklenlangen

• fur 6 · 263 = 105456 Anfangsstellungen bei Walzenlage I, II, III

• 1 Jahr Arbeit fur Rejewsky

• Im Mittel etwa 2.5 Walzenstellungen pro Fingerabdruck.


Kryptanalyse 2

Alan Turing: Erfinder der Turing Maschine

Cribs: Turing suchte nach Zyklen bei be-kanntem Klartext!

Stellung S S+1 S+2 S+3 S+4 S+5Klartext w e t t e r

↓ ↓ ↓Chiffretext E T J W P X

Zyklus: W–E–T–W


Kryptanalyse mit Colossus


Enigma Nachbauprojekt

• 2003: Erstellen von Handskizzen im Wehrtechnischen MuseumKoblenz

• 2003: CAD-Plane erstellt

• 2004: Firma KaVo Biberach startet Fertigung der Teile in derLehrwerkstatt

• 2010: erster funktionsfahiger ,,Rohbau”

• 2011: Publikationen des Artikels: An Enigma Replica andits Blueprints in Cryptologia. [EJHF11]

http://www.enigma.hs-weingarten.de

http://www.enigma.hs-weingarten.de


Das Original


Handskizzen


Handskizzen


CAD Plane


Walzen


Walzen


Nachbau


Original-Enigma mit Nachbau-Walzen


3.6 One-Time-Pad

Major J. Mauborgne und G. Vernam, AT&T, 1917.

z 7→ (z + r) mod 2 = z XOR r = z ⊕ r.

3.6 One-Time-Pad 103

001011011010111

110010111100101

111001100110010

Klartext

Folge von Zufallsbits

Chiffretext

Das One-Time-Pad ist eine Stromchiffre.

Definition 3.5 Ein Chiffriersystem heißt perfekt, wenn bei be-liebigem Klartext M und beliebigem Chiffretext C die a-priori-Wahrscheinlichkeit p(M) gleich der bedingten Wahrscheinlichkeit(a-posteriori-Wahrscheinlichkeit) p(M |C) ist, d. h.

p(M |C) = p(M). (3.3)


mit

p(M |C) =p(M ∧ C)

p(C)(3.4)

folgt

p(M ∧ C) = p(M) · p(C).

statistische Unabhangigkeit von Klartext M und Chiffretext C.

Definition 3.6 Eine Zahlenfolge (an) mit ai ∈ {0, 1} heißt(echte) Zufallsbitfolge, wenn die Werte 0 und 1 jeweils mitWahrscheinlichkeit 1/2 vorkommen und wenn es keine Moglich-keit gibt, aus der Kenntnis eines beliebig langen Anfangsstucksder Folge Informationen uber den Rest der Folge abzuleiten. (Sie-he auch Anhang 14.)


Lemma 3.1 Sei X eine Zufallsvariable zur Erzeugung einer echtenZufallsbitfolge. Dann gilt

P (x⊕ 0 = 0) = P (x⊕ 0 = 1) = 1/2 (3.5)

und P (x⊕ 1 = 0) = P (x⊕ 1 = 1) = 1/2. (3.6)

Beweis: Nach Voraussetzung gilt P (x = 0) = P (x = 1) = 1/2.Da x ⊕ 0 = x, ist fur die Gleichung 3.5 nichts zu zeigen. Dax ⊕ 1 = 1 fur x = 0 und x ⊕ 1 = 0 fur x = 1, werden die beidenWerte 0 und 1 fur X gerade vertauscht. Die Wahrscheinlichkeitenbleiben damit bei 1/2. 2


Satz 3.2 Wird ein One-Time-Pad mit einer echten Zufallsbitfolgebetrieben, so bietet es perfekte Sicherheit.

Beweis: Sei M die Menge aller Klartexte M der Lange n, Cdie Menge aller Chiffretexte C der Lange n und K die Menge allerSchlussel K der Lange n. Bei einem One-Time-Pad gilt

|M| = |C| = |K| =: m = 2n.

Da der Schlussel aus Zufallszahlen besteht, wird wegen Lemma 3.1fur einen beliebig vorgegebenen Klartext jeder Chiffretext mit dergleichen Wahrscheinlichkeit p(C) = 1/m erzeugt. Da es genau mSchlussel der Lange n gibt, gibt es genau m unterschiedliche Chif-fretexte zu jedem Klartext, die (wegen der Zufalligkeit der Schlussel)


alle mit der gleichen Wahrscheinlichkeit auftreten. Es gilt also

p(C|M) =1

m

Wendet man wie in Gleichung 3.4 die Definition der bedingtenWahrscheinlichkeit auchauf p(C|M) an, so erhalt man aus bei-den Gleichungen die bekannte (in Statistikbuchern zu findende)Bayes’sche Formel

p(C|M)p(M) = p(M |C)p(C).

Einsetzen ergibt1

mp(M) = p(M |C)

1

m,

woraus

p(M |C) = p(M)


folgt, was zu beweisen war. 2

Da es beim One-Time-Pad keine Moglichkeit gibt, aus einem be-liebig langen Chiffretext den Klartext zu rekonstruieren, erfullt esDefinition 2.1, das heißt es ist uneingeschrankt sicher.

Probleme:

• echte Zufallsbitfolge auf Digitalrechner nicht realisierbar.

• Pseudozufallszahlenfolge reduziert Sicherheit.

• ⇒ Verwendung physikalischen Rauschens.

• Schlusseltausch sehr aufwandig.

• Beispiel: Heisser Draht Moskau – Washington.

3.7 One-Time-Pad fast ohne Schlusseltausch 109

3.7 One-Time-Pad fast ohne Schlusseltausch

New York Times [Kol01] behauptet:Schlusseltauschproblem beim One-Time-Pad gelost.

zitiert Michael Rabin u. Doktorand Yan Zong Ding


d2=98/(&gkhj$§x"n),.=,(

Alice Bob

Alice speichert Bits Bob speichert Bits

8:12 E (9:46:34.79)

9:46:34.79

9:50

3.7 One-Time-Pad fast ohne Schlusseltausch 111

schon 1997 publiziert von Ueli Maurer, Christian Cachin [CM97,Mau01]sowie 1999 von Rabin und Aumann [AR99]

Kapitel 4

Moderne Blockchiffren

Prolog

Gesamtzahl aller Chiffren mit Blocklange 64 Bit = 264!

Schlussellange = log2(264!)

113

Stirlingsche Formel:

ln(n!) ≈ (n + 1/2) lnn− n + 1/2 ln(2π)

also werden

log2(264!) =1

ln 2ln(264!) ≈ 1

ln 2

(264 +

1

2

)ln(264)

=1

ln 2

(264 +

1

2

)log2(264) ln 2 ≈ 264 · 64 = 270 ≈ 1021

Bit benotigt. Das sind etwa 1011 GByte.

109 Festplatten a je 100 GByte

zus. etwa 500 000 Tonnen schwer.

114 4 Moderne Blockchiffren

4.1 Data-Encryption-Standard DES

Claude Shannon (1949): Geheimtext ist durch Konfusion und Dif-fusion aus dem Klartext zu bilden.

Horst Feistel [Fei73], IBM:

LUCIFER: 64-Bit-Blocken und 128-Bit-Schlussel

Vorganger von DES.

Bruce Schneier in [Sch96]:

4.1 Data-Encryption-Standard DES 115

Inoffiziell bezeichnete die NSA den DES als einen ihrer großten Fehler. Hatte die Behorde ge-wusst, dass die Einzelheiten herausgegeben und Software-Implementierungen moglich wurden,hatte sie niemals zugestimmt.


Geschichte von DES

vor 1970: wurde Kryptographie im Wesentlichen zur militarischen Kommunikation genutzt.Durch das Aufkommen der elektronischen Datenverarbeitung entsteht Bedarf zum Ver-schlusseln von Daten und zur Authentifikation.

Mai 1973: das NIST (National Institute of Standards and Technology, USA) startet eineoffentliche Ausschreibung fur einen standardisierten kryptographischen Algo-rithmus.

August 1974: Mangels qualifizierter Einreichungen veroffentlicht das NIST eine zweite Aus-schreibung. Schließlich wird ein Algorithmus eingereicht.

17.3.1975: Im amerikanischen Bundesanzeiger werden Einzelheiten eines von IBM ent-wickelten und von der NSA (National Security Agency) gepruften Algorithmusveroffentlicht.

1.8.1975: Im amerikanischen Bundesanzeiger wird die Offentlichkeit zu Stellungnahmenaufgefordert, die dann im Folgenden die undurchschaubare Rolle der NSA kritisierten.


15.6.1977: Der Data-Encryption-Standard wird veroffentlicht. Unter anderem schreibtder Standard eine Zertifizierung von DES-Implementierungen durch das NIST vor.Außerdem muss DES alle funf Jahre uberpruft werden.

1981: ANSI (American National Standards Institute) erkennt DES als Standard an.

1982-1986: Basierend auf DES werden Standards fur die Verschlusselung von PINs, furdie verschiedensten Finanztransaktionen, zur Schlusselverteilung sowie fur Telekommu-nikation und FAX definiert.

1983: DES wird gepruft und ohne Probleme neu zertifiziert.

1987: Nach langen Debatten wird DES neu zertifiziert.

1993: DES wird erneut zertifiziert (mit der Bemerkung, dass es Ende der 90er Jahre uberholtsein wurde).

1994: Mit einem Rechenaufwand von 50 Tagen auf 12 HP-9735-Workstations wurde DESerstmals geknackt.

1997: NIST kundigt die Entwicklung des Advanced-Encryption-Standard (AES) an.

17.7.1998: Die Electronic Frontier Foundation (EFF) knackt DES mit einem Spe-zialchip in weniger als drei Tagen.


19.4.1999: 100 000 PCs von Distributed.net und der EFF Spezialrechner knackenDES in 22 Stunden, 15 Minuten.


Ubersicht

Eingangspermutation

Klartext

0 0

K 1

1 1

K 2

2 2

15 15

K 16

1616

Schlusspermutation

Chiffretext

f

f

f

L R

R

L R

L R

RL

L


Die DES-Permutationen

liest man die Tabellen zeilenweise von links oben nach rechts unten, so bedeutet eine Zahl zan Position i, dass das Bit z auf Bit i abgebildet wird

Einganspermutation:

58 50 42 34 26 18 10 2 60 52 44 36 28 20 12 462 54 46 38 30 22 14 6 64 56 48 40 32 24 16 857 49 41 33 25 17 9 1 59 51 43 35 27 19 11 361 53 45 37 29 21 13 5 63 55 47 39 31 23 15 7

Schlusspermutation:

40 8 48 16 56 24 64 32 39 7 47 15 55 23 63 3138 6 46 14 54 22 62 30 37 5 45 13 53 21 61 2936 4 44 12 52 20 60 28 35 3 43 11 51 19 59 2734 2 42 10 50 18 58 26 33 1 41 9 49 17 57 25


Kompressionspermutation:

14 17 11 24 1 5 3 28 15 6 21 1023 19 12 4 26 8 16 7 27 20 13 241 52 31 37 47 55 30 40 51 45 33 4844 49 39 56 34 53 46 42 50 36 29 32

Expansionspermutation:

32 1 2 3 4 54 5 6 7 8 98 9 10 11 12 13

12 13 14 15 16 1716 17 18 19 20 2120 21 22 23 24 2524 25 26 27 28 2928 29 30 31 32 1


P-Box-Permutation:

16 7 20 21 29 12 28 17 1 15 23 26 5 18 31 102 8 24 14 32 27 3 9 19 13 30 6 22 11 4 25

Schlusselpermutation:

57 49 41 33 25 17 9 1 58 50 42 34 26 1810 2 59 51 43 35 27 19 11 3 60 52 44 3663 55 47 39 31 23 15 7 62 54 46 38 30 2214 6 61 53 45 37 29 21 13 5 28 20 12 4

Schlusselverschiebungen:

Runde 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16Anzahl 1 1 2 2 2 2 2 2 1 2 2 2 2 2 2 1


f

48 Bit

32 Bit

32 Bit

32 Bit

28 Bit28 Bit

32 Bit

i

11

48 Bit

��

��

��

Kompressionspermutation

Schlüssel

Schlüssel

Li iR

Shift Shift

Expansionspermutation

S−Box−Substitution

P−Box−Permutation

R

K

i−Li−


Die S-Box-Transformation

S−Box 1 S−Box 2 S−Box 3 S−Box 4 S−Box 5 S−Box 6 S−Box 7 S−Box 8

32 Bit Ausgabe

48 Bit Eingabe


Die S-Boxen von DES

...

S-Box 5:

2 12 4 1 7 10 11 6 8 5 3 15 13 0 14 914 11 2 12 4 7 13 1 5 0 15 10 3 9 8 64 2 1 11 10 13 7 8 15 9 12 5 6 3 0 14

11 8 12 7 1 14 2 13 6 15 0 9 10 4 5 3...

Beispiel 4.1 Angenommen, die Eingabe der S-Box 5 ist binar’110100’. Die Bits 1 und 6 ergeben den Zeilenindex 2, das heißtdie dritte Zeile in S-Box 5 und die restlichen Bits fuhren zu Spalte10, wo wir die Zahl 12 finden. Die Ausgabe der S-Box lautet also’1100’.


Die 16 Teilschlussel

gleicher Algorithmus wird zur Entschlusselung benutzt.

Die Teilschlussel werden in umgekehrter Reihenfolge angewendet.

Schwache Schlussel

Beispiel:

00000000000000000000000000001111111111111111111111111111111

alle Teilschlussel sind identisch!


Der Lawineneffekt

M1 = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000

M2 = 00000000 00000000 00000000 00000000 00000000 00000000 00000000 00000001

0

5

10

15

20

25

30

35

0 2 4 6 8 10 12 14 16

Ham

min

gdis

tanz

(M1,

M2)

Runde

Zwei Blocke M1, M2.

0

5

10

15

20

25

30

35

0 2 4 6 8 10 12 14 16

Ham

min

gdis

tanz

(M1,

M2)

Runde

Mittelwert uber 1000 zufallig erzeugte Klar-textblocke M1, M2.


Sicherheit und Nichtlinearitat

Eine Funktion f heißt linear, wenn fur alle Argumente x und y gilt

f (x⊕ y) = f (x)⊕ f (y),

• Jede lineare Funktion ist ahnlichkeitserhaltend

• Kleine Anderungen im Argument bewirken kleine Anderungenim Ergebnis.



Fur M4 = M3 ⊕M2 gilt

f (M4) = f (M3 ⊕M2) = f (M3)⊕ f (M2).

Aus Kenntnis der Chiffretexte f (M3) und f (M2) lasst sich ganzeinfach der Chiffretext f (M4) ermitteln.



• Lineare Abbildung: 64× 64-Matrix mit Elementen aus {0, 1}• 64×64-Matrix ist eindeutig bestimmt durch 64 linear unabhangi-

ge Klartextblocke und deren Chiffretexte.

• siehe Aufgabe ?? (Hill-Chiffre)

Differentielle Kryptanalyse:

247 gewahlte Klartextblocke und deren Chiffretext werden fur einenKnown-Plaintext-Angriff benotigt!



Alle DES Permutationen sind linear!

Die Permutation

3 1 4 5 2

wird dargestellt durch die Matrix0 0 1 0 01 0 0 0 00 0 0 1 00 0 0 0 10 1 0 0 0


Sicherheit und Geschwindigkeit

• 1996, auf HP 9000, 125 MHz: 196 000 DES-Blocke proSekunde

• Software-Implementierungen heute: ≥ 106 Blocke pro Sekunde.

• Bei Schlusselraum der Große 256 ≈ 7.2 · 1016 waren etwa 1 142Jahre fur einen Brute-Force-Angriff notig.


Sicherheit und Geschwindigkeit

Spezialrechner der EFF:

• Wert: 250 000 US$,

• Taktfrequenz: 40 MHz

• 9.22 · 1010 Blocke pro Sekunde.

RSA-DES-Challenge-III:

• 100 000 weltweit vernetzte PCs von Distributed.net und der Spe-zialrechner [EFF99] knacken DES in 22 Stunden.


• Rechenleistung: 2.45 · 1011 Blocke pro Sekunde.


Triple-DES

C = EK1(DK2(EK1(M))).

Geschwindigkeiten von Hardware-Implementierungen:> hundert Me-gabit pro Sekunde.


4.2 Advanced-Encryption-Standard AES

Anforderungen:

Formal muss AES eine symmetrische Blockchiffre sein, welche aufeiner Blockgroße von 128 Bit bei Schlussellangen von 128, 192und 256 Bit arbeitet.

Sicherheit gegen Angriffe aller Art und mathematische Rechtfer-tigung der Sicherheit.

Einfachheit des Designs.

Flexibilitat: AES soll auch andere Blockgroßen und Schlussel-

4.2 Advanced-Encryption-Standard AES 137

langen unterstutzen.

Effizienz: AES soll effizienter als Triple-DES sein.

Offenheit: AES soll offentlich, lizenzfrei, weltweit verfugbar sein.

Implementierung in Hardware und Software soll einfach sein.

Wettbewerb zur Ermittlung des besten Algorithmus.


Geschichte von AES


2.1.1997: Start der AES Entwicklungsanstrengungen durch NIST.

12.9.1997: “call for algorithms” fur AES.

20.8.1998: Auf AES Candidate Conference 15 AES-Kandidaten. NIST bittet um Kommen-tare.

15.4.1999: Kandidaten fur das Finale: MARS, RC6, Rijndael, Serpent, Twofish. NIST bittetoffentlich um Kommentare.

13.-14.4.2000: Dritte AES Candidate Conference (AES3) mit offentlichen Diskussionen derfunf Algorithmen.

15.5.2000: Abgabeschluss fur offentliche Kommentare.

2.10.2000: Bekanntgabe des Gewinners Rijndael von J. Daemen und V. Rijmen.

bis Feb. 2001: Offentliche Kommentare zu AES erwunscht.

Ende 2001: AES soll “federal information processing standard” (FIPS) werden.


AES-Wettbewerb

2. Oktober 2000, Sieger des Wettbewerbs:

• Rijndael (Algorithmus)

• entwickelt von Joan Daemen und Vincent Rijmen in Bel-gien [DR99].

Laut NIST erfullten alle funf Kandidaten der Endrunde die gestelltenSicherheitsanforderungen.


Die Blockchiffre Rijndael

Zahl der Runden von Rijndael, abhangig von Blockgroße b undSchlussellange k:

r b = 128 b = 192 b = 256

k = 128 10 12 14k = 192 12 12 14k = 256 14 14 14


Zustand (li.) und Schlussel (re.) in Rijndael

a0,0 a0,1 a0,2 a0,3

a1,0 a1,1 a1,2 a1,3

a2,0 a2,1 a2,2 a2,3

a3,0 a3,1 a3,2 a3,3

k0,0 k0,1 k0,2 k0,3 k0,4 k0,5

k1,0 k1,1 k1,2 k1,3 k1,4 k1,5

k2,0 k2,1 k2,2 k2,3 k2,4 k2,5

k3,0 k3,1 k3,2 k3,3 k3,4 k3,5


Runde 2

Runde 1

S

S

K

K

K

2

1

0

0

1

S

K

K11

11

12

Runde 12

Chiffretextblock (128 Bits)

Klartextblock (128 Bits)

Schlüsselexpansion

Schlüssel (192 Bits)

S i

K i

i−1S

Runde i

ByteSub

ShiftRow

MixColumn


Die ByteSub-Transformation

• Stellt die nichtlineare S-Box von AES dar.

• Wird auf jedes Byte des Zustands angewendet.

Ablauf:

1. Berechnen der multiplikativen Inversen in GF (28).


2. affine Transformation

y0

y1

y2

y3

y4

y5

y6

y7

=

1 0 0 0 1 1 1 11 1 0 0 0 1 1 11 1 1 0 0 0 1 11 1 1 1 0 0 0 11 1 1 1 1 0 0 00 1 1 1 1 1 0 00 0 1 1 1 1 1 00 0 0 1 1 1 1 1

·

x0

x1

x2

x3

x4

x5

x6

x7

+

11000110

.

Umkehrung von ByteSub:inverse affine Transformation gefolgt von der multiplikativen Inver-sen in GF (28).


Die ShiftRow-Transformation


Linksverschiebungen von ShiftRow

b = 128 b = 192 b = 256

c1 1 1 1c2 2 2 3c3 3 3 4

ShiftRow verschiebt die Zeilen 1 bis 3 der Zustandsmatrix zyklischnach links.

Zeile 0 wird nicht verandert.

Zeile 1 wird um c1 Bytes, Zeile 2 um c2 Bytes und Zeile 3 um c3

Bytes verschoben.

Umkehrung von ShiftRow:


Ausfuhren der zyklischen Verschiebungen nach rechts.


Die MixColumn-Transformation

bildet jede Spalte (a0,i, a1,i, a2,i, a3,i) des Zustands ab durch02 03 01 0101 02 03 0101 01 02 0303 01 01 02

a0,i

a1,i

a2,i

a3,i

.

Die Matrixelemente sind Bytes in hexadezimaler Darstellung.

Jedes Byte entspricht einem Polynom in GF (28)!

Die MixColumn-Transformation ist invertierbar (siehe Abschnitt 13.5.1bzw. [DR99]).


Die Schlusselexpansion (k ≤ 192)

Erzeugung der Rundenschlussel:

192-Bit Chiffrierschlussel . . .W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 . . .128-Bit-Schl. Runde 1 128-Bit-Schl. Runde 2 . . .

arbeitet auf 32-Bit-Worten

Bei Blocklange 128 Bit und zwolf Runden werden 128 · 13 = 1 664Schlusselbits benotigt. Fur Schlussellangen bis 192 Bit wird folgen-des Verfahren verwendet.

Bits 1 ... k = Schlussel.


DannWi = Wi−1 ⊕Wi−k/32

Fur i = l · k: vor dem XOR wird nichtlineare Substitution (S-Box)auf Wi−1 angewendet (siehe [DR99]).


Die inverse Chiffre

Ersetze jede Transformation durch ihre Inverse und kehre derenReihenfolge um!


Geschwindigkeit

AES ist

• etwa 3 mal schneller als DES.

• etwa 9 mal schneller als Triple-DES.

bei Schlussellange 192 Bit, Blocklange 128 Bit auf

• 200-MHz-Pentium-Pro: 22 bis 59 MBit/sec.

• 1000-MHz-Rechner: 200 MBit/sec.

Rijndael ist einfach implementierbar

• auf Parallelrechnern


• in Hardware (> 1 Gbit/Sec.)

• auf 8-Bit-Prozessoren von Chipkarten (≈ 1 KB Speicherplatz)


Sicherheit

• Sicherheit wurde theoretisch untersucht.

• Input-Output-Korrelationen sehr schwach

• Rijndael ist gegen differentielle Kryptanalyse und gegen li-neare Kryptanalyse resistent.

• Alle Angriffe der Konkurrenten waren erfolglos.

Die Benutzer konnen in sehr hohem Maße auf die Sicherheit vonAES vertrauen.


Andere Funktionalitaten

Rijndael laßt sich einsetzen als

• Message-Authentication-Code (MAC, Abschnitt 6.7)

• Einweg-Hash-Funktion (Abschnitt ??)

• Stromchiffre

• Pseudozufallszahlengenerator

4.3 Betriebsmodi von Blockchiffren 157

4.3 Betriebsmodi von Blockchiffren


ECB-Modus (electronic codebook):

• Monoalphabetische Chiffre

• Verschlusseln eines Blocks nach dem anderen mit dem gleichenSchlussel

• Es ist einfach, Wiederholungen von Blocken im Chiffretext zufinden

• Angreifer kann gezielt bestimmte Blocke ersetzen, loschen oderneue einzufugen.


CBC-Modus (cipher block chaining):

C0 = EK(M0)

C1 = EK(C0 ⊕M1)...

Ci = EK(Ci−1 ⊕Mi)...

EK EK EK EK

M 0 M M M1 2 3

.....

.....

0 1 2 3.....C C CC


Initialisierungsvektor (IV):

• Erster Block wird zufallig gefullt.

• Gleiche Klartexte werden unterschiedlich verschlusselt (im CBC-Modus).

• wird in vielen Anwendungen eingesetzt.

Padding: Auffullen des letzten Blocks mit Zufallsbits.


Andere Blockchiffren

Nane Entwickler Jahr Bemerkungen

IDEA James Massey(ETH) Zurich

1990 Wird in PGP eingesett und gilt als sehr sicher

Blowfish Bruce Schneier(Counterpane)

1994 Feistel-Chiffre S-Boxen sind schlusselabhangig. Ei-ner der sichersten Blockalgorithmen

Twofish Bruce Schneier(Counterpane)

1998 Feistel-Chiffre mit bijektiven schlusselabhangigen8x8-Bit-S-Boxen, GF (28). AES-Kandidat

RC2 Ron Rivest (MIT,RSA-Security)

1992 Wird eingesetzt in S/MIME mit Schlussellangen von40 bis 128 Bit

RC5 Ron Rivest 1995 var. Blockgroßen, Schlussel, Rundenzahlen

RC6 Ron Rivest 1998 AES-Kandidat

Serpent R. Anderson, E.Biham, L. Knudsen

1998 Feistel-Netz mit 32 Runden, konservatives Design,Platz 2 beim AES-Wettbewerb

MARS Don Coppersmith(IBM)

1999 Typ-3-Feistel-Netz, AES-Kandidat


Kapitel 5

Public-Key-Kryptographie

• Internet-Zeitalter

• Schlusseltauschproblem

• Mitte der 70er Jahre:

• Diffie-Hellmann-Algorithmus

• RSA-Algorithmus

164 5 Public-Key-Kryptographie

• ElGamal

5.1 Merkles Ratsel 165

5.1 Merkles Ratsel

Ralph Merkle, Student, Univ. of California, Berkeley, 1974:

Losung fur das Schlusseltauschproblem

vor Erfindung der Public-Key-Kryptographie


Alice unsicherer Kanal Boberzeugt zufallig

Nummern (x1, . . . , xn)Schlussel (y1, . . . , yn)Schlussel (k1, . . . , kn)

↓

wahlt j ∈ {1, . . . , n} ←− Ratsel ←−

berechnet

Ratsel =

Ek1(x1, y1)...

Ekn(xn, yn)

↓ ↓

knackt kj mitBrute-Force-Angriff

↓ speichert DB =

(x1, y1)...

(xn, yn)

(xj, yj) = Dkj(Ratselj)

↓ ↓chiffriert C = Eyj(M) −→ (C, xj) −→ sucht xj in DB

↓dechiffriert M = Dyj(C)

5.1 Merkles Ratsel 167

Warum ist dieses Verfahren sicher?

• Angreiferin Eve muß alle Ratsel losen, bis sie die Nummer xjfindet.

• Schlusselraum mit genau n Schlusseln, die bekannt sein durfen.

• Bob und Alice konnen ca. 10 000 Schlussel pro Sekunde testen.

• Sei n = 220.

• Bob chiffriert in zwei Minuten 220 = 1 000 000 Paare (xi, yi).

• Alice kann in zwei Minuten alle 220 Schlussel ki testen.

• Eve muss fur 220/2 Nachrichten je 220 Schlussel testen.

• Aufwand: ca. 636 Tage


Der Aufwand von Alice und Bob wachst linearmit n.Der Aufwand von Eve wachst quadratisch mitn.

5.2 Der RSA-Algorithmus 169

5.2 Der RSA-Algorithmus

Ron Rivest, Adi Shamir, Leonard Adleman, 1978

Der RSA-Algorithmus war patentiert bis September 2000.

• Rivest arbeitete neuen Versionen des Algorithmus,

• Shamir durch Angriffe und mathematische Analysen die Schwachendes Algorithums auf.

• Adleman wirkte auf beiden Seiten mit.


Der Algorithmus

(zuerst die Anwendung, dann die Schlusselerzeugung)

Definition 5.1 (Anwendung von RSA)

Verschlusseln: Die Nachricht M ∈ Zn wird codiert durch

E(M) = M e mod n. (5.1)

Entschlusseln: Ein Chiffretext C ∈ Zn wird decodiert durch

D(C) = Cd mod n. (5.2)


Definition 5.2 (Schlusselerzeugung)

1. Wahle zufallig zwei große Primzahlen p und q. Die Lange derZahlen sollte mind. 512 Bit gewahlt werden.

2. Berechne n = pq (n hat dann eine Lange 1024 Bit.).

3. Wahle eine kleine ungerade naturliche Zahl e, die zuϕ(n) = (p− 1)(q − 1) relativ prim ist, d. h. es giltggT(e, ϕ(n)) = 1.

4. Berechne d als Losung der Gleichung ed = 1 mod ϕ(n).Aufgrund von Satz 13.8 existiert d und ist eindeutigbestimmt. d kann berechnet werden mit dem erweitertenEuklidischen Algorithmus.

5. Gib das Paar P = (e, n) bekannt als offentlichenSchlussel.

6. Halte das Paar S = (d, n) geheim als geheimen Schlussel.



Beispiel 5.1 Wir wahlen p = 61 und q = 97 und erhalten

n = pq = 5917,

ϕ(n) = (p− 1)(q − 1) = 60 · 96 = 5760.

wahle e = 47 (teilerfremd zu 5760) und berechne mit erw. Euklid:

d = 47−1 mod 5760 = 1103.

Verschlusselung der Nachricht M = 348 613 407 195 771 184

34847 mod 5917 = 4479.

Chiffretext: C = 4479 1333 3931 2523 3725 1038Entschlusseln des ersten Blocks:

44791103 mod 5917 = 348.


Satz 5.1 (Korrektheit des RSA-Algorithmus) Der RSA-Algorithmus ist korrekt, d.h. ∀M ∈ Zn

D(E(M)) = E(D(M)) = M.

Beweis: Aus Gln. 5.1 und 5.2 folgt

D(E(M)) = E(D(M)) = M ed mod n.

Zu zeigen: M ed ≡ M mod n Da e und d multiplikative InverseModulo ϕ(n) = (p− 1)(q − 1) sind, gibt es ein k ∈ N mit

ed = 1 + k(p− 1)(q − 1).


Fur M 6≡ 0 mod p gilt

M ed ≡ M 1+k(p−1)(q−1) mod p = M(M p−1)k(q−1) mod p

= M · 1k(q−1) mod p = M mod p,

wobei wir in der dritten Gleichung den Satz 13.5 (Fermatschen) be-nutzt haben. Analog berechnet man M ed ≡ M mod q. Folgerungdes Chinesischen Restsatzes: Fur Primzahlen p und q gilt:

x ≡ a mod p ∧ x ≡ a mod q ⇔ x ≡ a mod pq.

Damit folgt sofort M ed ≡M mod pq = M mod n. 2


Sicherheit von RSA

Angriff:Zerlegung von n in ihre Primfaktoren p und q

Einfacher Algorithmus:Sieb des Eratosthenes: Zerlegung durch Probieren

Rechenzeit T (n) = c√n.

b-Bit-Zahl n: n ≈ 2b

T (b) ≤ c ·√n ≈ c ·

√2b = c ·

√2b,

besser: Zahlkorpersieb (number field sieve)

T (b) = e(1.70+O(1))·b1/3·(ln b−0.366)2/3. (5.3)


TABLE 1: Historical Factoring Records [Sil00]Year Size Number Who Method Hardware

1970 39 2128 + 1 Brillhart/Morrison CFRAC IBM Mainframe

1978 45 2223 - 1 Wunderlich CFRAC IBM Mainframe

1981 47 3225 - 1 Gerver QS HP-3000

1982 51 591 - 1 Wagstaff CFRAC IBM Mainframe

1983 63 1193 + 1 Davis/Holdridge QS Cray

1984 71 1071 - 1 Davis/Holdridge QS Cray

1986 87 5128 + 1 Silverman MPQS LAN Sun-3?s

1987 90 5160 + 1 Silverman MPQS LAN Sun-3?s

1988 100 11104 + 1 Internet MPQS Distributed

1990 111 2484 + 1 Lenstra/Manasse MPQS Distributed

1991 116 10142 + 1 Lenstra/Manasse MPQS Distributed

1992 129 RSA-129 Atkins MPQS Distributed

1996 130 RSA-130 Montgomery GNFS Distributed



2005 174 RSA-576 Bahr, Boehm et.al. GNFS 30 2.2GHz-Opteron-CPU-Jahre

2009 232 RSA-768 Kleinjung et.al. GNFS 2000 2.2GHz-Opteron-CPU-Jahre


Entwicklung der Faktorisierungaus [Sil00]


Silverman [Sil00]:One thing surprising about this data is that it is VERY linear. A simple least-squares fit

yields the equation: Size = 4.23 * (Year - 1970) + 23. The correlation coefficient is about

.955. This is somewhat puzzling. The algorithms are sub-exponential. That is, their run time

grows more slowly than an exponential function. Moore’s law is strictly exponential. It would

seem, therefore, based on theoretical grounds that this curve should be growing FASTER

than linearly. A possible explanation for this is that even though records continue to be

established, that over time the level of effort applied to each effort has dropped. Breaking

RSA-129 required a large effort involving many thousands of machines widely distributed over

the Internet. Compared with that, breaking RSA-512 was done by a relatively small group of

people using far fewer (albeit much faster) machines. If we solve for when a 1024-bit number

may be expected to be factored, based solely on extrapolating this historical data, we get an

answer of around 2037.


Folgerungen

• 1024-Bit-Modul musste etwa im Jahr 2037 faktorisiert sein.

• Die Firma RSA-Security empfiehlt (im Jahr 2010) eine Mindest-schlussellange von 1369 Bit.

• Empfehlung des Autors (Jahr 2001): 1024 Bit


Sicherheit von RSA

• Man hat bis heute aber noch nicht bewiesen, dass die Sicherheitvon RSA auf dem Problem der Faktorisierung großer Zahlenberuht.

• Die Faktorisierung von großen Primzahlen ist ein sehr schwie-riges Problem. Die Experten glauben, dass es kein effizientes(polynomielles) Verfahren zur Faktorisierung gibt. Bewiesen istdies jedoch nicht.

• Man weiss auch nicht, ob die Faktorisierung in der Klasse Poder in NP\ P liegt (Vorausgesetzt dass P 6= NP).


Uber die Sicherheit von RSA in 50 Jahren kann daher heute niemandeine definitive Aussage machen.


Effiziente Primzahltests

Der Primzahltest von Miller und Rabin basiert auf folgendem Satz:

Satz 5.2 Sei n eine erlaubte Zahl, d. h. eine ungerade Zahl furdie auch n−1

2 ungerade ist. Dann gilt:

1. n prim ⇒ an−1

2 = ±1 fur alle a ∈ Zn\{0}2. n nicht prim ⇒ a

n−12 = ±1 fur hochstens die Halfte der a ∈ Zn\{0}.

Darauf basiert folgender Test [Str96]:

Statistischer Primzahltest fur erlaubte Zahlen n:


1. Wahle Zufallszahlen a1, . . . , ak aus {1, . . . , n− 1}

2. Berechne an−1

2i in Zn

3. Falls alle an−1

2i = ±1, entscheide: n prim

sonst entscheide: n nicht prim.

Der Test ist korrekt falls n prim.

Ist jedoch n nicht prim, so kann es sein, dass der Test antwortet:prim.

Fehlerwahrscheinlichkeit ≤ (12)k


Gibt es genug Primzahlen?

Satz 5.3 Die Zahl π(n) der Primzahlen unterhalb n ist fur großen naherungsweise durch

π(n) ≈ n/ lnn

gegeben.

Damit lasst sich die Zahl der Primzahlen mit einer Lange bis zu 512Bit berechnen:

π(2512) ≈ 2512

512 ln 2≈ 1.34 · 10154

354.9≈ 3.8 · 10151


• Eine Festplatte mit diesen Zahlen wurde aufgrund ihrer Massezu einem schwarzen Loch kollabieren (siehe [Sch96]).

• Von 355 Zufallszahlen der Lange 512 Bit ist im Mittel etwa eineprim.


Effizienz und Implementierung von RSA

Me mod n

1024-Bit-Zahl M , 1024-Bit-Exponent e!

Beispiel 5.2

a19 = a24+2+1 = a2·2·2·2 · a2 · a = (((a2)2)2)2 · a2 · a.


Berechnung von ab mod n:

Modular-Exponent(a, b, n)d := 1for i := k downto 0 do

d := (d · d) mod nif bi = 1 thend := (d · a) mod n

return d


Beispiel 5.3 Berechnung von a19:

19 = 1 0 0 1 1

d = 1 · 1 = 1 i = 4d = 1 · a = a

d = a · a = a2 i = 3

d = a2 · a2 = a4 i = 2

d = a4 · a4 = a8 i = 1d = a8 · a = a9

d = a9 · a9 = a18 i = 0d = a18 · a = a19


Komplexitat: O(k3) Bit-Operationen


Laufzeiten

• Software-Implementierungen von RSA sind etwa 100-mal lang-samer als DES.

• Hardware-Implementierungen von RSA sind etwa 1000-mal lang-samer als DES.

• Auf SUN SPARC II mit 512 Bit Modul sind beim Verschlusseln17 KBit/sec. und beim Entschlusseln 3.2 KBit/sec. moglich.

• In Planung sind Chips mit 1 Megabit/sec.


Schnellere Implementierung von RSA

[MvOV97, KR01].

Geheimer Schlussel wird geandert von (d, n) in (d, n, p, q, p)

mit d, n, p, q aus Definition 5.2 und p = p−1 mod q sowie p < q.

Der offentliche Schlussel bleibt unverandert (e, n).

Signatur eines Dokuments M

Die Signatur S wird erzeugt durch:


S1 = Md mod p (5.4)

S2 = Md mod q (5.5)

h = p · (S2 − S1) mod q (5.6)

S = (S1 + p · h) mod n (5.7)

Satz 5.4 Mit e, d, n, p, q wie in Definition 5.2 und p = p−1 modq gilt S = S1 + p · h = Md mod n, d. h. das geanderte Verfahrenimplementiert RSA korrekt.

Beweis: Wir zeigen, dass S1 +p ·h ≡Md mod p und S1 +p ·h ≡Md mod q und wenden dann den chinesischen Restsatz an. Es gilt

(S1 + p · h) mod p = (S1 + p[ p · (S2 − S1) mod q]) mod p

= S1 mod p = Md mod p


(S1 + p · h) mod q = (S1 + p[ p · (S2 − S1) mod q]) mod q

= S1 mod q + (pp) mod q · (S2 − S1) mod q

= S1 mod q + S2 mod q − S1 mod q

= S2 mod q = Md mod q

Mit dem chinesischen Restsatz folgt S1 + p · h ≡ Md mod p q =Md mod n. 2

• Die Rechenzeit verringert sich bei diesem Verfahren etwa umden Faktor vier.

• Sicherheitslucke im OpenPGP-Standard, basierend auf dieserOptimierung (siehe Abschnitt 6.4).


Angriffe gegen RSA


Angriff ErkenntnisChosen-Ciphertext-Angriff gegenRSA-Signatur.

1. Niemals beliebige. 2. Vor demSignieren immer eine Einweg-Hash-Funktion anwenden (Ab-schnitt 6.3).

Angriff gegen RSA mit gemeinsa-mem Modul n.

Eine Benutzergruppe darf niemalsden gleichen Wert fur n wahlen.

Bei kleinem Verschlusselungsex-ponenten e und kurzen Nachrich-ten.

Nachrichten vor der Verschlusse-lung auffullen.

Angriff gegen RSA mit kleinemEntschlusselungsexponenten d.

Großes d wahlen. Dies ist bei klei-nem e automatisch der Fall.

Angriff moglich, wenn zuerst ver-schlusselt und dann signiert wur-de.

Immer zuerst signieren und dannverschlusseln.

5.3 Angriffe gegen Public-Key-Verfahren 197

5.3 Angriffe gegen Public-Key-Verfahren

• Chosen-Plaintext-Angriff

• Brute-Force-Angriff auf kurze Nachrichten

• Angriffe aufgrund von Seiteneffekten


Angriffe aufgrund von Seiteneffekten

• Angriff neuer Dimension gegen Kryptosysteme

• 1995 entdeckt von Paul Kocher

• timing-attack

• simple power analysis

• differential power analysis DPA


Rechenzeiten sind vom Schlussel abhangig

Modular-Exponent(a, b, n)d := 1for i := k downto 0 do

d := (d · d) mod nif bi = 1 thend := (d · a) mod n

return d


Abwehrmaßnahmen

• Modular-Exponent so verandern, dass die Laufzeit kon-stant wird.

• An Modular-Exponent kurze Warteschleife mit zufalligerDauer anhangen.

• Blenden des Gegners:

1. Erzeuge eine Zufallszahl r zwischen 0 und n− 1, die teiler-fremd zum Modul n ist..

2. Berechne c′ = cre mod n, wobei e der offentliche Exponentist.

3. Berechne m′ = (c′)d mod n mit Modular-Exponent.


4. Berechne m = m′r−1 mod n (Ubung ??).

Laufzeit fur Dechiffrierung unabhangig vom Chiffretext c.

Angriffe aufgrund von Seiteneffekten sind prinzipiell bei allen Kryp-tosystemen moglich.


5.4 Schlusseltausch

5.4 Schlusseltausch 203

Schlusseltausch mit symmetrischen Verfahren

E (k)kB

E (k)kB

E (k)kA

Alice

Trent

Bob

Bitte um

Sitzungsschlüssel

Abbildung 5.1: Schlusseltausch via Trustcenter


Man-in-the-Middle-Angriff

BobAlice Mallory

P

PP

PA M

M B

Bei der Verwendung eines fremden offentlichen Schlussels mussmoglichst immer die Authentizitat des Schlussels gepruft bzw. si-chergestellt werden.


Das Interlock-Protokoll

1. Alice sendet Bob ihren offentlichen Schlussel.

2. Bob sendet Alice seinen offentlichen Schlussel.

3. Alice chiffriert ihre Nachricht mit Bobs offentlichem Schlusselund sendet die Halfte davon an Bob.

4. Bob chiffriert seine Nachricht mit Alices offentlichem Schlusselund sendet die Halfte davon an Alice.

5. Alice schickt Bob die zweite Halfte ihrer verschlusselten Nach-richt.

6. Bob schickt Alice die zweite Halfte seiner verschlusselten Nach-richt.


7. Bob fugt die beiden Halften von Alices Nachricht zusammenund dechiffriert sie mit seinem geheimen Schlussel.

8. Alice fugt die beiden Halften von Bobs Nachricht zusammenund dechiffriert sie mit ihrem geheimen Schlussel.


Hybride Verschlusselung

Alice unsicherer BobKanal

wahlt zufalligenSitzungsschlussel k

symmetrisch:

verschlusselt C = Ek(M)public key:

verschlusselt Ck = EPB(k)(Ck ,C )−−−−−−−→ entschlusselt k = DSB(Ck)

entschlusselt M = Dk(C)



Perfect Forward Secrecy1

• NSA kann C und Ck speichern.

• Evtl. nach Jahren:

– Geheimer Schlussel bekannt (z.B. social Engineering), oder

– offentlicher Schlussel geknackt, oder

– RSA geknackt

• Abhilfe: Perfect Forward Secrecy = Diffie Hellman Algorithmus

1Jurgen Schmidt, Verpfuschte Verschlusselung, c’t Heft 18, 2013.


5.5 Der Diffie-Hellmann-Algorithmus

Whitfield Diffie, Martin Hellmann, 1976:

• Austausch eines geheimen Sitzungsschlussels k

• uber unsicheren Kanal

5.5 Der Diffie-Hellmann-Algorithmus 211

1. Alice und Bob einigen sich auf große Primzahl n und eine Zahlg. Diese beiden Zahlen durfen offentlich bekannt sein.

2. Alice wahlt große Zufallszahl x und sendet X = gx mod nan Bob. Offentlicher Schlussel: (X, g, n), geheimer Schlussel:(x, g, n).

3. Bob wahlt große Zufallszahl y und sendet Y = gy mod n an Ali-ce. Offentlicher Schlussel: (Y, g, n), geheimer Schlussel: (y, g, n).

4. Alice berechnet Sitzungsschlussel k = Y x mod n.

5. Bob berechnet Sitzungsschlussel k′ = Xy mod n

Es gilt k = k′, denn

k = Y x mod n = gxy mod n = Xy mod n = k′.


Warum ist dieses Verfahren sicher?

Kann Eve k berechnen?

Kann Eve x und y berechnen?

Auflosen der Gleichungen

Y = gy mod n und X = gx mod n

nach x bzw. y !?

x = logX/ log g.

Problem des diskreten Logarithmus.

5.6 Algorithmen mit Elliptischen Kurven 213

5.6 Algorithmen mit Elliptischen Kurven


Algorithmen mit Elliptischen Kurven

-1 1 2 3 4 5

-6

-4

-2

2

4

6

Dieelliptische Kurve zu y2 = x3 − 4x2 + 10.


Die Losungsmenge einer Gleichung der Form

y2 = ax3 + bx2 + cx + d

wird Elliptische Kurve genannt.

Seien A = (ax, ay) und B = (bx, by) Punkte mit ax 6= bx auf derelliptischen Kurve.

Diese zwei Punkte definieren eine Gerade, die einen dritten Schnitt-punkt C mit der Kurve besitzt.

man definiert:

A + B = −C = (cx,−cy)

Nimmt man nun noch einen “Punkt im Unendlichen” als Nullele-ment hinzu, so giltA+0 = A, oderA−A = 0, denn eine senkrechteGerade hat ihren dritten Schnittpunkt im Unendlichen.


Man kann auch multiplizieren, denn zum Beispiel ist

4A = A + A + A + A. (5.8)

Nennt man die Gruppenoperation nicht “+” sondern “·”, so habenwir eine multiplikative Gruppe definiert und Gleichung 5.8 wird zu

A4 = A · A · A · A.

• Wechsel zu endlichem Korper!

• Betrachte elliptische Kurven uber endlichem Korper, definieredie Multiplikation wie oben und rechne modulo n.

• RSA-Algorithmus, Diffie-Hellmann-Algorithmus, etc. konnen inder neuen Arithmetik implementiert

• Galoiskorper GF (2n), denn die Arithmetik kann sehr effizientimplementiert werden.


• RSA mit elliptischen Kurven ist bei 160-Bit-Schlussel so sicherwie normalesRSA 1024-Bit-Schlussel

Literatur: [Sti95, Men93, Kob94].

Kapitel 6

Authentifikation und digitale Signatur

6.1 Einwegfunktionen und Einweg-Hash-Funktionen 219

6.1 Einwegfunktionen und Einweg-Hash-Funktionen

Definition 6.1 Einwegfunktionen sind Funktionen f , die sichleicht berechnen lassen, deren Umkehrung f−1 jedoch nicht odernur sehr schwer (d. h. mit nicht vertretbarem Aufwand) zu berech-nen ist, insbesondere, wenn die Funktion f offentlich bekannt ist.

• Differenzieren ist berechenbar, d.h. man kann ein Programmschreiben fur diese Aufgabe.

• Das Finden einer Stammfunktion nicht berechenbar.

220 6 Authentifikation und digitale Signatur

• ⇒ Differenzieren ist eine Einwegfunktion.


Beispiel 6.1 Durch stures Ausmultiplizieren kann man zeigen, dassgilt

(x− 1)(x− 2)(x− 3)(x− 4)(x− 5)(x− 6)(x− 7)(x− 8)(x− 9)(x− 10)(x− 11) =

x11 − 66x10 + 1925x9 − 32670x8 + 357423x7 − 2637558x6 + 13339535x5

−45995730x4 + 105258076x3 − 150917976x2 + 120543840x− 39916800

Umkehrung sehr schwierig!

Schon fur Polynome funften Grades wie etwa

x5 + x4 + x3 + x2 + x− 1

sind die Nullstellen im allgemeinen nicht (exakt) berechenbar.Dass es ein derartiges Verfahren fur Ploynome funften und hoherenGrades nicht geben kann, wurde mit Hilfe der Galoistheorie bewie-sen [RS74, FS78].


Beispiel 6.2 RSA-Verschlusselung:

• M e mod n ist einfach

• Umkehrung (modulare Wurzel) ist sehr schwierig.

Definition 6.2 Einweg-Hash-Funktionen sind Einwegfunk-tionen, die beliebig lange Klartexte auf einen Hash-Wert festerLange abbilden.

nicht injektiv!!!

daher:


Es muß sehr schwierig sein, zwei Klartexte mit dem gleichen Hash-Wert zu finden.


Umsetzungsbeispiel:Eine Eingabe M beliebiger Lange wird dann zerlegt in k Teile Mi

der Lange m, d. h.

M = (M1,M2, . . . ,Mk)

Die Einwegfunktion f wird dann wie folgt rekursiv angewendet

h0 = 0 (6.1)

hi = f (Mi, hi−1) (6.2)

und der letzte berechnete Wert hk ist dann der Hash-Wert von M .


AES:Ist Ek(M) der mit dem Schlussel k aus dem Klartextblock M er-zeugte Chiffretextblock, so wird Gleichung 6.2 ersetzt durch

hi = EMi(hi−1)⊕ hi−1.


Einige wichtige Einweg-Hash-Funktionen

MD4 (MD steht fur message digest) MD4 wurde von Ron Ri-vest entwickelt und teilweise kryptanalysiert. Der Hash-Wert ist128 Bit lang.

MD5 Verbesserung von MD4 mit ebenfalls 128 Bit Hash-Wert,daher sicherer aber nicht unumstritten. Wird in PGP angewen-det.

SHA (Secure-Hash-Algorithm) wurde 1993 von der NSA (Natio-nal Security Agency) und NIST (National Institute of Standardsand Technology) entwickelt und ist auch eine Verbesserung vonMD4. Eine 1995 uberarbeitete Version hat nun den NamenSHA-1. Der Hash-Wert von SHA-1 ist 160 Bit lang.


RIPE-MD Eine weitere Variante von MD4 mit 160 Bit langemHash-Wert, die im EU-Projekt RIPE entwickelt wurde und sehrsicher sein soll.


Passwortverschlusselung

• Einwegfunktionen werden angewendet bei der Passwortver-schlusselung.

• Chiffrierte Passworter werden gespeichert.


Worterbuchangriff

Mallory stellt eine Liste der 100 000 gangigsten Passworter auf, wen-det die (bekannte) Einwegfunktion auf alle Passworter an und spei-chert die Ergebnisse zusammen mit den Passwortern. Nun stiehltMallory eine Passwortdatei und vergleicht diese mit seiner Datei aufUbereinstimmungen.

Abwehrversuch: 12 Bit Salt

Es existiert ein Liste in der etwa 732 000 ubliche Passworter mitallen 4 096 Salt-Werten verknupft und verschlusselt wurden.

Dateigroße bei 13 Byte langen verschlusselten Passwortern:

732 000 · 4 096 · 13 Byte = 3.9 · 1010 Byte = 39 GByte

Viel kleiner als die Datei mit allen Passwortern bestehend aus sechs


Tastaturzeichen, die auch ohne Salt schon etwa

966 · 13 Byte = 10 TByte

groß ware.


Der Geburtstagsangriff

Naiver Angriff gegen digitale Signatur: Dokument gegen einanderes mit gleichem Hash-Wert austauschen.

Besserer Angriff: Mallory erzeugt so lange unterschiedliche Ver-sionen eines Dokuments, bis die Hash-Wert gleich sind


Geburtstagsangriff

Frage 1: Wieviele Leute mussen in einem Raum sein, so dass mithoher Wahrscheinlichkeit (> 0.5) eine Person heute Geburtstaghat?

Frage 2: Wieviele Leute mussen in einem Raum sein, so dass mithoher Wahrscheinlichkeit (> 0.5) mindestens zwei Personen amgleichen Tag Geburtstag haben?

Zu Frage 1: Sei gi der Geburtstag von Person i fur i = 1, . . . , n.Damit im Mittel mindestens eine Person am Tag x Geburtstag


hat, muss die Wahrscheinlichkeit hierfur > 0.5 sein, also

P (g1 = x ∨ g2 = x ∨ . . . ∨ gn = x)

= 1− P (g1 6= x ∧ g2 6= x ∧ . . . ∧ gn 6= x)

= 1−(

364

365

)n> 0.5

Daraus lasst sich n berechnen, indem man(364

365

)n< 0.5

nach n auflost und n ≥ 253 erhalt.

Zu Frage 2: Gesucht ist nun die Zahl k der Personen, so dass imMittel mindestens zwei Personen am gleichen Tag Geburtstag


haben? Es muss also gelten

P (g1 = g2 ∨ g1 = g3 ∨ . . . ∨ gk−1 = gk)

= 1− P (g1 6= g2 ∧ g1 6= g3 ∧ . . . ∧ gk−1 6= gk)

= 1−(

364

365

)k(k−1)2

> 0.5

Setzt man nun k(k − 1)/2 = n, so erhalt man

k =1

2+

√1

4+ 2n = 22.98

Es mussen also k ≥ 23 Personen im Raum sein. Fur große ngilt naherungsweise k =

√2n.

Wenn der Hash-Wert aus m Bit besteht, dann mussen bei vorgege-benem Hash-Wert ca. n = 2m−1 Dokumente getestet werden, bis


Ubereinstimmung erzielt wird. Beim Geburtstagsangriff hingegengilt k ≈

√2n, d. h.

k ≈√

2 · 2m−1 =√

2m = 2m2 .

Um also eine Einweg-Hash-Funktion auch vor Geburtstagsangriffenzu schutzen, muss der Hash-Wert doppelt so lang gewahlt werdenwie fur einfache Angriffe.

In der Praxis werden heute Langen von 128 bis 160 Bit verwendet.


6.2 Zero-Knowledge-Protokolle

Problem: Einwahl uber Internet in Rechner!

Schlussel wird im Klartext ubertragen!

6.2 Zero-Knowledge-Protokolle 237

Challenge-and-Response


Alice unsicherer Kanal Bob

GibtBenutzerkennung

ID einID−−−−−→ sucht zu ID

Schlussel k inDatenbank

↓r←−−−−− wahlt Zufallszahl r

↓Res ′ = f(k′, r) Res = f(k, r)

↓Res ′−−−−−→ Res = Res ′?

Abbildung 6.1: Das Challenge-and-Response-Protokoll

Idee der Zero-Knowledge-Protokolle


Jemanden davon zu uberzeugen, dass man ein Geheimnis kennt,ohne jedoch auch nur ein Bit an Information uber das Geheimnispreiszugeben.

Beispiel 6.3: Losen kubischer Gleichungen

Der italienische Mathematiker Niccolo Tartaglia entdeckte 1535 dieFormel zur Losung von kubischen Gleichungen.

• Er laßt sich von den Kollegen kubische Gleichungen nennen

• Er loste sie unbeobachtet

• Er gibt die Losung bekannt.

• Kollegen verifizieren die Korrektheit der Losung


Beispiel 6.4: Der geheimnisvolle Geheimgang

Peggy (prover) kennt eine Zauberformel um die Tur des Geheim-gangs zu offnen. Sie uberzeugt Victor

A B Tür

Wahrscheinlichkeit fur einen erfolgreichen Betrug bei 100 Wieder-


holungen: 2−100 ≈ 10−30.


Das Fiat-Shamir-Protokoll

von A. Fiat, A. Shamir und U. Feige entwickeltes Zero-Knowledge-Protokoll

• Peggy: prover

• Victor: verifier

• Modul n = p · q• Peggy’s geheimer Schlussel s wird zufallig bestimmt

• Peggy’s offentlicher Schlussel v = s2 mod n


Peggy unsicherer Kanal Victor

Wahlt Zufallszahl r,berechnet x = r2 mod nund y = r s mod n

x ,y−−−−−−−−→Verifizierty2 mod n = x v mod n

Ein unsicheres Protokoll

Peggy kann aber ohne Kenntnis von s z. B. y = 2 wahlen, die


Gleichungy2 = x · v mod n

nach x auflosen und x, y an Victor schicken.


Peggy unsicherer Kanal Victor

Wahlt Zufallszahl r,berechnet x = r2 mod n

x−−−−−−−→Wahlt zufallig ein Bit b

b←−−−−−−−Berechnet

Falls b = 1:y = r s mod n

Falls b = 0:y = r mod n

y−−−−−−−→Verifiziert

Falls b = 1:y2 mod n = x v mod n

Falls b = 0:y2 mod n = x


nach k Runden Sicherheit von 1− 12

k.

Die Sicherheit des Verfahrens basiert wesentlich auf der Schwie-rigkeit der Berechnung modularer Quadratwurzeln.

Satz 6.1 Seien p und q Primzahlen und n = p · q. Dann ist dasBerechnen einer Losung s von v = s2 mod n gleich schwierig1 wiedie Primfaktorzerlegung von n.

Dieses Protokoll ist sehr gut fur die Implementierung auf Chipkartengeeignet.

6.3 Digitale Signaturen 247

6.3 Digitale Signaturen

Eine gute Unterschrift besitzt folgende Eigenschaften ([Sch96]):

1. Sie ist authentisch, d. h. sie zeigt, dass der Unterzeichner wil-lentlich unterschrieben hat.

2. Sie ist falschungssicher. Sie beweist, dass der Unterzeichnerund kein anderer das Dokument unterschrieben hat.

3. Sie ist nicht wiederverwendbar. Die Unterschrift kann nichtauf ein anderes Dokument kopiert werden.

4. Das unterzeichnete Dokument ist unveranderbar. Nach derUnterzeichnung kann es nicht mehr geandert werden.


5. Die Unterschrift ist bindend. Die Unterzeichnerin kann spaternicht behaupten, dass sie das Dokument nicht unterschriebenhat.

Unterschriften mit Tinte auf Papier erfullen keine dieser Aussagenvollstandig.

Signatur mit Public-Key-Algorithmus:

(M,ESA(M)).

Uberprufen der Unterschrift:

DPA(ESA(M)) = M

Bei großen Texten M :

(M,ESA(f (M))). (6.3)


Uberprufen der Unterschrift: berechnet Bob jetzt DPA(ESA(f (M)))und f (M) und vergleicht die beiden Werte.

Fur die Sicherheit des Verfahrens ist es wichtig, dass eine Einweg-Hash-Funktion benutzt wird!


Digital Signature Algorithm (DSA)

Im JAHR 1991 suchte das NIST nach einem Standard fur digita-le Signaturen und beauftragte die NSA mit der Entwicklung desDigital Signature Algorithm (DSA).

Viele Firmen wollten RSA als Standard fur digitale Signaturen ha-ben [Sch96].

DSA wird in PGP ab Version funf eingesetzt.


Blinde Signaturene = offentlicher Schlussel von Bob, d = geheimer Schlussel von Bob


Alice Bob

Wahlt Zufallszahl k,Verschlusselt M :t = M · ke mod n

t−−−−−−−→signiert t:u = td mod n

u←−−−−−−−Entschlusselt dassignierte Dokument:Md = u

k mod n


Was hier aussieht wie Zauberei, ist ganz einfach:

u

kmod n =

td

kmod n =

(M · ke)d

kmod n

=Md · ked

kmod n = Md mod n.

Blinde Signaturen wurden von D. Chaum [Cha85, Cha92] erfunden.


6.4 Digitale Signatur in der Praxis

Die digitale Signatur ist also sehr sicher und einfach zu benutzen.

Trotzdem gibt es in der Praxis einige Probleme, die hier etwas ge-nauer beleuchtet werden.

6.4 Digitale Signatur in der Praxis 255

Speichern des geheimen Schlussels

• sichere Verwahrung des geheimen Schlussels!

• Speichern des geheimen Schlussels auf der Festplatte??

• Symmetrischer 128-Bit-Schlussel ist etwa so sicher wie RSA mit1024 Bit.

• ⇒ Passwort muß 128 Bit lang sein!

• Groß-, Kleinbuchstaben und Ziffern = 64 Zeichen, d.h. 6 Bit.

128 Bit

6 Bit/Zeichen≈ 21 Zeichen.


Deutsche Texte lassen sich um etwa einen Faktor 3 bis 4 kompri-mieren. Daher:

Das Passwort (passphrase) fur die Verschlusselung des geheimenSchlussels eines Public-Key-Verfahrens muss mindestens 80 Zeichenlang sein.

Problem: Tippfehler beim Eintippen der 80 Zeichen

Losungen: Speichern des geheimen Schlussels auf Diskette.

Personalausweis auf Chipkarte

6.4 Digitale Signatur in der Praxis 257

Vertrauen in die Software

Der/die Unterzeichnende kann nicht unmittelbar kontrollieren, wasim Hauptspeicher und in der CPU des Rechners ablauft.

Signieren mit Chipkarte bietet einen gewissen Schutz.

Wie kann der Anwender jedoch kontrollieren was seine Chipkartesigniert?

Ein Autofahrer hat Vertrauen in die Funktionstuchtigkeit der Brem-sen seines Fahrzeuges, wenn es regelmassig gewartet wird.

Der Anwender sollte bei der Installation und vor jedem Start einesKryptographie-Programms die Signatur des Herstellers kontrollie-ren.


Noch besser als die Signatur des Herstellers ist die Signatur einerunabhangigen Pruf- und Zertifizierungsstelle, wie zum Beispiel desBundesamtes fur Sicherheit in der Informationstechnik (BSI) [BSI01].

Auch die Soft- und Hardware der Chipkarten muss zertifiziert wer-den.

6.5 Signaturgesetz 259

6.5 Signaturgesetz

• 1997: deutsches Signaturgesetz [Sig97a], bzw. Signaturverord-nung [Sig97b].

• strenge Vorgaben:

• der geheime Schlussel darf nicht auf einem Computer gespei-chert sein!

• Software, Hardware, Chipkarten mussen zertifiziert sein!

• Trustcenter, muss zertifiziert sein!

• Dezember 1999 [Sig00]:“community framework for electronicsignatures” des EU-Parlaments.


• Mai 2001: neues deutsches Signaturgesetz nach EU-Richtlinien.

• Unterscheidung zwischen verschiedenen Klassen digitaler Signa-tur.

deutsches Signaturgesetz vom 21. Mai 2001:Im Sinne dieses Gesetzes sind

1. “elektronische Signaturen” Daten in elektronischer Form, die anderen elektronischenDaten beigefugt oder logisch mit ihnen verknupft sind und die zur Authentifizierungdienen,

2. “fortgeschrittene elektronische Signaturen” elektronische Signaturen nach Nummer 1,die

a) ausschließlich dem Signaturschlussel-Inhaber zugeordnet sind,

b) die Identifizierung des Signaturschlussel-Inhabers ermoglichen,

c) mit Mitteln erzeugt werden, die der Signaturschlussel-Inhaber unter seiner alleinigenKontrolle halten kann, und


d) mit den Daten, auf die sie sich beziehen so verknupft sind, dass eine nachtraglicheVeranderung der Daten erkannt werden kann,

3. “qualifizierte elektronische Signaturen” elektronische Signaturen nachNummer 2, die

a) auf einem zum Zeitpunkt ihrer Erzeugung gultigen qualifizierten Zertifikat beruhenund

b) mit einer sicheren Signaturerstellungseinheit erzeugt wurde.

• elektronische Signatur nach Nummer 1: normale E-Mail odereingescannte handschriftliche Unterschrift.

• fortgeschrittene elektronische Signature: PGP-Standard.

• Qualifizierte elektronische Signatur: offentlicher Schlussel mussvon akkreditiertem Trustcenter zertifiziert sein. Signatur mussauf der Chipkarte mit einem Klasse-2- oder Klasse-3-Chipkartenlesererfolgen.


Klassifikation der verschiedenen Signaturtypen.

anwendbar bei

Signaturtypgesetzlich vorge-schriebener elek-tronischer Form

vereinbarterelektronischerForm

Rechtswirksam-keit

Beweiskraft

qualifizierteelektronischeSignatur

× × × sehr hoch

fortgeschritteneelektronischeSignatur

— × × hoch

elektronische Si-gnatur

— × × sehr schwach

E-Mail ohne Si-gnatur

— — × keine


Zusammenfassung

Digitale Signaturen

• sind komfortabel

• sind sicher

• sparen Zeit und Kosten

• bieten fur viele Anwendungen große Vorteile

• haben juristische Gultigkeit im Fall eines Rechtsstreits [TT01]

• sind abstrakter als handgeschriebene


6.6 Authentifikation mit digitaler Signatur

Alice unsicherer Kanal Bob

r←−−−−− wahlt Zufallszahl rsigniert r

ESA(r)

−−−−−→ DPA(ESA(r))?= r

Alice authentifiziert sich mit digitaler Signatur auf dem Server Bob.

6.6 Authentifikation mit digitaler Signatur 265

zu Zero-Knowledge-Beweis gleichwertig.


6.7 Message-Authentication-Code (MAC)

Authentizitat von Nachrichten

(M,EK(f (M)))

Kein Ersatz fur eine digitale Signatur!

MAC durch Verwendung einer symmetrischen Blockchiffre im CBC-Modus (Abschnitt 4.3). Der letzte Chiffretextblock dient hier alsMAC.

6.8 Biometrische Verfahren 267

6.8 Biometrische Verfahren

• Authentifikation von Personen auf Grund von unveranderlichenkorperlichen Merkmalen

• Stimme, Gesicht, Fingerabdruck, Netzhautstruktur

• Mustererkennung nicht einfach

• anfallig gegen trojanische Pferde

• Chipkarte: PIN-Code ersetzen durch FingerabdruckAchtung: anfallig gegen trojanische Pferde

• Zukunft: Sensor auf der Chipkarte




ROC-Kurven fur biometrische Authentifikation

0

20

40

60

80

100

0 20 40 60 80 100

FA

R =

fals

che

Akz

epta

nz U

nber

echt

igte

r [%

]

FRR = falsche Zurückweisung Berechtigter [%]

Hochsicherheits−anwendungen

Kriminalistik

schlechtes biometrisches System

gutes biometrisches System

gutes kryptographisches System


Kapitel 7

Public-Key-Infrastruktur

Problem: Man-in-the-Middle-Angriff

Die Authentizitat der offentlichen Schlussel ist von außerster Wich-tigkeit. Bevor Bob den offentlichen Schlussel von Alice benutzt,muss er dessen Authentizitat uberprufen.

273

Die Infrastruktur fur die Erzeugung, Authentisierung, Verteilungund Uberprufung von offentlichen Schlusseln sowie fur die sichereSpeicherung der geheimen Schlussel wird Public-Key-Infrastruktur(PKI) genannt.

274 7 Public-Key-Infrastruktur

7.1 Personliche Prufung offentlicher Schlussel

Type Bits/KeyID Date User ID

pub 1024/2F7BFC59 1998/05/18 Wolfgang Ertel <[email protected]>

Key fingerprint = 9E 2D DB 62 C3 E7 7A 79 00 48 37 F6 55 B6 A9 EF

Abbildung 7.1: 128-Bit-Fingerprint eines PGP-Schlussels in Form von 16 Byte bzw. 32 Hexadezimalziffern

Nachteil: sehr aufwandig.

7.2 Trustcenter 275

7.2 Trustcenter

Definition 7.1 Ein Trustcenter ist eine Institution, der alle Per-sonen vertrauen, und dessen offentlicher Schlussel auf sicheremWege bekannt gemacht wird. Die wichtigste Aufgabe des Trust-centers besteht in der Zertifizierung offentlicher Schlussel von Pri-vatpersonen, Firmen oder anderen Institutionen. Die Zertifizie-rung eines offentlichen Schlussels P besteht in der Prufung derAuthentizitat der Person oder Firma und der Signatur des Schlus-sels P mit dem geheimen Schlussel des Trustcenters.

Da der offentliche Schlussel des Trustcenters jedermann bekannt


ist, kann auch jedermann die Zertifikate des Trustcenters prufen.

Verschiedene Klassen von Zertifikaten!

Mochte Alice mit Bob geheim kommunizieren, so gehen die beidenfolgendermaßen vor:

7.2 Trustcenter 277

1. Alice besorgt sich ein Zertifikat der Klasse 3 oder 4 beieinem Trustcenter ihrer Wahl.

2. Bob besorgt sich ein Zertifikat der Klasse 3 oder 4 beieinem Trustcenter seiner Wahl.

3. Alice und Bob schicken sich gegenseitig ihre zertifizier-ten offentlichen Schlussel zu.

4. Alice uberpruft das Zertifikat auf Bobs offentlichemSchlussel.

5. Bob uberpruft das Zertifikat auf Alices offentlichemSchlussel.

6. Bob und Alice konnen sich nun geheime und signierteNachrichten zukommen lassen.


Erstellen von Zeitstempeln:

((M, Uhrzeit, Datum), EST (f(M, Uhrzeit, Datum))).

Trustcenter muß nach Signaturgesetz zertifiziert sein.

7.3 Zertifikatshierarchie 279

7.3 Zertifikatshierarchie

Firma 2

Dave Ellen Frank

Firma 1

CarolAlice Bob

Trustcenter

CA 2CA 1

Abbildung 7.2: Zweistufige Zertifikatshierarchie


7.4 Web-of-Trust

Alice

Bob Carol

signiert

PB vertraut

7.4 Web-of-Trust 281

• Benutzen Sie niemals einen Schlussel, den Sie nur per E-Mailerhalten haben oder den Sie irgendwo im Internet gefunden ha-ben, solange er nicht von einer Person Ihres Vertrauens signiertist!

• Signieren Sie niemals einen Schlussel, den Sie nur per E-Mailerhalten haben oder den Sie irgendwo im Internet gefunden ha-ben, auch wenn er von einer Person Ihres Vertrauens signiertist! Verifizieren Sie personlich oder telefonisch die Echtheit desSchlussels, den Sie signieren!

• Vertrauen in einen Schlussel bedeutet nicht automatisch Ver-trauen in den Besitzer des Schlussels!

Kapitel 8

Public-Key-Systeme

8.1 PGP 283

8.1 PGP

PGP [Zim95, PGP01] wurde 1994 von Phil Zimmermann ent-wickelt

PGP steht fur pretty good privacy und

• kann Dateien verschlusseln oder signieren

• war bis zur Version 2.6.3 generell frei vefugbar

• aber nicht aus den USA exportierbar

• wurde als Buch publiziert

• in Europa eingescannt PGP 2.6.3i

284 8 Public-Key-Systeme

• kann in diversen Email-Programmen eingebunden werden

8.1 PGP 285

Here’s a short summary of commands in PGP 2.6.3i:

Generate new key pair: pgp -kg [keybits]

Add key: pgp -ka keyfile [keyring]

Extract key: pgp -kx[a] userid keyfile [keyring]

View key(s): pgp -kv[v] [userid] [keyring]

View fingerprint: pgp -kvc [userid] [keyring]

Check & view in detail: pgp -kc [userid] [keyring]

Remove userid or key: pgp -kr userid [keyring]

(Repeat for multiple userids on a key)

Edit trust params: pgp -ke userid [keyring]

Add another userid: pgp -ke your_userid [keyring]

Edit passphrase: pgp -ke your_userid [keyring]

Sign a key in pubring: pgp -ks other_id [-u sign_id] [keyring]

Remove a sig from key: pgp -krs userid [keyring]

Revoke, dis/enable: pgp -kd userid [keyring]

Encrypt: pgp -e[a] textfile TO_id [TO_id2 TO_id3...]

Sign: pgp -s[a] textfile [-u MY_id]

Sign & encrypt: pgp -se[a] textfile TO_id [TO_id2 TO_id3...][-u MY_id]

Make detached cert: pgp -sb[a] [+clearsig=on] mainfile [-u MY_id]

(Can do binaries) (clearsig=on may be set in CONFIG.TXT)

Encrypt with IDEA only: pgp -c textfile

Decrypt or check sig: pgp [-d] [-p] cryptogram

(-d to keep pgp data, -p for original file name)

Check detached cert: pgp certfile [mainfile]

(If root of filenames are the same omit [mainfile])

Use [a] for ASCII output

Use [-o outfile] to specify an output file

Use [-@ textfile] to specify additional userids when encrypting

Use [-z"pass phrase"] to specify your pass phrase

Use [+batchmode] for errorlevel returns

Use [f] for stream redirection ( pgp -f[ARGS] <infile >outfile )

Use [w] to wipe plaintext file (encryption operations)

Use [m] to force display of plaintext only (no output file)

Use [t] to alter line endings for unix, etc.


Date: Wed, 29 Apr 1998 15:56:54 +0200

To: [email protected]

Subject: Signaturgesetz

From: Wolfgang Ertel <[email protected]>

ReplyTo: [email protected]

Mime-Version: 1.0

Content-Transfer-Encoding: 8bit

Content-Type: text/plain; charset=ISO-8859-1

Content-Length: 977

-----BEGIN PGP SIGNED MESSAGE-----

Sehr geehrte Damen und Herren,

anbei ein Auszug aus dem Signaturgesetz.

mfg

W. Ertel

Beschluss des Bundeskabinetts

zum Entwurf der Signaturverordnung

am 8.10.1997

Das Bundeskabinett hat am heutigen Tag dem Entwurf der

Signaturverordnung zugestimmt, den das Bundesministerium fuer Bildung,

Wissenschaft, Forschung und Technologie und das Bundesministerium des

Innern gemeinsam vorgelegt haben.

Die Bundesregierung schafft mit der Verordnung die notwendigen

Voraussetzungen fuer eine zeitnahe Umsetzung des Signaturgesetzes, das

als Art. 3 des Informations- und Kommunikationsdienste-Gesetzes

(IuKDG) am 1. August 1997 in Kraft getreten ist.

-----BEGIN PGP SIGNATURE-----

Version: 2.6.3i

Charset: noconv

iQBVAwUBNUcxVIrxrO+qmKMNAQHrwAH6AqmIGyAs7Oah9lgWsQQyhFjWYxvU5mgA

r5yrrDr7aMG4+rI/4ixR1Mbfs8SCSBmHmSlIgBC6ugphxhUXnQQSWg==

=KVTm

-----END PGP SIGNATURE-----

8.1 PGP 287

PGP 7.0 bietet neben dem Verschlusseln und Signieren folgendeFunktionen:

• IDS (intrusion dection system) zur automatischen Abwehr be-stimmter Netzwerkangriffe.

• VPN (virtual private networking) zur sicheren – vom Benutzerunbemerkten – Kommunikation zwischen Firmenfilialen (sieheAbschnitt 8.6).

• Automatische Ver- und Entschlusselung von Dateien auf derFestplatte.

• Einen Personal-Firewall zur Filterung von ein- und ausgehendenPaketen.

• Einfacher bzw. automatischer Zugang zu Trustcenter, CA (cer-tification authority) und Schlussel-Servern.


PGP-Schlusselring (pgp -kv)

Type Bits/KeyID Date User ID

pub 2048/CFC100F5 1997/05/02 TC TrustCenter Class 2 Private CA

pub 2048/833153FD 1998/03/01 TC TrustCenter Class 4 Business CA

pub 2048/C935FB3D 1997/05/02 TC TrustCenter Class 1 Private CA

pub 2048/CB1CDBF9 1997/05/02 TC TrustCenter Class 3 Private CA

pub 2048/6D37AF71 1998/03/01 TC TrustCenter Class 3 Business CA

pub 1024/804B5A69 1999/06/23 Hansi Muller <[email protected]>

pub 512/EBD9FB49 1998/06/16 Klaus Maier <[email protected]>

pub 2048/293A0B77 1998/06/29 Max Muster <[email protected]>

pub 768/27AE3DA9 1998/06/16 Hans Huber [email protected]

pub 2048/AAEBDCC9 1998/06/22 Alice Weiss <[email protected]>

pub 768/16BE84D5 1998/06/21 Bob Schwarz <[email protected]>

pub 768/6FAFE9B1 1997/06/14 Dan Hack <[email protected]>


8.1 PGP 289

Ein PGP-Schlussel mit Signaturen

pgp -kvv ertel


sig CB1CDBF9 TC TrustCenter Class 3 Private CA

sig 804B5A69 Hansi Muller <[email protected]>

sig 27AE3DA9 [email protected]

sig EBD9FB49 Klaus Maier <[email protected]>

sig AAEBDCC9 Alice Weiss <[email protected]>

sig 16BE84D5 Bob Schwarz <[email protected]>

sig 2F7BFC59 Wolfgang Ertel <[email protected]>


Die Big-Brother-Funktion

ab PGP 5.5.X besteht die Moglichkeit, die Geheimhaltung inner-halb von Institutionen (z. B. Firmen) aufzuheben, wie in [Rav98]beschrieben.

Kopien von Emails werden mit dem “Firmen”-Public-Key verschlusselt.

Bezeichnung:“Corporate-Message-Recovery-Key” (CMRK)

“Additional-Decryption-Key” (ADK)

• Festlegung eines ADK fur eingehende E-Mails

• Festlegung eines ADK fur ausgehende E-Mails

• Erzwingung der Benutzung eines ADK fur ausgehende und/oder eingehende E-Mails

• Erzwingung von zusatzlichen ADKs (z. B. weiterer “Firmen”)

8.1 PGP 291

• Erzwingung einer bestimmten Lange und Qualitat der Passphrase

• Erzwingung einer bestimmten Schlussellange

• Erzwingung, dass der ADK automatisch von allen Benutzern der Client-Version signiertwird, wenn diese einen Schlussel erzeugen

• Erzwingung eines bestimmten Kommentars im Nachrichtenheader

• Ausgabe einer Warnung, wenn mit einem Public-Key verschlusselt wird, der nicht mitdem ADK signiert wurde

• Verbot der Schlussel-Erzeugung

• Verbot der RSA-Schlussel-Erzeugung

• Verbot der konventionellen Verschlusselung

• Voreinstellung der Schlussel, die im Standard-Keyring enthalten sind

Auch Behorden konnten dieses Feature einsetzen.


GnuPG

• Gnu-Privacy-Guard (GnuPG) [ACGW99].

• 1999 von Werner Koch entwickelt.

• Open Source Tradition

• nur frei verfugbare Algorithmen

• teilweise kompatibel mit PGP

• halt sich an den OpenPGP-Standard

Algorithmen:

AES, triple DES, TWOFISH.

8.1 PGP 293

RSA, ElGamal, DSA

MD5, SHA-1, RIPEMD160 und TIGER/192.


Angriffe gegen PGP

Angriff auf PGP-Signatur mit manipuliertem Schlussel

Schwerwiegender Mangel im Datenformat des OpenPGP-Standardfur die Speicherung des geheimen Schlussels!

Entdeckt vonb Vlastimil Klıma und Tomas Rosa [KR01].

Angriff: Mallory verandert zufallig den gespeicherten, verschlussel-ten geheimen Schlussels von Alice und bringt Alice dazu, eine ihmbekannte Nachricht M zu signieren.

Aus der Signatur S und der Nachricht M kann er nun den Schlusselermitteln, wie unten beschrieben.

8.1 PGP 295

Dieser Angriff ist (war) moglich sowohl bei DSA-Signaturen, alsauch bei RSA-Signaturen.

Abwehrmaßnahme:

Veranderung der Datenstruktur zur Abspeicherung des geheimenSchlussels welche einen guten Integritatscheck erlaubt.

Angriff mit Nachschlussel

Bei PGP mit ADK-Feature und Diffie-Hellmann-Verschlusselung:

Mallory schickt Alice den veranderten offentlichen Schlussel P ′B vonBob, ohne dass sie diese Veranderung bemerkt [Sen00].

P ′B enthalt PB und PM

Fur jede mit P ′B verschlusselte Nachricht wurden nun von PGP


automatisch zwei Kopien erzeugt und jede mit einem der beidenSchlussel verschlusselt.

Mallory kann jede Nachricht von Alice an Bob abhoren ohne dassAlice eine Ahnung davon hat.

8.2 S/MIME und das X.509 Protokoll 297

8.2 S/MIME und das X.509 Protokoll

• S/MIME: Secure Multipurpose Internet Mail Extension

• Protokoll zum Verschlusseln und Signieren von E-Mail [IMC01].

• benutzt den Standard PKCS #7 (Cryptographic Message Syn-tax) fur verschlusselte E-Mails

• PKCS: public key cryptography system

• benutzt X.509-Protokoll [KP01] fur Zertifikate.


X.509-Protokoll

existiert seit 1988

ist heute ein wichtiger Industrie-Standard.

Ein X.509-Zertifikat besteht aus folgenden Teilen:

Version: Versionsnummer des Protokolls (1–3).

Seriennummer: Ganzzahlige, innerhalb einer CA eindeutige Se-riennummer.

Algorithmenidentifikation: Spezifikation des verwendeten Si-gnaturalgorithmus und der Einweg-Hash-Funktion.

Aussteller: Identifikation der ausstellenden CA.

Geltungsdauer: Zeitraum der Gultigkeit des Zertifikats.

8.2 S/MIME und das X.509 Protokoll 299

Subject: Person oder Objekt, deren/dessen Identitat das Zertifi-kat sichern soll.

Public-Key: Offentlicher Schlussel des “Subject”. Enthalt denNamen des verwendeten Algorithmus, die Schlussellange, denModul n und den offentlichen Exponenten e.

X.509v3-Erweiterungen: Raum fur spezielle Parameter der je-weiligen Anwendung.

Signatur: Signatur des Hash-Wertes aller anderen Felder durchden Aussteller.


8.3 OpenPGP versus S/MIME

• klare Tendenzen der Industrie fur S/MIME

• große Zahl von Benutzern bereits fur PGP als Werkzeug ent-schieden.

• Internet Engineering Task Force (IETF) [IET01], hat OpenPGP-Standard definiert [oPG01].

• Das Internet Mail Consortium versucht, beide Standards zusam-men zu fuhren [IMC01].

8.4 Secure shell (SSH) 301

8.4 Secure shell (SSH)

SSH secure shell ist ein sicherer Ersatz fur telnet, rlogin, rsh,rcp, etc.

SSH bietet:

• Sichere gegenseitige Authentifikation von Client und Server.

• Sicheres Login durch Authentifikation der Benutzer auf demServer mit RSA, oder DSA.

• Verschlusselung mit RSA und IDEA, Blowfish oder Triple-DES

• Sichere Verbindungen auch fur grafische Anwendungen unter


X11.

• Jeder TCP/IP-Port kann auf einen durch SSH abgesichertenPort umgeleitet werden. (Tunneln, IP-Tunneling)

Authentifikationsprotokoll:

• Uni-Rechner erzeugt 256-Bit-Zufallszahl r, verschlusselt diesemit PA.

• schickt EPA(r) an Alice.

• Alice entschlusselt r und schickt deren Hashwert f (r) an denUni-Rechner.

• Uni-Rechner checkt f (r).

8.5 Secure socket layer (SSL) 303

8.5 Secure socket layer (SSL)

Netscape: 1994

Nachfolger: Transport Layer Security (TLS) [TLS01]: 2001


Die Protokollebenen von SSL.

SSL-Handshake- SSL-Change-Cipher- SSL-Alert- HTTP

Protokoll Spec-Protokoll Protokoll

SSL-Record-Protokoll

TCP

IP

SSL-Record-Protokoll: kryptographische Algorithmen: MD5,

8.5 Secure socket layer (SSL) 305

SHA-1; RSA, Diffie-Hellmann; stehen RC4, RC2, DES, DES40,Triple-DES, IDEA, Fortezza (Chipkarten)

SSL-Alert-Protokoll: Warn- und Fehlermeldungen.

SSL-Change-Cipher-Protokoll: Initialisierung der ausgewahl-ten Algorithmen.

SSL-Handshake-Protokoll: Beim client_hello und server_hello werden die kryptographischen Algorithmen und der Kom-pressionsalgorithmus festgelegt. Authentifikation von Client undServer durch Zertifikate. Schlusseltausch die symmetrische Ver-schlusselung.

HTTP (Hypertext Transfer Protocol): Ubertragung der HTML-Seiten.

SSL in Europa bis 1999 nur mit 40 Bit-Schlusseln erhaltlich.

client_hello

server_hello

server_hello


Seit Februar 2000 auch langere Schlussel moglich.

Wichtig fur eine sichere Verbindung sind die Rechnerzertifikate, ins-besondere beim Server.

8.6 Virtual Private Networking und IP Security 307

8.6 Virtual Private Networking und IP Security

virtual private networking (VPN)

• Verschlusselung und Authentisierung ohne dass der einzelne Be-nutzer dies bemerkt

• auf der IP-Paket-Ebene

• jedes IP-Paket wird verschlusselt, unabhangig von dem verwen-deten Protokoll.

Die Verwendung von IPSec auf einem Firewall bietet folgende Vor-teile:


• Starke kryptographische Sicherheit fur Verkehr nach außen ohne Belastung des internenVerkehrs.

• IPSec auf einem Firewall kann nicht umgangen werden.

• Da IPSec unter der Transportschicht (TCP/UDP) arbeitet, muss die Anwendungssoft-ware nicht geandert werden.

• Der Benutzer bemerkt die Arbeit von IPSec nicht, muss also auch nicht geschult werden.

Kapitel 9

Elektronisches Bargeld

310 9 Elektronisches Bargeld

Geforderte Eigenschaften:

• Das Bezahlen muss einfach und mit sehr geringen Unkostenerfolgen ( ⇒ Micro-Payment)

• Das Bezahlen von kleinen Betragen muss unverbindlich sein.Bsp: Kauf einer Zeitung am Kiosk per Uberweisung!?

• Das Bezahlen muss anonym erfolgen.

• Das Wechselgeldproblem des klassischen Bargeldes muss demKunden erspart bleiben.

• Das Bezahlen soll auch zwischen Privatpersonen moglich sein.

• Das elektronische Bargeld soll moglichst viele Sprunge machenkonnen, bevor es wieder zur Bank zuruckkommt.

311

• Das elektronische Bargeld ist nur fur kleine Betrage bis ca. 500DM zu verwenden.

• Elektronische Munzen sollen falschungssicher sein.


9.1 Secret-Splitting

Zerteilen einer Bitfolge M in zwei Teile M1, M2, die beide fur sichallein wertlos sind.

So geht’s:

M1 = R⊕MM2 = R.

es gilt:

M = M1 ⊕M2 = R⊕R⊕M.

Verallgemeinerung:

9.1 Secret-Splitting 313

• (m,n)-Schwellenwertproblem

• n Teile

• Rekonstruktion nur moglich mit mind. m Teilen (m < n)


9.2 Bit-Commitment-Protokolle

Alice soll sich auf ein Bit festlegen, mochte dieses aber geheimhalten.

Bob jedoch will eine Garantie.

9.2 Bit-Commitment-Protokolle 315

Verfahren mit symmetrischer Verschlusselung

Festlegung:

1. Bob sendet eine Zufallszahl R an Alice.

2. Alice legt sich fest auf das Bit b und schickt M =EK(R, b) an Bob.

Uberprufung:

1. Alice sendet den Schlussel K an Bob.

2. Bob dechiffriert: R′, b′ = DK(M). Er vergleicht R′ mit R.Wenn R′ = R, dann vertraut Bob Alice.


Verfahren mit Einweg-Hash-Funktion

Festlegung:

1. Alice legt sich auf das Bit b fest und erzeugt zwei Folgenfester Lange aus Zufallsbits R1 und R2.

2. Sie wendet auf R1, R2 und b die Einweg-Hash-Funktion Han und schickt (H(R1, R2, b), R1) an Bob.

Uberprufung:

1. Alice schickt den Klartext (R1, R2, b) an Bob.

2. Bob berechnet H(R1, R2, b) und vergleicht R1 und das Er-gebnis mit Alices Nachricht. Bei Ubereinstimmung ist er vonder Echtheit des Bits uberzeugt.

9.3 Protokolle fur Elektronisches Bargeld 317

9.3 Protokolle fur Elektronisches Bargeld

Verfeinerung der Protokolle Nr. 1 bis 4 aus Kapitel 1 von D. Chaum [Cha85,Cha92, CFN88, Cha89, Sch96].

Ziel:Identifizierung des Betrugers trotz Anonymitat!


Protokoll Nr. 5

1. Alice erzeugt n Munzen mit unterschiedlichen, zufallig gewahlten langen Seriennummern,wie bei Protokoll Nr. 4. Nun spaltet sie ihre Identitat (Name, Adresse etc.) mit einemSecret-Splitting-Protokoll n-mal unterschiedlich auf, was zu den n Identitatsfolgen

I1 = (I1L, I1R)

I2 = (I2L, I2R)

. . .

In = (InL, InR

)

fuhrt.

2. Nun wendet Sie auf jede Halfte jeder Identitatsfolge getrennt ein Bit-Commitment-Protokoll an. Bei dem in Abschnitt 9.2 beschriebenen Protokoll mit Einweg-Hash-Funktion


sieht eine Munze dann etwa so aus:

Betrag

Seriennummer

[H(R1, R2, I1L), R1], [H(R3, R4, I1R), R3]

[H(R5, R6, I2L), R5], [H(R7, R8, I2R), R7]

. . .

[H(R4n−3, R4n−2, InL), R4n−3], [H(R4n−1, R4n, InR

), R4n−1]

Jede Halfte jeder Identitatsfolge ist nun also separat unkenntlich gemacht und un-veranderbar. Sie kann nur mit Alices Hilfe decodiert werden. Wegen der Verwendungeines Bit-Commitment-Protokolls kann Alice bei der Decodierung nicht schwindeln. Die-ser Prozess der Erzeugung von n Identitatsfolgen wird fur jede der n Munzendurchgefuhrt und dann werden die Folgen auf den Munzen gespeichert!

3. Alice verschlusselt die n Munzen mit einem Protokoll fur blinde Signaturen und schicktsie an die Bank.

4. Wie in Protokoll Nr. 4 verlangt die Bank nun von Alice die Entschlusselung von n − 1zufallig gewahlten Munzen. Die Bank uberpruft Betrag und Seriennummer und bittetAlice, alle Identitatsfolgen offenzulegen.


5. Falls alles in Ordnung ist, signiert die Bank die verbleibende Munze blind, belastet AlicesKonto und gibt die signierte Munze an Alice zuruck.

6. Alice macht ihre Munze wieder lesbar und geht mit ihr einkaufen.

7. Der Handler uberpruft die Signatur der Bank.

8. Nun muss Alice von jeder Identitatsfolge entweder die linke oder die rechte Halfte offnen.Der Handler bestimmt fur jede der Folgen zufallig, welche Halfte sie offnet.

9. Alice befolgt die Anweisung.

10. Der Handler bringt die Munze zur Bank mit der Bitte um Gutschrift auf sein Konto.

11. Die Bank uberpruft ihre Signatur und uberpruft in ihrer Datenbank, ob bereits eineMunze mit der gleichen Seriennummer eingegangen ist. Ist dies nicht der Fall, bekommtder Handler sein Geld und die Bank protokolliert Seriennummer und alle Identitatsinfor-mationen in ihrer Datenbank.

12. Ist die Seriennummer bereits in der Datenbank gespeichert, so liegt (mit sehr hoherWahrscheinlichkeit) ein Betrug vor. Nun werden die verschlusselten Identitatsdaten aufder Munze mit den in der Datenbank gespeicherten verglichen. Stimmen sie uberein, soweiß die Bank, dass der Handler die Munze kopiert hat.


Im anderen Fall ist Alice die Betrugerin.

Nun vergleicht die Bank alle Identitatspaare auf der Munze mit den gespeicherten. Gibtes ein Paar bei dem beide Halften geoffnet wurden, so verknupft die Bank diese beidenHalften mit XOR und liest die Identitat von Alice im Klartext.

Kapitel 10

Elektronische Zahlungssysteme

• Micro-Payment fur Pfennigbetrage und

• Macro-Payment fur Betrage ab etwa 5 DM.

Kategorien:

Elektronisches Bargeld: s.o., Beispiele sind Mondex und Ecash.

323

Kreditkarte: Beispiel: SET.

Abbuchung vom Konto: Erteilen einer Einzugsermachtigungan den Handler.

Abrechnung uber die Telefonrechnung:Variante: uber das Konto des Mobiltelefons. Authentisierung perRuckruf der Abrechnungsstelle beim Mobiltelefon des Kunden.

324 10 Elektronische Zahlungssysteme

10.1 Die Geldkarte

Chipkarte mit sicherer Speicherung des Betrags und kryptographi-schen Protokollen fur Authentifikation und Kommunikation.

10.1 Die Geldkarte 325

Vergleich von Geldkarte und Mondex-System

Karte

Wallet

Karte

Händler Karte

Händler

Bank

MondexGeldkarte

Bank

Zukunftig soll uber spezielle Kartenlesegerate auch das Bezahlen im


Internet mit Geldkarte moglich sein.

10.2 Mondex 327

10.2 Mondex

• 1990 in Großbritannien gestartet.

• Bis heute Pilotversuche in Großbritannien, den USA, Kanada,Australien und anderen Landern.

• Gegenuber der Geldkarte mehr Komfort.

• Gegenuber der Geldkarte geringere Sicherheit.

• Details geheim (Kerkhoffs-Prinzip!) ⇒ unter FachleutenMisstrauen!


10.3 Ecash 329

10.3 Ecash

• Basiert auf elektronischen Munzen

• Ahnelt Protokoll Nr. 5 (D. Chaum)

• Algorithmen: RSA mit 768-Bit-Schlussel, Triple-DES, SHA-1

• Wegen mangelnder Akzeptanz im Pilotversuch von DeutscherBank eingestellt!


10.4 Secure Electronic Transactions (SET)

• Aufwandiges Protokoll zum Bezahlen mit Kreditkarten

• Ende 1997 von VISA und MasterCard gestartet

• zweiseitige Authentifizierung, Verschlusselung, Vertraulichkeit

• Bsp.: Handler erfahrt keine Kreditkartennummer des Kunden!

• Kunde und Handler mussen Zertifikate beantragen ⇒ Nach-teil gegenuber anderen Systemen.

10.4 Secure Electronic Transactions (SET) 331

Ablauf einer SET-Transaktion

Kapitel 11

Politische Randbedingungen

11.1 Starke Kryptographie und der Lauschangriff 333

11.1 Starke Kryptographie und der Lauschangriff

• ECHELON: weltweites Abhorsystem zum routinemaßigen Abhorender Internet-Leitungen und Satellitenverbindungen.

• Sicherheit der starken Kryptographie so hoch, dass selbst dieNSA nicht mithoren kann.

• Dilemma: Polizei hat ein Problem bei der Verbrechensbekamp-fung.

• In Frankreich war das Verschlusseln von 1990 bis 1996 verboten.

• USA: 1993 bis 1996 Escrowed Encryption Standard (EES) ein-

334 11 Politische Randbedingungen

gefuhrt: Verwendung des Clipper-Chips fur Verschlusselung. Dergeheime Schlussel war in jedem Clipper-Chip fest codiert undbeim NIST hinterlegt. Mit richterlicher Anordnung konnte dannabgehort werden.


Chaffing and Winnowing

Ron Rivest [Riv98] ( ⇒ RSA)

Idee: Nachrichten geheimhalten ohne verschlusseln.

Jede Nachricht wird in Pakete zerlegt.

Jedes Paket wird mit einem MAC signiert.

Die Pakete werden alle als Klartext verschickt und besitzen eineSeriennummer zur Rekonstruktion.

(Beispiel aus [Riv98]):

(1,Hi Bob,465231)

(2,Meet me at,782290)

(3,7PM,344287)

(4,Love-Alice,312265)


Alice, die Absenderin, streut zu jedem Paket falsche Pakete miteiner Zufallszahl statt dem MAC ein:

(1,Hi Larry,532105)

(1,Hi Bob,465231)

(2,Meet me at,782290)

(2,I’ll call you at,793122)

(3,6PM,891231)

(3,7PM,344287)

(4,Yours-Susan,553419)

(4,Love-Alice,312265)

Bob, der Empfanger, kennt den Schlussel und kann den MAC uber-prufen. So kann er die Spreu (chaff) vom Weizen trennen.

• Behorden konnten die Hinterlegung des geheimen Schlusselsverlangen.


• Rivest argumentiert so: Da der Schlussel ein Signaturschlusselist, hat die Behorde kein Recht, diesen zu verlangen.


11.2 US-Exportgesetze

Seit 12.1.2000 wurden die Exportrestriktionen fast ganz aufgeho-ben.

Kryptographische Software darf nun an Nicht-Regierungs-Endbenutzerweltweit exportiert werden mit Ausnahme der sieben “Terroristen-Lander” Kuba, Iran, Irak, Libyen, Nord Korea, Sudan und Syrien.

Kapitel 12

Sicherheitslucken in der Praxis

Wenn man ein Verfahren anwendet, das beweisbar sicher und kor-rekt ist, dann hat man beste Voraussetzungen fur Sicherheit in derPraxis. Jedoch keine Garantie!!!

340 12 Sicherheitslucken in der Praxis

Mogliche Gefahrenquellen (unvollstandig!):

Programmierfehlerggf. sicherheitsrelevante Programmteile automatisch verifizie-ren.

Aufbewahrung von SchlusselnProbleme: zu kurze Passworte (Worterbuchangriff), unverschlussel-te Ubertragung des Passwortes, aufgeschriebene Passworter

Bestechung, Erpressung, physische Gewalt

Unvollstandiges LoschenBeim Verschlusseln von Dateien muss darauf geachtet werden,dass die Klartextdatei mit binaren Nullen uberschrieben wird.

341

Kopieren von Schlusseln aus dem HauptspeicherLange Verweilzeiten von Schlusseln im Hauptspeicher sind ungunstig,Auslagern auf die Festplatte sollte verhindert werden.

Schlechte Zufallszahlen

Schlechte Passworter/Vorlagephrasen⇒ Chipkarte mit gespeichertem Schlussel.

Betriebssystemfehler

Inhomogener Sicherheitstandard innerhalb eines Systems

Ein System ist nur so sicher wie der schwachste Zugang.

Umstandliche BedienungSicherheitsfunktionen sollten einfach zu bedienen sein. Sie soll-ten leichter ein- als auszuschalten sein.

342 12 Sicherheitslucken in der Praxis

Geringe Nachfrage nach Sicherheitsfunktionen

Verkehrsanalyse

Trojanische PferdeTrojanische Pferde sind vorgetauschte Benutzeroberflachen, umz. B. Passworter abzuhoren.

Gefalschte offentliche SchlusselVertrauen Sie nur einem offentlichen Schlussel, den Sie personlichvom Eigentumer erhalten haben, oder der von einer Zertifizie-rungsbehorde signiert wurde.

Entsorgen gebrauchter Datentrager

Abhoren elektromagnetischer Wellen

Angriffe aufgrund von Seiteneffekten

343

Gefalschte Zeitstempel

Kapitel 13

Das kleine Einmaleins auf endlichen Mengen

Gesucht: Arithmetik auf endlicher Menge mit n Elementen

Losung: Rechnen mit Resten,d. h. Addieren und Multiplizieren modulo n.

13.1 Modulare Arithmetik 345

13.1 Modulare Arithmetik

17 : 3 = 5 Rest 2 oder 17 = 5 · 3 + 2

12 : 3 = 4 Rest 0 oder 12 = 4 · 3

Der Divisionsrest ist immer eindeutig und es gilt

Satz 13.1 Seien a, b ∈ N und b > 0. Dann gibt es eindeutigenaturliche Zahlen q und r mit a = qb + r und r < b.

Beweis: Es gilt 0 < b ≤ a und ab ≥ a. Sei q das großte Viel-fache von b mit qb ≤ a. Dann ist (q + 1)b = qb + b > a. Also

346 13 Das kleine Einmaleins auf endlichen Mengen

r = a− qb < b.Eindeutigkeit: Angenommen es gibt zwei Paare r1, q1, r2, q2, mitr1 > r2 und q1 < q2, welche die Gleichungen a = q1b + r1

und a = q2b + r2 erfullen. Dann folgt q1b + r1 = q2b + r2 und(q2− q1)b = r1− r2. Wegen q2− q1 > 0 ist r1− r2 ≥ b. Damit istauch r1 ≥ b im Widerspruch zur Annahme. 2

Definition 13.1 Seien a, n ∈ Z und sei a = nq + r mit r < n.Dann schreibt man

r = a mod n.

Zwei Zahlen a, b ∈ Z heißen restgleich, wenn a mod n =b mod n. Man schreibt a ≡ b mod n und spricht a ist kon-gruent zu b modulo n.


Beispiel 13.1

19 ≡ 12 mod 7 = 5 und 19− 12 = 7 ist teilbar durch 7,

2, 5, 8, 11, 14, 17, 20, 23, . . . sind paarweise kongruent modulo 3.

Satz 13.2 Wenn zwei Zahlen bei Division durch n den gleichenRest haben, ist ihre Differenz ein Vielfaches des Moduls n. Fura, b ∈ Z gilt also

a ≡ b mod n ⇔ (a− b) ist teilbar durch n,

Beweis: “⇒”: Sei a ≡ b mod n. Dann haben a und b bei Divisiondurch n den gleichen Rest r. Also gilt a = q1n + r, b = q2n + rund a− b = (q1− q2)n. Damit ist a− b ohne Rest teilbar durch n.


“⇐”: Sei (a − b) durch n teilbar. Dann gibt es ein q ∈ N mita − b = q n. Dividiert man a und b durch n, so erhalt man a =qan + ra und b = qbn + rb. Also gilt

a− b = (qa − qb)n + (ra − rb) = q n

(ra − rb) = (q − qa + qb)n

und (ra− rb) ist durch n teilbar. Da ra, rb < n ist ra− rb < n. Dieeinzige durch n teilbare Zahl kleiner n ist 0. Also ist ra − rb = 0,d. h. a und b sind restgleich. 2

Definition 13.2 Sei n ∈ N. Dann ist Zn := Z/nZ :={0, 1, . . . , n− 1}.


Definition 13.3 Eine naturliche Zahl n > 1 heißt Primzahl,wenn sie nur durch 1 und sich selbst ohne Rest teilbar ist.


Definition 13.4 Eine Struktur (M,+, ·) auf einer Menge M mitden inneren Verknupfungen +, · heißt Ring, wenn gilt:

• (M,+) ist eine kommutative Gruppe, d. h. es gibt bezuglich +ein neutrales Element 0 sowie zu jedem Element a ein Inverses−a und es gelten das Assoziativ- und Kommutativgesetz.

• (M, ·) besitzt ein neutrales Element 1, und es gilt das Assozia-tivgesetz.

• Es gelten die Distributivgesetze a(b+c) = ab+ac und (a+b)c =ac + bc fur alle a, b, c ∈M .

Definition 13.5 Ein Ring (M,+, ·) heißt Korper, wenn (M, ·)kommutativ ist und wenn es zu jedem Element a ein multiplikativesInverses a−1 = 1/a gibt.


Beispielsweise ist (Z,+) eine kommutative Gruppe, (Z,+, ·) einkommutativer Ring und (Q,+, ·) ein Korper.

betrachte (Zn,+, ·).

Addition bzw. Multiplikation sind definiert als (a + b) mod n bzw.(a · b) mod n.

Konvention: oft schreibt man a + b statt (a + b) mod n.

Satz 13.3 (Zn,+, ·) ist ein kommutativer Ring.

Beweis: als Ubung 2

in Zn gelten alle Rechenregeln, analog wie in Q, mit Ausnahme der


Division.

Lemma 13.1 Jeder Korper (K,+, ·) ist nullteilerfrei, d. h. fur allex, y ∈ K\{0} gilt x · y 6= 0.

Beweis: Angenommen es gabe x 6= 0, y 6= 0 mit x ·y = 0. DurchMultiplikation mit y−1 folgt x = 0 im Widerspruch zur Vorausset-zung. 2

13.2 Invertierbarkeit in Zn 353

13.2 Invertierbarkeit in Zn


Beispiel 13.2 (Z4,+, ·) = ({0, 1, 2, 3},+, ·) und Verknupfungs-tabelle:

· 0 1 2 30 0 0 0 01 0 1 2 32 0 2 0 23 0 3 2 1

Z4 ist nicht nullteilerfreigibt es zu 2 kein multiplikativesInverses!Z4 ist kein Korper.3 · 3 = 1.

(Z3,+, ·) = ({0, 1, 2},+, ·) ist ein Korper:

· 0 1 20 0 0 01 0 1 22 0 2 1

1 · 2 = 2 · 1 = 22 ist invers zu sich selbst12 = 2.


Aber: 12 6= 0.5! denn diese Zahl gibt es in Z2 nicht. Es gilt 1

2 + 12 =

2 + 2 = 1.

Satz 13.4 Fur den Ring (Zn,+, ·) gilt:

n prim ⇔ (Zn,+, ·) ist ein Korper.

Beweis: “⇐”: Angenommen Zn ist ein Korper. Dann gilt fur jezwei Elemente x, y ∈ Zn: xy mod n 6= 0 und damit auch xy 6= n.Das heißt aber genau, dass n prim ist.

“⇒”: Sei n prim und sei a 6= 0 eine beliebige Zahl aus Zn. Wirbilden alle Produkte

a · 0, a · 1, a · 2, . . . , a · (n− 1) (13.1)

von a in Zn und zeigen nun, dass diese paarweise voneinander ver-


schieden sind. Ware namlich a · b = a · c fur 0 ≤ b < c < n, sogalte

a · (c− b) ≡ 0 mod n,

d. h. a · (c− b) ist durch n ohne Rest teilbar und es gibt x ∈ N mit

a · (c− b) = x · n.Zerlegen wir nun beide Seiten dieser Gleichung in ihre Primfakto-ren, so kommen links nur Zahlen aus {1, . . . , n− 1} vor, wahrendrechts ein Vielfaches der Primzahl n steht. Dies ist ein Widerspruchzur Eindeutigkeit der Primfaktorzerlegung naturlicher Zahlen. Da-mit sind alle Produkte in (13.1) verschieden und es gilt

{a · 0, a · 1, a · 2, . . . , a · (n− 1)} = {0, 1, 2, . . . , n− 1}. (13.2)

Da 1 ∈ {0, 1, 2, . . . , n − 1} und 1 Produkt von a und einer Zahlq ∈ {0, 1, 2, . . . , n − 1} ist, ist dieses q invers zu a. Da a 6= 0


beliebig gewahlt wurde, gibt es in Zn zu jeder Zahl außer null eininverses. 2

Satz 13.5 (Fermat) Sei n eine Primzahl. Dann gilt in Zn furalle a 6= 0

an−1 = 1.

Beweis: Nach Satz 13.4 ist Zn ein Korper, da n prim ist. Danngilt fur a 6= 0 die Mengengleichung

{1, . . . , n− 1} = {a · 1, . . . , a · (n− 1)},

denn fur x 6= y gilt in einem Korper immer ax 6= ay (Ware diesnicht der Fall, so wurde aus a(x − y) = 0 folgen x = y, was derVoraussetzung x 6= y widerspricht.), weshalb alle Produkte von a


mit einer der Zahlen 1, . . . , n − 1 unterschiedlich und 6= 0 seinmussen.

Mit obiger Mengengleichung gilt auch

1 · . . . · n− 1 = a · 1 · . . . · a · (n− 1) = an−1 · 1 · . . . · (n− 1)

Da Zn ein Korper ist, durfen wir die Zahlen 2, 3, . . . , n− 1 kurzenund erhalten

an−1 = 1,

womit der Satz bewiesen ware. 2

Nebeneffekt: Es gilt an−1 = aan−2 = 1 und damit

a−1 = an−2.


Z. B. ist in Z23

6−1 = 621 = 616+4+1 = (((62)2)2)2 · (62)2 · 6 = ((132)2)2 · (13)2 · 6= (82)2 · 8 · 6 = 182 · 8 · 6 = 2 · 8 · 6 = 96 mod 23 = 4,

Probe: in Z23 ist 6 · 4 = 1.

Unklar: wie geht’s wenn n nicht prim?


13.3 Der Euklidische Algorithmus

Definition 13.6 Fur a, b ∈ N sei ggT(a, b) der großte gemein-same Teiler von a und b, d. h. die großte ganze Zahl, die a und bohne Rest teilt.

13.3 Der Euklidische Algorithmus 361

Beispiel 13.3 Der großte gemeinsamer Teiler von 531 und 93 lasstsich wie folgt durch wiederholte Division berechnen:

531 = 5 · 93 + 66

93 = 1 · 66 + 27

66 = 2 · 27 + 12

27 = 2 · 12 + 3

12 = 4 · 3

Tatsachlich ist ggT(531, 93) = 3, denn es gilt folgender Satz:


Satz 13.6 Euklidischer Algorithmus: Seien a, b ∈ N\{0}.Dann gilt

ggT(a, b) =

{ggT(b, a mod b) falls a mod b 6= 0

b falls a mod b = 0

Beweis: Zuerst beweisen wir den Terminierungsfall der Rekursi-onsformel: Sei a mod b = 0. Dann ist a ist durch b ohne Rest teilbarund a ist Vielfaches von b. Also ist ggT(a, b) = b.Sei nun a mod b 6= 0. Dann ist a = qb + r. Ist d der ggT von aund b, so teilt d auch qb und damit auch r = a− qb. Also ist d einTeiler von b und r. Jeder Teiler von b und r ist auch Teiler von a


und ist damit ≤ d. d ist also auch ggT von b und r. Es folgt

ggT(a, b) = d = ggT(b, r) = ggT(b, a mod b). 2

Mathematica-Programm fur den Euklidischen Algorithmus:

ggT[a ,b ] := ggT[b,Mod[a,b]]

ggT[a ,0] := a

Nochmal das Beispiel:

531 = 5 · 93 + 66

93 = 1 · 66 + 27

66 = 2 · 27 + 12

27 = 2 · 12 + 3


ruckwarts Einsetzen:

3 = 27− 2 · 12

= 27− 2 · (66− 2 · 27) = −2 · 66 + 5 · 27

= −2 · 66 + 5 · (93− 66) = 5 · 93− 7 · 66

= 5 · 93− 7(531− 5 · 93) = −7 · 531 + 40 · 93


Verallgemeinerung: mit r0 := a und r1 := b gilt

r0 = q0 · r1 + r2

r1 = q1 · r2 + r3

. . .

ri = qi+1 · ri+1 + ri+2

. . .

rn−3 = qn−2 · rn−2 + rn−1

rn−2 = qn−1 · rn−1 + rn

rn−1 = qn · rn

ruckwarts Einsetzen ergibt

d = rn

= rn−2 − qn−1 · rn−1= rn−2 − qn−1 · (rn−3 − qn−2 · rn−2) = −qn−1rn−3 + (1 + qn−1qn−2)rn−2

= (. . .)rn−4 + (. . .)rn−3

. . .

= (. . .)r0 + (. . .)r1

= x · r0 + y · r1= x · a+ y · b,


was zu folgendem Satz fuhrt.

Satz 13.7 Sei d = ggT(a, b). Dann gibt es ganze Zahlen x undy mit

d = ggT(a, b) = a x + b y.

Sei ggT(a, n) = 1.

Dann gibt es x und y mit 1 = a x + n y und

1 = 1 mod n = a x mod n + n y mod n = a x mod n.

also: x = a−1.


Beispiel 13.4 gesucht ist 136−1 mod 3003.

3003 = 22 · 136 + 11

136 = 12 · 11 + 4

11 = 2 · 4 + 3

4 = 1 · 3 + 1

⇒ ggT(3003, 136) = 1, also ruckwarts Einsetzen:

1 = 4− 1 · 3= 4− (11− 2 · 4) = 3 · 4− 11

= 3 · (136− 12 · 11)− 11 = 3 · 136− 37 · 11

= 3 · 136− 37 · (3003− 22 · 136) = 817 · 136− 37 · 3003


Also: 817 = 136−1 mod 3003


erweiterter Euklidischer Algorithmus

ErwEuklid(a,b)If(b == 0) Then Return(a,1,0)

(d,x,y) = ErwEuklid(b,Mod(a,b))Return(d,y,x-Div(a,b)*y)

Definition 13.7 Zwei naturliche Zahlen a und b heißen relativprim, wenn ggT(a, b) = 1.

Damit sind nun endlich die Voraussetzungen fur den folgenden, furmultiplikative Chiffren und Tauschchiffren wichtigen Satz geschaf-


fen:

Satz 13.8 Ist ggT(a, n) = 1, dann gibt es zu a eine Inversea−1 bezuglich der Multiplikation in Zn mit aa−1 ≡ 1 mod n. Dererweiterte Euklidische Algorithmus berechnet a−1.

13.4 Die Eulersche ϕ-Funktion 371

13.4 Die Eulersche ϕ-Funktion

Definition 13.8 Fur jede naturliche Zahl n gibt die Eulersche ϕ-Funktion ϕ(n) die Anzahl der naturlichen Zahlen kleiner als n an,die zu n teilerfremd sind, das heißt

ϕ(n) = |{0 ≤ k < n|ggT(k, n) = 1}| .


Beispiel 13.5 ϕ(15) = 8, denn die Zahlen 1,2,4,7,8,11,13,14 sindteilerfremd zu 15. Nun berechnen wir a8 mod 15 fur alle a < 15.

a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14a8 mod 15 0 1 1 6 1 10 6 1 1 6 10 1 6 1 1

Man erkennt, dass a8 mod 15 = 1 immer dann, wenn a und 15 tei-lerfremd sind. Dies gilt allgemein, denn es gilt folgender Satz.

Satz 13.9 Wenn ggT(a, n) = 1, dann gilt aϕ(n) mod n = 1.

Ist n eine Primzahl, so erkennt man leicht, dass ϕ(n) = n− 1. DerFermatsche Satz ergibt sich daher als Spezialfall dieses Satzes.

13.4 Die Eulersche ϕ-Funktion 373

Beispiel 13.6 230 mod 15 = 4, aber

230 mod 15 mod 15 = 20 mod 15 = 1.

Offenbar gilt nicht ab mod n = ab mod n mod n.1

Neuer Versuch:

230 mod ϕ(15) mod 15 = 230 mod 8 mod 15 = 26 mod 15 = 64 mod 15 = 4.

Satz 13.10 Wenn ggT(a, n) = 1, dann gilt ab mod n =ab mod ϕ(n) mod n.

Beweis: Der Exponent b lasst sich schreiben als b = qϕ(n) + r


mit r = b mod ϕ(n). Damit ergibt sich

ab mod n = aqϕ(n)+r mod n = ((aqϕ(n) mod n) · (ar mod n)) mod n

= (aϕ(n) mod n) · (aϕ(n) mod n) · . . . · (aϕ(n) mod n) · (ar mod n)

= 1 · 1 · . . . · 1 · (ar mod n) = ar mod n = ab mod ϕ(n) mod n,

wobei in der vierten Gleichung Satz 13.9 verwendet wurde. 2

13.5 Primzahlen 375

13.5 Primzahlen

iteratur: [?]

Satz 13.11 (Fundamentalsatz der Arithmetik) Jede naturlicheZahl n > 1 besitzt eine eindeutige Primfaktorzerlegung, d.h. zun > 1 gibt es eindeutig bestimmte Primzahlen p1, . . . , pk undnaturliche Zahlen a1, . . . , ak mit

n = pa11 · p

a22 · · · pann .


Satz 13.12 Es gibt unendlich viele Primzahlen.

Beweis: Angenommen es gibt endlich viele Primzahlen und diegroßte Primzahl sei p. Dann berechnen wir die Zahl

n = 2 · 3 · 5 · . . . · p + 1.

Diese Zahl n ist nicht durch eine der Primzahlen 2 bis p teilbar,denn bei jeder Division bleibt der Rest 1. n ist also durch keinePrimzahl teilbar. Aus Satz 13.11 wissen wir jedoch, dass jede Zahlin ihre Primfaktoren zerlegt werden kann. Dieser Widerspruch fuhrtzur Behauptung. 2

Wichtig fur die Schlusselgenerierung beim RSA-Algorithmus:

13.5 Primzahlen 377

Definition 13.9 Fur jede naturliche Zahl n gibt π(n) die Zahlder Primzahlen kleiner oder gleich n an.

Satz 13.13 Die Zahl π(n) der Primzahlen unterhalb n ist furgroße n naherungsweise durch

π(n) ≈ n

lnn− 1.08366≈ n

lnn

gegeben.


1e+09

2e+09

3e+09

4e+09

2e+10 4e+10 6e+10 8e+10 1e+11

n

Primzahlhäufigkeit

π(n)n/(ln(n)−1.08366)

n/ln(n)

0

0.05

0.1

0.15

0.2

0.25

0.3

100000 1e+10 1e+15 1e+20 1e+25 1e+30 1e+35 1e+40

π(n)

/n

n

Primzahldichte

Die Funktion π(n) sowie die beiden Approximationen (links) unddie Primzahldichte (rechts).

13.5 Primzahlen 379

13.5.1 Primzahltests

Fermatscher Satz zur Suche nach großen Primzahlen.

an−1 6= 1 ⇒ n ist nicht prim.

an−1 = 1 ⇒ ?


Beispiel 13.7 berechne an−1 mod n fur alle a zwischen 2 und n−1 (siehe auch Ubung ??) und bestimmen die relative Haufigkeit vonEinsen.

10000 0.

10001 0.00630

10002 0.

10003 0.00349

10004 0.

10005 0.00629

10006 0.

10007 1.

10008 0.

10009 1.

10010 0.

10011 0.02787

10012 0.00019

10013 0.00149

10014 0.

10015 0.00029

10016 0.

10017 0.00149

10018 0.

10019 0.00029

10020 0.

10021 0.00988

10022 0.

10023 0.00069

10024 0.00019

10025 0.00309

10026 0.

10027 0.03221

10028 0.

10029 0.00029

10030 0.

10031 0.00029

10032 0.

10033 0.00348

10034 0.

10035 0.00069

10036 0.00079

10037 1.

10038 0.

10039 1.

10040 0.

10041 0.00029

10042 0.

10043 0.00029

10044 0.

10045 0.00945

10046 0.

10047 0.00069

10048 0.00019

10049 0.00149

10050 0.

10051 0.00109

10052 0.

10053 0.00069

10054 0.00019

10055 0.00029

10056 0.

10057 0.00626

10058 0.

10059 0.00069

10060 0.

10061 1.

10062 0.

10063 0.00029

10064 0.

10065 0.00626

10066 0.00019

10067 1.

10068 0.

10069 1.

10070 0.

10071 0.00029

10072 0.

10073 0.00029

10074 0.

10075 0.00704

10076 0.00039

10077 0.00029

10078 0.

10079 1.

10080 0.

10081 0.02530

10082 0.

10083 0.00029

10084 0.00019

10085 0.00148

10086 0.00039

10087 0.00228

10088 0.

10089 0.00069

10090 0.00079

10091 1.

10092 0.

10093 1.

10094 0.

10095 0.00544

10096 0.00138

10097 0.00029

10098 0.

10099 1.

10100 0.

Relative Haufigkeit von an−1 mod n = 1 fur n ∈ [10000, 10100].Suche nach der maximalen Wahrscheinlichkeit fur

an−1 mod n = 1 unter allen Zahlen n im Intervall [10000,20000].Ergebnis: 12959/15839 ≈ 0.8182. Dieses Maximum tritt auf bei

n = 15841 = 7 · 31 · 73.Fur etwa 82% aller a zwischen 2 und 15840 ist also

a15840 mod 15841 = 1.Simpler Primzahltest:

1. Wahle Zufallszahlen a1, . . . , ak aus {2, . . . , n− 1}2. Berechne an−1

i in Zn3. Falls alle an−1

i = 1, entscheide: n primsonst entscheide: n nicht prim.

Mochte man z.B. n = 15841 testen und wahlt zufallig 100 Zahlenai zwischen 2 und 15840, so ist die Wahrscheinlichkeit, dass sich100 mal a15840

i mod 15841 = 1 ergibt, gleich 0.82100 ≈ 2.4 · 10−9.Das ist die Fehlerwahrscheinlichkeit fur diesen Test, die aber nur

fur n ∈ [10000, 20000] gilt.

13.5 Primzahlen 381

Test von Miller und Rabin:

Satz 13.14 Sei n eine erlaubte Zahl, d. h. eine ungerade Zahlfur die auch n−1

2 ungerade ist. Dann gilt:

1. n prim ⇒ an−1

2 = ±1 fur alle a ∈ Zn\{0}2. n nicht prim ⇒ a

n−12 = ±1 fur hochstens die Halfte der a ∈ Zn\{0}.

Der Beweis der ersten Aussage ist einfach. Da n ungerade ist, istn−1

2 eine naturliche Zahl und es gilt

(an−1

2 + 1)(an−1

2 − 1) = an−1 − 1 = 0

Die letzte Gleichung folgt aus dem Fermatschen Satz (Satz 13.5).

Da Zn ein Korper ist, wird das Produkt (an−1

2 + 1)(an−1

2 − 1) Null


wenn einer der Faktoren Null wird. Daraus folgt die Behauptung.

Fur den Beweis der zweiten Aussage dieses Satzes wird auf [Str96]verwiesen. Will man nun eine Zahl n auf Primalitat testen, so kannman folgendes vereinfachte Verfahren aus [Str96] anwenden.

Statistischer Primzahltest fur erlaubte Zahlen n:

1. Wahle Zufallszahlen a1, . . . , ak aus {1, . . . , n− 1}

2. Berechne an−1

2i in Zn

3. Falls alle an−1

2i = ±1, entscheide: n prim

sonst entscheide: n nicht prim.

Dieser Test ist sehr effizient, aber er gibt nicht immer die korrekte

Antwort. Ist n prim, so gilt nach Satz 13.14 fur alle ai: an−1

2i = ±1.

13.5 Primzahlen 383

Ist jedoch n nicht prim, so kann es sein, dass an−1

2i = ±1 fur alle

ai und der Test antwortet: prim. Die Zahlen a1, . . . , ak werdenubrigens Zeugen (engl. witness) genannt.

Die Fehlerwahrscheinlichkeit ist ≤ (12)k, denn nach Satz 13.14 ist

die Fehlerwahrscheinlichkeit fur jedes einzelne ai hochstens 12. Fur

die Praxis ist dieser Wert jedoch nicht von Interesse, sondern es wirdein anderer Wert benotigt, den man wie folgt berechnet [Sti95]. Furden beschriebenen Test ist die Wahrscheinlichkeit, eine Zahl als primzu klassifizieren, wenn sie zusammengesetzt ist, kleiner oder gleich(1

2)k. Formal laßt sich dies als bedingte Wahrscheinlichkeit

P ( t | p ) ≤ 1

2(13.3)

ausdrucken. Hierbei steht t fur das Ereignis “Die Zahl n bestehtden Test”, p fur das Ereignis “Die Zahl n ist prim” und t


sowie p fur die jeweilige Negation.

Wie erwahnt, ist P ( t | p ) fur die Praxis nicht interessant. Vielmehrbenotigt man die bedingte Wahrscheinlichkeit P ( p | t ) dafur, dassdie Zahl n nicht prim ist, wenn der Test sie als prim klassifiziert.Diesen Wert berechnen wir nun mit der Bayes-Formel

P ( p | t ) =P ( t | p )P ( p )

P ( t )=

P ( t | p )P ( p )

P ( t | p )P ( p ) + P ( t | p )P ( p ).

(13.4)Von den hier benotigten Werten sind

P ( t | p ) = 1

und P ( t | p ) ≤(

1

2

)k

13.5 Primzahlen 385

bekannt. Damit vereinfacht sich Gleichung 13.4 zu

P ( p | t ) ≤(1

2)kP ( p )

P ( p ) + (12)kP ( p )

=P ( p )

P ( p ) + 2kP ( p )(13.5)

=1− P ( p )

1− P ( p ) + 2kP ( p )(13.6)

Wenn die Zahl n in dem Intervall [N, 2N ] liegt, so ist die Zahl derPrimzahlen in diesem Intervall nach Satz 13.13 etwa gegeben durch

2N

ln 2N− N

lnN=

2N

ln 2 + lnN− N

lnN≈ 2N

lnN− N

lnN=

N

lnN≈ n

lnn

Da bei dem Test vorausgesetzt wird, dass n erlaubt ist, gilt

P ( p ) = P (n prim|n erlaubt) =P (n prim und n erlaubt)

P (n erlaubt)≈

12

1lnn14

=2

lnn


Hier wurde außerdem verwendet, dass etwa die Halfte der Primzah-len und ein Viertel aller naturlichen Zahlen erlaubte Zahlen sind.Aus Gleichung 13.6 ergibt sich somit

P ( p | t ) /1− 2

lnn

1− 2lnn + 2k 2

lnn

≈ 1

1 + 2k 2lnn

=1

1 + 2k+1

lnn

≈ lnn

2k+1

Fur RSA mit 1024 Bit langen Schlusseln werden bei der Schlussel-generierung 512 Bit lange Primzahlen benotigt. Folgende Tabellegibt daher fur n = 2512 eine obere Schranke fur die Fehlerwahr-scheinlichkeit P ( p | t ) des Tests an.

k 10 20 40 80(1 + 2k+1

512 ln 2

)−1

0.148 1.69 · 10−4 1.61 · 10−10 1.47 · 10−22

Der Anwender dieses Tests kann also selbst die mittlere Korrekt-

13.5 Primzahlen 387

heit der Antwort des Tests bestimmen, indem er die Anzahl k dergewahlten Zufallszahlen entsprechend hoch setzt. Fur k = 80 istdie Fehlerwahrscheinlichkeit kleiner oder gleich 1.47 · 10−22.

Deterministischer Primzahltest:

• Im August 2002 fanden drei Inder polynomiellen deterministi-schen Primzahltest [?].

• Keine praktische Bedeutung.

• Theoretisch von großer Bedeutung


13.6 Der endliche Korper GF (28)

Gesucht: Chiffre, die auf Bytes arbeitet.

(Z256,+, ·) ungeeignet. warum?

Losung: GF (28) mit 256 Elementen

Die Bits b7, b6, b5, b4, b3, b2, b1, b0 eines Bytes sind Koeffizienten desPolynoms

b(x) = b7x7 + b6x

6 + b5x5 + b4x

4 + b3x3 + b2x

2 + b1x + b0

Das Byte mit dem hexadezimalen Wert ‘57’ (binar 01010111) re-

13.6 Der endliche Korper GF (28) 389

prasentiertx6 + x4 + x2 + x + 1.


Addition

Die Addition von Polynomen ist definiert als Addition der Koeffizi-enten modulo 2.

Beispiel: ‘57’ ⊕ ‘83’ = ‘D4’, oder

(x6 + x4 + x2 + x + 1)⊕ (x7 + x + 1) = x7 + x6 + x4 + x2.

Binardarstellung01010111

⊕ 10000011

11010100

(bitweises XOR).

Die Menge aller Bytes mit dem bitweisen XOR ist eine Gruppe.


Multiplikation

Polynome werden multipliziert modulo eines irreduziblen Polynomsm(x) vom Grad 8.

Ein Polynom heißt irreduzibel, falls es sich nicht als Produkt zwei-er (anderer) Polynome darstellen lasst. Das in Rijndael benutztePolynom ist

m(x) = x8 + x4 + x3 + x + 1

oder ‘11B’ in hexadezimaler Darstellung.


Beispiel 13.8 In GF (28) gilt ‘57’ · ‘83’ = ‘C1’, denn

(x6 + x4 + x2 + x + 1) · (x7 + x + 1)

= x13 + x11 + x9 + x8 + x7+

x7 + x5 + x3 + x2 + x+

x6 + x4 + x2 + x + 1

= x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1

und

(x13 + x11 + x9 + x8 + x6 + x5 + x4 + x3 + 1) mod (x8 + x4 + x3 + x + 1)

= x7 + x6 + 1

Es gibt zwar keine einfache Operation auf Byte-Ebene fur die Multi-plikation, doch auch sie lasst sich effizient implementieren [DR99].


GF (28) ist ein Korper.

Berechnung des Inversen bezuglich der Multiplikation mit erweiter-tem Euklidischem Algorithmus oder nach dem Satz von Fermat,angewandt auf Polynome.


Polynome mit Koeffizienten in GF (28)

Die Elemente von GF (28) sind schlicht alle Byte-Werte, das heißtdie Zahlen 0 bis 255.

Polynome (Grad ≤ 3) mit Bytes als Koeffizienten sind 4-Byte-Worte

Beispiel: ‘57 00 D4 11’ steht fur

57x3 + D4x + 11,

Die Koeffizienten des Polynoms sind nun selbst Polynome, das heißtElemente von GF (28). Damit sind Addition und Multiplikation vonderartigen Polynomen definiert.

Fur die Multiplikation von zwei Polynomen verwenden wir das Sym-bol ⊗.


Hier werden die Koeffizienten entsprechend den Regeln von GF (28)addiert und multipliziert. Man erhalt ein Polynom vom Grad ≤ 6.Dieses wird nun reduziert auf den Grad ≤ 3 durch Bestimmung desDivisionsrestes modulo x4 + 1.

Multiplikation eines derartigen Polynoms mit x modulo x4 + 1 ent-spricht einer zyklischen Verschiebung aller vier Bytes um eins nachlinks.

Beispiel:

((57x3 + D4x + 11)⊗ x) mod (x4 + 1) = D4x2 + 11 x + 57.

In [DR99] wird auch gezeigt, dass die Multiplikation d(x) = a(x)⊗b(x) eines Polynoms a(x) = a3x

3+a2x2+a1+a0 mit dem Polynom

b(x) = b3x3 + b2x

2 + b1 + b0 modulo x4 + 1 dargestellt werden kann


als die Matrixmultiplikationd0

d1

d2

d3

=

a0 a3 a2 a1

a1 a0 a3 a2

a2 a1 a0 a3

a3 a2 a1 a0

b0

b1

b2

b3

,

wobei wie oben die einzelnen Additionen und Multiplikationen nachden Regeln in GF (28) durchgefuhrt werden.

In Rijndael wird ein festes Polynom a(x) gewahlt und in der MixColumn-Transformation mit einem 4-Byte-Wort multipliziert.

Fur das Dechiffrieren ist es wichtig, dass diese Multiplikation um-kehrbar ist, d. h. dass es ein zu a(x) inverses Polynom a−1(x) gibt.

Wie in Satz 13.8 und Satz 3.1 fur multiplikative Chiffren muss dasPolynom a(x) teilerfremd zum Modul x4 + 1 sein.


Das in Rijndael gewahlte Polynom 03x3 + 01x2 + 01x + 02 erfulltdiese Bedingung.

Kapitel 14

Erzeugen von Zufallszahlen

Anwendungen:

• randomisierte Algorithmen

• stochastische Simulation (Monte-Carlo-Simulation)

• Kryptographie (z.B. Schlusselerzeugung, One-Time-Pad)

Lit: Don Knuth “The Art of Computer Programming” Bd. 2

399

Definition von Zufalligkeit:

U. Maurer [Mau92]: “A random bit generator is a devicethat is designed to output a sequence of statistically inde-pendent and symmetrically distributed1 binary random va-riables, i.e., that is designed to be the implementation of aso-called binary symmetric source (BSS). In contrast, apseudo-random bit generator is designed to deterministicallygenerate a binary sequence that only appears as if it weregenerated by a BSS.”

Eine Folge ist zufallig, falls fur jede Lange ` die Verteilung allerZeichenketten der Lange ` maximale Entropie besitzt.

1 Eine binare Variable heißt symmetrisch verteilt, wenn die Wahrscheinlichkeit fur beide Werte exakt 1/2ist.

400 14 Erzeugen von Zufallszahlen

Pseudozufallszahlen

Ein Pseudozufallszahlengenerator (PRNG, pseudo random num-ber generator) ist ein Algorithmus, der nach Eingabe einer odermehrer Initialisierungszahlen (seed numbers) deterministisch eineZahlenfolge erzeugt.

Fur kryptographische Anwendungen sehr problematisch!

Alternative:

Verwendung von physikalischen Zufallsereignissen, wie thermischesRauschen oder radioaktiver Zerfall echte Zufallszahlen

⇒ real random number generator (RRNG).

Philosophie:

401

Bis heute ist unklar ob verborgene Parameter scheinbar zufalli-gen Prozess deterministisch beschreiben.


Kolmogorov-Komplexitat

• Laßt sich eine (große) Datei komprimieren, so ist die der Inhaltnicht zufallig.

• Echte Zufallszahlen lassen sich nicht komprimieren!

• Ist (31415926 . . .) zufallig?

• Nein, denn π = 3.1415926 . . . laßt sich komprimieren

• Computerprogramm kann beliebig viele Dezimalstellen von πberechnen!

403

Definition 14.1 Die Kolmogorov-Komplexitat einer Folgeist die Lange des kurzesten Programms, das die Folgenglieder die-ser Folge berechnen kann [LV88].

Eine zufallige Folge hat unendliche Kolmogorov-Komplexitat!

Fur die Praxis untauglich, denn die Kolmogorov-Komplexitat istnicht berechenbar!

Jeder PRNG erzeugt nur Zahlenfolgen endlicher Kolmogorov-Komplexitat.Also sind diese nicht zufallig


Kompression von Zufallszahlenfolgen

Satz 14.1 Kein Programm kann ohne Verlust alle Dateien mitmindestens n Bit komprimieren (n ≥ 0).

Beweis: Angenommen, ein Programm konnte dies. Wir kompri-mieren mit diesem Programm (nur!) alle Dateien mit genau n Bit.Die komprimierten Dateien sind dann hochstens n−1 Bit groß. DieZahl der komprimierten Dateien der Großen 0 bis n− 1 ist

1 + 2 + 4 + 8 + . . . + 2n−1 = 2n − 1.

Da es 2n Dateien mit n Bit gibt, mussen mindestens zwei Dateienauf die gleiche Datei komprimiert werden. Damit ist die Kompres-sion nicht verlustfrei. 2

405


Pseudozufallszahlengeneratoren

Lineare Kongruenzgeneratoren sind rekursiv definiert durch

xn = (axn−1 + b) mod m.

mit Parametern a, b und m

Die Periode ist hochstens m. Warum?

[Sch96] empfiehlt fur 32 Bit Integer Zahlen a = 7141, b = 54773und m = 259200

Auch Polynomiale Kongruenzgeneratoren der Form

xn = (akxkn−1 + ak−1x

k−1n−1 + . . . + a0) mod m.

konnen geknackt werden.

407

BBS-Generator [BBS86]

Wahle Primzahlen p und q mit

p ≡ q ≡ 3 mod 4.

Berechne n = p ·q und wahle eine Zufallszahl s, mit ggT(S, n) = 1ist.

Berechne den Seedx0 = s2 mod n.

Der Generatur berechnet nun, beginnend mit i = 1 wiederholt

xi = (xi−1)2 mod n

bi = xi mod 2,

Bit bi wird als i− tes Zufallsbit ausgegeben.


BBS gilt als sehr gut, aber:

Ein mit BBS betriebenes One-Time-Pad ist so sicher wie eine Chiffremit einen Schlussel der Lange |s|!

409

Lineare Schieberegister mit Ruckkopplung


Definition 14.2

• Ein Schieberegister der Lange n besteht aus einem Bitvektor(xn, . . . , x1). In jedem Rechenschritt werden die Bits um eineStelle nach rechts verschoben, d. h.

xn 7→ xn−1 , . . . , x2 7→ x1

und es wird links ein neues Bit In nachgeschoben sowie dasletzte Bit Out ausgegeben:

In 7→ xn, x1 7→ Out .

• Ein lineares Schieberegister mit Ruckkopplung (LFSR)berechnet die Eingabe (In) durch Addition modulo 2 von be-stimmten Bits des Registers. (LFSR ist die Abkurzung von li-near feedback shift register.)

411

Beispiel 14.1 LFSR1:

x3

x x2 1

1 1 1

x3 x2 x1 Out1 1 1

0 1 1 1

1 0 1 1

1 1 0 1

0 1 1 0

Periode 3.


Beispiel 14.2 LFSR2 hat die Periode 7:

1 1 1

x3 x2 x1 Out1 1 1

0 1 1 1

1 0 1 1

0 1 0 1

0 0 1 0

1 0 0 1

1 1 0 0

1 1 1 0

Die maximale Periode eines LSFR der Lange n ist 2n − 1.

413

Beispiel 14.3 Analyse eines LFSR der Lange 3Wir beobachten die Bitfolge

B = (01110010)

und suchen die Parameter a1, a2, a3.

1 1 0

a3 a a2 1

Das LFSR lasst sich mathematisch darstellen durch die Abbildung

(x3, x2, x1) 7→ (a1x1 ⊕ a2x2 ⊕ a3x3, x3, x2),

welche iterativ wiederholt wird. Die ersten drei Bit der Folge Bgeben den Zustand des LFSR zu einem bestimmten Zeitpunkt an,d. h. x1 = 0, x2 = 1, x3 = 1Zustand des LFSR: (1, 1, 0)Je eine Zeiteinheit spater gilt fur den Zustand

(1, 1, 1) = (a2 ⊕ a3, 1, 1) (14.1)

(0, 1, 1) = (a3 ⊕ a2 ⊕ a1, 1, 1) (14.2)

(0, 0, 1) = (a2 ⊕ a1, 0, 1) (14.3)

Aus (14.1), (14.2), (14.3) erhalt man die Gleichungen

a2 ⊕ a3 = 1 (14.4)

a3 ⊕ a2 ⊕ a1 = 0 (14.5)

a2 ⊕ a1 = 0 (14.6)

und berechnet

(14.4) in (14.5) : 1⊕ a1 = 0 ⇒ a1 = 1 (14.7)

(14.7) in (14.6) : a2 ⊕ 1 = 0 ⇒ a2 = 1 (14.8)

(14.8) in (14.4) : a3 = 0 (14.9)

Das Schieberegister hat also die Form

1 1 0

und die Folge der Zustande einer Periode von LFSR3 ist

1 1 0

1 1 1 0

0 1 1 1

0 0 1 1

1 0 0 1

0 1 0 0

1 0 1 0

1 1 0 1

0

Man beachte, dass zur Analyse von LFSR3 nur sechs Bit der Aus-gabefolge benutzt wurden und dass LFSR3 maximale Periode hat.


Allgemein kann man zeigen, dass zur Analyse eines linearen Schie-beregisters hochstens 2n Bit der Ausgabefolge benotigt werden.(Berlekamp-Massey-Algorithmus)

415

Stromchiffren

Die Qualitat des Schlusselstroms bestimmt die Sicherheit der Strom-chiffre.

Definition 14.3 Die lineare Komplexitat einer Folge ist dieLange des kurzesten LFSR, das die Folge erzeugen kann.

Besitzt also eine Schlusselfolge endliche lineare Komplexitat n, sowerden nur 2n Bit der Folge benotigt, um den Code der zugehorigenStromchiffre zu knacken.

⇒ Kolmogorov-Komplexitat.


Echte Zufallszahlen

• Spezialhardware

◦ Physikalische Rauschquelle, AD-Wandler, Verstarker, Filter,Test(?)

◦ Spezialhardware (thermisches Rauschen) fur Testzwecke

◦ Spezialhardware fur kryptographische Anwendungen zu teuer

• Intel: thermisches Rauschen eines Widerstands im Pentium-III-Prozessor

◦ Frequenz: 75000 Bits pro Sekunde [Int99, JK99]

• Maxtor: Rauschen von IDE-Festplatten

417

◦ Frequenz: 835200 Bits pro Sekunde [ES00]


Der Neumann-Filter

John von Neumann, 1963

f : 00 7→ ε

11 7→ ε

01 7→ 0

10 7→ 1,

ε = leere Zeichekette

Beispiel 14.4 10001101011100101110 7→ 10011

419

Beispiel 14.5 11111111111111111111 7→ ε

Beispiel 14.6 10101010101010101010 7→ 1111111111Allgemein gilt:

Satz 14.2 Sind aufeinanderfolgende Bits in eine Bit-Folge stati-stisch unabhangig, so sind nach Anwendung des Neumann-Filtersdie Bits symmetrisch verteilt. Die Lange der Bit-Folge verkurztsich dabei um den Faktor p(1− p).

Beweis: Wenn in der Folge a die Bits unabhangig sind und mitWahrscheinlichkeit p den Wert “1” annehmen, dann ist die Wahr-scheinlichkeit fur ein Paar “01” gleich p(1−p). Die Wahrscheinlich-keit fur ein Paar “10” ist auch gleich p(1− p). Damit ist die Wahr-scheinlichkeit pn fur den Wert “1” nach Anwendung des Neumann-


Filters gegeben durch

pn =p(1− p)

2p(1− p)= 1/2.

Fur den Beweis des Verkurzungsfaktors wird auf Ubung 14.4 ver-wiesen. 2

421

Einfluß der Asymmetrie auf die Ausbeute desNeumann-Filters

0

0.05

0.1

0.15

0.2

0.25

0 0.2 0.4 0.6 0.8 1

p(1-p)

p


14.1 Ubungen

Aufgabe 14.1

Warum ist die Periode eines linearen Kongruenzgenerators nachoben beschrankt durch den Wert des Moduls m? Wie mußte manden Generator bei festem Modul m abandern, um die Periodendauerwesentlich langer zu machen.

Aufgabe 14.2

Implementierung und Test von Pseudozufallszahlengeneratoren [BBS86].

14.1 Ubungen 423

a) Implementieren Sie einen linearen Kongruenzgenerator der Form

xn = (axn−1 + b) mod m

mit a = 7141, b = 54773 und m = 259200 in einer (moglichstschnellen) Programmiersprache Ihrer Wahl.

b) Testen Sie die mit diesem Generator erzeugten Bits auf Sym-metrie und Periodizitat.

c) Wiederholen Sie die Tests nach Anwendung des Neumann-Filters.

d) Implementieren Sie den BBS-Generator.

e) Wahlen Sie kleine Werte (< 30) fur p und q und wiederholenSie die o.a. Tests mit und ohne Neumann-Filter.

f) Wahlen Sie nun großere Werte fur p und q (100 < p < q <1000) und wiederholen die Tests.


Aufgabe 14.3

a) Warum ist der Symmetrietest nicht ausreichend, um die Qualitateines Zufallszahlengenerators zu testen?

b) Schlagen Sie andere Tests vor, um die Qualitat eines PRNG furkryptographische Anwendungen zu testen.

c) Was konnen Sie theoretisch sagen uber die Periode des BBS-Generators?

Aufgabe 14.4

Zeigen Sie, dass sich die Lange einer endlichen Bit-Folge (an)n∈{0,1}mit unabhangigen Bits durch Anwendung des Neumann-Filters umetwa den Faktor p(1 − p) verkurzt, wenn der relative Anteil vonEinsen gleich p ist. (Satz 14.2)

14.1 Ubungen 425

Losung zu Aufgabe 14.4

Die Wahrscheinlichkeit fur zwei aufeinanderfolgende Einsen in derFolge ist p2 und fur zwei aufeinanderfolgende Nullen ist sie (1−p)2.Sei n = |(an)n∈{0,1}| und m = |(bn)n∈{0,1}| die Lange der Ergebnis-Folge (bn)n∈{0,1}. Dann gilt

m =1

2(1− p2− (1− p)2) · n =

1

2· 2 · p(1− p) · n = p(1− p) · n.

Literaturverzeichnis

[ACGW99] M. Ashley, M. Copeland, J. Grahn, and D. Wheeler. The gnu privacy handbook. http://www.

gnupg.org/gph/en/manual/book1.html, 1999. 6.4

[AR99] Y. Aumann and M. Rabin. Information theoretically secure communication in the limited storagespace model. In M. Wiener, editor, Advances in Cryptology - CRYPTO’99, volume 1666 ofLNCS, page 65 ff. Springer Verlag, 1999. (document)

[BBS86] L. Blum, M. Blum, and M. Shub. A simple unpredictable pseudo-random number generator. SIAMJournal of Computing, 15(2):364–383, 1986. 13.5.1, 14.2

[BGW01] N. Borisov, I. Goldberg, and D. Wagner. Security of the wep algorithm. http://www.isaac.cs.

berkeley.edu/isaac/wep-faq.html, Januar 2001. (document)

[BSI01] It-sicherheitskriterien - zertifizierung. Bundesamt fur Sicherheit in der Informationstechnik, http://www.bsi.de/zertifiz/index.htm, 2001. 6.4

http://www.gnupg.org/gph/en/manual/book1.html

http://www.gnupg.org/gph/en/manual/book1.html

http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html

http://www.isaac.cs.berkeley.edu/isaac/wep-faq.html

http://www.bsi.de/zertifiz/index.htm

http://www.bsi.de/zertifiz/index.htm

LITERATURVERZEICHNIS 427

[CFN88] D. Chaum, A. Fiat, and M. Naor. Untraceable Electronic Cash. In S. Goldwasser, editor, Advancesin Cryptology CRYPTO ’88, pages 319–327. Springer Verlag, 1988. 6.4

[Cha85] D. Chaum. Security without Identification: Transaction Systems to Make Big Brother Obsolete.Communications of the ACM, 28(10):1030–1044, 1985. http://www.chaum.com/articles/

Security_Wthout_Identification.htm. 6.4, 6.4

[Cha89] D. Chaum. Online Cash Checks. In J.J. Quisquater and J. Vandewalle, editors, Advances inCryptology EUROCRYPT ’89, pages 288–293. Springer Verlag, 1989. http://www.chaum.

com/articles/Online_Cash_Checks.htm. 6.4

[Cha92] D. Chaum. Achieving Electronic Privacy. Scientific American, pages 96–101, August 1992.http://www.chaum.com/articles/Achieving_Electronic_Privacy.htm. 6.4, 6.4

[CM97] C. Cachin and U. Maurer. Unconditional security against memory-based adversaries. In B. Kali-ski, editor, Advances in Cryptology - CRYPTO’97, volume 1233 of LNCS, pages 209–225.Springer Verlag, 1997. ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc/wwwisc/CacMau97b.ps. (document)

[Dew89] A.K. Dewdney. Auf den Spuren der Enigma. Spektrum der Wissenschaft, Computer KurzweilIII, pages 96–99, 1989. Kurze, einfache Beschreibung der Enigma und ihrer Analyse. (document)

[DR99] J. Daemen and V. Rijmen. Aes proposal: Rijndael. NIST-AES Homepage: http://csrc.nist.gov/encryption/aes/round2/r2algs.htm, 1999. (document), 13.5.1

[EFF99] Electronic frontier foundation. http://www.eff.org/pub/Privacy/Crypto_misc/

DESCracker/, 1999. (document)

http://www.chaum.com/articles/Security_Wthout_Identification.htm

http://www.chaum.com/articles/Security_Wthout_Identification.htm

http://www.chaum.com/articles/Online_Cash_Checks.htm

http://www.chaum.com/articles/Online_Cash_Checks.htm

http://www.chaum.com/articles/Achieving_Electronic_Privacy.htm

ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc/wwwisc/CacMau97b.ps

ftp://ftp.inf.ethz.ch/pub/publications/papers/ti/isc/wwwisc/CacMau97b.ps

http://csrc.nist.gov/encryption/aes/round2/r2algs.htm

http://csrc.nist.gov/encryption/aes/round2/r2algs.htm

http://www.eff.org/pub/Privacy/Crypto_misc/DESCracker/

http://www.eff.org/pub/Privacy/Crypto_misc/DESCracker/

428 LITERATURVERZEICHNIS

[EJHF11] W. Ertel, L. Jans, W. Herzhauser, and J. Feßler. An Enigma Replica and its Blueprints. Crypto-logia, 35(1):16–21, 2011. http://www.tandfonline.com/doi/abs/10.1080/01611194.2010.533256. (document)

[Ert07] W. Ertel. Angewandte Kryptographie. Hanser Verlag Munchen, 3. edition, 2007. http://www.hs-weingarten.de/~ertel/kryptobuch.html.

[ES00] W. Ertel and E. Schreck. Real random numbers produced by a maxtor disk drive. http://

ti-voyager.fbe.fh-weingarten.de/ertel/rrng/maxtor.html, 2000. 13.5.1

[Fei73] H. Feistel. Cryptography and computer privacy. Scientific American, Mai 1973. (document)

[FS78] G. Fischer and R. Sacher. Einfuhrung in die Algebra. Teubner Verlag, 1978. 6.1

[Har95] A. Harris. Enigma. Heyne Verlag, 1995. (Englisches Orignial erschienen bei Ballantine Books).(document)

[IET01] Internet engineering task force. http://www.ietf.org, Marz 2001. 6.4

[IMC01] S/mime and openpgp. Internet Mail Consortium, http://www.imc.org/smime-pgpmime.html,2001. 6.4, 6.4

[Int99] The intel random number generator. Intel Platform Security Division, http://developer.intel.com/design/security/rng/rngppr.htm, 1999. 13.5.1

[JK99] B. Jun and P. Kocher. The intel random number generator (white paper). http://developer.

intel.com/design/security/rng/rngppr.htm, 1999. 13.5.1

http://www.tandfonline.com/doi/abs/10.1080/01611194.2010.533256

http://www.tandfonline.com/doi/abs/10.1080/01611194.2010.533256

http://www.hs-weingarten.de/~ertel/kryptobuch.html

http://www.hs-weingarten.de/~ertel/kryptobuch.html

http://ti-voyager.fbe.fh-weingarten.de/ertel/rrng/maxtor.html

http://ti-voyager.fbe.fh-weingarten.de/ertel/rrng/maxtor.html

http://www.ietf.org

http://www.imc.org/smime-pgpmime.html

http://developer.intel.com/design/security/rng/rngppr.htm





[Kah67] D. Kahn. The Codebreakers: The Story of Secret Writing. Macmillan Publishing Co., NewYork, 1967. Umfassende Dokumentation militarischer Kryptanalyse im 20. Jahrhundert. (document)

[Kah91] D. Kahn. Seizing the Enigma. Houghton Mifflin Co., Boston, 1991. (document)

[Kob94] N. Koblitz. A Course in Number Theory and Cryptography. Springer Verlag, 1994. GutesLehrbuch mit viel Mathematik. (document)

[Kol01] G. Kolata. The key vanishes: Scientist outlines unbreakable code. New York Times, 20. Marz2001. http://www.nytimes.com/2001/02/20/science/20CODE.html. (document)

[KP01] S. Kent and T. Polk. Public-key infrastructure (x.509) (pkix). http://www.ietf.org/html.

charters/pkix-charter.html, 2001. 6.4

[KR01] V. Klima and T. Rosa. Attack on private signature keys of the openpgp format, pgp programsand other applications compatible with openpgp. http://www.i.cz/en/pdf/openPGP_attack_

ENGvktr.pdf, Marz 2001. (document), 6.4

[LV88] M. Li and P. Vitanyi. Two decades of applied kolmogorov complexity. In 3rd IEEE Conferenceon Structure in Complexity theory, pages 80–101, 1988. 14.1

[Mau92] U. Maurer. A universal statistical test for random bit generators. Journal of Cryptography,5(2):89–105, 1992. 13.5.1

[Mau01] U. Maurer. Information-theoretic cryptography. http://www.inf.ethz.ch/department/TI/um/research/itc, Marz 2001. (document)

http://www.nytimes.com/2001/02/20/science/20CODE.html

http://www.ietf.org/html.charters/pkix-charter.html

http://www.ietf.org/html.charters/pkix-charter.html

http://www.i.cz/en/pdf/openPGP_attack_ENGvktr.pdf

http://www.i.cz/en/pdf/openPGP_attack_ENGvktr.pdf

http://www.inf.ethz.ch/department/TI/um/research/itc

http://www.inf.ethz.ch/department/TI/um/research/itc


[Men93] A. Menezes. Elliptic Curve Public Key Cryptosystems. Kluwer Academic Publishers, 1993.(document)

[MvOV97] A. Menezes, P. van Oorschot, and S. Vanstone. Handbook of Applied Cryptography. DiscreteMathematics and Its Applications. CRC Press, 1997. (document)

[Nob96] I. Noble. Virtual Enigma. http://www.geocities.com/CapeCanaveral/Launchpad/6720/,1996. Sehr guter Enigma-Simulator und Informationen uber Enigma. (document)

[oPG01] An open specification for pretty good privacy (openpgp). http://www.ietf.org/html.

charters/openpgp-charter.html, Februar 2001. 6.4

[PGP01] The international pgp home page. http://www.pgpI.org, 2001. 6.4

[Rav98] K. Raven. Deutsche Anleitung zu PGP 5.5.X. http://members.xoom.com/Corvuscorax/

pgp5kurs.htm, 1998. 6.4

[Riv98] R. Rivest. Chaffing and winnowing: Confidentiality without encryption. http://theory.lcs.mit.edu/~rivest/chaffing.txt, April 1998. 6.4

[RS74] F. Reinhardt and H. Soeder. dtv–Atlas zur Mathematik (Band 1: Grundlagen – Algebra undGeometrie). Deutscher Taschenbuchverlag, Munchen, 1974. 6.1

[Sch96] B. Schneier. Angewandte Kryptogrphie. Addison-Wesley, 1996. Deutsche Ubersetzung. (docu-ment), 6.4, 6.4, 6.4, 13.5.1

[Sen00] R. Senderek. Key-experiments – how pgp deals with manipulated keys. http://senderek.de/

security/key-experiments.html, August 2000. 6.4

http://www.geocities.com/CapeCanaveral/Launchpad/6720/

http://www.ietf.org/html.charters/openpgp-charter.html

http://www.ietf.org/html.charters/openpgp-charter.html

http://www.pgpI.org

http://members.xoom.com/Corvuscorax/pgp5kurs.htm

http://members.xoom.com/Corvuscorax/pgp5kurs.htm

http://theory.lcs.mit.edu/~rivest/chaffing.txt

http://theory.lcs.mit.edu/~rivest/chaffing.txt

http://senderek.de/security/key-experiments.html

http://senderek.de/security/key-experiments.html


[Sig97a] Informations- und kommunikationsdienste-gesetz - iukdg, artikel 3: Gesetz zur digitalen signatur.Deutscher Bundestag, Juni 1997. 6.4

[Sig97b] Entwurf der signaturverordnung. Bundeskabinett, http://www.iid.de/rahmen/info081097.

html, Oktober 1997. 6.4

[Sig00] Digital signatures. European Commission - Information Society Directorate-General, http://

europa.eu.int/ISPO/ecommerce/legal/digital.html, August 2000. 6.4

[Sil00] R. Silverman. A cost-based security analysis of symmetric and asymmetric key lengths. http:

//www.rsasecurity.com/rsalabs/bulletins/bulletin13.html, 2000. (document)

[Sti95] D. Stinson. Cryptography: Theory and Practice. CRC press, 1995. Fur den mathematischinteressierten Leser sehr zu empfehlen. (document), 13.5.1

[Str96] V. Strassen. Zufalls–Primzahlen und Kryptographie. Konstanzer Schriften in Math. u. Inform. Nr. 7,Univ. Konstanz, 1996. Leicht lesbarer Artikel uber Primzahltests fur die Kryptographie. (document),13.5.1

[TLS01] Transport layer security (tls). http://www.ietf.org/html.charters/tls-charter.html, Ja-nuar 2001. 6.4

[TT01] TC-Trustcenter. personliche mitteilung. http://www.tc-trustcenter.de, 2001. 6.4

[Vig01] Java-applets zur analyse der vigenere chiffre. http://math.ucsd.edu/~crypto/java/

EARLYCIPHERS/Vigenere.html,http://www.math.nmsu.edu/~crypto/Vigenere.html,

http://www.iid.de/rahmen/info081097.html

http://www.iid.de/rahmen/info081097.html

http://europa.eu.int/ISPO/ecommerce/legal/digital.html

http://europa.eu.int/ISPO/ecommerce/legal/digital.html

http://www.rsasecurity.com/rsalabs/bulletins/bulletin13.html

http://www.rsasecurity.com/rsalabs/bulletins/bulletin13.html

http://www.ietf.org/html.charters/tls-charter.html

http://www.tc-trustcenter.de

http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Vigenere.html

http://math.ucsd.edu/~crypto/java/EARLYCIPHERS/Vigenere.html

http://www.math.nmsu.edu/~crypto/Vigenere.html


http://www.uncg.edu/mat/security/vigenere/vigenere.html

, 2001. (document)

[Zim95] P. Zimmermann. The Official PGP User’s Guide. MIT Press, 1995. 6.4

http://www.uncg.edu/mat/security/vigenere/vigenere.html

Documents

Wolfgang Ertel - hs-weingarten.deertel/kryptobuch/kryptobuch-ertel-folien.pdf · 2.1 Terminologie 11 2.1 Terminologie Kryptographie wird verstanden als die Lehre der Absicherung von