Rsa

RSA Tobias M. Bölz

Inhaltsverzeichnis 1. Einleitung

2

2. Public-Key-Verschlüsselung

2

3. Beschreibung des Verfahrens

3

4. Beweis

4

5. Sicherheit

5

5.1. Angriffsmöglichkeiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2. Sicherheitsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6. Implementation

5 5 5

6.1. Schlüsselgenerierung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Berechnung von M e mod n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A. Beispielprogramme

6 7 8

A.1. inversmod.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2. encrypt1.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3. encrypt2.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . B. Literatur

8 8 9 10

Dieser Inhalt ist unter einem Creative Commons Namensnennung-Nicht-Kommerziell-Weitergabe unter gleichen Bedingungen Lizenzvertrag lizenziert. Um die Lizenz anzusehen, gehen Sie bitte zu http://creativecommons.org/licenses/by-nc-sa/2.0/de/ oder schicken Sie einen Brief an Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

1

2

PUBLIC-KEY-VERSCHLÜSSELUNG

1. Einleitung Das RSA-Verfahren war das erste Public-Key-Verschlüsselungsverfahren, das sowohl zur Verschlüsselung als auch zur Erstellung digitaler Unterschriften eignete. Es wurde 19781 erfunden und ist nach seinen Erfindern Ronald Rivest, Adi Shamir und Leonard Adleman benannt [1]. Da das Konzept eines Public-Key-Verschlüsselungsverfahren von Whitfield Diffie und Martin E. Hellman [2] den Anstoss zu den Überlegungen gab, wird diese Idee im nächsten Abschnitt erklärt. Danach finden Sie eine Beschreibung des RSA-Verfahrens und die Grundzüge eines möglichen Beweisverfahrens, Überlegungen zur Sicherheit sowie Algorithmen, mit deren Hilfe man es implementieren kann.

2. Public-Key-Verschlüsselung Das Konzept der Public-Key-Verschlüsselung (auch asymmetrische Verschlüsselung genannt) wurde 1976 von Whitfield Diffie und Martin E. Hellman entwickelt [2]: Jeder Benutzer veröffentlicht eine Verschlüsselungsmethode E und hält die dazugehörige Entschlüsselungsmethode D geheim. Für E und D muss folgendes gelten: (1) Die Entschlüsselung der Verschlüsselten Form der Nachricht M ist M, also D(E(M)) = M (2) E und D sollen leicht berechenbar sein. (3) D darf nicht leicht (und sollte am besten gar nicht) aus E berechenbar sein. (4) Es soll genauso möglich sein, einen Text mit dem Entdchlüsselungsalgorithmus zu verschlüsseln und dann mit dem Verschlüsselungsalgorithmus zu entschlüsseln: E(D(M)) = M Dies wird beim Erstellen von digitalen Unterschriften verwendet. Eine Funktion E, die (1)-(3) erfüllt, ist eine trap-door one-way function. Wenn sie auch noch (4) erfüllt, ist sie eine trap-door one-way permutation. Dabei bestehen die Fuktionen zur Ver- bzw. Entschlüsselung in der Regel aus einer allgemeinen Funktion und einem Schlüssel. Eine Nachricht wird unter Verwendung des öffentlichen Schlüssels des Empfängers verschlüsselt. Um die Nachricht zu Entschlüsseln verwendet der Empfänger seinen privaten Schlüssel (siehe Abbildung 1). Wenn es sich bei der verwendeten Funktion um eine trap-door one-way permutation handelt, ist es ebenfalls möglich, eine Nachricht digital zu unterschreiben. Dabei wird die Nachricht mit D und dem privaten Schlüssel des Senders verschüsselt. Da (4) gilt kann nun jeder, der den öffentlichen Schlüssel des Senders besitzt, die unterschriebe Nachricht mittels E wieder in Klartext umwandeln (siehe Abbildung 2). Da nur der Sender seinen privaten Schlüssel besitzt kann nur er die Nachricht unterschrieben haben. Ist die Nachricht 1 laut

manchen Quellen 1977, die Veröffentlichung fand aber definitiv 1978 statt

2

3

BESCHREIBUNG DES VERFAHRENS

Abbildung 1: Verschlüsselung mit einem Public-Key-Verfahren

