Asymmetrische Verschlüsselung (RSA)

• Schlüsselpaar: Jeder Teilnehmer besitzt einen öffentlichen Schlüssel (zum Verschlüsseln) und einen privaten Schlüssel (zum Entschlüsseln).
• Kein sicherer Kanal nötig: Der öffentliche Schlüssel darf frei verteilt werden – der Hauptvorteil gegenüber symmetrischen Verfahren.
• RSA (1977): Basiert auf der Schwierigkeit, große Zahlen $n = p \cdot q$ zu faktorisieren.
• Langsam: RSA ist etwa 1000× langsamer als AES – daher werden hybride Verfahren (RSA + AES) verwendet.
• Padding notwendig: Textbook-RSA ist unsicher. In der Praxis: OAEP (Verschlüsselung), PSS (Signaturen).

Grundprinzip asymmetrischer Verschlüsselung

Bei symmetrischen Verfahren teilen sich Sender und Empfänger denselben geheimen Schlüssel – der muss aber irgendwie sicher übertragen werden. Bei asymmetrischen Verfahren gibt es zwei mathematisch verknüpfte Schlüssel:

• Öffentlicher Schlüssel (public key): darf jeder wissen, wird zum Verschlüsseln genutzt.
• Privater Schlüssel (private key): bleibt geheim, wird zum Entschlüsseln genutzt.

Nur der Besitzer des privaten Schlüssels kann Nachrichten entschlüsseln, die mit seinem öffentlichen Schlüssel verschlüsselt wurden.

Vorteil: Kein sicherer Kanal für Schlüsseltransport erforderlich.
Nachteil: Rechenintensiv, dadurch viel langsamer als symmetrische Verfahren.

RSA – Schlüsselgenerierung

RSA wurde 1977 von Rivest, Shamir und Adleman am MIT entwickelt. Ablauf der Schlüsselerzeugung:

1. Wähle zwei große Primzahlen $p$ und $q$ (in der Praxis je 1024 oder 2048 Bit).
2. Berechne den Modulus $n = p \cdot q$.
3. Berechne die Eulersche Phi-Funktion $\varphi(n) = (p-1)(q-1)$.
4. Wähle den öffentlichen Exponenten $e$ mit $1 < e < \varphi(n)$ und $\gcd(e, \varphi(n)) = 1$. In der Praxis meist $e = 65537 = 2^{16} + 1$.
5. Berechne das multiplikative Inverse $d$ mit $e \cdot d \equiv 1 \pmod{\varphi(n)}$ (erweiterter Euklidischer Algorithmus).

Öffentlicher Schlüssel: $(n, e)$
Privater Schlüssel: $d$ (und $p, q, \varphi(n)$ müssen geheim bleiben!)

RSA – Ver- und Entschlüsseln

Sei $m$ die Nachricht als Zahl mit $0 \le m < n$.

Verschlüsseln (mit öffentlichem Schlüssel):

$c = m^e \bmod n$

Entschlüsseln (mit privatem Schlüssel):

$m = c^d \bmod n$

Korrektheit

Es gilt $c^d = (m^e)^d = m^{e \cdot d}$. Wegen $e \cdot d \equiv 1 \pmod{\varphi(n)}$ ist $e \cdot d = 1 + k \cdot \varphi(n)$ für ein $k \in \mathbb{N}$. Damit:

$m^{ed} = m^{1 + k\varphi(n)} = m \cdot (m^{\varphi(n)})^k \equiv m \cdot 1^k = m \pmod n$

Der letzte Schritt folgt aus dem Satz von Euler: $m^{\varphi(n)} \equiv 1 \pmod n$ für $\gcd(m, n) = 1$.

Sicherheit von RSA

Die Sicherheit von RSA basiert auf dem Faktorisierungsproblem: Aus $n$ die Primfaktoren $p$ und $q$ zu bestimmen, ist für große $n$ praktisch unmöglich.

Wer $p$ und $q$ kennt, kann $\varphi(n)$ berechnen und daraus $d$ – RSA wäre gebrochen.

Heutige Schlüssellängen:

Bitlänge $n$	Sicherheit
1024 Bit	nicht mehr empfohlen
2048 Bit	Standard bis ca. 2030
4096 Bit	langfristig sicher (nach heutigem Stand)

Padding – warum Textbook-RSA unsicher ist

Reines RSA ohne Padding hat schwerwiegende Schwächen:

• Deterministisch: Gleiche Nachricht ergibt immer denselben Chiffretext → keine semantische Sicherheit.
• Kleine Nachrichten: Ist $m^e < n$, entfällt der Modulo und man kann $m = \sqrt[e]{c}$ direkt ziehen.
• Multiplikative Struktur: $c_1 \cdot c_2 = (m_1 \cdot m_2)^e \bmod n$ ermöglicht Angriffe.

