RSA-Verschlüsselung

Links:

Eulers digitale Unterschriften, Prof. Dr. Wiland Schmale, Universität Oldenburg, pdf:
Eine sehr prägnante, leicht verständliche Einführung ins RSA-Verfahren
(Eulers digitale Unterschriften anklicken)

http://de.wikipedia.org/wiki/RSA-Kryptosystem

1.
Ein Text soll verschlüsselt übermittelt werden. Zunächst können wir ohne weiteres diesen Text in eine Zahlenfolge umwandeln, indem jedem Buchstaben, jeder Zahl und jedem Sonderzeichen eine zweistellige Dezimalzahl zugeordnet wird.
Beispiel: Leerschlag = 00, A = 01, B = 02, usw. Der so entstandene Zifferntext wird in Blöcke unterteilt.

Beispiel:
"dies ist geheim" wird:
04 09 05 19 00 09 19 20 00 07 05 08 05 09 13
Hier wurden Zweierblöcke hergestellt. Jeder Block ist eine Dezimalzahl.

Nun werden zwei sehr grosse Primzahlen p und q gewählt (die grösser als 10^Blocklänge sein sollten, hier also grösser als 10² . Man bildet das Produkt p⋅ q = m. Nun werden noch ein Exponent e und eine Geheimzahl g gewählt, deren Eigenschaften wir später genauer bestimmen werden.

Es gibt nun einen öffentlichen und einen geheimen Schlüssel. Der öffentliche Schlüssel besteht aus dem Zahlenpaar (m, e), das in einem Verzeichnis veröffentlicht allen Interessierten zugänglich ist.
Der geheime Schlüssel besteht aus dem Zahlenpaar (m, g), der von der sendenden Person streng geheim gehalten werden muss (g steht für "geheim") . Er dient zum Entschlüsseln von Nachrichten.

Wir werden später sehen, dass die Kenntnis von p und q es erlauben würde, die Geheimzahl g zu berechnen. Der springende Punkt ist jedoch, dass die Zahl m = p⋅ q so gross ist, dass eine Zerlegung in die Faktoren p und q auch von schnellsten Rechnern nicht bewältigt werden kann. Man kann zwar aus p und q relativ schnell das Produkt m berechnen, das Zerlegen von m in die Faktoren p und q ist jedoch praktisch unmöglich. Man spricht vom Falltür-Prinzip.

An einem einfachen Modellbeispiel mit p = 3 und q = 5 (somit m = 15) illustrieren wir das Vorgehen.

Wir rechnen mit Restklassen modulo 15. Das bedeutet: Von jeder Zahl betrachten wir nur den Rest, der bei Division durch 15 bleibt.

Beispiel:
36 lässt bei Division durch 15 den Rest 6. Wir schreiben: 36  ≡₍₁₅₎ 6 .
(Gesprochen: 36 ist kongruent 6 modulo 15.)

Jede ganze Zahl z lässt sich auf ihren 15er-Rest reduzieren. Wir rechnen nun mit diesen 15 Restzahlen wie folgt: Wenn beim Addieren, Multiplizieren oder Potenzieren Zahlen grösser als 14 entstehen, reduzieren wir diese auf ihre 15er-Reste und rechnen mit den reduzierten Zahlen weiter. Wir rechnen also lediglich mit den Zahlen 0 bis 14; dies sind die möglichen 15er-Reste.

Satz: Haben zwei Zahlen denselben 15er-Rest, so ist ihre Differenz durch 15 teilbar: Aus 36  ≡₍₁₅₎ 6 folgt z.B. , dass 15 ein Teiler von 36 - 6 ist.
Auch die Umkehrung des Satzes gilt. Somit: a  ≡₍₁₅₎ b ⇔ 15 teilt (a - b).

Mit diesen "Restzahlen" kann man rechnen. Beispiele:

Mit unserer sehr kleinen Wahl von p, q und m können wir die Zahlen von 1 bis 14
verschlüsseln. Wir rechnen mit 15er-Resten. Unsere öffentlich zugängliche Zahl e sei 3. Wir verschlüsseln eine Zahl von 1 bis 14, indem wir sie hoch 3 rechnen (e steht für "Exponent"). Man prüft nach, dass dann aus dem
Klartext {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14} der
codierte Text {1, 8, 12, 4, 5, 6, 13, 2, 9, 10, 11, 3, 7, 14} entsteht.

Erstaunlicherweise sind das wieder alle Zahlen von 1 bis 14, einfach in anderer Reihenfolge. Der Exponent 3 vermag dies zu schaffen. Andere Exponenten schaffen dies nicht, wie man leicht nachprüft. Man probiere z.B. den Exponenten 2, der dies nicht schafft. Fürs Verschlüsseln brauchen wir aber eine Codierung, die zwei verschiedene Zahlen des Klartextes in zwei verschiedene Zahlen des codierten Textes umwandelt und zwar für alle 14 Zahlen des Klartextes.

Wie funktioniert nun die Decodierung? Diese funktioniert in unserem Beispiel mit der Geheimzahl g = 3. Potenzieren wir jede Zahl des codierten Textes mit 3, entsteht erstaunlicherweise wieder der ursprüngliche Klartext. Man prüfe dies nach.

Verschlüsselt und entschlüsselt wird also durch Potenzieren mit geeigneten Zahlen e und g. Dabei müssen e und g folgende Bedingungen erfüllen:

1. Das Potenzieren mit e muss aus den Zahlen 1 bis 14 erneut die Zahlen 1 bis 14 in anderer Reihenfolge ergeben.
2. (z^e)^g = z^eg muss wieder ≡₍₁₅₎ z sein.

Man kann zeigen, dass (1) aus (2) folgt. Wenn also Bedingung (2) erfüllt ist, entstehen automatisch wieder die 14 Zahlen in anderer Reihenfolge.

2.

Beim Rechnen mit Restzahlen kann ein Produkt zweier Zahlen, die nicht 0 sind, durchaus 0 ergeben: 3⋅5 ≡₍₁₅₎ 0,   12⋅5 ≡₍₁₅₎ 0.

Dieser Effekt tritt nicht auf, wenn die Faktoren teilerfremd zu m sind (in unserem Fall also teilerfremd zu 15).

Die zu 15 teilerfremden Zahlen sind folgende 8 Zahlen:
1, 2, 4, 7, 8, 11, 13, 14.


Die Anzahl der zu einer Zahl m teilerfremden Zahlen wird mit φ(m) bezeichnet; φ ist die Eulersche φ -Funktion. Sie ordnet jeder natürlichen Zahl z die Anzahl der zu ihr teilerfremden Zahlen, die kleiner als z sind, zu.

Es ist φ(15) = 8.

Nennen wir die Menge { 1, 2, 4, 7, 8, 11, 13, 14} der zu 15 teilerfremden Zahlen E₁₅ ("E" soll an Leonhard Euler erinnern).

Man stellt folgendes fest (und kann dies leicht einsehen):

1. Das Produkt zweier Zahlen aus E₁₅ ergibt rest-reduziert wieder eine Zahl aus E₁₅ .
2. Zu jeder Zahl a ∈ E₁₅ gibt es eine Zahl b ∈ E₁₅ , mit a⋅b≡₍₁₅₎ 1.
   

So sieht die Multiplikationstabelle der Zahlen aus E₁₅ aus. Die Produkte sind stets wieder auf ihren 15er-Rest reduziert.

In jeder Zeile und in jeder Spalte kommt jede der 8 Zahlen genau einmal vor. Das System bildet eine mathematische Gruppe.

Mit Hilfe obiger Multiplikationstafel kann man nun ein Phänomen zeigen, das auf Leonhard Euler zurückgeht und Satz von Euler genannt wird. Auf unser Beispiel bezogen heisst dies:

Beim Rechnen mit 15er-Resten gilt für jede ganze Zahl z, die teilerfremd zu 15 ist:

Satz von Euler:

z^φ(15) = z⁸ ≡₍₁₅₎ 1 .  Allgemein:  z^φ(m) ≡_(m) 1

für alle ganzen Zahlen z, die teilerfremd zu m sind.

Das heisst im Spezialfall unseres Beispiels: Jede ganze Zahl z, die teilerfremd zu 15 ist, ergibt hoch 8 gerechnet den 15er-Rest 1.

Es genügt, den Satz für die z ∈ E_m zu zeigen.

3.

Beweis des Satzes von Euler

Die Beweisidee, die keine Kenntnisse von mathematischen Gruppen voraussetzt, ist entnommen aus dem pdf von Prof. Dr. Wiland Schmale.

Wir zeigen den Sachverhalt an einem Beispiel. Der allgemeine Beweis ist dann leicht zu führen. Wir wählen wieder m = 15. Mit z = 2 ∈ E₁₅ illustrieren wir den Vorgang.

Feststellung 1: Wenn wir die Folge (1, 2, 4, 7, 8, 11, 13, 14) mit 2 multiplizieren und 15er-Rest-reduzieren, entstehen erneut alle Zahlen nur in anderer Reihenfolge. (Dies gilt auch für jede andere Zahl aus E₁₅.) Die Multiplikationstabelle oben illustriert dies.

Nun bilden wir das Produkt P = 1⋅2⋅4⋅7⋅8⋅11⋅13⋅14.

Wir multiplizieren jeden Faktor mit 2:
(2⋅1)⋅(2⋅2)⋅(2⋅4)⋅(2⋅7)⋅(2⋅8)⋅(2⋅11)⋅(2⋅13)⋅(2⋅14).

Dies ist einerseits wieder kongruent zu P, denn die Faktoren haben bei Multiplikation mit 2 lediglich ihre Positionen vertauscht (siehe Multiplikationstabelle oben).

Andererseits können wir die acht roten Faktoren 2 herausziehen und erhalten
2⁸⋅P.

Somit gilt: 2⁸⋅P ≡₍₁₅₎P oder 2⁸⋅P - P = P⋅(2⁸ - 1) ≡₍₁₅₎0, das heisst
15 teilt P⋅(2⁸ - 1), aber 15 teilt P nicht (denn alle Faktoren von P sind teilerfremd zu 15), somit teilt 15 die Zahl 2⁸ - 1. Folglich hat die Zahl 2⁸ den 15er-Rest 1.

Die Überlegung lässt sich leicht allgemein führen. Wir finden dann:

Für jede Zahl z ∈ E_m und damit auch für jede zu m teilerfremde ganze Zahl z gilt:

z^φ(m) ≡_(m)1 .

4.

Der Satz von Euler und die RSA-Verschlüsselung

Wir haben folgende Bedingungen an die Schlüsselzahlen e und g gefunden, damit Codierung und Decodierung klappen:

1. Das Potenzieren mit e muss aus den Zahlen 1 bis 14 erneut die Zahlen 1 bis 14 in anderer Reihenfolge ergeben.
2. (z^e)^g = z^eg muss wieder ≡₍₁₅₎ z sein.

Dabei folgt (1) aus (2); wir müssen also nur (2) garantieren.

Wählen wir e⋅g so, dass e⋅g ≡₍₈₎1, so ist (e⋅g - 1) ein Vielfaches von 8, und folglich gilt für Zahlen z, die teilerfremd zu 15 sind nach dem Satz von Euler
z^eg-1 ≡₍₁₅₎1.

Dann ist z^eg = z⋅z^eg-1 ≡₍₁₅₎ z. Dies ist aber Bedingung (2).

Damit funktioniert die Codierung und Decodierung.

Mit unserer anfänglichen Wahl e = 3 und g = 3 erfüllen wir die Bedingung
e⋅g ≡₍₈₎1 und deshalb funktionierte die Codierung und Decodierung.

Allgemeines Vorgehen:

1. Wähle zwei riesige Primzahlen p und q und bilde das Produkt m =  p⋅q.
2. Bestimme φ(m) . Für m = p⋅q ist φ(m) = (p - 1)⋅(q - 1). (Der Beweis hierfür ist nicht allzu schwierig.)
3. Bestimme e und g nach der Bedingung e⋅g ≡_(φ(m))1 . *)
4. Codierung: z wird z^e (Potenzieren mit e).
5. Der Schlüssel (m, e) wird öffentlich bekannt gegeben.
6. Decodierung: Potenzieren mit g. g muss geheim bleiben. Die Faktoren p und q können nach Generieren von g vergessen werden; man vernichte entsprechende Hinweise.

