Inhaltsverzeichnis

1  Einleitung  5

2  Begriffsdefinitionen  5

2.1  Kryptosysteme und kryptographische Verfahren  5

2.2  Asymmetrische kryptographische Verfahren  6

3  Der mathematische Hintergrund des RSA - Algorithmus  7

3.1  Definition Teilbarkeit:  7

3.2  Division mit Rest  8

3.3  Größter gemeinsamer Teiler  9

3.4  Euklidischer Algorithmus  9

3.5  Erweiterter Euklidischer Algorithmus  10

3.6  Satz von Euler  11

4  Das Verschlüsselungsverfahren RSA  12

4.1  Die Schlüsselerzeugung  12

4.1.1  Algorithmus  12

4.1.2  Implementierung  13

4.1.3  Beispiel  15

4.2  Verschlüsselung, Entschlüsselung und digitale Signatur  15

4.2.1  Algorithmus  16

4.2.2  Laufzeit  17

4.2.3  Beispiel  18

5  Kryptoanalyse des RSA  19

5.1  Algorithmus  20

5.2  Laufzeit  21

6  Schlussbemerkung  22

7  Anhang  24

7.1  Quantoren  24

7.2  O-Notation  24

8  Literaturverzeichnis  25

3

1 Einleitung

Kryptographie bezeichnet die Wissenschaft der Verschlüsselung und Kryptoanalyse die Wissenschaft, die sich damit beschäftigt, den kryptischen Code "zu knacken". Die Gesamtheit beider Wissensdisziplinen bezeichnet man mit Kryptologie ¹ . Da die Sicherheit von kryptographischen Verfahren nur im Kontext kryptoanalytischer Erkenntnisse bewertbar ist, wird in dieser Arbeit auch ein kurzer Einblick in die Kryptoanalyse gegeben. Im besonderen beschäftigt sich diese Arbeit mit dem RSA-Verfahren, einem Vertreter der asymmetrischen kryptografischen Verfahren. Sie geht dabei nicht auf mögliche Ausgestaltungen des Verschlüsselungsprotokolls sowie deren Vor und Nachteile ein. Vielmehr wird sie sich auf die aus den mathematischen Grundlagen des RSA resultierenden Eigenschaften konzentrieren. Dafür werden in Kapitel 2 wichtige Begriffe eingeführt, die das Thema näher charakterisieren. In Kapitel 3 werden die mathematischen Grundlagen für das Verständnis des RSA-Verfahrens vorgestellt, welches in Kapitel 4 erläutert wird. Anschließend wird in Kapitel 5 die Kryptoanalyse des RSA-Verfahrens diskutiert. Am Ende rundet eine Schlussbemerkung diese Arbeit ab.

2 Begriffsdefinitionen

Um die Basis für eine wissenschaftliche Auseinandersetzung mit asymmetrischen kryptographischen Verfahren, insbesondere RSA zu schaffen, ist es notwendig auf die hier verwandte Terminologie einzugehen und wichtige mathematische Sätze einzuführen. Dies soll in den nun folgenden Kapiteln geschehen.

2.1 Kryptosysteme und kryptographische Verfahren

