Nachlesen

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.

Inhalt

Beschreibung des RSA-Verfahrens
Beispiel
Beweis der Korrektheit

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:

c \equiv m^e \pmod{N}.

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:

m \equiv c^d \pmod{N}.

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:

\begin{align*} m^e \equiv m^{q_p \cdot (p-1) + r_p} &\equiv 1^{q_p} \cdot m^{r_p} \equiv m^{r_p} \pmod{p} \\[0.5em] m^e \equiv m^{q_q \cdot (q-1) + r_q} &\equiv 1^{q_q} \cdot m^{r_q} \equiv m^{r_q} \pmod{q}. \end{align*}

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:

\begin{align*} c &\equiv c_p \pmod{p} \\[0.5em] c &\equiv c_q \pmod{q}. \end{align*}

Die Lösung $c$ dieser simultanen Kongruenz kann mithilfe des chinesischen Restsatzes direkt bestimmt werden; es gilt:

c = c_p \cdot s_q \cdot q + c_q \cdot s_p \cdot p.

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)$

Jetzt üben!

Nutze den individuell konfigurierbaren Aufgabengenerator, um unbegrenzt Aufgaben zum Thema RSA zu erzeugen und zu üben.

Verschlüsseln

Es soll die Nachricht $m=42$ verschlüsselt werden. Hierzu wird der öffentliche Schlüssel $(e,N) = (69, 391)$ verwendet. Es folgt

\begin{align*} \begin{alignedat}{2} c &\equiv m^e && \pmod{N} \\[0.5em] &\equiv {42}^{69} && \pmod{391} \\[0.5em] &\equiv 281 && \pmod{391} \end{alignedat} \end{align*}

Für den Geheimtext gilt also $c=281$.

Jetzt üben!

Nutze den individuell konfigurierbaren Aufgabengenerator, um unbegrenzt Aufgaben zum Thema Modulares Potenzieren zu erzeugen und zu üben.

Entschlüsseln

Es soll der Geheimtext $c=281$ entschlüsselt werden. Hierzu wird der private Schlüssel $(d,N) = (301,391)$ verwendet. Es folgt

\begin{align*} \begin{alignedat}{2} m &\equiv c^d && \pmod{N} \\[0.5em] &\equiv {281}^{301} && \pmod{391} \\[0.5em] &\equiv 42 && \pmod{391} \end{alignedat} \end{align*}

Für die entschlüsselte Nachricht gilt also $m=42$.

Jetzt üben!

Nutze den individuell konfigurierbaren Aufgabengenerator, um unbegrenzt Aufgaben zum Thema Modulares Potenzieren zu erzeugen und zu üben.

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:

\begin{align*} \begin{alignedat}{2} 281^{301} = 281^{18 \cdot 16 + 13} &\equiv 281^{13} \equiv 9^{13} \equiv 8 && \pmod{17} \\[0.5em] 281^{301} = 281^{13 \cdot 22 + 15} &\equiv 281^{15} \equiv 5^{15} \equiv 19 && \pmod{23}. \end{alignedat} \end{align*}

Hieraus ergibt sich die folgende simultane Kongruenz:

\begin{align*} \begin{alignedat}{2} m &\equiv 8 && \pmod{17} \\[0.5em] m &\equiv 19 && \pmod{23}. \end{alignedat} \end{align*}

Anwenden des erweiterten euklidischen Algorithmus zum Bestimmen der ganzen Zahlen $s_p$ und $s_q$, sodass

s_p \cdot 17 + s_q \cdot 23 = 1

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:

\begin{align*} m &= 8 \cdot 3 \cdot 23 + 19 \cdot (-4) \cdot 17 \\[0.5em] &= -740. \end{align*}

Bei ${[-740]}_{391}$ handelt es sich um die Restklasse des gesuchten Ergebnisses. Diese wird abschließend noch in den Standardvertreter umgerechnet; es gilt:

{[-740]}_{391} = {[42]}_{391}.

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.

\begin{align*} \begin{alignedat}{2} c^d &\overset{(1)}{\equiv} {\left( m^e \right)}^{d} && \pmod{N} \\[0.5em] &\overset{(2)}{\equiv} m^{e \cdot d} && \pmod{N} \\[0.5em] &\overset{(3)}{\equiv} m^{k \cdot \varphi(N) + 1} && \pmod{N} \\[0.5em] &\overset{(4)}{\equiv} m \cdot m^{k \cdot \varphi(N)} && \pmod{N} \\[0.5em] &\overset{(5)}{\equiv} m \cdot {\left( m^{\varphi(N)} \right)}^k && \pmod{N} \\[0.5em] &\overset{(6)}{\equiv} m \cdot 1^k && \pmod{N} \\[0.5em] &\overset{(7)}{\equiv} m && \pmod{N} \end{alignedat} \end{align*}

Erklärungen zu den Schritten
(1)	Gemäß Definition des Verschlüsselns gilt $c \equiv m^e \pmod{N}$
(2)	Anwenden von Potenzgesetz III
(3)	Wegen $e \cdot d \equiv 1 \pmod{\varphi(N)}$ existiert ein $k \in \Z$ mit $e \cdot d = k \cdot \varphi(N) + 1$
(4)	Anwenden von Potenzgesetz Ia
(5)	Anwenden von Potenzgesetz III
(6)	Gemäß Satz von Euler gilt $m^{\varphi(N)} \equiv 1 \pmod{N}$, falls $m$ und $N$ teilerfremd sind. Für große Primzahlen $p$ und $q$ kann dies beispielsweise durch die Wahl von hinreichend kleinen Werten $m$ mit $m \lt \min(p,q)$ leicht garantiert werden.
(7)	Ausrechnen

öffentlicher Schlüssel:	\((69,391)\)
privater Schlüssel:	\((301,391)\)

Erklärungen zu den Schritten
(1)	Gemäß Definition des Verschlüsselns gilt \(c \equiv m^e \pmod{N}\)
(2)	Anwenden von Potenzgesetz III
(3)	Wegen \(e \cdot d \equiv 1 \pmod{\varphi(N)}\) existiert ein \(k \in \Z\) mit \(e \cdot d = k \cdot \varphi(N) + 1\)
(4)	Anwenden von Potenzgesetz Ia
(5)	Anwenden von Potenzgesetz III
(6)	Gemäß Satz von Euler gilt \(m^{\varphi(N)} \equiv 1 \pmod{N}\), falls \(m\) und \(N\) teilerfremd sind. Für große Primzahlen \(p\) und \(q\) kann dies beispielsweise durch die Wahl von hinreichend kleinen Werten \(m\) mit \(m \lt \min(p,q)\) leicht garantiert werden.
(7)	Ausrechnen