*) Die Zahlen e und g müssen, um diese Bedingung zu erfüllen, teilerfremd zu φ(m) sein. Es gibt somit φ(φ(m)) - 1 Kandidaten dafür. In unserem Beispiel sind das die zu 8 teilerfremden Zahlen ohne die 1, also 3, 5, 7. Die Produkte 3⋅3, 5⋅5 und 7⋅7 erfüllen die Bedingung e⋅g ≡₍₈₎1.

Bemerkung: Alle z, die kleiner als p und kleiner als q sind, sind sicher teilerfremd zu m = p⋅q und erfüllen die Voraussetzungen für den Satz von Euler. Wir müssen also p und q recht hoch wählen, respektive den Text in genügend kleine Segmente unterteilen. Je höher p, q sind, desto schwieriger wird es, aus p⋅q = m die Faktoren p und q zu erurieren.

5.

Digitale Unterschrift

Bob und Alice möchten verschlüsselte Nachrichten austauschen.

Alice hat folgende Schlüssel:
Öffentlicher Schlüssel: (m_Alice, e_Alice), geheimer Schlüssel: (m_Alice, g_Alice).

Bob hat folgende Schlüssel:
Öffentlicher Schlüssel: (m_Bob, e_Bob), geheimer Schlüssel: (m_Bob, g_Bob).

