RSA-Algorithmus

Ich habe mich dazu entschlossen ein kleines Tutorial über das RSA-Kryptosystem zu schreiben. Dem Leser soll dabei die Funktionsweise des Verfahrens näher gebracht werden. Zudem soll er am Schluss fähig sein einen Einfachen RSA-Schlüssel selber zu entschlüsseln. Ich halte mich bei dem Tutorial an die englische Ausgabe der NSA.
Zu aller erst müssen einmal die Hintergründe von RSA erläutert werden. RSA basiert auf zwei verschiedenen Schlüsseln. Einer ist öffentlich. Mit diesem können Nachrichten verschlüsselt werden. Einer ist privat. Nur mit diesem Schlüssel kann die verschlüsselte Nachricht wieder entschlüsselt werden.
RSA wurde von Ronald Rivest, Adi Shamir und Leonard Adleman entwickelt. RSA gilt als das erste asymmetrische Verschlüsselungsverfahren. Alle drei arbeiteten damals im MIT-Labor für Computerwissenschaften und wurden durch einen Artikel von Withfield Diffie und Martin Hellman auf das Problem der asymmetrischen Verschlüsselung aufmerksam gemacht. Im Prinzip geht es dabei darum eine Funktion zu finden, die nur in eine Richtung berechnet werden kann. Bei so einer Funktion ist es einfach aus einer gegebenen Zahl ein Ergebnis zu berechnen. Aus dem Ergebnis wieder die anfängliche Zahl zu berechnen ist dagegen nur mit erheblichem Aufwand möglich.



Die Lösung für das Problem sind Primzahlen. Primzahlen sind Zahlen, die nur durch 1 oder sich selber Teilbar sind. Beispielsweise sind 7 oder 19 Primzahlen. Es ist einfach das Produkt aus 7 und 19 zu berechnen. Aus 133 allerdings wieder beide Primzahlen zu erhalten ist bedeutend schwerer. Hierfür muss man von Anfang an alle Primzahlen durchprobieren. Mann beginnt also mit 2, 3,... und teilt die 133 so lange bis eine Zahl ohne Rest heraus kommt. Eine Zahl die das Produkt aus 2 Primzahlen ist kann NUR durch diese beiden Zahlen geteilt werden. Das ist das schöne an Primzahlen.
Für den weiteren Teil bezeichnen wir die beiden Primzahlen mit p und q. Das Produkt beider Zahlen als n.
n = p * q 
Wie findet man nun Primzahlen? Eine Primzahl ist ja, wie bereits erwähnt, durch keine andere Zahl zu teilen. Eine Möglichkeit Primzahlen zu finden ist es daher alle bekannten Primzahlen S miteinander zu Multiplizieren. Das Ergebnis daraus addiert man mit 1. Anschließend schaut man durch welche der bekannten Zahlen die neue Zahl teilbar ist. Der dadurch entstandene Wert ist eine neue Primzahl. Falls keine Zahl geht, so ist die ursprünglich gefundene Zahl eine Primzahl.
S = {P1, P2,..., Pn}
P = (P1 * P2 * ... * Pn) + 1
Nehmen wir also an wir kennen alle Primzahlen bis 7. Das sind 2, 3, 5 und 7. Das Produkt aller Zahlen + 1 ist demnach:
(2 * 3 * 5 * 7)+1 = 211
Tatsächlich ist 211 eine Primzahl. Es gibt jedoch noch jede Menge Primzahlen die zwischen 7 und 211 liegen. Um mit dieser Methode jedoch weiter machen zu können brauchen wir bekanntlich alle Zahlen bis 211. Das ganze ist also nicht sehr effektiv. Letztendlich bleibt uns nichts weiteres übrig als alle Zahlen selber durchzuprobieren. Genau aus diesem Grund sind Primzahlen in der Kryptographie auch so beliebt.

