Aufgaben

RSA-Verfahren – Interaktiver Aufgabengenerator

Artikel zum Nachlesen: RSA-Verfahren

Der interaktive Aufgabengenerator zum Thema RSA-Verfahren erzeugt dir eine unbegrenzte Anzahl an individuell anpassbaren, prozedural generierten Übungsaufgaben. Er unterstützt dich dabei, die Aufgaben zu lösen, das Thema ausgiebig zu üben und zu verstehen. Hierzu erstellt der Generator für jede Aufgabe eine ausführliche, verständliche Schritt-für-Schritt Musterlösung und bietet dir zudem die Möglichkeit, deine eigenen Lösungen direkt zu überprüfen. Alle Lösungen und Lösungswege werden deterministisch mithilfe der zugrundeliegenden mathematischen Verfahren berechnet. 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

Die ausgewählten Beispiele ermöglichen es dir, einige Generator-Konfigurationen und die verfügbare Unterstützung beim Lösen der Aufgaben unverbindlich und in aller Ruhe kennenzulernen.

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

Der Aufgabengenerator ermöglicht es dir, beliebig viele, an deine individuellen Bedürfnisse angepasste Aufgaben zu generieren, um dich perfekt mit dem Thema vertraut zu machen.

Melde dich an, um unbegrenzt Übungsaufgaben zu erzeugen. Jetzt anmelden!

Konfiguration anpassen

Konfiguriere den Aufgabengenerator nach deinen Wünschen – von einfachen Beispielen bis zu anspruchsvollen Herausforderungen.

Lege den Bereich der erlaubten Primfaktoren fest (von 2 bis 10.000) und entscheide, ob der private RSA-Schlüssel aus den Primfaktoren oder aus einem gegebenen öffentlichen RSA-Schlüssel bestimmt werden soll.

Bereich der Primfaktoren:

–

Typ:

Primfaktoren

Öffentlicher RSA-Schlüssel

Hier könnte deine generierte Aufgabe stehen!

Eigene Aufgabe

Eigene Aufgabe verwenden

Löse deine eigenen Aufgaben oder lasse deiner Neugier freien Lauf – mit voller Unterstützung des Generators.

Melde dich an, um deine eigenen Aufgaben zu verwenden und zu lösen. Jetzt anmelden!

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

Primzahlen

Öffentlicher RSA-Schlüssel

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

\[p=\]

\[q=\]

\[e=\]

Aufgabe lösen

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.

\[N=\]

\[\varphi(N)=\]

\[d=\]