Kryptographie, Codierung und IT-Sicherheit — Informatik · DE-Abitur Notizen

Symmetrische Verfahren — Caesar, Vigenère, AES#

BasisNRW-IF6BY-Inf-7BW-Inf-8

Symmetrische Verfahren nutzen denselben geheimen Schlüssel für Ver- und Entschlüsselung. Ihre gesamte Sicherheit ruht auf der Geheimhaltung dieses Schlüssels — nach dem Kerckhoffs-Prinzip darf das Verfahren öffentlich bekannt sein, nur der Schlüssel muss geheim bleiben (Sicherheit durch Verschleierung des Algorithmus, „security by obscurity", gilt als unseriös). Daraus folgt ihr Grundproblem: Der Schlüssel muss vorab über einen sicheren Kanal ausgetauscht werden (das Schlüsselverteilungsproblem, das erst die asymmetrische Kryptographie löst). Grundvokabular: Klartext, Schlüssel, Geheimtext (Chiffretext), Ver- und Entschlüsselung.

Die Caesar-Chiffre ist eine monoalphabetische Substitution: Jeder Buchstabe wird um eine feste Zahl k verschoben — c ≡ (m + k) mod 26 beim Verschlüsseln, m ≡ (c − k) mod 26 beim Entschlüsseln (mit A = 0, …, Z = 25). Beispiel mit k = 3: aus „HAL" wird „KDO". Der Schlüsselraum umfasst nur 25 sinnvolle Schlüssel und ist damit per Brute Force sofort durchprobierbar; selbst ohne das verrät die Häufigkeitsanalyse (im Deutschen ist E der häufigste Buchstabe) den Schlüssel.

Die Vigenère-Chiffre ist polyalphabetisch: Ein periodisch wiederholtes Schlüsselwort liefert für jede Position eine andere Caesar-Verschiebung. Für „INFORMATIK" mit Schlüssel „ABI" (A = 0, B = 1, I = 8) verschieben sich die Positionen um 0, 1, 8, 0, 1, 8, … — derselbe Klarbuchstabe wird je nach Stelle unterschiedlich abgebildet, was die Häufigkeitsanalyse zunächst vereitelt (im 19. Jahrhundert galt es als „unbrechbar"). Die Schwäche ist jedoch genau die Periodizität: Der Kasiski-Test und der Friedman-Test ermitteln aus Wiederholungen die Schlüssellänge; danach zerfällt der Text in Spalten, die je eine simple Caesar-Chiffre sind und einzeln per Häufigkeitsanalyse fallen.

Das One-Time-Pad (OTP) verwendet einen echt zufälligen Schlüssel, der so lang wie der Klartext ist und nur einmal benutzt wird; Claude Shannon (1949) bewies dafür die perfekte Sicherheit — der Geheimtext verrät nichts über den Klartext. In der Praxis scheitert es am Schlüsselmanagement (man müsste so viel sicheren Schlüssel verteilen wie Nutzdaten). Entscheidend: Die Sicherheit hängt ausschließlich an Einmaligkeit und Zufall — wird derselbe Schlüssel zweimal genutzt (Two-Time-Pad), hebt die XOR-Differenz zweier Geheimtexte den Schlüssel auf und das Verfahren ist trivial gebrochen.

Moderne symmetrische Verfahren sind Block- oder Stromchiffren. AES (Advanced Encryption Standard, Algorithmus Rijndael, NIST-Standard seit 2001) ist die Block-Chiffre der Wahl: 128-Bit-Blöcke, Schlüssel zu 128/192/256 Bit, ein Substitutions-Permutations-Netzwerk über mehrere Runden, oft hardwarebeschleunigt — der Arbeitspferd-Algorithmus für TLS, Festplatten- und VPN-Verschlüsselung. Der Vorgänger DES (1977, nur 56-Bit-Schlüssel) gilt durch Brute Force als überholt.

Eine Block-Chiffre allein verschlüsselt nur einen Block — wie viele Blöcke verkettet werden, regeln die Betriebsmodi: ECB (jeder Block unabhängig → gleiche Klartextblöcke ergeben gleiche Geheimtextblöcke, das Muster bleibt sichtbar, berüchtigt als „ECB-Pinguin" — nie verwenden), CBC (Verkettung mit Initialisierungsvektor), CTR (Zählermodus, macht aus der Block- eine parallelisierbare Stromchiffre) und GCM (authenticated encryption — Vertraulichkeit und Integrität zugleich, heutiger Standard).

Typische Fehler

Vigenère als „polyalphabetisch und damit unbrechbar" bezeichnet — der Kasiski-/Friedman-Test bricht es über die Schlüssellänge.
One-Time-Pad bei Schlüsselwiederverwendung als sicher angegeben — nur einmalig + echt zufällig ist es perfekt sicher.
AES als asymmetrisch klassifiziert — AES ist symmetrisch (ein gemeinsamer geheimer Schlüssel).
ECB als sicheren Standardmodus verwendet — es leckt Klartextmuster; Standard sind CBC/CTR/GCM.

LK-Vertiefung

eA-Vertiefung: Begründen Sie über die perfekte Sicherheit (Shannon 1949), warum das One-Time-Pad informationstheoretisch unbrechbar ist (der Geheimtext ist von Zufall ununterscheidbar), und erläutern Sie, warum genau die Schlüsselverteilung es praktisch untauglich macht — und damit zur asymmetrischen Kryptographie überleitet.

Aktive Wiederholung

Erläutern Sie an einem konkreten Beispiel die Vigenère-Verschlüsselung des Klartexts „INFORMATIK" mit Schlüssel „ABI" und analysieren Sie eine Schwäche des Verfahrens.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Asymmetrische Verfahren — RSA und Diffie-Hellman#

VertiefungKMK-EPA-Inf-ModellierenNRW-IF6BY-Inf-7BW-Inf-8

RSA-Schlüsselpaar — Verschlüsselung und Entschlüsselung

Abb. 1Öffentlicher Schlüssel (e, n) verschlüsselt, privater Schlüssel (d, n) entschlüsselt; Sicherheit basiert auf Faktorisierungsschwierigkeit.

Asymmetrische Verfahren verwenden ein Schlüsselpaar: einen frei verteilbaren öffentlichen Schlüssel (zum Verschlüsseln bzw. Verifizieren) und einen geheim gehaltenen privaten Schlüssel (zum Entschlüsseln bzw. Signieren). Das löst das Schlüsselverteilungsproblem der symmetrischen Verfahren — es muss kein gemeinsames Geheimnis vorab sicher ausgetauscht werden. Mathematisch beruhen sie auf Einwegfunktionen mit Falltür (trapdoor): leicht in eine Richtung, praktisch unumkehrbar ohne das geheime Zusatzwissen. Den Begriff der Public-Key-Kryptographie führten Whitfield Diffie und Martin Hellman (1976) ein.

RSA (Rivest, Shamir, Adleman 1977) ist das asymmetrische Standardverfahren; seine Sicherheit beruht auf der praktischen Schwierigkeit der Faktorisierung: Zwei große Primzahlen zu multiplizieren (n = p·q) ist leicht, das Produkt wieder in seine Primfaktoren zu zerlegen ist (nach heutigem Stand) unbezahlbar schwer. Genau diese Asymmetrie ist die Falltür.

Die Schlüsselerzeugung verläuft in fünf Schritten: (1) zwei große Primzahlen p, q wählen; (2) den Modul n = p·q bilden; (3) φ(n) = (p−1)(q−1) berechnen (eulersche φ-Funktion); (4) einen öffentlichen Exponenten e mit 1 < e < φ(n) und ggT(e, φ(n)) = 1 wählen; (5) den privaten Exponenten d als modulares Inverses lösen: e·d ≡ 1 (mod φ(n)) — entscheidend mod φ(n), nicht mod n — per erweitertem euklidischem Algorithmus. Der öffentliche Schlüssel ist (e, n), der private (d, n); p, q und φ(n) müssen geheim bleiben bzw. vernichtet werden.

Verschlüsselt wird mit dem öffentlichen Schlüssel über c ≡ mᵉ (mod n), entschlüsselt mit dem privaten über m ≡ cᵈ (mod n). Die Korrektheit (cᵈ ergibt wieder m) folgt aus dem Satz von Euler/Fermat: Weil e·d ≡ 1 (mod φ(n)) ist, gilt m^(e·d) ≡ m (mod n).

Vollständig durchgerechnetes Mini-Beispiel (siehe auch das nebenstehende Rechenbeispiel): p = 3, q = 11 → n = 33, φ(n) = 2·10 = 20. Wähle e = 3 (ggT(3, 20) = 1). Bestimme d aus 3·d ≡ 1 (mod 20) → d = 7 (denn 3·7 = 21 ≡ 1 mod 20). Verschlüsselung von m = 4: c = 4³ mod 33 = 64 mod 33 = 31. Entschlüsselung: m = 31⁷ mod 33; mit 31 ≡ −2 (mod 33) ist (−2)⁷ = −128 ≡ 4 (mod 33) — also wieder m = 4. Öffentlicher Schlüssel (3, 33), privater (7, 33).

Zwei Verwendungen sind streng zu trennen: Für Vertraulichkeit verschlüsselt der Sender mit dem öffentlichen Schlüssel des Empfängers, sodass nur dieser mit seinem privaten Schlüssel entschlüsseln kann; für Authentizität/Signatur signiert der Sender mit seinem eigenen privaten Schlüssel, und jeder verifiziert mit dem öffentlichen Schlüssel des Senders. Praktisch nutzt RSA Moduln von ≥ 2048 Bit (Schulbeispiele rechnen mit winzigen Primzahlen). Der verwandte Diffie-Hellman-Schlüsseltausch (Sicherheit über den diskreten Logarithmus) wird im Abschnitt Schlüsseltausch und PKI vertieft. Querverweis: RSA setzt voraus, dass die Faktorisierung kein effizientes Verfahren besitzt — ein hypothetischer Beweis P = NP (Topic Theoretische Informatik) bzw. ein hinreichend großer Quantenrechner (Shor-Algorithmus) würde es gefährden.

n = p\cdot q,\quad \varphi(n) = (p-1)(q-1),\quad e\cdot d \equiv 1 \pmod{\varphi(n)}

RSA-Schlüsselerzeugung

p, q große Primzahlen; e mit ggT(e, φ(n)) = 1; d ist multiplikatives Inverses von e modulo φ(n).

c \equiv m^{e} \pmod{n},\qquad m \equiv c^{d} \pmod{n}

RSA-Ver- und Entschlüsselung

Nachricht m wird mit dem öffentlichen Schlüssel (e, n) verschlüsselt; nur Inhaber von d kann entschlüsseln.

Musterlösung

RSA-Verschlüsselung mit p = 5, q = 11

Erzeugen Sie ein RSA-Schlüsselpaar mit p = 5, q = 11, e = 3 und verschlüsseln Sie die Nachricht m = 9.

Schritt 1 — Modul und φ(n)
n = p·q = 55. φ(n) = (p−1)(q−1) = 4·10 = 40.
Schritt 2 — e validieren
ggT(e, φ(n)) = ggT(3, 40) = 1 — e ist zulässig.
Schritt 3 — Privaten Schlüssel d berechnen
Erweiterter Euklid: 3·d ≡ 1 (mod 40). Lösung d = 27, denn 3·27 = 81 = 2·40 + 1.
Schritt 4 — Verschlüsseln
c = m^e mod n = 9^3 mod 55 = 729 mod 55 = 14 (denn 729 = 13·55 + 14).
Schritt 5 — Probe-Entschlüsselung
m′ = c^d mod n = 14^27 mod 55. Über Square-and-Multiply: 14^2 = 196 ≡ 31; 14^4 ≡ 31² mod 55 = 961 mod 55 = 26; weiter bis 14^27 mod 55 = 9. Bestätigt m′ = m.

Ergebnis: Öffentlicher Schlüssel (e=3, n=55), privater Schlüssel d=27. Chiffrat c = 14.

Typische Fehler

`e · d ≡ 1 mod n` statt `mod φ(n)` gerechnet — der häufigste RSA-Fehler.
e nicht teilerfremd zu φ(n) gewählt → es existiert kein Inverses d.
φ(n) als p·q statt (p−1)(q−1) berechnet.
Vertraulichkeit und Authentizität verwechselt — Verschlüsseln mit Empfänger-Public-Key, Signieren mit Sender-Private-Key.
Bei der Potenz-Modulo-Rechnung nicht modular reduziert — mᵉ wird riesig; stattdessen schrittweise mod n rechnen (z. B. über −2 statt 31).

LK-Vertiefung

eA-Vertiefung: Beurteilen Sie die Sicherheitskonsequenzen eines hypothetischen Quantencomputers (Shor-Algorithmus) für RSA und nennen Sie alternative Verfahren (Lattice-based, McEliece).

Aktive Wiederholung

Berechnen Sie für p = 5, q = 11 ein gültiges RSA-Schlüsselpaar mit e = 3; verschlüsseln und entschlüsseln Sie die Nachricht m = 4.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Hashfunktionen, MACs und digitale Signaturen#

StandardNRW-IF6BY-Inf-7

Eine kryptografische Hashfunktion H: {0,1} → {0,1}ⁿ bildet eine beliebig lange Eingabe auf einen fest langen Hashwert (Digest, „digitaler Fingerabdruck") ab — sie ist deterministisch (gleiche Eingabe → gleicher Hash), schnell berechenbar, aber bewusst nicht umkehrbar (Einweg). Eine kleinste Änderung der Eingabe verändert etwa die Hälfte der Ausgabebits (Lawineneffekt). Aktuelle sichere Vertreter sind SHA-256 und SHA-3* (Keccak).

Drei Sicherheitseigenschaften sind sauber zu trennen: Pre-Image-Resistenz (zu gegebenem Hash h ist praktisch kein Urbild m mit H(m) = h findbar — die Einweg-Eigenschaft), Second-Pre-Image-Resistenz (zu gegebenem m₁ ist kein zweites m₂ ≠ m₁ mit gleichem Hash findbar) und Kollisionsresistenz (es ist überhaupt kein Paar m₁ ≠ m₂ mit H(m₁) = H(m₂) findbar). Die Kollisionsresistenz ist die stärkste Anforderung und wegen des Geburtstagsparadoxons schon mit rund 2^(n/2) Versuchen angreifbar. MD5 und SHA-1 gelten als gebrochen (es wurden praktische Kollisionen erzeugt) und dürfen sicherheitskritisch nicht mehr verwendet werden.

Ein HMAC (Hash-based Message Authentication Code) verkettet die Hashfunktion mit einem gemeinsamen geheimen Schlüssel und sichert so Integrität und Authentizität in einem Schritt: Wer den Schlüssel nicht kennt, kann den Code weder fälschen noch nachrechnen. Weil der Schlüssel geteilt ist, ist HMAC ein symmetrisches Authentifizierungsmittel und liefert keine Nicht-Abstreitbarkeit (beide Seiten könnten den Code erzeugt haben).

Eine digitale Signatur verbindet Hashfunktion und asymmetrisches Verfahren: Der Sender bildet den Hash der Nachricht und „verschlüsselt/signiert" diesen mit seinem privaten Schlüssel; der Empfänger hasht die empfangene Nachricht selbst und prüft sie mit dem öffentlichen Schlüssel des Senders gegen die Signatur. Man signiert den Hash (nicht die ganze Nachricht), weil die asymmetrische Operation langsam ist und der Hash fest kurz. Erreicht werden damit Integrität, Authentizität und Nicht-Abstreitbarkeit (nur der Inhaber des privaten Schlüssels konnte signieren) — der entscheidende Mehrwert gegenüber dem symmetrischen HMAC.

Für die Passwortspeicherung gilt: niemals im Klartext, sondern als gesalzener Hash. Ein Salt (ein zufälliger, pro Nutzer verschiedener Zusatz) verhindert, dass gleiche Passwörter denselben Hash ergeben, und entwertet vorberechnete Rainbow-Tables. Zudem nimmt man absichtlich langsame, speicherharte Schlüsselableitungsfunktionen (KDF) wie bcrypt, scrypt, Argon2 oder PBKDF2 — ihre Langsamkeit bremst Brute-Force-Angriffe; eine schnelle Allzweck-Hashfunktion wie SHA-256 ist für Passwörter gerade nicht geeignet.

Weitere Anwendungen nutzen die Eindeutigkeit des Fingerabdrucks: Git adressiert Commits/Objekte über ihren Hash (inhaltsadressiert), die Blockchain verkettet Blöcke über den Hash des Vorgängers (jede nachträgliche Änderung bräche die Kette), Code-Signaturen und Zertifikate signieren jeweils den Hash, und Prüfsummen belegen die Unversehrtheit heruntergeladener Dateien.

Typische Fehler

Verschlüsselung und Hash vermischt — ein Hash ist nicht umkehrbar (keine „Entschlüsselung des Hashes").
Salt vergessen → gleicher Hash für gleiche Passwörter, Rainbow-Table-Angriff möglich.
Signatur mit Empfänger-Private-Key beschrieben — korrekt ist der Sender-Private-Key.
Eine schnelle Hashfunktion (SHA-256) direkt zur Passwortspeicherung verwendet statt einer langsamen KDF (bcrypt/Argon2).
HMAC und digitale Signatur gleichgesetzt — nur die Signatur liefert Nicht-Abstreitbarkeit.

LK-Vertiefung

eA-Vertiefung: Erläutern Sie über das Geburtstagsparadoxon, warum die Kollisionsresistenz nur etwa 2^(n/2) statt 2ⁿ Aufwand bietet und ein Hash daher doppelt so lang sein muss wie das angestrebte Sicherheitsniveau. Begründen Sie zudem, warum die Hash-Verkettung einer Blockchain nachträgliche Manipulationen erkennbar macht.

Aktive Wiederholung

Erläutern Sie das Zusammenspiel von Hashfunktion und asymmetrischem Verfahren bei der Erzeugung einer digitalen Signatur und beurteilen Sie, welche Sicherheitsziele (Integrität, Authentizität, Nicht-Abstreitbarkeit) dadurch erreicht werden.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Codierung und Informationstheorie — Shannon und Huffman#

StandardNRW-IF6BY-Inf-7BW-Inf-8

Huffman-Baum für {A:0,4 · B:0,3 · C:0,2 · D:0,1}

Abb. 2Bottom-up zusammengefasste Wahrscheinlichkeiten; linke Kante 0, rechte Kante 1 liefert den Präfixcode A = 0, B = 11, C = 101, D = 100.

Die Informationstheorie (Claude Shannon, 1948) misst Information quantitativ: Der Informationsgehalt eines Symbols mit Wahrscheinlichkeit p beträgt −log₂ p Bit — ein seltenes Symbol trägt mehr Information als ein häufiges. Die Shannon-Entropie H(X) = −Σ pᵢ log₂ pᵢ ist der mittlere Informationsgehalt einer Quelle in Bit pro Symbol und damit das Maß ihrer „Überraschung": Eine Gleichverteilung hat maximale Entropie (kaum komprimierbar), eine schiefe Verteilung niedrige (gut komprimierbar).

Daraus folgt der Quellencodierungssatz als harte Grenze: Keine verlustfreie Codierung kommt im Mittel unter H(X) Bit pro Symbol. Die Entropie beziffert also die unvermeidbare Mindestrate — Kompression bedeutet, sich dieser Schranke anzunähern, sie aber nie zu unterschreiten.

Ein Präfixcode (präfixfrei) ist so gebaut, dass kein Codewort Präfix eines anderen ist; dadurch ist die Bitfolge eindeutig und ohne Trennzeichen dekodierbar — man liest sie von links nach rechts und schließt jedes Codewort ab, sobald ein Blatt erreicht ist. Anschaulich ist ein Präfixcode ein Binärbaum, dessen Symbole nur an den Blättern sitzen (Kante nach links = 0, nach rechts = 1).

Die Huffman-Codierung (David Huffman, 1952) konstruiert den optimalen Präfixcode bottom-up: Jedes Symbol startet als Blatt mit seiner Wahrscheinlichkeit; in jeder Runde werden die zwei Knoten kleinster Wahrscheinlichkeit zu einem neuen Knoten (Summe der beiden) zusammengefasst, bis ein einziger Baum bleibt. Häufige Symbole landen nahe der Wurzel (kurze Codes), seltene tief im Baum (lange Codes) — variable Codelänge. Es gilt die Schranke H(X) ≤ L̄ < H(X) + 1 für die mittlere Codelänge L̄ = Σ pᵢ·lᵢ.

Wichtig ist die Bedeutung von „optimal": Huffman minimiert die mittlere (mit den Wahrscheinlichkeiten gewichtete) Codelänge, nicht die Länge einzelner Codewörter. Anwendung findet das Verfahren in DEFLATE/ZIP (kombiniert mit LZ77), JPEG, PNG, MP3 (in bestimmten Stufen) und vielen Hardware-Codecs — meist als finale Entropiestufe nach einer vorgeschalteten Modellierung.

H(X) = -\sum_{i=1}^{n} p_i \,\log_2 p_i

Shannon-Entropie

Mittlerer Informationsgehalt einer Quelle in Bit pro Symbol; untere Schranke der verlustfreien Kompression.

\overline{L} = \sum_{i=1}^{n} p_i \cdot \ell_i

Mittlere Codewortlänge

Huffman-Code minimiert L̄ unter der Präfixbedingung; H(X) ≤ L̄ < H(X) + 1.

Musterlösung

Huffman-Code für {A:0.4, B:0.3, C:0.2, D:0.1}

Konstruieren Sie einen Huffman-Code für die gegebenen Häufigkeiten und vergleichen Sie die mittlere Codewortlänge mit der Entropie.

Schritt 1 — Priority Queue
Sortiert: D(0.1), C(0.2), B(0.3), A(0.4). Verbinde D+C zu (DC, 0.3).
Schritt 2 — Weiter zusammenfassen
Nächste zwei kleinste: DC(0.3) + B(0.3) → DCB(0.6). Dann DCB(0.6) + A(0.4) → Wurzel(1.0).
Schritt 3 — Codeworte ablesen
A = 0 (1 Bit), B = 11 (2 Bit), C = 101 (3 Bit), D = 100 (3 Bit). Präfixfrei.
Schritt 4 — Mittlere Länge berechnen
L̄ = 0.4·1 + 0.3·2 + 0.2·3 + 0.1·3 = 0.4 + 0.6 + 0.6 + 0.3 = 1.9 Bit/Zeichen.
Schritt 5 — Vergleich mit Entropie
H(X) = −(0.4·log2 0.4 + 0.3·log2 0.3 + 0.2·log2 0.2 + 0.1·log2 0.1) ≈ 1.846 Bit. Es gilt H ≤ L̄ < H+1 — Huffman ist optimal unter Präfixcodes.

Ergebnis: Codewort A=0, B=11, C=101, D=100; mittlere Länge L̄ = 1,9 Bit ≈ Entropie 1,846 Bit.

Typische Fehler

Entropie mit log₁₀ statt log₂ berechnet — das Ergebnis ist dann nicht in Bit.
Beim Huffman-Baum nicht die ZWEI kleinsten Wahrscheinlichkeiten verschmolzen.
„Optimaler" Code als „kürzeste Codewörter" gedeutet — gemeint ist die kürzeste MITTLERE Codelänge.
Behauptet, Kompression könne unter die Entropie H(X) gehen — H(X) ist die untere Schranke.
Symbole nicht nur an Blättern platziert — dann ist der Code nicht mehr präfixfrei.

LK-Vertiefung

eA-Vertiefung: Begründen Sie über die Schranke H(X) ≤ L̄ < H(X) + 1, warum Huffman nur unter ganzzahligen Codewortlängen optimal ist, und erläutern Sie, wieso die arithmetische Codierung bei nicht-dyadischen Wahrscheinlichkeiten näher an die Entropie herankommt. Zeigen Sie an einer Verteilung, dass maximale Entropie genau bei Gleichverteilung erreicht wird.

Aktive Wiederholung

Konstruieren Sie für die Symbolwahrscheinlichkeiten {A: 0.4, B: 0.2, C: 0.2, D: 0.1, E: 0.1} den Huffman-Baum, berechnen Sie die mittlere Codelänge und vergleichen Sie sie mit der Entropie.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Schlüsseltausch, PKI und Zertifikate#

VertiefungNRW-IF6BY-Inf-7BW-Inf-8

Symmetrische Verfahren brauchen einen gemeinsamen geheimen Schlüssel — doch wie vereinbaren ihn zwei Parteien über einen unsicheren Kanal, den ein Lauscher vollständig mithört? Dieses Schlüsselaustauschproblem ist der Ausgangspunkt der Public-Key-Idee und wurde 1976 von Diffie und Hellman gelöst.

Der Diffie-Hellman-Schlüsseltausch nutzt öffentliche Parameter — eine große Primzahl p und einen Generator g. Jede Seite wählt einen geheimen Exponenten (Alice a, Bob b) und sendet öffentlich A = gᵃ mod p bzw. B = gᵇ mod p. Beide berechnen daraus denselben gemeinsamen Schlüssel g^(ab) mod p — Alice als Bᵃ mod p, Bob als Aᵇ mod p —, ohne ihn je zu übertragen. Die Sicherheit beruht auf dem diskreten Logarithmus: Aus g, p und gᵃ den Exponenten a zurückzurechnen ist praktisch unmöglich.

Konkretes Mini-Beispiel: p = 11, g = 2; Alice wählt a = 3 → A = 2³ mod 11 = 8; Bob wählt b = 4 → B = 2⁴ mod 11 = 5. Alice rechnet Bᵃ = 5³ mod 11 = 125 mod 11 = 4, Bob rechnet Aᵇ = 8⁴ mod 11 = 4096 mod 11 = 4 — beide erhalten denselben Schlüssel g^(ab) = 2¹² mod 11 = 4, obwohl nur 2, 11, 8 und 5 über die Leitung gingen (siehe das nebenstehende Rechenbeispiel).

Weil asymmetrische Operationen langsam sind, kombiniert die Praxis beides zur hybriden Verschlüsselung: Das asymmetrische Verfahren (RSA bzw. DH) transportiert bzw. vereinbart nur einen symmetrischen Sitzungsschlüssel, mit dem dann die Massendaten effizient per AES verschlüsselt werden. So vereint man die sichere Schlüsselverteilung der Public-Key-Welt mit der Geschwindigkeit der symmetrischen — genau das tut der TLS-Handshake.

Ein öffentlicher Schlüssel beweist allerdings nicht, wem er gehört. Eine Public-Key-Infrastruktur (PKI) bindet öffentliche Schlüssel über Zertifikate (Format X.509) an Identitäten; ein Zertifikat wird von einer Zertifizierungsstelle (CA) signiert und so beglaubigt. Das Vertrauen läuft über eine Kette: Ein Wurzelzertifikat (im Betriebssystem/Browser vorinstalliert) signiert Zwischenzertifikate, diese signieren Server-Zertifikate; der Browser validiert die Kette bis zu einer ihm hinterlegten Wurzel und vertraut nur solchen Ketten — nicht „jedem".

Ohne Authentifizierung ist der reine DH anfällig für den Man-in-the-Middle (MitM): Ein Angreifer in der Mitte führt mit Alice und Bob je einen separaten DH durch und reicht die Nachrichten weiter, sodass er beide Schlüssel kennt. Erst die Authentifizierung über Zertifikate (im TLS-Handshake) bindet den ausgetauschten Schlüssel an die echte Gegenstelle und vereitelt den MitM — der Schlüsseltausch braucht also zwingend eine Identitätsprüfung.

A = g^{a} \bmod p,\quad B = g^{b} \bmod p,\quad K = B^{a} \equiv A^{b} \equiv g^{ab} \pmod{p}

Diffie-Hellman-Schlüsseltausch

Öffentlich sind p, g, A, B; der gemeinsame Schlüssel K wird nie übertragen. Sicherheit beruht auf dem diskreten Logarithmus.

Musterlösung

Diffie-Hellman-Schlüsseltausch mit p = 23, g = 5

Berechnen Sie den gemeinsamen Schlüssel, den Alice (geheim a = 6) und Bob (geheim b = 15) über den öffentlichen Kanal mit p = 23 und g = 5 vereinbaren.

Schritt 1 — Öffentliche Werte berechnen
A = g^a mod p = 5^6 mod 23 = 8 (über 5^2 ≡ 2, 5^4 ≡ 4, 5^6 ≡ 4·2 = 8). B = g^b mod p = 5^15 mod 23 = 19.
Schritt 2 — Werte austauschen
Alice sendet A = 8, Bob sendet B = 19. Die geheimen Exponenten a und b bleiben jeweils privat und werden nie übertragen.
Schritt 3 — Gemeinsamen Schlüssel ableiten
Alice: K = B^a mod p = 19^6 mod 23 = 2 (denn 19 ≡ −4, (−4)^6 = 4096 ≡ 2). Bob: K = A^b mod p = 8^15 mod 23 = 2. Beide erhalten denselben Wert.
Diffie-Hellman-Schlüsseltausch
$A = g^{a} \bmod p,\quad B = g^{b} \bmod p,\quad K = B^{a} \equiv A^{b} \equiv g^{ab} \pmod{p}$
Öffentlich sind p, g, A, B; der gemeinsame Schlüssel K wird nie übertragen. Sicherheit beruht auf dem diskreten Logarithmus.
Schritt 4 — Sicherheitsinterpretation
Ein Angreifer kennt p, g, A, B, müsste aber den diskreten Logarithmus (a aus A) lösen — für große p praktisch unmöglich. Anfällig ist DH ohne Authentifizierung für Man-in-the-Middle.

Ergebnis: Gemeinsamer Schlüssel K = 2; identisch über beide Berechnungswege bestätigt.

Typische Fehler

Diffie-Hellman als Verschlüsselungsverfahren bezeichnet — es ist ein Schlüssel-AUSTAUSCH, kein Chiffrierverfahren.
Den geheimen Exponenten a bzw. b für öffentlich gehalten — öffentlich sind nur p, g, A und B.
PKI-Vertrauen als „der Browser vertraut jedem Zertifikat" missverstanden — nur Ketten zu hinterlegten Wurzeln gelten.
MitM-Anfälligkeit von unauthentifiziertem DH übersehen — DH allein authentifiziert die Gegenstelle nicht.
Bei der DH-Rechnung nicht modular reduziert — Zwischenwerte wie 8⁴ schrittweise mod p kleinhalten.

LK-Vertiefung

eA-Vertiefung: Erläutern Sie, wie der TLS-Handshake DH-Schlüsseltausch und Zertifikatsvalidierung kombiniert, und begründen Sie den Sicherheitsgewinn durch ephemere Schlüssel (Forward Secrecy).

Aktive Wiederholung

Berechnen Sie für p = 23, g = 5 mit den geheimen Exponenten a = 6 und b = 15 den gemeinsamen Diffie-Hellman-Schlüssel und beurteilen Sie, warum eine Authentifizierung gegen Man-in-the-Middle nötig ist.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.

Zahlensysteme und Datenrepräsentation#

BasisNRW-IF1BY-Inf-1BW-Inf-1

In einem Stellenwertsystem zur Basis b verwendet man die Ziffern 0 bis b−1, und der Wert einer Zahl ist die gewichtete Summe Σ Ziffer·b^Stelle. Gebräuchlich sind Dual (Basis 2), Oktal (8), Dezimal (10) und Hexadezimal (16, mit den Ziffern 0–9 und A–F für 10–15). Die Umrechnung Dezimal → Basis erfolgt per fortlaufender Division mit Rest (Reste von unten nach oben lesen), die Umrechnung Basis → Dezimal per Wertigkeitssumme. Beispiel: 13 dezimal → 13 = 8+4+1 = 1101₂; rückwärts 1101₂ = 1·8 + 1·4 + 0·2 + 1·1 = 13.

Eine Hex-Ziffer fasst genau vier Bit (ein „Nibble") zusammen, zwei Hex-Ziffern ein Byte — daher ist Hexadezimal die kompakte Schreibweise für Binärdaten (Speicheradressen, Farben #RRGGBB). Beispiel: 0xB = 1011₂ = 11; das Byte 1011 0110₂ entspricht 0xB6 = 128+32+16+4+2 = 182 dezimal. Man gruppiert dazu die Bits einfach in Viererblöcke.

Das Zweierkomplement stellt negative Ganzzahlen dar: Man invertiert alle Bits und addiert 1; das höchstwertige Bit erhält dabei die Wertigkeit −2^(n−1). Der große Vorteil: Addition und Subtraktion funktionieren ohne Sonderbehandlung des Vorzeichens (dieselbe Addierschaltung), und es gibt nur eine Null. Beispiel −6 im 4-Bit-System: +6 = 0110, invertiert 1001, plus 1 → 1010 (Probe: −8 + 2 = −6).

Der Wertebereich des n-Bit-Zweierkomplements ist −2^(n−1) bis 2^(n−1) − 1 — also asymmetrisch, mit einer negativen Zahl mehr (z. B. 8 Bit: −128 bis +127). Ein Überlauf (Overflow) entsteht, wenn das Ergebnis diesen Bereich verlässt (etwa 127 + 1 „kippt" zu −128); er ist an den Carry-/Vorzeichenregeln erkennbar.

Gleitkommazahlen nach IEEE 754 bestehen aus Vorzeichen, Exponent (mit Bias) und Mantisse und decken einen riesigen Wertebereich bei endlicher Genauigkeit ab. Daraus folgen unvermeidbare Rundungsfehler: Viele Dezimalbrüche (etwa 0,1) sind binär nicht exakt darstellbar, weshalb 0,1 + 0,2 ≠ 0,3 exakt gilt. Praktische Konsequenz: Gleitkommazahlen nie mit `==` vergleichen, sondern mit einer kleinen Toleranz (Epsilon).

Die Zeichencodierung ordnet Zeichen Bitmustern zu: ASCII (7 Bit, 128 Zeichen) deckt nur Englisch ab, Latin-1/ISO-8859-1 (8 Bit) westeuropäische Zeichen. Unicode ist der Zeichensatz (jedes Zeichen ein „Code Point"), UTF-8 dagegen eine Kodierung davon mit variabler Länge (1–4 Byte), die zudem ASCII-kompatibel ist und sich als Web-Standard durchgesetzt hat. Unicode (der Vorrat) und UTF-8 (eine konkrete Bytedarstellung) sind also nicht dasselbe.

z = (-1)^{s}\cdot 1{,}m \cdot 2^{(e - \text{Bias})}

IEEE-754-Gleitkommazahl

Vorzeichenbit s, normalisierte Mantisse 1,m, Exponent e mit Bias (127 bei single, 1023 bei double).

Musterlösung

Zweierkomplement und Zahlensysteme

Stellen Sie die Dezimalzahl −6 als 8-Bit-Zweierkomplement dar und wandeln Sie die Binärzahl 1011 0010 in Hexadezimal- und Dezimalschreibweise (als vorzeichenlose Zahl) um.

Schritt 1 — Betrag binär darstellen
+6 = 0000 0110 als 8-Bit-Dualzahl.
Schritt 2 — Zweierkomplement bilden
Alle Bits invertieren: 1111 1001. Anschließend 1 addieren: 1111 1010. Das ist die 8-Bit-Darstellung von −6.
Schritt 3 — Probe über die Wertigkeit
Im Zweierkomplement hat das höchste Bit Wertigkeit −2^7 = −128: −128 + 64 + 32 + 16 + 8 + 0 + 2 + 0 = −6. Bestätigt.
Schritt 4 — Umrechnung 1011 0010
Vierergruppen: 1011 = B, 0010 = 2 → Hex 0xB2. Dezimal vorzeichenlos: 128 + 32 + 16 + 2 = 178.

Ergebnis: −6 = 1111 1010 (8-Bit-Zweierkomplement); 1011 0010 = 0xB2 = 178 (vorzeichenlos).

Typische Fehler

Bei Zweierkomplement die +1 nach dem Invertieren vergessen.
Hex-Ziffer A–F als Dezimalziffer fehlinterpretiert (A = 10, nicht 1).
Wertebereich symmetrisch angegeben — es gibt eine negative Zahl mehr (8 Bit: −128 bis +127).
Gleitkommazahlen als exakt angenommen — Rundungsfehler beim Vergleich mit `==` ignoriert.
UTF-8 und Unicode gleichgesetzt — Unicode ist der Zeichensatz, UTF-8 eine (variabel lange) Kodierung davon.

LK-Vertiefung

eA-Vertiefung: Erläutern Sie anhand der IEEE-754-Single-Precision-Darstellung, warum 0,1 + 0,2 ≠ 0,3 im Gleitkommabereich gilt.

Aktive Wiederholung

Berechnen Sie die 8-Bit-Zweierkomplement-Darstellung von −13 und wandeln Sie die Binärzahl 1100 1010 in Hexadezimal- und vorzeichenlose Dezimalschreibweise um.

Aktiv abrufen

Erinnere dich an die Kernpunkte — dann aufdecken.