RSA Prinzip

Asymmetrische Verschlüsselung (Mini-RSA) – anschaulich erklärt

Idee

Bei RSA-ähnlichen Verfahren gibt es:

• einen öffentlichen Schlüssel ( $oS_{1},oS_{2}$ ) – den darf jeder kennen,
• einen privaten Schlüssel $pS$ – den kennt nur der Empfänger.

Die Kernoperation ist Potenzieren modulo einer Zahl:

• Verschlüsseln/Signieren (hier dein Beispiel): $vN=N^{pS}{\bmod {o}}S_{1}$
• Entschlüsseln/Prüfen: $N=vN^{oS_{2}}{\bmod {o}}S_{1}$

Damit das klappt, sind die Exponenten so gewählt, dass sie zueinander invers sind (im echten RSA gilt $e\cdot d\equiv 1{\pmod {\varphi (n)}}$).

Dein Mini-Beispiel

Gegeben

• Nachricht $N$: B → $2$
• privater Schlüssel $pS=5$
• öffentlicher Schlüssel (Teil 1) $oS_{1}=14$

Verschlüsselung

$vN=N^{pS}{\bmod {o}}S_{1}=2^{5}{\bmod {1}}4=32{\bmod {1}}4=4$ Damit ist die verschlüsselte Nachricht $vN=4$ (du deutest das als D).

Entschlüsselung (mit komplettem öffentlichen Schlüssel)

• $oS_{1}=14$
• $oS_{2}=11$

$N=vN^{oS_{2}}{\bmod {o}}S_{1}=4^{11}{\bmod {1}}4=2=B$

Warum kommt wieder $2$ heraus?

Die Potenzen von $4$ modulo $14$ wiederholen sich periodisch: ${\begin{aligned}4^{1}&\equiv 4\ ({\bmod {\ }}14)\\4^{2}&\equiv 16\equiv 2\ ({\bmod {\ }}14)\\4^{3}&\equiv 8\ ({\bmod {\ }}14)\\4^{4}&\equiv 32\equiv 4\ ({\bmod {\ }}14)\end{aligned}}$ Das Muster $4,2,8,4,2,8,\dots$ setzt sich fort. Für den Exponenten 11 landet man wieder bei 2.

„Richtiges“ Mini-RSA – vollständig hergeleitet

Im echten RSA entstehen die Schlüssel so:

1. Wähle zwei Primzahlen $p,q$.
2. Berechne $n=p\cdot q$ und $\varphi (n)=(p-1)(q-1)$.
3. Wähle einen öffentlichen Exponenten $e$ mit $\gcd(e,\varphi (n))=1$.
4. Berechne den privaten Exponenten $d$ als multiplikatives Inverses von $e$ modulo $\varphi (n)$: $e\cdot d\equiv 1{\pmod {\varphi (n)}}$.
5. Öffentlicher Schlüssel: $(n,e)$, privater Schlüssel: $d$.

Mini-Beispiel

• Wähle $p=3,\;q=11$.
• $n=33$, $\varphi (n)=20$.
• Wähle $e=3$.
• Löse $3\cdot d\equiv 1{\pmod {20}}$ → $d=7$.

Schlüssel

• Öffentlicher Schlüssel: $(33,3)$
• Privater Schlüssel: $d=7$

Verschlüsselung

$C=N^{e}{\bmod {n}}=2^{3}{\bmod {3}}3=8$

Entschlüsselung

$N=C^{d}{\bmod {n}}=8^{7}{\bmod {3}}3=2$

Verbindung zu deinem Beispiel

In deinem Beispiel sind die Rollen etwas vertauscht (Verschlüsselung mit privatem Schlüssel, Entschlüsselung mit öffentlichem). Mathematisch ist es dasselbe Prinzip: ${\bigl (}N^{pS}{\bmod {o}}S_{1}{\bigr )}^{oS_{2}}{\bmod {o}}S_{1}=N$

Wichtige Hinweise

• Gezeigte Zahlen sind extrem klein → unsicher, nur Demonstration.
• Praxis: große Primzahlen (2048/3072 Bit), standardisierte Exponenten (meist $e=65537$), sichere Libraries.

Kurzfazit

• Verschlüsseln/Signieren: Potenzieren modulo $n$.
• Entschlüsseln/Verifizieren: passender Gegen-Exponent.
• Bedingung: $e\cdot d\equiv 1{\pmod {\varphi (n)}}$.