Als Übung kann man einmal selbst ausprobieren alle Primzahlen von 0-100 zu finden. Am besten werden hierfür alle Zahlen auf ein Blatt Papier geschrieben. Wenn man nun eine Primzahl gefunden hat kann man diese markieren. Es können zudem alle vielfachen der Primzahl durchgestrichen werden, da diese ja durch die Primzahl teilbar sind und daher keine Primzahlen mehr seien können. Beispielsweise ist 3 eine Primzahl. 6, 9, 12, ... können demnach keine Primzahlen mehr sein.

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Ein beliebtes Werkzeug der Kryptographie ist der Modulo. Der Modulo ist der Rest einer Division. Beispielsweise ist der Modulo von 5 und 3 = 2, da 5/3 = 1 Rest 2.
a mod n = b
41 mod 7 = 6
21 mod 2 = 1
87 mod 9 = 6
Als nächstes muss der Begriff der Kongruenz geklärt werden. Die Kongruenz ist eine Beziehung zwischen drei Zahlen. Man nennt zwei Zahlen kongruent bezüglich der dritten zahl, wenn diese bei einer Division durch die dritte Zahl (den Modul) den gleichen Rest haben. Beispielsweise sind 5 und 11 kongruent bezüglich 3, da 5/3 = 1 Rest 2 und 11/3 = 3 Rest 2. Beide Zahlen haben den gleichen Rest. Um die Kongruenz zwischen a und b bezüglich n darzustellen schreibt man:
a ≡ b (mod n)
Um diesen Sachverhalt bei zwei Zahlen schnell feststellen zu können berechnet man zuerst a-b. Das Ergebniss muss sich nun ohne Rest durch n Teilen lassen. a und b sind also konkruent, wenn
(a - b) mod n = 0
gilt. Hier noch zwei Beispiele:
13 ≡ 5 (mod 8)
5 ≡ 26 (mod 7)
Das letzte Konzept das wir brauchen ist der größte gemeinsame Teiler, kurz ggT. Der ggT beschreibt, wie der Name schon sagt, die größte natürliche Zahl, durch die zwei verschiedene Zahlen geteilt werden können, ohne das ein Rest entsteht. Die 12 kann beispielsweise durch 1, 2, 3, 4, 6 und 12 geteilt werden. Die 18 kann ducht 1, 2, 3, 6, 9 und 18 geteilt werden. Ihr größter gemeinsamer Teiler ist 6.
ggT(12, 18) = 6
Es gilt zudem:
ggT(a, b) = ggT(a mod b, b)
Nun geht es ans Eingemachte. Wie bereits erwähnt funktioniert RSA mit zwei Schlüsseln. Einem privaten und einem öffentlichen. Mit beiden Schlüsseln können Nachrichten verschlüsselt werden. Entschlüsseln kann man die Nachrichten jedoch nur mit dem Gegenstück.
Angenommen jemand möchte uns eine verschlüsselte Nachricht m schicken, dann nimmt er den öffentlichen Schlüssel EB und verschlüsselt damit die Nachricht EB(m). Der öffentliche Schlüssel ist dabei für jeden verfügbar. Um die Nachricht wieder zu entschlüsseln benutzen wir nun unseren privaten Schlüssel DB und wenden ihn auf die verschlüsselte Nachricht EB(m) an und erhalten unsere Nachricht. DB(EB(m)) = m.
Das ganze funktioniert auch in die andere Richtung. Beispielsweise möchte nun jemand von uns Wissen, ob wir wirklich derjenige sind, der wir vorgeben zu sein. In diesem Fall gibt er uns eine Nachricht die wir mit unserem privaten Schlüssel verschlüsseln sollen. Da nur wir den privaten Schlüssel haben kann das niemand anderes sonst tun. Entschlüsselt wird die Nachricht in diesem Fall mit dem öffentlichen Schlüssel.

