RSA und der Satz von Euler

Das RSA-Verfahren, mit dem Browser und Banken Nachrichten verschlüsseln, ist angewandte Algebra in ${\mathbb{Z}}_n$. Wie ein Schlüsselpaar entsteht und was Ver- und Entschlüsseln in Zahlen heißt, steht in der Schulfassung unter Öffentlicher Schlüssel und RSA mit dem Mini-Beispiel $n=33$. Hier kommt der Beweis, dass das Entschlüsseln wirklich die Nachricht zurückgibt.

Das Verfahren

Wähle zwei verschiedene Primzahlen $p$ und $q$ und setze $n=pq$. Nach dem chinesischen Restsatz und der Produktformel ist $\phi (n)=(p-1)(q-1)$. Wähle einen öffentlichen Exponenten $e$ mit $\mathrm{ggT}(e,\phi (n))=1$. Dann hat $e$ ein Inverses modulo $\phi (n)$, und du bestimmst den privaten Exponenten $d$ mit $e·d\equiv 1(\mathrm{mod}\phi (n))$, mit dem erweiterten euklidischen Algorithmus. Der öffentliche Schlüssel ist $(n,e)$, der private ist $d$. Eine Nachricht $m\in \{0,1,\dots ,n-1\}$ wird zu $c\equiv m^e(\mathrm{mod}n)$ verschlüsselt und mit $m\equiv c^d(\mathrm{mod}n)$ wieder entschlüsselt.

Beweis. Aus $ed\equiv 1(\mathrm{mod}\phi (n))$ folgt $ed=1+k(p-1)(q-1)$ mit einem $k\ge 0$. Wir zeigen die Kongruenz getrennt modulo $p$ und modulo $q$. Fall 1: $p\nmid m$. Nach dem kleinen Satz von Fermat ist $m^{p-1}\equiv 1(\mathrm{mod}p)$, also $m^{ed}=m·{(m^{p-1})}^{k(q-1)}\equiv m·1=m(\mathrm{mod}p)$. Fall 2: $p\mid m$. Dann sind beide Seiten $\equiv 0(\mathrm{mod}p)$. Genauso zeigt man $m^{ed}\equiv m(\mathrm{mod}q)$. Da $p$ und $q$ teilerfremd sind, folgt $m^{ed}\equiv m(\mathrm{mod}pq)$ aus dem chinesischen Restsatz, denn $p$ und $q$ teilen beide die Differenz $m^{ed}-m$, also auch ihr Produkt. $\square$

Der Beweis kommt mit dem kleinen Satz von Fermat aus, dem Spezialfall des Satzes von Euler für Primzahlen. Er zeigt auch, warum man zwei verschiedene Primzahlen braucht und warum der Fall $p\mid m$ unproblematisch ist, obwohl dann $m$ keine Einheit in ${\mathbb{Z}}_n$ ist und der Satz von Euler nicht direkt anwendbar wäre.

Warum das sicher ist

Wer $n$ und $e$ kennt, kann $d$ nur bestimmen, wenn er $\phi (n)$ kennt, und das ist so schwer wie das Zerlegen von $n$ in $p·q$: Aus $n$ und $\phi (n)$ ergibt sich $p+q=n-\phi (n)+1$, und $p$, $q$ sind dann die Nullstellen von $x^2-(p+q)x+n$. Für Zahlen $n$ mit mehreren hundert Stellen ist kein schnelles Zerlegungsverfahren bekannt. Wählt man die Nachricht klein und $e$ klein, kann man sie ohne Schlüssel durch Wurzelziehen finden, deshalb füllt man in der Praxis Nachrichten auf („Padding“). Dreht man die Rollen um, entsteht eine digitale Signatur: Wer $d$ kennt, kann $s=m^d$ bilden, und jeder prüft mit dem öffentlichen $e$, ob $s^e\equiv m$ gilt.

Rivest, Shamir und Adleman beschrieben das Verfahren 1977 und veröffentlichten es 1978 in den „Communications of the ACM“. Clifford Cocks hatte bereits 1973 beim britischen GCHQ ein gleichwertiges Verfahren entwickelt, das erst 1997 freigegeben wurde.

Immer neue Aufgaben zu Schlüsseln, Ver- und Entschlüsseln gibt es auf dem Blatt Rechnen in Restklassen (Aufgabenart „RSA mit kleinen Primzahlen“).