Deshalb werden in der Praxis Padding-Verfahren eingesetzt:

• OAEP (Optimal Asymmetric Encryption Padding) – für Verschlüsselung.
• PSS (Probabilistic Signature Scheme) – für digitale Signaturen.

Hybride Verfahren

RSA ist ca. 1000× langsamer als AES. Deshalb kombiniert man beide:

1. Sender erzeugt zufälligen AES-Sessionkey $k$.
2. Nutzdaten werden mit $k$ per AES verschlüsselt.
3. Der Sessionkey $k$ wird mit dem RSA-öffentlichen Schlüssel des Empfängers verschlüsselt.
4. Beides (verschlüsselte Daten + verschlüsselter Sessionkey) wird gesendet.

Dieses Prinzip ist die Grundlage von TLS/HTTPS, PGP und S/MIME.

RSA für digitale Signaturen

RSA kann auch zum Signieren verwendet werden – die Rollen werden vertauscht:

• Signieren (mit privatem Schlüssel): $\text{Sig} = m^d \bmod n$
• Verifizieren (mit öffentlichem Schlüssel): prüfe $\text{Sig}^e \bmod n \stackrel{?}{=} m$

Nur der Besitzer des privaten Schlüssels kann eine gültige Signatur erzeugen – jeder mit dem öffentlichen Schlüssel kann sie prüfen.

Karte 1 · RSA-Kochrezept in Miller-Notation

Miller nennt $\varphi(n)$ konsequent $z$. Merke die fünf Schritte in genau dieser Reihenfolge, sie decken jede Klausur-Teilaufgabe ab.

1. Zwei Primzahlen wählen: $p, q$ prim.
2. Modulus: $n = p \cdot q$.
3. Miller-Phi: $z = \varphi(n) = (p-1)(q-1)$.
4. Öffentlicher Exponent: $e$ mit $1 < e < n$ und $\gcd(e, z) = 1$.
5. Privater Exponent: $d$ mit $e \cdot d \equiv 1 \bmod z$ (via erweitertem Euklid).

Schlüsselpaare: $E = (e, n)$ öffentlich, $D = (d, n)$ privat.

Chiffrieren: $c \equiv m^e \bmod n$. Dechiffrieren: $m \equiv c^d \bmod n$.

Miller-Beobachtung: $e$ und $d$ sind symmetrisch — dieselbe Rechnung liefert eine Signatur, wenn Alice zuerst mit $d$ potenziert und Bob mit $e$ prüft.

Karte 2 · Erweiterter Euklid nach Miller (Folie S.79)

Miller schreibt das Verfahren als Zwei-Spalten-Tabelle — links die Modulo-Reste $r_i$, rechts die ganzzahligen Quotienten $x_i$. Anschließend läuft eine Rückwärts-Rekursion.

Tabelle:

$z \bmod e = r_0 \quad|\quad z \div e = x_0$
$e \bmod r_0 = r_1 \quad|\quad e \div r_0 = x_1$
$r_0 \bmod r_1 = r_2 \quad|\quad r_0 \div r_1 = x_2$
$\vdots$
$r_{t-2} \bmod r_{t-1} = 1 \quad|\quad r_{t-2} \div r_{t-1} = x_t$

Abbruch, sobald ein Rest 1 auftaucht (das bestätigt zugleich $\gcd(z, e) = 1$). Ist der letzte echte Rest größer als 1, ist $e$ ungültig.

Rekursion:

$A_{t+2} = 0, \quad A_{t+1} = 1$

$A_k = A_{k+2} - x_k \cdot A_{k+1} \quad$ für $k = t, t-1, \ldots, 0$

Gesuchtes $d = A_0 \bmod z$ (bei negativem $A_0$ einfach $z$ addieren).

Beispiel A: $z = 60,\ e = 53$

$60 \bmod 53 = 7 \quad|\quad 60 \div 53 = 1 \quad\Rightarrow r_0 = 7,\ x_0 = 1$
$53 \bmod 7 = 4 \quad|\quad 53 \div 7 = 7 \quad\Rightarrow r_1 = 4,\ x_1 = 7$
$7 \bmod 4 = 3 \quad|\quad 7 \div 4 = 1 \quad\Rightarrow r_2 = 3,\ x_2 = 1$
$4 \bmod 3 = 1 \quad|\quad 4 \div 3 = 1 \quad\Rightarrow r_3 = 1,\ x_3 = 1 \quad\text{(Stop)}$

Also $t = 3$. Rekursion:

