RSA-Verschlüsselung
Inhaltsverzeichnis
Einleitung
(Kryptographie, Arithmetik)
Eulersche φ-Funktion
Miller-Rabin-Test
Fermat-Satz
Euklidischer Algorithmus
4.1 Der einfache euklidische Algorithmus
4.2 Der moderne euklidische Algorithmus
4.3 Der erweiterte euklidische Algorithmus
RSA
((Programmtechnische Umsetzung ))
Schlusswort
Quellen
Einleitung
In diesem Text werde ich die RSA-Methode als eine der modernen Verschlüsselungsverfahren behandeln. Kryptographische Verfahren gab es bereits im dritten Jahrtausend v.Chr., sie wurden zum Schutz des Diplomatischen Briefverkehrs genutzt. Diese Verfahren waren allerdings sehr leicht zu knacken, und deshalb wurden diese immer weiter verbessert. Das Problem dabei ist jedoch, dass um eine unknackbares Verfahren zu entwickeln ein Verschlüsselungsschlüssel von der gleichen Länge wie der zu verschlüsselnde Text benötigt werden würde. Dieser müsste aber geheim bleiben – daher könnte man auch direkt die Nachricht geheim übertragen. Deshalb hat man auf einen immer längeren Schlüssel und eine kompliziertere Verschlüsselung gesetzt (wie die Enigma im 2. Weltkrieg). Allerdings blieben diese Verfahren von dritten immer mit viel Aufwand decodierbar. Besonders in de Zeit der Hochleistungscomputer können sehr schnell sehr viele Kombinationen durchprobiert werden und die klassischen Methoden sind von daher vollkommen unsicher. Aus diesem Grunde wurde die RSA-Verschlüsselungstechnik entwickelt.
Nachfolgend
werden wir viel mit modularer Arithmetik umgehen, daher werde
ich eben eine kleine Einführung geben.
Die modulare
Arithmetik (oder auch „Rechnen mit Rest“) ist im Prinzip
ganz einfach. Wir haben das schon alle in der Grundschule gemacht.
Früher
(in der Grundschule) hat man eine Gleichung wie etwa 25 / 7 so
gelöst:
25 / 7 = 3 Rest 4
Die Rechnung könnten wir auch als Modulus (mod) aufschreiben:
25 = 4 mod 7
Anschließend möchte sollten wir einige Rechentricks uns ansehen.
Wie zum Bespiel löst man die Rechnung 1728 mod 5 im Kopf?
Als erstes nimmt man die Zahl 28 auseinander: 28 = 16 + 8 + 4
Daraus
ergibt sich:
1728 ≡
1716 * 178 * 174
Nun Rechnet man das Modul von 17 aus.
17 ≡ 2 mod 5
Das
bedeutet:
172 ≡ 22
mod 5 ≡ 4 mod 5
174
≡ 42
mod 5 ≡ 1 mod 5
178
≡ 12
mod 5 ≡ 1 mod 5
1716
≡ 12
mod 5 ≡ 1 mod
5
1728 ≡
1716 * 178 * 174
≡ 1
* 1
* 1
≡ 1 mod 5
Eulersche φ-Funktion
Die eulersche φ-Funktion(auch eulersche Funktion genannt) ist eine zahlentheoretische Funktion. Sie gibt für jede Zahl n an, wie viele positive ganze Zahlen a < n zu ihr teilerfremd sind.
Die Zahl 6 ist zu zwei der Zahlen von 1 bis 6 teilerfremd (1 und 5), also ist φ(6) = 2.
Die Zahl 13 ist als Primzahl zu den zwölf Zahlen 1 bis 12 teilerfremd, also ist φ(13) = 12.
Die ersten zehn Werte der φ-Funktion lauten:
|
n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
|
teilerfremde |
1 |
1 |
1, 2 |
1, 3 |
1, 2, 3, 4 |
1, 5 |
1, 2, 3, 4, 5, 6 |
1, 3, 5, 7 |
1, 2, 4, 5, 7, 8 |
1, 3, 7, 9 |
|
φ(n) |
1 |
1 |
2 |
2 |
4 |
2 |
6 |
4 |
6 |
4 |
Eigenschaften
Die φ-Funktion ist eine multiplikative zahlentheoretische Funktion. Das heißt, dass für teilerfremde Zahlen m und n die Gleichung
φ(m* n) = φ(m) * φ(n)
gilt.
Berechnung
Da jede Primzahl p nur durch 1 und sich selbst teilbar ist, ist sie zu den Zahlen 1 bis p − 1 teilerfremd. Es gilt daher:
φ(p) = p-1
Miller-Rabin-Test
Das Rabin-Miller-Verfahren ist ein statistisches Verfahren um hoch wahrscheinliche Primzahlen zu finden. Dabei liefert dieses Verfahren keine 100%igen Primzahlen sondern filtert nur eindeutig nicht prime Zahlen heraus. Die Wahrscheinlichkeit bei mehreren Durchläufen dieses Testes eine nicht prime Zahl zu erhalten ist jedoch geringer als das Risiko, dass Empfänger und Sender einer Nachricht gleichzeitig vom Blitz erschlagen werden.
Hier das Verfahren:
Wähle n als zu testende Zahl (ungerade)
Berechne d: n - 1 = 2s * d
Wähle zufällig eine Zahl a, für die gilt 1 < a < n
Wenn ad ≡ 1 (mod n) oder ad2r ≡ -1 (mod n) ist n eine starke Pseudoprimzahl oder eine Primzahl
Man kann diesen Test noch mit anderen Verfahren, wie z.B. mit dem Lucas-Lehmer-Test, kombinieren, in der Regel reicht dieser Test jedoch bei mehrfacher Anwendendung auf ein n.
Fermat-Satz
Der kleine fermatsche Satz, kurz „der kleine Fermat“, ist ein Lehrsatz der Zahlentheorie. Er macht eine Aussage über die Eigenschaften von Primzahlen und wurde im 17. Jahrhundert von Pierre de Fermat aufgestellt. Der Satz beschreibt die allgemein gültige Kongruenz:
wobei a eine ganze Zahl und p eine Primzahl ist.
Man kann den kleinen Fermatschen Satz zum Satz von Euler verallgemeinern.
Für zwei teilerfremde Zahlen n und a gilt:
wobei φ(n) die eulersche φ-Funktion bezeichnet. Diese liefert die Anzahl der Zahlen zwischen 1 und n-1 welche teilerfremd zu n sind. Ist n eine Primzahl, so ist φ(n) = n - 1, so dass man Fermats kleinen Satz als Spezialfall erhält.
Euklidischer Algorithmus
Der einfache Euklidische Algorithmus
Der euklidische Algorithmus ist ein Algorithmus aus dem mathematischen Teilgebiet der Zahlentheorie. Mit ihm lässt sich der größte gemeinsame Teiler(ggT) Zweier natürlicher Zahlen berechnen. Der euklidische Algorithmus ist der älteste nicht-triviale Algorithmus und wird heute noch eingesetzt. Er wurde von dem griechischen Mathematiker Euklid um 300 v.Chr. niedergeschrieben.
Um den ggT zu finden zog Euklid wiederholt die kleinere der beiden Längen von der größeren ab.
Euklid Graphisch (Quelle: Wikipedia.org)
Der moderne Euklidische Algorithmus
Wenn jedoch die Differenz der beiden Zahlen sehr groß ist, braucht man sehr viele Schritte. Deshalb benutzt man heute hauptsächlich den Division-Algorithmus, der anstatt in vielen Schritten die kleinere Zahl abzuziehen, den Rest der Division der größeren Zahl durch die kleinere berechnet.
a und r0 sind die Ausgangszahlen, wobei a < ro.
a = q1 * r0 + r1 a ≡ r1 (mod r0)
r0 = q2 * r1 + r2 r0 ≡ r2 ( mod r1)
r1 = q3 * r2 + r3 usw.
.
.
.
rn-1 = qn+1 * rn + 0
Der Divisor der letzten Division ist dann der ggT.
ggT(a, b) = rn
Erweiterter Euklidischer Algorithmus
Der erweiterte Euklidische Algorithmus ermittelt neben dem ggT auch noch zwei ganze Zahlen s und t, die folgende Gleichung erfüllen
ggT(a,
b) = s * a + t * b
Hier
der einfache Euklid mit den Zahlenpaar 99, 78:
99 = 1 * 78 + 21
78 = 3 * 21 + 15
21 = 1 * 15 + 6
15 = 2 * 6 + 3
6 = 2 * 3 + 0
Für den erweiterten Euklid wird das ganze rückwärts aufgewickelt:
3 = 15 – 2 * 6
= 15 – 2 * (21 – 1 * 15) = 3 * 15 – 2 * 21
= 3 * (78 – 3 * 21) – 2 * 21 = 3 * 78 – 11 * 21
= 3 * 78 – 11* (99 – 1 * 78) = 14 * 78 - 11 * 99
Im ersten Schritt wird die vorletzte Gleichung des einfachen Euklids nach rn-1 umgestellt. Anschließend wird aus dem jeweils darüber liegenden Schritt der Rest rekursiv eingesetzt.
Ergebnis: s = 14 und t = -11.
RSA
Bei der Nachrichtenübermittelung gibt es immer zwei Seiten und den Spion, in meinem Fall Empfänger E und Sender S .
Wenn S Nachricht verschlüsseln will, tut er dies mit dem öffentlichen Schlüssel (public key) der von E bereitgestellt wird. Das Entschlüsseln mit dem öffentlichen Schlüssel ist unmöglich, sondern ist nur mit einem geheimen Schlüssel (privater Schlüssel, private key) von E möglich. Da der private Schlüssel sehr lang ist, gibt es viele Kombinationen, die ein Spion ausprobieren müsste. Das bedeutet jedoch auch, das nicht einmal der Sender die Nachricht wieder entschlüsseln könnte.
Der öffentliche Schlüssel setzt sich dabei aus dem private Schlüssel und einer anderen Primzahl zusammen
Der öffentliche Schlüssel ist ein Zahlenpaar (e,N) und der private Schlüssel ein Zahlenpaar (d,N), wobei N bei beiden Schlüsseln gleich ist. Man nennt N den RSA-Modul, e den Verschlüsselungsexponenten und d den Entschlüsselungsexponenten. Diese Zahlen werden durch das folgende Verfahren erzeugt:
Wähle zufällig und stochastisch unabhängig zwei Primzahlen p ungleich q mit ca. 150 Stellen. In der Praxis rät man dazu jeweils eine Zahl und führt mit dieser anschließend einen Primzahltest (siehe Miller-Rabin) durch.
Berechne das RSA-Modul N
N = p * q
Berechne die Eulersche φ-Funktion von N
φ(N) = φ(p,q) = (p-1)(q-1)
Wähle eine zu φ(N) teilerfremde Zahl e, für die gilt 1 < e < φ(N)
Teilerfremd bedeutet: ggT(N, e) = 1 (siehe „Euklidische Algorithmus“)
Aus Effizienzgründen wird e klein gewählt, üblich ist 216 + 1 = 65537
Berechne den Entschlüsselungsexponenten d:
e*d ≡ 1 (mod φ(N))
(mit Zuhilfenahme des erw. Euklids)
Damit haben wir alle benötigten Schlüssel (e, d, N). Alle anderen Variablen sollten auf sichere Weise gelöscht werden.
Verschlüsseln von Nachrichten
Um eine Nachricht K zu verschlüsseln, verwendet der Absender die Formel
C ≡ Ke (mod N)
und erhält so aus dem Klartext K den Geheimtext C.
Entschlüsseln von Nachrichten (Decodieren)
Der Geheimtext C kann durch modulare Exponentiation wieder zum Klartext K entschlüsselt werden. Der Empfänger benutzt die Formel
K ≡ Cd (mod N) *
mit dem nur ihm bekannten Wert d sowie N.
cd ≡ (Ke)d mod N ≡ Ke*d mod N ≡ Kφ(N)+1 mod N ≡ Kφ(N)*K1 mod N ≡ K mod N
Praktisches Beispiel
Um einen Text zu verschlüsseln, müssen zunächst Buchstaben in Zahlen umgewandelt werden. Dazu verwendet man in der Praxis zum Beispiel den ASCII-Code. Hier sei willkürlich die folgende Zuordnung gewählt:
A=01 B=02 C=03 usw. (00 = Leerzeichen)Darüber hinaus sei angenommen, dass jeweils drei Zeichen zu einer Zahl zusammengefasst werden. Die Buchstabenfolge „AXT“ wird also zu „012420“. Die kleinste zu verschlüsselnde Zahl ist dann 000000 (drei Leerzeichen), die größte 262626 (ZZZ). Der Modulus N = p * q muss also größer 262626 sein.
Klartext: W I K I P E D I A Kodierung: 230911 091605 040901
Zunächst werden geheim zwei Primzahlen gewählt, beispielsweise p = 307 und q = 859. Damit ergibt sich:
N = p * q = 263713
φ(N) = (p – 1) * (q – 1) = 262548
e = 1721 (zufällig, teilerfremd zu φ(N))
d = 1373 (das multiplikative Inverse zu e mod φ(N) mit Hilfe des Erweiterten euklidischen Algorithmus)
Öffentlicher Schlüssel: e = 1721 und N = 263713
Geheimer Schlüssel: d = 1373 und N = 263713
Cn = Kne mod N für n=1,2,3(,...) C1 = 2309111721 mod 263713 = 001715 C2 = 0916051721 mod 263713 = 184304 C3 = 0409011721 mod 263713 = 219983
Kn = Cnd mod N für n=1,2,3(,...) K1 = 0017151373 mod 263713 = 230911 K2 = 1843041373 mod 263713 = 091605 K3 = 2199831373 mod 263713 = 040901
Schlusswort
RSA ist eine sehr sichere und viel benutzte Verschlüsselung. Sie ist jedoch im Vergleich zu 3DES und AES mindestens um einen Faktor 1.000 langsamer. Deshalb benutzt man für die Verschlüsselung größerer Datenmengen hybride Verfahren. Diese setzen symmetrische sowie die asymmetrische Verfahren ein. Es genügt jedoch, RSA zum Austausch eines Schlüssels für die symmetrische Verschlüsselung zu benutzen.
Quellen
Wikipedia.org
Bg-stJohann.tsn.at
uni-erlangen.de
Und viele weitere
Hinweis:
Als Multiplikationszeichen wurde ein Stern ( * ) und als Dividierungszeichen ein Schrägstrich ( / ) benutzt.