Die grundlegenden Eigenschaften von RSA

Inhaltsverzeichnis

1 Einleitung

2 Begriffsdefinitionen
2.1 Kryptosysteme und kryptographische Verfahren
2.2 Asymmetrische kryptographische Verfahren

3 Der mathematische Hintergrund des RSA – Algorithmus
3.1 Definition Teilbarkeit:
3.2 Division mit Rest
3.3 Größter gemeinsamer Teiler
3.4 Euklidischer Algorithmus
3.5 Erweiterter Euklidischer Algorithmus
3.6 Satz von Euler

4 Das Verschlüsselungsverfahren RSA
4.1 Die Schlüsselerzeugung
4.1.1 Algorithmus
4.1.2 Implementierung
4.1.3 Beispiel
4.2 Verschlüsselung, Entschlüsselung und digitale Signatur
4.2.1 Algorithmus
4.2.2 Laufzeit
4.2.3 Beispiel

5 Kryptoanalyse des RSA
5.1 Algorithmus
5.2 Laufzeit

6 Schlussbemerkung

7 Anhang
7.1 Quantoren
7.2 O-Notation

8 Literaturverzeichnis

Abkürzungsverzeichnis:

Abbildung in dieser Leseprobe nicht enthalten

Abbildungsverzeichnis:

Abbildung 1 Zeitaufwand, um Schlüssel unterschiedlicher Größen zu brechen

Abbildung 2 Auszug aus Buchmann, J. (2001), S. 5

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^[1]. 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 Klartext k ([Abbildung in dieser Leseprobe nicht enthalten](plaintext) Klartextraum) seinen Code c ([Abbildung in dieser Leseprobe nicht enthalten] (chiphertext) Chiffretextraum) zu. Die Entschlüsselungsfunktion (D decode function) ordnet jedem Code c wieder seinen Klartext k zu.

Da das Geheimhalten ganzer Algorithmen E und D schwierig bis unmöglich ist^[2], gründet die Philosophie der modernen Kryptographie auf das Prinzip von Kerckhoff^[3]:

"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^[5]:

1. P ist die Menge aller Klartexte (Klartextraum)
2. C ist die Menge aller Chiffretexte^[6] (Chiffretextraum)
3. K ist die Menge aller Schlüssel (Schlüsselraum)
4. E [Abbildung in dieser Leseprobe nicht enthalten]ist die Menge aller Verschlüsselungsfunktionen: [Abbildung in dieser Leseprobe nicht enthalten]
5. D [Abbildung in dieser Leseprobe nicht enthalten]ist die Menge aller Entschlüsselungsfunktionen: [Abbildung in dieser Leseprobe nicht enthalten]
6. Für jeden Kodierschlüssel gibt es einen passenden Dekodierschlüssel
[Abbildung in dieser Leseprobe nicht enthalten]

Mit der hier verwandten Terminologie ist es also die Aufgabe des Verschlüsselungsalgorithmus, die Funktion [Abbildung in dieser Leseprobe nicht enthalten] zu berechnen. Der Entschlüsselungsalgorithmus berechnet analog die Funktion [Abbildung in dieser Leseprobe nicht enthalten]. Beide zusammen bilden ein kryptographisches Verfahren.

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^[7] ). 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^[8]. 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^[9].