$A_5 = 0,\ A_4 = 1$
$A_3 = A_5 - x_3 \cdot A_4 = 0 - 1 \cdot 1 = -1$
$A_2 = A_4 - x_2 \cdot A_3 = 1 - 1 \cdot (-1) = 2$
$A_1 = A_3 - x_1 \cdot A_2 = -1 - 7 \cdot 2 = -15$
$A_0 = A_2 - x_0 \cdot A_1 = 2 - 1 \cdot (-15) = 17$

Ergebnis: $d = 17$. Probe: $53 \cdot 17 = 901 = 15 \cdot 60 + 1 \equiv 1 \bmod 60$ ✓

Beispiel B: $z = 160,\ e = 107$ (aus Klausuraufgabe unten)

$160 \bmod 107 = 53 \quad|\quad 160 \div 107 = 1 \quad\Rightarrow r_0 = 53,\ x_0 = 1$
$107 \bmod 53 = 1 \quad|\quad 107 \div 53 = 2 \quad\Rightarrow r_1 = 1,\ x_1 = 2 \quad\text{(Stop)}$

Also $t = 1$. Rekursion:

$A_3 = 0,\ A_2 = 1$
$A_1 = A_3 - x_1 \cdot A_2 = 0 - 2 \cdot 1 = -2$
$A_0 = A_2 - x_0 \cdot A_1 = 1 - 1 \cdot (-2) = 3$

Ergebnis: $d = 3$. Probe: $107 \cdot 3 = 321 = 2 \cdot 160 + 1 \equiv 1 \bmod 160$ ✓

Karte 3 · Ägyptisches Potenzieren (Square-and-Multiply)

Miller nennt Square-and-Multiply konsequent ägyptisches Potenzieren (Übungsaufg. 16). Ohne diese Technik ist $m^e \bmod n$ für Klausur-typische Exponenten nicht in endlicher Zeit rechenbar.

Rezept (MSB-first):

1. Exponent binär schreiben, führendes Bit ist immer 1.
2. Startwert $r = 1$.
3. Für jedes Bit von links nach rechts: $r \leftarrow r^2 \bmod n$; falls Bit = 1, zusätzlich $r \leftarrow r \cdot m \bmod n$.
4. Nach dem letzten Bit ist $r = m^e \bmod n$.

Mini-Beispiel: $3^5 \bmod 7$ mit $5 = 101_2$.

Start: $r = 1$
Bit 1 (MSB): $r = 1^2 \cdot 3 = 3$
Bit 0: $r = 3^2 = 9 \equiv 2 \bmod 7$
Bit 1: $r = 2^2 \cdot 3 = 12 \equiv 5 \bmod 7$

Ergebnis: $3^5 \bmod 7 = 5$ ✓

Karte 4 · Vollständige Klausuraufgabe: $p=11,\ q=17,\ e=107,\ m=6$

Schritt 1 — Schlüssel erzeugen:

$n = p \cdot q = 11 \cdot 17 = 187$
$z = (p-1)(q-1) = 10 \cdot 16 = 160$
$\gcd(107, 160) = 1$ ✓ (aus EEA-Tabelle sichtbar)
$d = 3$ (aus Karte 2, Beispiel B)
Probe: $e \cdot d = 107 \cdot 3 = 321 \equiv 1 \bmod 160$ ✓

Also $E = (107, 187)$, $D = (3, 187)$.

Schritt 2 — Verschlüsseln $c = 6^{107} \bmod 187$:

Binärdarstellung: $107 = 64 + 32 + 8 + 2 + 1 = 1101011_2$.

Vorab-Potenzen (jeweils quadrieren und $\bmod 187$):

$6^1 \equiv 6$
$6^2 \equiv 36$
$6^4 = 36^2 = 1296 = 6 \cdot 187 + 174 \equiv 174$
$6^8 = 174^2$. Mit $174 \equiv -13 \bmod 187$ folgt $6^8 \equiv (-13)^2 = 169$
$6^{16} = 169^2 = 28561 = 152 \cdot 187 + 137 \equiv 137$
$6^{32} = 137^2 = 18769 = 100 \cdot 187 + 69 \equiv 69$
$6^{64} = 69^2 = 4761 = 25 \cdot 187 + 86 \equiv 86$

Zusammensetzen $6^{107} = 6^{64} \cdot 6^{32} \cdot 6^{8} \cdot 6^{2} \cdot 6^{1}$:

$86 \cdot 69 = 5934 = 31 \cdot 187 + 137 \equiv 137$
$137 \cdot 169 = 23153 = 123 \cdot 187 + 152 \equiv 152$
$152 \cdot 36 = 5472 = 29 \cdot 187 + 49 \equiv 49$
$49 \cdot 6 = 294 = 1 \cdot 187 + 107 \equiv 107$

