inf-schule | Ein Einblick ins RSA-Verfahren » Die Einwegfunktion hinter RSA

Die Einwegfunktion hinter RSA

Das Verfahren

Bevor wir klären können, wie das Verfahren funktioniert, schauen wir uns eine ganz kurze Anleitung an. Es ist dabei nicht wichtig, die Schritte genau zu verstehen. Alternativ kannst du (im Schnelldurchlauf) die Schritte auf der Seite CrypTool: RSA Step by Step durchlaufen.

Das RSA Verfahren

Suche zwei große Primzahlen $p$ und $q$.
Berechne die Schlüssel:
1. $n = p \cdot q$
2. $\phi(n) = (p-1)\cdot (q-1)$
3. Wähle $e$ teilerfremd zu $\phi(n)$.
4. Berechne $d$ als modulares multiplikatives Inverses von $e$ modulo $\phi(n)$.
5. Veröffentliche $(n,e)$ als öffentlichen Schlüssel; halte $(n,d)$ als privaten Schlüssel geheim.
Verschlüssle den Klartext (eine Zahl) $m$ so: $c = m^e \text{ mod } n$
Verschlüssle den Geheimtext (eine Zahl) $c$ so: $m = c^d \text{ mod } n$

Das haben wir jetzt vermutlich noch nicht verstanden, aber eine Beobachtung fällt dir bestimmt schon auf: Sowohl Klartext als auch Geheimtext sind hier Zahlen (und keine Texte), mit denen dann gerechnet wird.

Aufgabe 1

Erkläre, warum es unproblematisch ist, dass das Verfahren nur für Zahlen funktioniert.

💡 Tipp

Wie werden Texte im Computer gespeichert? $\to$ Codierungen.

Die Suche nach einer Einwegfunktion

Asymmetrische Verschlüsselungsverfahren bauen auf Einwegfunktionen auf, siehe Fachkonzept – Asymmetrisches Chiffriersystem. Wir suchen nun eine passende Einwegfunktion – und damit die Grundidee hinter dem RSA-Verfahren. Wenn du es eilig hast, kannst du direkt zum dritten Versuch springen. Die ersten beiden Versuche helfen aber, den Begriff einer Einwegfunktion besser zu fassen.

Versuch 1

Die erste Idee wurde bereits von Julius Cäsar benutzt: Alle Zeichen einer Nachricht werden um eine vorgegebene Anzahl Stellen verschoben.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
| | | | | | | | | | | | | | | | | | | | | | | | | |
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

Mit Zahlen statt Buchstaben sieht die Verschlüsselung dann so aus:

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 00 01 02

Die Funktion, die hier zur Verschlüsselung genutzt wird, nennen Mathematikerinnen und Mathematiker modulare Addition. Addition, weil jede Zahl mit drei (oder einem anderen Schlüssel) addiert wird. Modular bedeutet, dass man ab einer bestimmten Zahl (dem Modul, hier $26$) wieder bei $0$ anfängt.

(a) Erkläre, inwieweit man hier $(26,3)$ als öffentlichen Schlüssel und $(26,23)$ als privaten Schlüssel ansehen kann.

(b) Erkläre, warum die Verschlüsselung mit modularer Addition ganz sicher keine Einwegfunktion darstellt.

💡 Tipp

Für eine Einwegfunktion müssen zwei Eigenschaften erfüllt sein:

Das Verschlüsseln mit dem öffentlichen Schlüssel und das Entschlüsseln, wenn man den privaten Schlüssel kennt, müssen schnell möglich sein. Das ist hier erfüllt!
Wenn man den privaten Schlüssel nicht kennt, darf man das Verfahren nicht schnell knacken können. Insbesondere darf man also auch nicht den privaten Schlüssel einfach aus dem öffentlichen Schlüssel ausrechnen können. Ist das hier erfüllt?

Versuch 2

Ein neuer Versuch könnte so aussehen: Statt Zahlen zu addieren, wollen wir sie multiplizieren. Auch das soll modular geschehen, wenn wir also über eine vorgegebene Grenze hinausgehen, fangen wir wieder bei $0$ an.

Zum Verschlüsseln werden Zahlen in einem vorgegebenen Bereich (hier $00$ bis $29$) mit einer öffentlichen Zahl (hier $7$) multipliziert. Dabei fangen wir ab dem Modul $30$ wieder bei $00$ an ($30 \to 0$; $31 \to 1$; ...).

00 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 39
 |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
00 07 14 21 28 05 12 19 26 03 10 17 24 01 08 15 22 29 06 13 20 27 04 11 18 25 02 09 16 23

(a) Überprüfe, am Beispiel der Zahl $6$, ob hier wirklich richtig gerechnet worden ist: $6 \cdot 7 = ??$. Weil das Ergebnis $30$ oder größer ist, musst du $30$ abziehen, um auf den Geheimtext zu kommen. Überprüfe auch das Ergebnis der Zahl $9$. Achtung: Hier musst du mehrfach $30$ abziehen.

