⭐ RSA Algorithmus

Der RSA Algorithmus ist der aktuell am weitesten verbreitete asymmetrische Verschlüsselungsalgorithmus und wird etwa für die SSL/TLS Verschlüsselung beim HTTPS-Protokoll verwendet. Der Algorithmus wurde 1977 von Ronald Rivest, Adi Shamir und Leonard Adlerman unter dem Namen RSA entwickelt und publiziert¹.

Funktionsweise​

Die Funktionsweise basiert darauf, dass es leicht ist, $c = m^{e}\: mod\: n$ zu berechnen, aber praktisch unmöglich, ohne den privaten Schlüssel d die Umkehr­funktion zu berechnen.

n

öffentliche Zahl

e

öffentlicher Schlüssel des Empfängers

d

privater Schlüssel des Empfängers

$m<n$

Klartext

c

Geheimtext

Verschlüsselung​

Zur Verschlüsselung berechnet Bob den Geheimtext c:

Wobei mod der Ganzzahlige Rest bei der Division mit n darstellt. Beispiel: $13 \: mod \: 4=1$, da $\frac{13}{4} = 3\: Rest\: 1$.

Die Zahl $n$ ist das Produkt von zwei ver­schiedenen Primzahlen $p$ und $q$, diese sind geheim. Wie können $p$ und $q$ geheim sein, wenn doch $n = p\cdot q$ öffentlich ist? Dies beruht nur darauf, dass die Primfaktor­zerlegung von $n$ zu rechen­aufwendig ist, da $n$ sehr gross ist (z.B. 1024 Bit lang).

Für die Zahl e muss gelten

Hierbei ist

die Anzahl der zu n teiler­fremden Zahlen, die kleiner als n sind.

Entschlüsselung​

Der Empfänger hat als privaten Schlüssel eine Zahl $d$ mit

daher

für irgend ein $k \in \N_{o}$.

Ist $n = pq$, so gilt nach einem Satz von Euler für alle Zahlen $m$ mit $m < n$ und für alle natürlichen Zahlen $k$:

Zur Ent­schlüsselung berechnet der Empfänger also

und erhält damit den Klartext $m$.

RSA in Python​

Schlüsselerzeugung:​

Als erstes wählt man zwei Primzahlen $p$ und $q$ und berechnet daraus

$n = p \cdot q$

und

$\varphi(n) = \varphi(p) \cdot \varphi(q) = (p-1) \cdot (q-1)$

Nun muss man ein Zahlenpaar $e$ und $d$ finden, die bezüglich $\varphi(n)$ multiplikativ invers zueiunander sind. Das bedeutet, dass gilt:

$d \cdot e \mod \phi(n) = 1$

Das Zahlenpaar findet man mit dem sogenannten erweiterten euklidschen Algorithmus:

Erster Versuch: 3 hat kein multiplikatives inverses bezüglich $\varphi(n)$

Zweiter Versuch: 5 hat auch kein multiplikatives inverses bezüglich $\varphi(n)$

Dritter Versuch: 7 hat ein multiplikatives inverses bezüglich $\varphi(n)$.

(Nebenbei: Der Grund, warum es mit 3 und 5 nicht geklappt hat: Die Zahlen müssen zu $\varphi(n)$ teilerfremd sein, aber 120 ist durch 3 und 5 teilbar)

Kurze Überprüfung: Ist das Produkt von $e$ und $d$ modulo $\varphi(n)$ tatsächlich 1?

Verschlüsselung​

Der öffentliche Schlüssel besteht nun aus den Zahlen $e$ und $n$. Diesen darf jeder wissen.

Der private Schlüssel besteht aus den Zahlen $d$ und $n$. Dieser muss geheimgehalten werden.

Mit dem RSA-Verfahren lassen sich nun Zahlen von 0 bis (n-1) verschlüsseln.

Um eine Nachricht $m$ zu verschlüsseln, muss man folgendes berechnen:

$c = m^e \mod n$

Resultat ist eine verschlüsselte Nachricht $c$

Entschlüsseln​

Um die verschlüsselte Nachricht $c$ zu entschlüsseln, muss man folgendes berechnen:

$m = c^e \mod n$

Praktische Anwendung: Text mit RSA verschlüsseln:​

Um einen Text mit RSA zu verschlüsseln hat man nun zahlreiche Möglichkeiten. Hier ist nur ein Beispiel:

Zunächst wandeln wir jeden Buchstaben der Nachricht 'HALLO' in eine Zahl um:

Mit der Python-Funktion bin machen wir daraus Binärzahlen in form eines strings, allerdings brauchen wir die zwei ersten Zeichen 0b, die Python vor jede Binärzahl schreibt nicht und zwacken diese ab. Ausserdem füllen wir die Zahl mit zfill immer mit Nullen auf 5 Stellen auf. Warum 5 Stellen? Weil man für 26 Buchstaben mindestens 5 Bit (= 32 Möglichkeiten) braucht:

Aus diesen 5-Stelligen Binärzahlen machen wir 7-Stellige Binärzahlen, indem wir die Bits einfach der Reihe nach lesen. Falls es nicht aufgeht, hängen wir einfach noch Nullen dran.

Warum 7 Bit? Weil für dieses Beispiel $n = p \cdot q = 11 \cdot 13 = 143$ ist, worin 127 (grösste Zahl mit 7 bit) gerade Platz hat. Das Resultat sind 4 Zahlen:

Diese vier Zahlen werden nun einzeln RSA-Verschlüsselt:

Am anderen Ende können die Zahlen wieder einzeln entschlüsselt werden:

Die Zahlen werden wieder binär umgewandelt, diesmal auf 7 Stellen mit Nullen gefüllt:

Aufgeteilt in 5-Stellige Binärzahlen erhalten wir die ursprünglichen Zahlen und daraus die ursprünglichen Buchstaben:

Sicherheit​

Warum ist dies sicher? Dieses Beispiel wäre natürlich nicht sicher, weil die Primzahlen viel zu klein sind, aber bei grossen Primzahlen $p$ und $q$ würde es viel zu lange dauern, diese Teiler nur aus $n$ zu bestimmen.

Um dies zu verdeutlichen hier eine naive Funktion factors, die die Teiler einer Zahl zurückgibt, falls sie exisiteren. In der Zelle darunter wird diese Funktion benutzt, um Primzahlen zu finden indem einfach eine Zahl nach der anderen durchprobiert wird. Wird eine Primzahl gefunden, verdoppeln wir unseren Kandidaten und suchen von dort aus weiter.

Am Anfang geht das ganze recht schnell, aber schon bald dauert es ewig lange, um die nächste Primzahl zu finden. Einerseits, weil es immer weniger Primzahlen gibt, aber andererseits wird die factors-Funktion immer langsamer.