de
Seitenbanner
Menu
A-Z
Aufgaben

RSA-Verfahren – Interaktiver Aufgabengenerator mit Musterlösungen

Artikel zum Nachlesen: RSA-Verfahren

Der interaktive Aufgabengenerator zum Thema RSA-Verfahren erzeugt dir eine unbegrenzte Anzahl an individuell anpassbaren Übungsaufgaben und Beispielen. Er unterstützt dich dabei, diese zu lösen und das Thema ausgiebig zu üben. Hierzu erstellt der Generator für jede Aufgabe eine ausführliche, verständliche Musterlösung und bietet dir zudem die Möglichkeit, deine eigenen Lösungen direkt zu überprüfen. Sämtliche Hilfestellungen stehen sowohl für die freien Beispiele als auch für generierte und eigene Aufgaben im vollen Umfang zur Verfügung.

Aufgabe erstellen

Beispielaufgaben

Beispielaufgaben

Aufgabe 1 von 3

Gegeben seien die beiden Primzahlen $p$ und $q$ sowie die zum öffentlichen RSA-Schlüssel gehörende Zahl $e$.

\[\begin{align*}
p &= 13 \\[0.5em]
q &= 17 \\[0.5em]
e &= 23
\end{align*}\]

Bestimme den öffentlichen RSA-Schlüssel $(e,N)$ und berechne den zugehörigen privaten RSA-Schlüssel $(d,N)$.

Aufgabengenerator

Aufgabengenerator

Konfiguration anpassen
 – 
Eigene Aufgabe

Eigene Aufgabe verwenden

Gib an, ob die RSA-Schlüssel aus vorgegebenen Primzahlen oder aus einem vorhandenen RSA-Schlüssel berechnet werden sollen.

Gib die zu verwendenden Primzahlen $p$ und $q$ sowie den zum öffentlichen RSA-Schlüssel $(e,N)$ gehörenden Wert $e$ ein.

Aufgabe lösen

Musterlösung

Musterlösung

Zunächst wird der RSA-Modul $N$ als Produkt der beiden Primzahlen $p=13$ und $q=17$ berechnet.

\[N = p \cdot q = 13 \cdot 17 = 221\]

Anschließend wird der Wert $\varphi(N)$ berechnet.

Mithilfe der Primfaktorzerlegung der Zahl $N=221$ kann der Wert $\varphi(N)$ der eulerschen $\varphi$-Funktion berechnet werden.

\[\begin{align*}
\varphi(221) &= \varphi\bigl(13 \cdot 17\bigr) \\[0.5em]
&= \varphi\bigl(13\bigr) \cdot \varphi\bigl(17\bigr) \\[0.5em]
&= {\underbrace{\bigl(13 - 1\bigr)}_{12}} \cdot {\underbrace{\bigl(17 - 1\bigr)}_{16}} \\[0.5em]
&= 192
\end{align*}\]

Mithilfe des berechneten Werts $\varphi(221)$ kann nun die Zahl $d$ bestimmt werden, für die $e \cdot d \equiv 1 \pmod{\varphi(N)}$ gilt – bei $d$ handelt es sich also um das multiplikative Inverse von $e=23$ in $\Z_{192}$.

Zum Bestimmen des multiplikativen Inversen der Restklasse $ [23]_{192}$ im Restklassenring $\Z_{192}$ muss mit dem euklidischen Algorithmus zunächst der größte gemeinsame Teiler von $ 192$ und $ 23$ berechnet werden.

\[\begin{align*}
192 &= 8 \cdot 23 + 8 \\[0.5em]
23 &= 2 \cdot 8 + 7 \\[0.5em]
8 &= 1 \cdot 7 + 1 \\[0.5em]
7 &= 7 \cdot 1 + 0
\end{align*}\]

Der größte gemeinsame Teiler $ 1$ kann wie üblich an der vorletzten Zeile abgelesen werden. Da $ 192$ und $ 23$ folglich teilerfremd sind, kann das gesuchte multiplikative Inverse durch Rückwärtseinsetzen gefunden werden.

\[\begin{align*}
1 &=1 \cdot 8-1 \cdot 7 \\[0.5em]
&=1 \cdot 8-1 \cdot \left(23 - 2 \cdot 8\right) \\[0.5em]
&=-1 \cdot 23 + 3 \cdot 8 \\[0.5em]
&=-1 \cdot 23 + 3 \cdot \left(192 - 8 \cdot 23\right) \\[0.5em]
&=3 \cdot 192-25 \cdot 23
\end{align*}\]

Aus dieser Gleichheit kann insbesondere die folgende Kongruenz abgelesen werden:

\[\begin{align*}
1 &\equiv \underbrace{3 \cdot 192}_{\equiv 0}-25 \cdot [23]_{192} \pmod{192} \\[0.5em]
&\equiv -25 \cdot [23]_{192} \pmod{192}
\end{align*}\]

Bei $x'=-25$ handelt es sich noch nicht um das gesuchte multiplikative Inverse, da dieser Wert kleiner als $0$ ist. Das Inverse kann allerdings durch Addition des Moduls $ 192$ erhalten werden:

\[x \equiv -25 \equiv -25 + 192 \equiv 167 \pmod{192}\]

Bei $x=167$ handelt es sich um das gesuchte multiplikative Inverse von $ 23$ in $\Z_{192}$.

Nach der Berechnung des multiplikativen Inversen $d=167$ von $e=23$ in $\Z_{\varphi(221)}$ können nun sowohl der öffentliche als auch der private RSA-Schlüssel erzeugt werden.

öffentlicher Schlüssel: $\bigl(e, N\bigr) = \bigl(23,221\bigr)$
privater Schlüssel: $\bigl(d, N\bigr) = \bigl(167,221\bigr)$
Lösung überprüfen

Eigene Lösung überprüfen

Gib die berechneten Werte $N$ und $\varphi(N)$ sowie den zum privaten RSA-Schlüssel $(d,N)$ gehörenden Wert $d$ ein.