(b) Zur Umkehrung kann man einen Geheimtext auf dieselbe Weise mit $13$ multiplizieren. Man nennt $13$ das modulare multiplikative Inverse von $7$ modulo $30$. Probiere das an mehreren Beispielen aus. Kommt wirklich wieder der Klartext heraus?

(c) Erkläre, warum die modulare Multiplikation keine Einwegfunktion darstellt, falls man für eine gegebene Zahl (z.B. 7) problemlos ihr modulares multiplikative Inverses (hier 13) ausrechnen kann. Erkläre, was das für die Sicherheit des Verfahrens bedeuten würde.

(d) Ein Weg, modulare Inverse zu finden, besteht darin, einfach alle möglichen Zahlen durchzuprobieren. Die folgende Funktion macht das. Probiere aus, damit das modulare Inverse von 7 modulo 30 und das modulare Inverse von 49 modulo 1000010000100001000010000100001000010000100001000010000 zu bestimmen. Beurteile danach: Handelt es sich bei der modularen Multiplikation um eine Einwegfunktion?

def modInv(e, n):
    gefunden = False
    d = 1
    while n >= d and not gefunden:
        if (e * d) % n == 1:
            gefunden = True
        else:
            d = d + 1
    if d > n:
        d = -1
    return d

e = int(input("Gib die Zahl ein, deren modulares Inverses du suchst: "))
n = int(input("Gib den Modul ein, also ab wann wieder bei 0 weitergerechnet wird: "))
d = modInv(e,n)
print("Das modulare Inverse von " + str(e) + " modulo " + str(n) + " lautet " + str(d) + ".")

(e) Scheinbar ist es für große Zahlen nicht möglich, modulare multiplikative Inverse in sinnvoller Zeit zu berechnen. Tatsächlich kann man im Falle von Aufgabe (d) ausrechnen, dass ein handelsüblicher Rechner $10^{39}$ Jahre benötigt, um alle Kandidaten auszuprobieren. Doch vielleicht gibt es ja andere Möglichkeiten, als alles auszuprobieren? Teste die gleichen Zahlen mit dem folgenden Programm. (Der Quellcode ist kompliziert und hier auch nicht relevant).

def erweiterterEuklidischerAlgorithmus(a, b):
    aalt = a
    amitte = b
    xalt = 1
    xmitte = 0
    yalt = 0
    ymitte = 1
    while amitte != 0:
        q = aalt // amitte
        aneu = aalt - q * amitte
        xneu = xalt - xmitte * q
        yneu = yalt - ymitte * q
        xalt = xmitte
        xmitte = xneu
        yalt = ymitte
        ymitte = yneu
        aalt = amitte
        amitte = aneu
    return (aalt, xalt, yalt)

def modInv(a, m):
    (ggt, x, y) = erweiterterEuklidischerAlgorithmus(a, m)
    if ggt > 1:
        return -1
    else:
        if 0 > x:
            x = x + m
        return x

e = int(input("Gib die Zahl ein, deren modulares Inverses du suchst: "))
n = int(input("Gib den Modul ein, also ab wann wieder bei 0 weitergerechnet wird: "))
d = modInv(e,n)
print("Das modulare Inverse von " + str(e) + " modulo " + str(n) + " lautet " + str(d) + ".")

(f) Was kannst du nun nach den weiteren Versuchen sagen? Stellt die modulare Multiplikation eine Einwegfunktion dar?

Versuch 3

Unsere bisherigen Versuche waren wenig erfolgreich. Der nächste Versuch, eine Einwegfunktion zu finden, hat auf den ersten Blick nichts mit Verschlüsselungsverfahren zu tun. Doch tatsächlich betrachten wir jetzt das Herzstück des RSA-Verfahrens:

(a) Im Tool unten kannst du einen Schwierigkeitsgrad auswählen. Links erhältst du eine Multiplikationsaufgabe, rechts eine Primfaktorzerlegung. Probiere das kurz aus.

(b) Erkläre, inwieweit die rechte Seite die linke umkehrt.

(c) Überprüfe mit dem Tool, ob es die Multiplikation zweier Primzahlen eine Einwegfunktion darstellen könnte. Ihr könnt euch dabei z.B. in einer Gruppe aufteilen: Die linke Hälfte des Raumes bearbeitet die Multiplikation, die rechte die Primfaktorzerlegung. Welche Seite ist schneller? Könnt ihr die schweren Aufgaben ohne technische Hilfsmittel lösen?

(d) Erläutere, warum diese Experimente nicht ausreichen, um definitiv zu sagen, dass eine Einwegfunktion gefunden wurde. Vergleiche dazu mit Versuch 2.