Um die beiden Schlüssel zu erhalten ist folgendes notwendig:
1. Zuerst müssen zwei extrem große Primzahlen p und q gefunden werden.
2. Das Produkt n = pq wird berechnet.
3. ɸ(n) = (p-1)(q-1) wird berechnet.
4. Es wird eine Zahl e gewählt die Teilerfremd zu ɸ(n) ist. Es gilt also: ggT(e, ɸ(n) = 1
5. Jetzt muss eine Zahl d gefunden werden für die gilt: ed ≡ 1 (mod ɸ(n)).

Das war es auch schon. Der private Schlüssel ist d, e und n sind zusammen der öffentliche Schlüssel. Gerade die Schritte 4 und 5 sehen schwieriger zu berechnen aus als sie sind. Die beiden Primzahlen p und q können nun ohne Bedenken verworfen werden. Zum ver- und entschlüsseln der Nachricht werden diese nicht mehr gebraucht, sie sind jedoch ein großes Sicherheitsrisiko, wenn sie bekannt werden.

Um einen Buchstaben x der Nachricht m mit dem öffentlichen Schlüssel n und e zu verschlüsseln wird folgende Formel benutzt:
y = xe mod n
Dabei ist y das verschlüsselte Ergebnis. Um das ganze nun wieder in den ursprünglichen Buchstaben x zu entschlüsseln benötigen wir den privaten Schlüssel d und den Modul n.
x = yd mod n

Am besten machen wir das ganze einmal an einem Beispiel. Zuerst brauchen wir also zwei Primzahlen. In unserem Beispiel nehmen wir 5 und 13. Aus beiden Zahlen bilden wir  den Modul n. 5*13 = 65 = n. Jetzt müssen wir ɸ(n) berechnen. Hierführ setzen wir unsere Zahlen in die Formel ein.

ɸ(n) = (p-1)(q-1)
ɸ(n) = 48

Jetzt muss der Exponent e gefunden werden. Dieser muss Teilerfremd zu ɸ(n) sein. Wir benutzen hierfür die Zahl 5. Damit haben wir schon einmal alles was wir brauchen um eine Nachricht zu verschlüsseln. Wir möchten jetzt die Nachricht "Hallo" verschlüsseln. Hieführ wandeln wir die Buchstaben in Zahlen um. Das geschieht am besten nach dem ABC, also ist A=1, B=2,...

B  E  B  U  G
02 05 02 21 07

Wir haben dabei jeden Buchstaben zweistellig umgewandelt. Jetzt müssen wir die Zahlen noch in 4er Gruppen zusammenfügen. Sollte die Letzte zahl nur zwei Stellen haben füllen wir sie mit nullen. Das ganze kann Anschließend mit dem Exponenten e = 5 und dem Modul 65 verschlüsselt werden.

025 mod 65 = 32
055 mod 65 = 5
025 mod 65 = 32
215 mod 65 = 21
075 mod 65 = 37

Unsere verschlüsselte Nachricht lautet nun 32 05 32 21 37.  Ich habe hieführ einen Taschenrechner benutzt. Es gibt aber auch einen Trick um den Modul zu berechnen. ka+b = ka * kb. Diese Rechenregel kann man auch auf unsere Rechnung übertragen. Das ganze einmal an einem Beispiel verdeutlicht.

215 mod 65
= (211 mod 65) * (212 mod 65) * (212 mod 65)
= (21 mod 65) * (51 mod 65) * (51 mod 65)
= (21 * 51 (mod 65)) * (51 mod 65)
= (1071 mod 65) * (51 mod 65)
= 31 * 51 (mod 65)
= 1518 mod 65
= 21


Hinweis: Jedem, der schon einmal etwas mit Cryptographie zu tun hatte sollte hierbei sofort ewas auffallen. Falls wir wirklich so verschlüsseln wollen wäre das schlecht. Der gleiche Buchstabe erhält immer die gleiche verschlüsselte Zahl. Anhand der Häufigkeitsanalyse könnte auf diese Art sehr schnell die Nachricht entschlüsselt werden. Aus diesem Grund werden meistens mehrere Buchstaben zu einem Block zusammengefasst. Beispielsweise wird aus 02 und 05, 0205 gemacht. Dieser gesamte Block wird anschließend verschlüsselt. Um dieses Beispiel jedoch einfach zu halten habe ich den Modul möglichst klein gehalten. Der Modul muss jedoch immer größer sein, als der zu verschlüsselnde Block. Aus diesem Grund wurden die Buchstaben nur in 2er-Blöcken verschlüsselt.

Das ganze können wir nun mit dem privaten Schlüssel d wieder entschlüsseln. Um den privaten Schlüssel zu erhalten benötigen wir eine Zahl d für die gilt: ed ≡ 1 (mod ɸ(n)). Wenn wir unsere Zahlen einsetzen erhalten wir: 5d ≡ 1 (mod 48). Das heist also, dass 5d-1 ein vielfaches von 48 sein muss. Das ganze lässt sich auf verschiedene Arten durchprobieren. Ich stelle hierfür die Formel um und sage: 5d = (k*48)+1. Die Zahl k ist dabei beliebig und muss immer weiter erhöht werden, bis man eine Zahl gefunden hat, die sich durch 5 Teilen lässt. In unserem Fall ist k = 3 ist, dann ist 5d = 145. Damit ist d = 29.

Was brauchen wir nun, wenn wir den privaten Schlüssel d nicht haben und trotzdem die Nachricht entschlüsseln wollen? Um d zu berechnen benötigen wir die beiden Primzahlen p und q. Diese sollten jedoch streng geheim sein. Es bleibt uns also nichts anderes übrig als diese selbst zu berechnen. Beide Zahlen sind in dem Modul n enthalten. Aus diesem Grund sollte der Modul auch möglichst groß gewählt werden.

Finde die Primfaktoren

91
57
115
817
13*7, 19*3, 5*23, 19*43

Finde die Lösung

473 mod 9
34 mod 12
822 mod 23
1837 mod 11
931 mod 62
5, 10, 17, 0, 1

Richtig oder falsch?

25 ≡ 17 mod 8
63 ≡ 21 mod 12
53 ≡ 33 mod 10
91 ≡ 42 mod 2
82 ≡ 7 mod 25
Richtig, Falsch, Richtig, Falsch, Richtig

Finde den ggT

ggT(28, 462) = 7
ggT(36, 27) = 3
ggT(110, 63) = 1
ggT(147, 100) = 1
ggT(54, 7) = 1
7, 3, 1, 1, 1

Entschlüssle die Nachricht

n = 35, e = 5
Das Leerzeichen ist mit 28 Codiert.
09 04 10 28 14 01 10 13 08 24 20 10 28 18 04 23 09 28 14 04 13 08 20 28 24 15 28 10 04 14 06 01 13 08

Entschlüssle die Nachricht

n = 2813, e = 5
Das Leerzeichen ist mit 28 Codiert. Ein Block besteht aus zwei Buchstaben.
0821 1183 0667 2100 2324 1594 0745 2148 2742 2706 1197

Bookmark and Share

1 Kommentare:

Paul Münch hat gesagt…

Wunderbar erklärt und genau das was ich gesucht habe. Ich werde diese Seite auf einem Plakat zu Kryptosystemen verlinken.

Kommentar veröffentlichen