Wegen der Existenz einer Umkehrfunktion von [Abbildung in dieser Leseprobe nicht enthalten] (Punkt 6 der Eigenschaften kryptographischer Verfahren) ist [Abbildung in dieser Leseprobe nicht enthalten] injektiv^[10]. Da [Abbildung in dieser Leseprobe nicht enthalten] injektiv und bekannt ist (z.B. einen Angreifer), lässt sich theoretisch [Abbildung in dieser Leseprobe nicht enthalten] auch invertieren (also [Abbildung in dieser Leseprobe nicht enthalten] errechnen)^[11]. Es sind also bei asymmetrischen Verfahren Kodierfunktionen zu verwenden, welche praktisch nicht zu invertieren sind. Solche Funktionen werden mit Einwegfunktion bezeichnet^[12]. Da theoretisch jedes asymmetrische Verfahren gebrochen werden kann, ist die Forderung nach absoluter Sicherheit bei asymmetrischen Verfahren^[13] zu relativieren. Man erwartet, dass das Verfahren ineffizient angewendet werden kann, aber nicht effizient gebrochen werden kann^[14]. Effizient bedeutet dabei in polynominaler Laufzeit^[15]: [Abbildung in dieser Leseprobe nicht enthalten], wobei e1...en positive Konstanten sind und [Abbildung in dieser Leseprobe nicht enthalten]bezeichnen die Längen der Binärentwicklung der n Inputgrößen ([Abbildung in dieser Leseprobe nicht enthalten]) des Algorithmus. Für den hier betrachteten Fall ist n gleich zwei und z1 die Schlüssellänge, während z2 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^[16] 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^[17] [Abbildung in dieser Leseprobe nicht enthalten] gilt [Abbildung in dieser Leseprobe nicht enthalten] (sprich: a teilt b oder b ist durch a teilbar) gdw.^[18] [Abbildung in dieser Leseprobe nicht enthalten](sprich: es gibt eine ganze Zahl [Abbildung in dieser Leseprobe nicht enthalten] mit an = b).

In diesem Fall heißt a Teiler von b, b Vielfaches von a.

Es gilt^[19]: [Abbildung in dieser Leseprobe nicht enthalten] (1a)

und^[20] [Abbildung in dieser Leseprobe nicht enthalten] (1b)

und^[21] [Abbildung in dieser Leseprobe nicht enthalten] (1c)

3.2 Division mit Rest

Sei weiter [Abbildung in dieser Leseprobe nicht enthalten] die größte ganze Zahl, die kleiner als a ist (abrunden). Bsp. [Abbildung in dieser Leseprobe nicht enthalten]

Satz:

„Wenn a, b ganze Zahlen sind, b>0, dann gibt es eindeutig bestimmte ganze Zahlen q und r derart, dass a=qb+r und [Abbildung in dieser Leseprobe nicht enthalten]ist, nämlich [Abbildung in dieser Leseprobe nicht enthalten]und r=a-bq.“^[22] (2)

Beweis: In einem ersten Schritt wird gezeigt dass q und r die Gleichung erfüllen:

Abbildung in dieser Leseprobe nicht enthalten.

In einem zweiten Schritt ist noch zu zeigen, dass aus [Abbildung in dieser Leseprobe nicht enthalten] und [Abbildung in dieser Leseprobe nicht enthalten] folgt [Abbildung in dieser Leseprobe nicht enthalten]und [Abbildung in dieser Leseprobe nicht enthalten]. Es gilt [Abbildung in dieser Leseprobe nicht enthalten] und [Abbildung in dieser Leseprobe nicht enthalten].Und schließlich [Abbildung in dieser Leseprobe nicht enthalten]. 

Man definiert [Abbildung in dieser Leseprobe nicht enthalten] und a div b:= q. (3)

Bemerkung:

Wenn [Abbildung in dieser Leseprobe nicht enthalten]’ dann folgt aus [Abbildung in dieser Leseprobe nicht enthalten] und [Abbildung in dieser Leseprobe nicht enthalten]: [Abbildung in dieser Leseprobe nicht enthalten]. (3a)

Beweis:

Abbildung in dieser Leseprobe nicht enthalten

Abbildung in dieser Leseprobe nicht enthalten

Wenn [Abbildung in dieser Leseprobe nicht enthalten] dann folgt [Abbildung in dieser Leseprobe nicht enthalten] (3b)

Beweis:

Abbildung in dieser Leseprobe nicht enthalten und damit:

