Aufgaben

Aufgaben zum RSA-Verfahren

Der interaktive Aufgabengenerator zum Thema RSA-Verfahren erstellt dir eine unbegrenzte Anzahl an individuell anpassbaren Aufgaben 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 deine eigenen Aufgaben verfügbar.

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

Musterlösung
Lösung überprüfen

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 von $23$ in $\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)$

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