für einen bestimmten Empfänger bestimmt, so verschlüsselt man die signierte Nachricht mit dessen öffentlichen Schlüssel. Alternativ zur Signierung der gesamten kann auch nur eine unterschriebene Prüfsumme mit der Nachricht versendet werden.

Abbildung 2: Digitale Unterschrift mit einem Public-Key-Verfahren

Diffie und Hellman stellten nur das Konzept, jedoch keine mögliche Implementation vor.

3. Beschreibung des Verfahrens Um eine Nachricht M zu verschlüsseln, benötigt man einem öffentlichen Schlüssel (e, n). Zum Entschlüsseln einer verschlüsselten Nachricht C benötigt man einen privaten Schlüssel (d, n). Die Nachricht muss in Blöcke zerlegt werden und die Blöcke jeweils duch einen Integer zwischen 0 und n − 1 repräsentiert werden. Welches Verfahren hier verwendet wird ist für die Verschlüsselung unerheblich, da es nur dazu dient, die Nachricht in numerische Form zu bringen. Eine Nachricht wird mit der Funktion C = M e mod n mit dem öffentlichen Schlüssel (e, n) verschlüsselt. Zur Entschlüsselung dient die Funktion M = Cd mod n mit dem privaten Schlüssel (d, n) (M,C, e, d, n ∈ N). Damit diese Methode funktioniert, müssen e, d und n folgendermaßen berechnet werden: • n ist das Produkt zweier sehr großer Primzahlen p und q: n = p·q p und q müssen geheim bleiben, da sich aus ihnen und dem öffentlichen Schlüssel der private Schlüssel berechnen liese.

3

4

BEWEIS

• d ist eine große zufällige natürliche Zahl, die zu (p − 1) · (q − 1) teilerfremd ist, also ggT(d, (p − 1) · (q − 1)) = 1 erfüllt. • e ist das Inverse zu d bezüglich mod (p − 1)(q − 1), oder anders ausgedrückt (e · d) mod (p − 1) · (q − 1) = 1

4. Beweis Das RSA-Verfahren basiert grundlegend auf dem Satz von Euler, der besagt, dass aϕ(n) ≡ 1 mod n wenn a und n teilerfremd sind. Dabei ist ϕ(n) die Eulersche ϕ-Funktion, die die Anzahl aller natürlichen Zahlen, die kleiner als n und teilerfremd zu n sind, liefert (Für einen Beweis siehe z. B. [3]). Für Primzahlen gilt ϕ(p) = p − 1 Bei RSA ist n das Produkt zweier Primzahlen p und q. Deshalb ist ϕ(n) = ϕ(p) · ϕ(q) = (p − 1) · (q − 1) Die zu zeigenden Aussagen D(E(M)) = M und E(D(M)) = M mit E(M) = M e mod n und D(C) = Cd mod n lässt sich gemäß der Potenzregel zur Restwertarithmetik folgendermaßen umformen: M = D(E(M)) = (E(M))d mod n = M e·d mod n M = E(D(M)) mod n = M e·d mod n Aus der Bedingung (e · d) mod (p − 1) · (q − 1) = 1 folgt e · d = k · ϕ(n) + 1 für ein k ∈ N. Aus dem Satz von Euler ergib sich M p−1 ≡ 1 mod p und da (p − 1) ϕ(n) teilt ist M k·ϕ(n)+1 ≡ M mod p Da das Selbe für q gilt und e · d = k · ϕ(n) + 1 gilt M e·d ≡ M mod n und somit auch D(E(M)) = M und E(D(M)) = M.

4

6

IMPLEMENTATION

5. Sicherheit Man vermutet, dass die Sicherheit von RSA auf dem Problem der Faktorisierung großer Zahlen basiert. Dies ist jedoch nicht bewiesen; es könnte sein, dass es noch andere Möglichkeiten gibt, M aus C und e zu berechnen. 5.1. Angriffsmöglichkeiten

Eine Agriffsmöglichkeit besteht darin, n zu faktorisieren. Dann lässt sich aus den erhaltenen Zahlen und d e berechnen. Eines der schnellsten Verfahren dazu ist die Elliptische-Kurven-Faktorisierung. Die sich daraus ergebenden Schätzungen für die Dauer der Faktorisierung von n sehen Sie in Tabelle 1. Es ist also praktisch unmöglich, n zu faktorisieren, wenn es groß genug ist. Schlüsselgröße 399 Bit 512 Bit 1024 Bit

