RSA-Verschlüsselung


Inhaltsverzeichnis

  1. Einleitung

    (Kryptographie, Arithmetik)

  2. Eulersche φ-Funktion

  3. Miller-Rabin-Test

  4. Fermat-Satz

  5. Euklidischer Algorithmus

    4.1 Der einfache euklidische Algorithmus

    4.2 Der moderne euklidische Algorithmus

    4.3 Der erweiterte euklidische Algorithmus

  6. RSA

  7. ((Programmtechnische Umsetzung ))

  8. Schlusswort

  9. 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
17
442 mod 5 ≡ 1 mod 5
17
812 mod 5 ≡ 1 mod 5
17
1612 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.


Beispiele

n

1

2

3

4

5

6

7

8

9

10

teilerfremde
Reste

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:


  1. Wähle n als zu testende Zahl (ungerade)

  2. Berechne d: n - 1 = 2s * d

  3. Wähle zufällig eine Zahl a, für die gilt 1 < a < n

  4. 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:

ap a (mod p)

wobei a eine ganze Zahl und p eine Primzahl ist.

Verallgemeinerung

Man kann den kleinen Fermatschen Satz zum Satz von Euler verallgemeinern.

Für zwei teilerfremde Zahlen n und a gilt:

aφ(n) ≡ 1 (mod n)

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.



Beispiel: ggT(44,12) = 4

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


Erzeugung des öffentlichen und privaten Schlüssels

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:


  1. 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.

  2. Berechne das RSA-Modul N

    N = p * q

  3. Berechne die Eulersche φ-Funktion von N

    φ(N) = φ(p,q) = (p-1)(q-1)

  4. 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

  5. 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

Vorarbeiten

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

Schlüsselerzeugung

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

Verschlüsselung

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

Entschlüsselung

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









Hinweis:

Als Multiplikationszeichen wurde ein Stern ( * ) und als Dividierungszeichen ein Schrägstrich ( / ) benutzt.