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 \(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\cdot8-1\cdot7 \\[0.5em]
&=1\cdot8-1\cdot(23-2\cdot8) \\[0.5em]
&=-1\cdot23+3\cdot8 \\[0.5em]
&=-1\cdot23+3\cdot(192-8\cdot23) \\[0.5em]
&=3\cdot192-25\cdot23
\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 \pmod{192} \\[0.5em]
&\equiv -25 \cdot 23 \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.