Dauer 830 MIPS-Jahre 4, 2 · 105 MIPS-Jahre 2, 8 · 1015 MIPS-Jahre

Bewertung mit schnellem Rechner machbar vorläufig sicher langfristig sicher

Tabelle 1: Schätzung der Dauer der Faktorisierung von n unter Verwendung der Elliptische-KurvenFaktorisierung. (Quelle: [4])

Es wäre auch möglich, ϕ(n) zu berechnen, ohne n zu faktorisieren. Aus ϕ(n) und e kann ebenfalls e berechnet werden. Da n zusammengesetzt ist, gibt es jedoch keine einfache Möglichkeit, ϕ(n) zu berechnen, ohne n zu faktorisieren. Ein anderer Weg wäre, d zu erraten. Da es jedoch sehr viele mögliche d gibt ist dieses Verfahren äußerst ineffizient. 5.2. Sicherheitsprobleme

Es könnte sein, dass ein Benutzer durch Unterschreiben eine verschlüsselte Nachricht entschlüsselt. Dazu müsste er jedoch zufällig den selben privaten Schlüssel haben, wie derjenige, der die Nachricht verschlüs∗ selt hat, oder einen Schlüssel, für den gilt M = Cd mod n∗ . Dies ist sehr unwahrscheinlich, jedoch nicht ausgeschlossen. Ein weiteres Problem, das bei der Implementation auftritt, ist, dass die meisten Algorithmen zur Bestimmung von Primzahlen probabilistisch arbeiten. Wenn für p oder q eine zusammengesetzte Zahl verwendet wird, wird die Ver- bzw. Entschlüsselung wahrscheinlich nicht korrekt funktionieren.

6. Implementation Dieser Abschnitt stellt einige Algorithmen, die zur Implementation verwendet werden können, vor. Den Quelltext von lauffähigen Programmen mit den hier vorgestellten Algorithmen finden Sie im Anhang.

5

6.1

Schlüsselgenerierung

6

IMPLEMENTATION

6.1. Schlüsselgenerierung

Der öffentliche und der private Schlüssel können folgendermaßen generiert werden: 1. Da n das Produkt zweier Primzahlen p und q ist, muss ein Weg gefunden werden, sehr große zufällige Primzahlen zu finden. Dabei sollten p und q ähnlich groß und halb so groß wie die vorgesehene Größe von n sein. Dazu gibt es verschiedene Möglichkeiten. Eine ist, so lange Zufallszahlen in der gewünschten Größe generieren, bis eine Primzahl dabei ist. Dabei werden die Zahlen in der Regel aus Geschwindigkeitsgründen mit probabilistischen Methoden überprüft, was zu Fehlern führen kann. Eine Alternative, die jedoch sehr viel Speicher benötigen würde, wäre, aus einer Liste mit Primzahlen zufällig eine auszuwählen. 2. Für d eignet sich z. B. jede Primzahl, die größer als p und q ist. 3. Um e aus d und ϕ(n) zu berechnen kann man den erweiterten Euklidischen Algorithmus verwenden [1, 5]. Dieser berechnet zusätzlich zum ggT die Koeffizienten u und v der Gleichung ggT(a, b) = u · a + v · b; u, v ∈ Z. Setzt man nun a = ϕ(n) und b = e erhält man ggT(ϕ(n), e) = u · ϕ(n) + v · e = 1 da e und ϕ(n) teilerfremd sind. mod ϕ(n) ergibt sich (u · ϕ(n) + v · e) mod ϕ(n) = v · e mod ϕ(n) = 1 v erfüllt also die für d geforderten Bedingungen. Der Euklidischen Algorithmus führt ggT(a, b) auf ggT(b, a mod b) zurück. Der erweiterte Euklidische Algorithmus führt zusätzlich u · a + v · b auf u0 · b + v0 · (a mod b) zurück. Die folgende C-Funktion berechnet den ggT von a und b sowie u und v. Die Ergebnisse werden in den globalen Variablen g, u und v gespeichert. int g, u, v; void erweuklid(int a, int b) { if(b == 0) { g = a; u = 1; v = 0; } else { erweuklid(b, a % b); int tmp = u; u = v; v = tmp - a / b * v; } }