Ein Kryptosystem besteht aus einer Verschlüsselungsfunktion und einer Entschlüsselungsfunktion. Die Verschlüsselungsfunktion (E encode function) ordnet jedem k ∈ (plaintext) Klartextraum) seinen Code c ( c ∈ P C Klartext k ( (chiphertext)

Chiffretextraum) zu. Die Entschlüsselungsfunktion (D decode function) ordnet jedem Code c wieder seinen Klartext k zu.

¹ Vgl. Wobst, R. (1998), S. 15; Beutelspacher, A. (1993), S. 10

5

Da das Geheimhalten ganzer Algorithmen E und D schwierig bis unmöglich ist ² , gründet die Philosophie der modernen Kryptographie auf das Prinzip von Kerckhoff ³ : "Die Sicherheit eines Kryptosystems darf nicht von der Geheimhaltung des Algorithmus

abhängen. Die Sicherheit gründet sich nur auf die Geheimhaltung des Schlüssels." 4

Damit lässt sich jedes Kryptosystem durch ein Fünftupel (P, C, K, E, D) mit den folgenden Eigenschaften beschreiben ⁵ :

1. P ist die Menge aller Klartexte (Klartextraum)

2. C ist die Menge aller Chiffretexte ⁶ (Chiffretextraum)

3. K ist die Menge aller Schlüssel (Schlüsselraum)

E k ∈ = → {

4. E =

5. D

6. Für jeden Kodierschlüssel gibt es einen passenden Dekodierschlüssel

= ∈ ∀ ∈ ∃ ∈ ∀ p p E D P p )) ( ( : : : K d K e

e d

Mit der hier verwandten Terminologie ist es also die Aufgabe des = → × Verschlüsselungsalgorithmus, die Funktion ) ( : ) , ( ; : p E p k v C P K v zu berechnen.

k

Der Entschlüsselungsalgorithmus berechnet analog die Funktion = → × ) ( : ) , ( ; : c D c k v P C K e . Beide zusammen bilden ein kryptographisches Verfahren.

k

2.2 Asymmetrische kryptographische Verfahren

Asymmetrische kryptographische Verfahren (Public-Key-Algorithmus) sind

kryptographische Verfahren mit der Eigenschaft, dass der Dekodierschlüssel d ungleich dem Kodierschlüssel e ist und auch aus diesem praktisch nicht berechnet werden kann (Public-Key-Eigenschaft ⁷ ). Damit ist es möglich, den Kodierschlüssel (public key) zu veröffentlichen, während man den dazugehörigen Dekodierschlüssel (private key) geheim hält ⁸ . Der Sender besitzt damit alle nötigen Informationen zum Kodieren der Nachricht (public key), während die nötigen Informationen zum Dekodieren (private key) nur der Empfänger kennt ⁹ .

² Vgl. historische Bsp. Burnett, S./Paine, S. (2001): S. 45 ff. : Weitere Gründe sind die Möglichkeit des

Vertriebs von Algorithmen deren Sicherheit von einem Schlüssel abhängt (geheime Algorithmen müssten für

jeden Kunden neu entworfen werden) und die Möglichkeit der Diskussion der Algorithmen (mit der Option

sie danach noch verwenden zu können)

³ Kerckhoffs von Nieuwenhof (1835-1903)

⁴ Vgl. Beutelspacher, A. (1993), S.23

∃ ∀, ist im Anhang Teil Quantoren erklärt ⁵ ähnlich. Buchmann, J. (2001), S. 55; die Bedeutung der Zeichen

⁶ In der Literatur auch mit Codes oder Schlüsseltexte bezeichnet.

⁷ Vgl. Beutelspacher, A./Schwenk, J./Wolfenstetter, K.-D. (1995), S.11

⁸ Speziell bei RSA ist es auch möglich, den Dekodierschlüssel zum Kodieren von Nachrichten zu benutzen,

die mit dem Kodierschlüssel dekodiert werden können.

⁹ Im Gegensatz zu symmetrischen Verfahren, bei denen der Dekodierschlüssel gleich dem Kodierschlüssel

ist, muss der Schlüsselaustausch hier nicht geheim stattfinden.

6

Wegen der Existenz einer Umkehrfunktion von D (Punkt 6 der Eigenschaften

d

D injektiv ¹⁰ . Da d kryptographischer Verfahren) ist d D injektiv und bekannt ist (z.B. einen E errechnen) ¹¹ . Es sind also Angreifer), lässt sich theoretisch d D auch invertieren (also e

bei asymmetrischen Verfahren Kodierfunktionen zu verwenden, welche praktisch nicht zu invertieren sind. Solche Funktionen werden mit Einwegfunktion bezeichnet ¹² . Da theoretisch jedes asymmetrische Verfahren gebrochen werden kann, ist die Forderung nach absoluter Sicherheit bei asymmetrischen Verfahren ¹³ zu relativieren. Man erwartet, dass das Verfahren ineffizient angewendet werden kann, aber nicht effizient gebrochen werden kann ¹⁴ . Laufzeit ¹⁵ : Effizient bedeutet dabei in polynominaler

( )

( ) ( ) ( ) e e e Ο z size z size z size , wobei e 1 ...e n positive Konstanten sind und L n 2 1

n ^{2 1} ) ( ) ( 1 z size z size bezeichnen die Längen der Binärentwicklung der n Inputgrößen L

n

( z z L ) des Algorithmus. Für den hier betrachteten Fall ist n gleich zwei und z 1 die

n 1

Schlüssellänge, während z 2 die Länge des Klar- bzw. Chiffretextes ist.

3 Der mathematische Hintergrund des RSA - Algorithmus

Um die Funktionsweise des RSA-Algorithmus zu verstehen, ist es notwendig, gewisse mathematische Begriffe zu verstehen. Die nun folgenden zwei Kapitel ¹⁶ werden die für das Verständnis dieser Arbeit notwendigen Begriffe einführen. Einen detaillierteren Einblick in diese Materie gibt Buchmann, J. (2001).

3.1 Definition Teilbarkeit:

Für zwei ganze Zahlen ¹⁷ a ∈ gilt a | (sprich: a teilt b oder b ist durch a teilbar) Z b , b gdw. ¹⁸ = ∈ ∃ n ∈ mit an = b). b an Z n : Z (sprich: es gibt eine ganze Zahl In diesem Fall heißt a Teiler von b, b Vielfaches von a.

¹⁰ f ist injektiv bedeutet, dass aus f(x) = f(y) folgt x=y.

¹¹ Eine triviale Methode ist es alle Klartexte mit dem öffentlichen Schlüssel zu verschlüsseln und das

Ergebnis mit dem Code (den zu entschlüsselnden Chiffretext) zu vergleichen. Der passende Klartext wird

ausgegeben.

¹² Vgl. Bauer, F.L. (1993), S.144

¹³ Der One-Time -Pad (Vgl. Wobst, R. (1998):, S.60 ff.) bietet ein absolut sicheres sym.

Verschlüsselungsverfahren. Trotzdem wird die Forderung nach absoluter Sicherheit, wegen der

Unpraktikabilität des One-Time -Pads für viele Probleme, auch bei sym. Verfahren relativiert.

¹⁴ Vgl. Buchmann, J. (2001): S. 7

¹⁵ Die O-Notation ist im Anhang beschrieben.

¹⁶ Die kapitelweise Anordnung der Begriffe soll das Nachschlagen erleichtern.

¹⁷ Die Menge der ganzen Zahlen wird mit Z bezeichnet.

¹⁸ „Aussage1 gdw. Aussage2“ bedeutet, dass wenn Aussage1 gilt, auch Aussage2 gilt und umgekehrt.

7