RSA Prinzip

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

Idee

Bei RSA-ähnlichen Verfahren gibt es:

• einen öffentlichen Schlüssel ( $o{S}_1,o{S}_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}modo{S}_1$
• Entschlüsseln/Prüfen: $N=v{N}^{o{S}_2}modo{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(\mathrm{mod}\phi (n))$).

Dein Mini-Beispiel

Gegeben

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

Verschlüsselung

$vN=N^{pS}modo{S}_1=2^{5}mod14=32mod14=4$ Damit ist die verschlüsselte Nachricht $vN=4$ (du deutest das als D).

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

• $o{S}_1=14$
• $o{S}_2=11$

$N=v{N}^{o{S}_2}modo{S}_1=4^{11}mod14=2=B$

Warum kommt wieder $2$ heraus?

Die Potenzen von $4$ modulo $14$ wiederholen sich periodisch: $\begin{array}{rl}{4}^1& \equiv 4(mod14)\\ 4^2& \equiv 16\equiv 2(mod14)\\ 4^3& \equiv 8(mod14)\\ 4^4& \equiv 32\equiv 4(mod14)\end{array}$ 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 $\phi (n)=(p-1)(q-1)$.
3. Wähle einen öffentlichen Exponenten $e$ mit $\gcd (e,\phi (n))=1$.
4. Berechne den privaten Exponenten $d$ als multiplikatives Inverses von $e$ modulo $\phi (n)$: $e\cdot d\equiv 1(\mathrm{mod}\phi (n))$.
5. Öffentlicher Schlüssel: $(n,e)$, privater Schlüssel: $d$.

Mini-Beispiel

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

Schlüssel

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

Verschlüsselung

$C=N^{e}modn=2^{3}mod33=8$

Entschlüsselung

$N=C^{d}modn=8^{7}mod33=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: $(N^{pS}modo{S}_1{)}^{o{S}_2}modo{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(\mathrm{mod}\phi (n))$.