Ergebnis: $c = 107$.

Schritt 3 — Kontrolle via Entschlüsseln $m = 107^3 \bmod 187$:

$107^2 = 11449 = 61 \cdot 187 + 42 \equiv 42$
$107^3 = 42 \cdot 107 = 4494 = 24 \cdot 187 + 6 \equiv 6$

Ergebnis: $m = 6$ ✓ — identisch mit dem Klartext, RSA-Runde geschlossen.

Karte 5 · Miller-Klausurbeispiel mit Chiffratfolge (Folie S.75–76)

Setup: Bobs öffentlicher Schlüssel $E_B = (53, 77)$. Alice sendet die Chiffratfolge $c = (62, 16, 74, 45, 21)$.

Angreifersicht (klein genug für Handrechnung):

$n = 77 = 7 \cdot 11 \;\Rightarrow\; p = 7,\ q = 11$
$z = 6 \cdot 10 = 60$
$d$: Miller-EEA aus Beispiel A liefert direkt $d = 17$ (denn $z = 60,\ e = 53$).
Probe: $53 \cdot 17 = 901 \equiv 1 \bmod 60$ ✓

Blockweise Entschlüsselung — jeweils $c_i^{17} \bmod 77$:

$62^{17} \bmod 77 = 6$
$16^{17} \bmod 77 = 25$
$74^{17} \bmod 77 = 2$
$45^{17} \bmod 77 = 12$
$21^{17} \bmod 77 = 21$

Mit Miller-Kodierung $\text{A} = 2, \text{B} = 3, \ldots, \text{Z} = 27$ ergibt $(6, 25, 2, 12, 21)$ die Buchstaben E, X, A, K, T.

Klartext: EXAKT.

Karte 6 · RSA-Schlüsseltausch (Übungsaufg. 17)

Praktisch wird RSA fast nie zur Massenverschlüsselung genutzt, sondern nur zum Transport eines symmetrischen Sitzungsschlüssels $k$ (z.B. eines AES-Schlüssels).

Ablauf:

1. Alice erzeugt einen zufälligen Session-Key $k$ (AES-128/256).
2. Alice holt Bobs öffentlichen Schlüssel $E_B = (e_B, n_B)$ und berechnet $c = k^{e_B} \bmod n_B$.
3. Alice schickt $c$ an Bob.
4. Bob rechnet $k = c^{d_B} \bmod n_B$ und hat denselben Session-Key.
5. Beide führen ab jetzt AES-Verkehr mit $k$.

Perfect Forward Secrecy? Nein, so nicht. Bobs RSA-Schlüsselpaar bleibt über viele Sitzungen konstant. Wird Bobs $d_B$ irgendwann kompromittiert — und ein Angreifer hat die alten Chiffrate mitgeschnitten —, lassen sich alle vergangenen $k$ und damit der gesamte historische Verkehr entschlüsseln.

PFS wäre nur möglich, wenn Bob für jede Sitzung ein frisches RSA-Paar erzeugte; das ist zu teuer. Deshalb setzt TLS ab Version 1.3 für den Schlüsseltausch nicht mehr RSA, sondern ephemerales Diffie-Hellman (ECDHE) ein — RSA bleibt dort nur zur Signatur der DH-Parameter.

Karte 7 · Klausur-Checkliste RSA

Standard-Reihenfolge in jeder RSA-Aufgabe:

1. $p, q$ aus Angabe → $n = p \cdot q$.
2. $z = (p-1)(q-1)$ ausrechnen (nicht $n-1$!).
3. $e$ prüfen: $\gcd(e, z) \stackrel{!}{=} 1$.
4. Miller-EEA-Tabelle (2 Spalten) → $d = A_0 \bmod z$.
5. Probe $e \cdot d \equiv 1 \bmod z$ hinschreiben — der Korrektor sieht sofort, ob $d$ stimmt.
6. Ver-/Entschlüsseln via ägyptischem Potenzieren.
7. Endprobe: $c^d \bmod n$ ergibt wieder $m$.

Typische Fallen:

• $z$ und $n$ vertauscht. Regel: Der Exponent wird mod $z$ reduziert, die Zahl selbst mod $n$.
• Vorzeichenfehler in der EEA-Rekursion. $A_k$ darf negativ sein, am Ende $+z$ addieren.
• Falsche Bit-Reihenfolge bei Square-and-Multiply (LSB-first vs. MSB-first). Wir nutzen MSB-first.
• Zwischenergebnisse nicht sofort $\bmod n$ reduziert → Zahlen explodieren.