Will Bob an Alice eine Nachricht senden, verschlüsselt er sie mit dem öffentlichen Code von Alice, d.h. potenziert mit e_Alice modulo m_Alice.
Alice entschlüsselt die Nachricht durch Potenzieren mit der Geheimzahl g_Alice . Das kann nur sie; sofern m_Alice ein riesiges Produkt p⋅q zweier Primzahlen ist, findet auch ein Supercomputer die Zerlegung in die beiden Primfaktoren p und q nicht innert nützlicher Zeit; somit kann auch φ(m_Alice) = (p - 1)(q - 1) nicht eruiert werden, weshalb auch die Geheimzahl g_Alice nicht berechnet werden kann.

Nun tritt aber ein Problem auf: Nicht nur Bob, sondern jede andere Person, die den öffentlichen Schlüssel von Alice kennt, könnte ihr eine Nachricht senden und sich für Bob ausgeben. Damit Alice sicher ist, dass die Nachricht wirklich von Bob stammt, muss Bob eine digitale Unterschrift anbringen können, die nur er leisten kann.

Bob geht dazu so vor:

Wir nehmen an, dass der Modul m_Alice kleiner sei als der Modul m_Bob.

1. Bob verschlüsselt die Nachricht, welche seine "Unterschrift" beinhaltet, mit e_Alice.

2. Anschliessend wendet er auf diese verschlüsselte Nachricht g_Bob an.
Das kann nur er und niemand sonst, weshalb dieser Schritt seine eigentliche digitale Unterschrift beinhaltet.

3. Was tut Alice mit der so erhaltenen Nachricht? Sie wendet zuerst den öffentlichen Schlüssel e_Bob an, wodurch sie Verschlüsselungsschritt 2 von Bob wieder rückgängig macht. (Fängt jemand die Nachricht ab, kann er dies auch tun, findet das Resultat jedoch immer noch "Alice-verschlüsselt" vor und kann sie nicht lesen.)

4. Nun kann Alice auf den resultierenden Text ihre Entschlüsselung g_Alice anwenden und findet den sinnvollen Unterschrifts-Text von Bob. Der kann nur von ihm stammen, da nur er den Verschlüsselungs-Schritt 2 mit g_Bob durchführen konnte.

Ist m_Alice > m_Bob, so sind die Schritte 1 und 2 und die Schritte 3 und 4 zu tauschen.

Über die Möglichkeit von Unterschriftsfälschungen und deren Verhinderung s. hier.