de
Seitenbanner
Menu
A-Z
Aufgaben

Aufgaben zum RSA-Verfahren

Artikel zum Nachlesen: RSA-Verfahren

Der interaktive Aufgabengenerator zum Thema RSA-Verfahren erstellt dir eine unbegrenzte Anzahl an individuell anpassbaren Aufgaben und Beispielen und unterstützt dich dabei, diese zu bearbeiten und zu lösen – unter anderem durch ausführliche und verständliche Musterlösungen . Darüber hinaus ist dieselbe Unterstützung auch für eigene Aufgaben verfügbar.

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.