Abbildung in dieser Leseprobe nicht enthalten

Wenn [Abbildung in dieser Leseprobe nicht enthalten], dann folgt [Abbildung in dieser Leseprobe nicht enthalten]. (3c)

Beweis: folgt unmittelbar aus Definition (3).

3.3 Größter gemeinsamer Teiler

Der größte gemeinsame Teiler zweier ganzer Zahlen [Abbildung in dieser Leseprobe nicht enthalten], die nicht beide gleich null sind ([Abbildung in dieser Leseprobe nicht enthalten]) (kurz: ggT(a,b)) ist definiert als die größte ganze Zahl, die sowohl a als auch b teilt^[23]: [Abbildung in dieser Leseprobe nicht enthalten]. (4a)

Es gilt^[24]: ggT(a,b) = ggT(a,-b) = ggT (-a,b) = ggT(-a,-b). (4b)

3.4 Euklidischer Algorithmus

Der Euklidische Algorithmus beruht auf folgendem Zusammenhang:

Abbildung in dieser Leseprobe nicht enthalten (5)

Dies motiviert zur Bildung folgender Folge:

Abbildung in dieser Leseprobe nicht enthalten (6a)

Wegen (2) ist [Abbildung in dieser Leseprobe nicht enthalten]. Damit strebt die Folge [Abbildung in dieser Leseprobe nicht enthalten]gegen null. Sei n die kleinste natürliche Zahl mit [Abbildung in dieser Leseprobe nicht enthalten], so ist [Abbildung in dieser Leseprobe nicht enthalten] nach (5) der ggT(a,b). (6b)

Beweis: Wegen Gleichung (4b) gilt: ggT(a,b)=ggT(|a|,|b|).

1. Fall (b=0):

[Abbildung in dieser Leseprobe nicht enthalten]2. Fall: (|b|>0):

Wegen Def. (4a) ist zu zeigen:

Abbildung in dieser Leseprobe nicht enthalten.

Nach (2) gibt es eine ganze Zahl q mit | a|=q|b|+(a mod |b|).

[...]

^[1] Vgl. Wobst, R. (1998), S. 15; Beutelspacher, A. (1993), S. 10

^[2] 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)

^[3] Kerckhoffs von Nieuwenhof (1835-1903)

^[4] Vgl. Beutelspacher, A. (1993), S.23

^[5] ähnlich. Buchmann, J. (2001), S. 55; die Bedeutung der Zeichen ist im Anhang Teil Quantoren erklärt

^[6] In der Literatur auch mit Codes oder Schlüsseltexte bezeichnet.

^[7] Vgl. Beutelspacher, A./Schwenk, J./Wolfenstetter, K.-D. (1995), S.11

^[8] 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.

^[9] Im Gegensatz zu symmetrischen Verfahren, bei denen der Dekodierschlüssel gleich dem Kodierschlüssel ist, muss der Schlüsselaustausch hier nicht geheim stattfinden.

^[10] f ist injektiv bedeutet, dass aus f(x) = f(y) folgt x=y.

^[11] 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.

^[12] Vgl. Bauer, F.L. (1993), S.144

^[13] 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.

^[14] Vgl. Buchmann, J. (2001): S. 7

^[15] Die O-Notation ist im Anhang beschrieben.

^[16] Die kapitelweise Anordnung der Begriffe soll das Nachschlagen erleichtern.

^[17] Die Menge der ganzen Zahlen wird mit Z bezeichnet.

^[18] „Aussage1 gdw. Aussage2“ bedeutet, dass wenn Aussage1 gilt, auch Aussage2 gilt und umgekehrt.

^[19] Beweis:

^[20] Beweis:

^[21] Beweis:

^[22] Zitat Buchmann, J. (2001):, S. 3

^[23] Man kann zeigen, dass eine solche Zahl existiert gdw. .

^[24] Ergibt sich unmittelbar aus Gleichung (1a).