6

6.2

Berechnung von M e mod n

6

IMPLEMENTATION

6.2. Berechnung von M e mod n

Zur Berechnung von M e mod n bzw. Cd mod n gibt es viele Möglichkeiten. Die am wenigsten optimale wäre, die Standard-Funktionen der Programmiersprache, also z. B. in C pow(M, e) % n. Hier würden die einzelnen Rechenschritte nacheinander durchgeführt, was dazu führt, dass das Zwischenergebnis von M e , das extrem groß ist, zwischengespeichert würde. Wenn man die zu lösende Gleichung folgendermaßen umformt M i+1 mod n = (M · (M i mod n)) mod n kann man erkennen, dass sie auch rekursiv gelöst werden kann [6]. Dies lässt sich leicht mit Hilfe einer Schleife implementieren: int C = 1, i; for(i = 1; i <= d; i++) { C = (C * M) % n; } In [1] wird die Potenzierung durch wiederholte Quadrierung und Multiplikation vorgeschlagen. Diese Methode funktioniert folgendermaßen: 1. ek ek−1 . . . e1 e0 sei die binäre Repräsentation von e 2. Initialisierung: C = 1 3. Wiederhole die folgenden Schritte für i = k, k − 1, . . . , 0 a) C = C2 mod n b) Wenn ei = 1, dann C = (C · M) mod n 4. Jetzt ist C = M e mod n In C sieht das z. B. folgendermaßen aus: int C = 1; while(e != 0) { C = (C * C) % n; if(e & 1) { C = (C * M) % n; } e = e >> 1; } Es gibt natürlich noch viele andere und vor allem auch effizientere Algorithmen für diese Problem. Eine Auswahl finden Sie z. B. in [7].

7

A

BEISPIELPROGRAMME

A. Beispielprogramme A.1. inversmod.c #include <stdio.h> #include <stdlib.h> void erweuklid(int a, int b); int g, u, v; int main(int argc, char **argv) { erweuklid(atoi(argv[1]), atoi(argv[2])); printf("%i\n", v); return 0; } void erweuklid(int a, int b) { if(b == 0) { g = a; u = 1; v = 0; } else { erweuklid(b, a % b); int tmp = u; u = v; v = tmp - a / b * v; } }

A.2. encrypt1.c #include <stdio.h> #include <stdlib.h> int encrypt(int M, int e, int n); int main(int argc, char **argv) { printf("%i\n", encrypt(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]))); return 0; }

8

A.3

encrypt2.c

A

BEISPIELPROGRAMME

int encrypt(int M, int e, int n) { int C = 1; int i; for(i = 1; i <= e; i++) { C = (C * M) % n; } return C; }

A.3. encrypt2.c #include <stdio.h> #include <stdlib.h> int encrypt(int M, int e, int n); int main(int argc, char **argv) { printf("%i\n", encrypt(atoi(argv[1]), atoi(argv[2]), atoi(argv[3]))); return 0; }

int encrypt(int M, int e, int n) { int C = 1; while(e != 0) { C = (C * C) % n; if(e & 1) { C = (C * M) % n; } e = e >> 1; } return C; }

9

B. Literatur

[1] Rivest, R. L., Shamir, A. und Adleman, L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. 1978 [2] Diffie, W. und Hellman, P. New Directions in Cryptography. 1976 [3] Wikipedia. Satz von Euler. http://de.wikipedia.org/wiki/Satz_von_Euler [4] Patzelt, D. Vortrag zum Thema RSA-Verschlüsselung. http://www.inf.hs-zigr.de/˜wagenkn/TI/Komplexitaet/Referate/RSA/ [5] Erweiterter Euklidischer Algorithmus. http://www.iti.fh-flensburg.de/lang/algorithmen/code/krypto/euklid.htm [6] Werner, B. RSA-Verschlüsselung und weitere Anwendungen elementarer Zahlentheorie auf die Kalenderrechnung. 2003 [7] Knuth, D. E. The Art of Computer Programming, Vol. 2: Seminumerical Algorithms. Addison-Wesley, 1969

10