RSA-Verfahren
Beim RSA-Verfahren handelt es sich um ein asymmetrisches kryptografisches Verfahren, das sowohl zum Verschlüsseln als auch zum digitalen Signieren verwendet werden kann. Hierzu wird ein Schlüsselpaar verwendet, das aus einem privaten Schlüssel (zum Entschlüsseln und Signieren) und einem öffentlichen Schlüssel (zum Verschlüsseln und Überprüfen der Signatur) besteht.
Der Name RSA geht auf die Urheber Ron Rivest, Adi Shamir und Leonard Adleman zurück, die das Verfahren 1977 publiziert haben.
Beschreibung des RSA-Verfahrens
Erzeugung des öffentlichen und des privaten Schlüssels
Beim öffentlichen Schlüssel (engl. public key) handelt es sich um ein Zahlenpaar \((e,N)\); analog handelt es sich beim privaten Schlüssel (engl. private key) um ein Zahlenpaar \((d,N)\). Der Wert \(e\) wird Verschlüsselungsexponent genannt, der Wert \(d\) wird analog Entschlüsselungsexponent genannt. Der Wert \(N\) wird RSA-Modul genannt und ist für beide Schlüssel identisch.
Die beiden Zahlenpaare können mithilfe der folgenden Schritte erzeugt werden:
-
Auswahl von zufälligen Primzahlen \(p\) und \(q\) mit \(p \neq q\). Die beiden Zahlen sollten in etwa dieselbe Größenordnung haben, jedoch nicht zu dicht beieinander liegen. In der Praxis sollte in etwa der Rahmen \(0{,}1 \lt |\log_2{p} - \log_2{q}| \lt 30\) eingehalten werden.
-
Berechnen des RSA-Moduls
\[ N = p \cdot q \] -
Berechnung der eulerschen \(\varphi\)-Funktion
\[ \varphi(N) = \bigl( p-1 \bigr) \cdot \bigl( q-1 \bigr) \] -
Auswahl einer zu \(\varphi(N)\) teilerfremden Zahl \(e\) mit \(1 \lt e \lt \varphi(N)\).
-
Berechnung des Werts \(d\) als multiplikatives Inverses von \(e\) bezüglich des Moduls \(\varphi(N)\). Dies kann beispielsweise mithilfe des erweiterten euklidischen Algorithmus erfolgen. Für die Werte \(e\) und \(d\) gilt somit die Kongruenz
\[ e \cdot d \equiv 1 \pmod{\varphi(N)}. \]
Aus den berechneten Werten \(e\), \(d\) und \(N\) ergeben sich unmittelbar der öffentliche Schlüssel \((e,N)\) sowie der private Schlüssel \((d,N)\).
Die Zahlen \(p\), \(q\) und \(\varphi(N)\) werden nicht länger benötigt und können nach der Schlüsselerzeugung gelöscht werden. Da diese Werte aus \(e\), \(d\) und \(N\) rekonstruiert werden können, müssen \(p\), \(q\), \(\varphi(N)\) und \(d\) geheim gehalten werden.
Verschlüsseln
Das Verschlüsseln einer Nachricht \(m\) mit \(1 \leq m \lt N\) geschieht beim RSA-Verfahren durch modulares Potenzieren mithilfe der folgenden Formel:
Auf diese Weise kann aus der ursprünglichen Nachricht \(m\) der Geheimtext \(c\) erhalten werden. Bei den in der Formel auftauchenden Werten \(e\) und \(N\) handelt es sich um den Verschlüsselungsexponenten sowie den RSA-Modul, aus denen sich der öffentliche Schlüssel \((e,N)\) zusammensetzt.
Entschlüsseln
Das Entschlüsseln des Geheimtextes \(c\) mit \(1 \leq c \lt N\) geschieht beim RSA-Verfahren durch modulares Potenzieren mithilfe der folgenden Formel:
Auf diese Weise kann aus dem Geheimtext \(c\) wieder die ursprüngliche Nachricht \(m\) erhalten werden. Bei den in der Formel auftauchenden Werten \(d\) und \(N\) handelt es sich um den Entschlüsselungsexponenten sowie den RSA-Modul, aus denen sich der private Schlüssel \((d,N)\) zusammensetzt.
RSA-Verfahren mit dem chinesischen Restsatz
Mithilfe des chinesischen Restsatzes kann das Ver-/Entschlüsseln beim RSA-Verfahren effizienter durchgeführt werden. Nach der algebraischen Version des chinesischen Restsatzes handelt es sich bei der Abbildung \(\Z_N \rightarrow \Z_p\times\Z_q\) mit \({[x]}_N \mapsto \bigl({[x]}_p,{[x]}_q\bigr)\) um einen Ringisomorphismus zwischen dem Restklassenring \(\Z_N\) und dem direkten Produkt der Restklassenringe \(\Z_p\) und \(\Z_q\) . Dies bedeutet, dass Operationen statt in \(\Z_N\) stellvertretend in \(\Z_p \times \Z_q\) durchgeführt werden können und dass ihr Ergebnis anschließend nach \(\Z_N\) übertragen werden kann.
Für das Verschlüsseln beim RSA-Verfahren (das Entschlüsseln funktioniert analog) bedeutet dies, dass anstelle der Potenz \(m^e \bmod{N}\) stellvertretend die Potenzen \(m^e \bmod{p}\) und \(m^e \bmod{q}\) berechnet werden können. Da es sich bei \(p\) und \(q\) um Primzahlen handelt, können beide Potenzen zunächst mithilfe des Satzes von Fermat bzw. mithilfe des Satzes von Euler vereinfacht werden; es existieren ganze Zahlen \(q_p,q_q,r_p,r_q\) mit \(0 \leq r_p \lt p-1\) und \(0 \leq r_q \lt q-1\), für die gilt:
Die zumeist deutlich kleineren und besser/schneller zu berechnenden Potenzen \(m^{r_p} \equiv c_p \pmod{p}\) und \(m^{r_q} \equiv c_q \pmod{q}\) können anschließend durch modulares Potenzieren berechnet werden. Bei \(\bigl({[c_p]}_p, {[c_q]}_q\bigr)\) handelt es sich um die gesuchte Lösung in \(\Z_p \times \Z_q\). Um diese in das gewünschte Ergebnis in \(\Z_N\) zu überführen, muss die folgende simultane Kongruenz gelöst werden:
Die Lösung \(c\) dieser simultanen Kongruenz kann mithilfe des chinesischen Restsatzes direkt bestimmt werden; es gilt:
Die hierfür benötigten ganzen Zahlen \(s_p\) und \(s_q\) existieren aufgrund des Lemmas von Bézout und können beispielsweise mithilfe des erweiterten euklidischen Algorithmus aus der Gleichung \(s_p \cdot p + s_q \cdot q = 1\) bestimmt werden. Bei \({[c]}_N\) handelt es sich um das Ergebnis in \(\Z_N\) und beim Standardrepräsentanten der Restklasse \({[c]}_N\) handelt es sich um den Geheimtext \(c\).
Anmerkung: Da sich die Primzahlen \(p,q\) für einen gegebenen RSA-Schlüssel nicht ändern, müssen die Werte \(s_p\) und \(s_q\) pro Schlüssel nur einmal berechnet werden. Dasselbe gilt für die Werte \(r_p\) und \(r_q\), da sich der Verschlüsselungsexponent \(e\) (analog auch der Entschlüsselungsexponent \(d\)) für einen gegebenen RSA-Schlüssel ebenfalls nicht ändert.
Beispiel
Erzeugung des öffentlichen und des privaten Schlüssels
Die Erzeugung des öffentlichen und des privaten Schlüssels erfolgt schrittweise mit dem zuvor beschriebenen Verfahren.
-
Zunächst werden zwei zufällige Primzahlen \(p=17\) und \(q=23\) ausgewählt.
-
Für die Primzahlen \(p=17\) und \(q=23\) ergibt sich der RSA-Modul wie folgt:
\[ N = p \cdot q = 17 \cdot 23 = 391. \] -
Anschließend wird der Wert \(\varphi(391)\) der eulerschen \(\varphi\)-Funktion bestimmt. Es gilt
\begin{align*} \varphi(391) &= \varphi\bigl(17 \cdot 23\bigr) \\[0.5em] &= \varphi\bigl(17\bigr) \cdot \varphi\bigl(23\bigr) \\[0.5em] &= {\underbrace{\bigl(17 - 1\bigr)}_{16}} \cdot {\underbrace{\bigl(23 - 1\bigr)}_{22}} \\[0.5em] &= 352 \end{align*} -
Die Auswahl des zu \(\varphi(391)\) teilerfremden Verschlüsselungsexponenten \(e\) erfolgt zufällig, beispielsweise \(e = 69\).
-
Im letzten Schritt muss nun der Entschlüsselungsexponent \(d\) berechnet werden. Mithilfe des erweiterten euklidischen Algorithmus ergibt sich zunächst
\begin{align*} \begin{alignedat}{2} 1 &\equiv \underbrace{10 \cdot 352}_{\equiv 0}-51 \cdot 69 && \pmod{352} \\[0.5em] &\equiv -51 \cdot 69 && \pmod{352}, \end{alignedat} \end{align*}woraus unmittelbar
\[ d \equiv -51 \equiv 301 \pmod{352} \]folgt. Somit handelt es sich bei \(d=301\) um den gesuchten Entschlüsselungsexponenten.
Insgesamt hat sich also das folgende Schlüsselpaar ergeben:
öffentlicher Schlüssel: | \((69,391)\) |
---|---|
privater Schlüssel: | \((301,391)\) |
Verschlüsseln
Es soll die Nachricht \(m=42\) verschlüsselt werden. Hierzu wird der öffentliche Schlüssel \((e,N) = (69, 391)\) verwendet. Es folgt
Für den Geheimtext gilt also \(c=281\).
Entschlüsseln
Es soll der Geheimtext \(c=281\) entschlüsselt werden. Hierzu wird der private Schlüssel \((d,N) = (301,391)\) verwendet. Es folgt
Für die entschlüsselte Nachricht gilt also \(m=42\).
Ver-/Entschlüsseln mit dem chinesischen Restsatz
Es soll der Geheimtext \(c=281\) mithilfe des chinesischen Restsatzes entschlüsselt werden. Hierzu wird der private Schlüssel \((d,N) = (301,391)\) verwendet. Für \(N=391\) gilt \(p=17\) und \(q=23\).
Anstelle der Potenz \(281^{301} \bmod{391}\) werden die Potenzen \(281^{301} \bmod{17}\) und \(281^{301} \bmod{23}\) bestimmt. Diese können mithilfe des Satzes von Fermat zunächst vereinfacht und anschließend berechnet werden:
Hieraus ergibt sich die folgende simultane Kongruenz:
Anwenden des erweiterten euklidischen Algorithmus zum Bestimmen der ganzen Zahlen \(s_p\) und \(s_q\), sodass
gilt, liefert \(s_p=-4\) und \(s_q=3\). Als Lösung der simultanen Kongruenz ergibt sich nach dem chinesischen Restsatz somit die folgende Lösung:
Bei \({[-740]}_{391}\) handelt es sich um die Restklasse des gesuchten Ergebnisses. Diese wird abschließend noch in den Standardvertreter umgerechnet; es gilt:
Bei \(m=42\) handelt es sich somit um die unverschlüsselte Nachricht.
Beweis der Korrektheit
Für das RSA-Verfahren ist es essentiell, dass eine verschlüsselte Nachricht \(c\) stets wieder in die korrekte unverschlüsselte Nachricht \(m\) überführt werden kann. Hierfür muss gezeigt werden, dass stets \(c^d \equiv m \pmod{N}\) gilt. Dies kann beispielsweise wie folgt bewiesen werden.
Erklärungen zu den Schritten | |
---|---|
(1) |
|
(2) |
|
(3) |
|
(4) |
|
(5) |
|
(6) |
|
(7) |
|