DE-Abitur · InformatikT·077 / 8

Kryptographie, Codierung und IT-Sicherheit

Symmetrische und asymmetrische Verfahren, Hashfunktionen, digitale Signaturen sowie verlustfreie Codierung (Huffman) prägen den modernen IT-Sicherheitsdiskurs. RSA als asymmetrisches Standardverfahren ist EPA-Pflicht; Shannon-Entropie verbindet Codierung und Informationstheorie.

6Abschnitteca. 12Min Lesezeit3Kompetenzen

KB-MI · Modellieren und Implementieren — Verschlüsselungsverfahren auf kleinen Zahlen rechnerisch nachvollziehen.KB-BB · Begründen und Bewerten — Sicherheit und Effizienz von Verfahren vergleichen.KB-KG · Kommunizieren und Gesellschaft — IT-Sicherheit gesellschaftlich einordnen.

Operatoren:analysieren · berechnen · beurteilen · erläutern · darstellen

grundlegendes Niveau

gA: Caesar- und Vigenère-Chiffre als symmetrische Verfahren, Prinzip öffentlicher Schlüssel, Hash zur Integritätsprüfung.

erhöhtes Niveau

eA: RSA mit kleinen Primzahlen vollständig durchrechnen (Schlüsselerzeugung, Ver- und Entschlüsselung), Diffie-Hellman, digitale Signaturen, Huffman-Codierung.

Inhalt · 6 Abschnitte

Kryptographie, Codierung und IT-Sicherheit

Symmetrische Verfahren — Caesar, Vigenère, AES#

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

Kernpunkte

Symmetrische Verfahren nutzen denselben geheimen Schlüssel für Ver- und Entschlüsselung; Schlüssel muss sicher ausgetauscht werden.
Caesar-Chiffre: Verschiebung jedes Buchstabens um k Positionen — historisch, kryptografisch trivial (Schlüsselraum nur 25).
Vigenère-Chiffre: Caesar mit periodischem Schlüsselwort — bis 19. Jh. „unbrechbar", bricht durch Friedman/Kasiski-Test.
One-Time-Pad: Schlüssel so lang wie Klartext, einmalig — beweisbar sicher (Shannon 1949), praktisch unhandlich.
AES (Advanced Encryption Standard, Rijndael, 2001): Block-Chiffre mit 128/192/256-Bit-Schlüsseln; Standard für TLS, Festplattenverschlüsselung.
Betriebsmodi: ECB (unsicher, gleiche Blöcke → gleicher Cipher), CBC (Verkettung), CTR (Zählermodus, parallelisierbar), GCM (auth. encryption).

Typische Fehler

Vigenère als „polyalphabetisch unbrechbar" — falsch, Kasiski-Test bricht bei langem Klartext.
One-Time-Pad bei Schlüsselwiederverwendung als sicher angegeben — bei Wiederverwendung trivial brechbar.
AES als asymmetrisch klassifiziert — ist symmetrisch.

Asymmetrische Verfahren — RSA und Diffie-Hellman#

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

Kernpunkte

Asymmetrische Verfahren verwenden ein Schlüsselpaar: öffentlicher Schlüssel (verschlüsseln/verifizieren) und privater Schlüssel (entschlüsseln/signieren).
RSA (Rivest, Shamir, Adleman 1977): Sicherheit beruht auf Schwierigkeit der Faktorisierung großer Zahlen n = p·q.
Schlüsselerzeugung: 1) Primzahlen p, q wählen, 2) n = p·q, φ(n) = (p−1)(q−1), 3) e mit ggT(e, φ(n)) = 1, 4) d mit e·d ≡ 1 mod φ(n).
Verschlüsselung c ≡ mᵉ mod n; Entschlüsselung m ≡ cᵈ mod n. Korrektheit folgt aus Satz von Euler.
Diffie-Hellman-Schlüsseltausch: Alice und Bob einigen sich öffentlich auf gemeinsamen Schlüssel, ohne ihn zu übertragen — Sicherheit beruht auf diskretem Logarithmus.
Praktisch: RSA mit ≥ 2048 Bit; für kleine Schulbeispiele p, q ≤ 13 mit kleinen Primzahlen rechnen.
Querverweis: Die Sicherheit von RSA setzt voraus, dass die Faktorisierung kein effizientes Verfahren besitzt — ein hypothetischer Beweis P = NP (Topic Theoretische Informatik) würde das Verfahren gefährden.

RSA-SCHLÜSSELERZEUGUNG

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

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

RSA-VER- UND ENTSCHLÜSSELUNG

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

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

RSA-SCHLÜSSELPAAR — VERSCHLÜSSELUNG UND ENTSCHLÜSSELUNG

Welche drei Beschriftungen in "RSA-Schlüsselpaar — Verschlüsselung und Entschlüsselung" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

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

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)` — typischer Rechenfehler.
Primzahlpaar nicht teilerfremd zu e gewählt → kein Inverses.
Vertraulichkeit und Authentizität bei RSA verwechselt — Verschlüsselung mit Empfänger-PubKey, Signatur mit Sender-PrivKey.

LK-Vertiefung

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

Hashfunktionen, MACs und digitale Signaturen#

StandardNRW-IF6BY-Inf-7

Kernpunkte

Eine kryptografische Hashfunktion H: {0,1}* → {0,1}ⁿ ist Einweg, kollisionsresistent und deterministisch — Beispiele SHA-256, SHA-3.
Eigenschaften: Pre-Image-Resistenz, 2nd-Pre-Image-Resistenz, Kollisionsresistenz; MD5 und SHA-1 gelten als gebrochen.
HMAC (Hash-based Message Authentication Code) kombiniert Hash mit geheimem Schlüssel — schützt Integrität und Authentizität.
Digitale Signatur: Hash der Nachricht wird mit Sender-PrivKey verschlüsselt; Empfänger verifiziert mit Sender-PubKey.
Hashfunktionen werden auch für Passwortspeicherung verwendet — mit Salt und langsamer KDF (bcrypt, Argon2, PBKDF2) gegen Rainbow-Table-Angriffe.
Anwendungsbereiche: Git-Commits, Blockchain (Hash-Verkettung), Code-Signaturen, Zertifikate.

Typische Fehler

Verschlüsselung und Hash vermischt — Hash ist nicht umkehrbar.
Salt vergessen → Rainbow-Table-Angriff möglich.
Signatur mit Empfänger-PrivKey beschrieben — falsch, Sender-PrivKey.

Codierung und Informationstheorie — Shannon und Huffman#

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

Kernpunkte

Shannon-Entropie H(X) = −Σ pᵢ log₂ pᵢ misst den mittleren Informationsgehalt einer Quelle in Bit pro Symbol.
Untere Schranke der verlustfreien Kompression: keine Codierung kommt unter H(X) Bit/Symbol.
Präfixcode: kein Codewort ist Präfix eines anderen — eindeutig dekodierbar ohne Trennzeichen.
Huffman-Codierung (1952): konstruiert optimalen Präfixcode bottom-up aus den Symbolwahrscheinlichkeiten; mittlere Codelänge L̄ erfüllt H(X) ≤ L̄ < H(X) + 1.
Algorithmus: in jeder Runde die zwei kleinsten Wahrscheinlichkeiten zu einem neuen Knoten zusammenfassen, bis ein Baum entsteht.
Anwendung: ZIP/Deflate (mit LZ77 kombiniert), JPEG, MP3 (in spezifischen Stufen), Hardware-Codecs.

SHANNON-ENTROPIE

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

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

MITTLERE CODEWORTLÄNGE

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

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

HUFFMAN-BAUM FÜR {A:0,4 · B:0,3 · C:0,2 · D:0,1}

Welche drei Beschriftungen in "Huffman-Baum für {A:0,4 · B:0,3 · C:0,2 · D:0,1}" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Bottom-up zusammengefasste Wahrscheinlichkeiten; linke Kante 0, rechte Kante 1 liefert den Präfixcode.

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.
Beim Huffman-Baum die kleinsten Wahrscheinlichkeiten falsch zusammengefasst.
„Optimaler" Code = kürzeste Codewörter — tatsächlich kürzeste mittlere Codelänge.

Schlüsseltausch, PKI und Zertifikate#

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

Kernpunkte

Das Schlüsselaustauschproblem symmetrischer Verfahren: Wie vereinbaren zwei Parteien einen geheimen Schlüssel über einen unsicheren Kanal?
Diffie-Hellman löst dies: aus öffentlichen Werten g, p, A, B berechnen beide denselben Schlüssel g^(ab) mod p, ohne ihn zu übertragen — Sicherheit beruht auf dem diskreten Logarithmus.
Hybride Verschlüsselung kombiniert asymmetrisch (Schlüsseltausch) und symmetrisch (Massendaten): RSA/DH transportiert einen AES-Sitzungsschlüssel, AES verschlüsselt dann effizient.
Eine Public-Key-Infrastruktur (PKI) bindet öffentliche Schlüssel an Identitäten über Zertifikate (X.509), die von einer Zertifizierungsstelle (CA) signiert werden.
Vertrauensketten: ein Wurzelzertifikat (im Betriebssystem/Browser vorinstalliert) signiert Zwischenzertifikate, die wiederum Server-Zertifikate signieren — Validierung entlang der Kette.
Bedrohung Man-in-the-Middle: ungeschützter DH ist anfällig; erst die Authentifizierung über Zertifikate (im TLS-Handshake) bindet den Schlüssel an die echte Gegenstelle.

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.

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üsselaustausch.
Den geheimen Exponenten a/b für öffentlich gehalten — nur g, p, A, B sind öffentlich.
PKI-Vertrauen als „Browser vertraut jedem" missverstanden — nur Ketten zu hinterlegten Wurzeln gelten.
MitM-Anfälligkeit von unauthentifiziertem DH übersehen.

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).

Zahlensysteme und Datenrepräsentation#

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

Kernpunkte

Stellenwertsysteme: Dual (Basis 2), Oktal (8), Dezimal (10), Hexadezimal (16); Umrechnung über fortlaufende Division (Dezimal → Basis) bzw. Wertigkeitssumme.
Eine Hex-Ziffer fasst vier Bit zusammen (0xB = 1011) — kompakte Schreibweise für Bytes (zwei Hex-Ziffern = 8 Bit).
Zweierkomplement stellt negative Ganzzahlen dar: Bits invertieren und 1 addieren; das höchste Bit hat die Wertigkeit −2^(n−1). Vorteil: Addition funktioniert ohne Sonderbehandlung des Vorzeichens.
Wertebereich n-Bit-Zweierkomplement: −2^(n−1) bis 2^(n−1) − 1; Überlauf entsteht, wenn das Ergebnis außerhalb liegt.
Gleitkommazahlen nach IEEE 754: Vorzeichen, Exponent (mit Bias) und Mantisse; endliche Genauigkeit verursacht Rundungsfehler (0,1 ist binär nicht exakt darstellbar).
Zeichencodierung: ASCII (7 Bit), Latin-1 (8 Bit), Unicode mit der Kodierung UTF-8 (variable Länge 1–4 Byte, ASCII-kompatibel) für internationale Texte.

IEEE-754-GLEITKOMMAZAHL

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

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).
Gleitkommazahlen als exakt angenommen — Rundungsfehler bei Vergleichen mit `==` ignoriert.
UTF-8 und Unicode gleichgesetzt — Unicode ist der Zeichensatz, UTF-8 eine 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.

Wird geladen

EuraStudy

Dein Lernraum wird vorbereitet — Curriculum, Notizen und KI verbinden sich.

Kryptographie, Codierung und IT-Sicherheit

6Abschnitteca. 12Min Lesezeit3Kompetenzen

Operatoren:analysieren · berechnen · beurteilen · erläutern · darstellen

grundlegendes Niveau

gA: Caesar- und Vigenère-Chiffre als symmetrische Verfahren, Prinzip öffentlicher Schlüssel, Hash zur Integritätsprüfung.

erhöhtes Niveau

eA: RSA mit kleinen Primzahlen vollständig durchrechnen (Schlüsselerzeugung, Ver- und Entschlüsselung), Diffie-Hellman, digitale Signaturen, Huffman-Codierung.

Symmetrische Verfahren — Caesar, Vigenère, AES#

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

Kernpunkte

Symmetrische Verfahren nutzen denselben geheimen Schlüssel für Ver- und Entschlüsselung; Schlüssel muss sicher ausgetauscht werden.
Caesar-Chiffre: Verschiebung jedes Buchstabens um k Positionen — historisch, kryptografisch trivial (Schlüsselraum nur 25).
Vigenère-Chiffre: Caesar mit periodischem Schlüsselwort — bis 19. Jh. „unbrechbar", bricht durch Friedman/Kasiski-Test.
One-Time-Pad: Schlüssel so lang wie Klartext, einmalig — beweisbar sicher (Shannon 1949), praktisch unhandlich.
AES (Advanced Encryption Standard, Rijndael, 2001): Block-Chiffre mit 128/192/256-Bit-Schlüsseln; Standard für TLS, Festplattenverschlüsselung.
Betriebsmodi: ECB (unsicher, gleiche Blöcke → gleicher Cipher), CBC (Verkettung), CTR (Zählermodus, parallelisierbar), GCM (auth. encryption).

Typische Fehler

Vigenère als „polyalphabetisch unbrechbar" — falsch, Kasiski-Test bricht bei langem Klartext.
One-Time-Pad bei Schlüsselwiederverwendung als sicher angegeben — bei Wiederverwendung trivial brechbar.
AES als asymmetrisch klassifiziert — ist symmetrisch.

Asymmetrische Verfahren — RSA und Diffie-Hellman#

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

Kernpunkte

Asymmetrische Verfahren verwenden ein Schlüsselpaar: öffentlicher Schlüssel (verschlüsseln/verifizieren) und privater Schlüssel (entschlüsseln/signieren).
RSA (Rivest, Shamir, Adleman 1977): Sicherheit beruht auf Schwierigkeit der Faktorisierung großer Zahlen n = p·q.
Schlüsselerzeugung: 1) Primzahlen p, q wählen, 2) n = p·q, φ(n) = (p−1)(q−1), 3) e mit ggT(e, φ(n)) = 1, 4) d mit e·d ≡ 1 mod φ(n).
Verschlüsselung c ≡ mᵉ mod n; Entschlüsselung m ≡ cᵈ mod n. Korrektheit folgt aus Satz von Euler.
Diffie-Hellman-Schlüsseltausch: Alice und Bob einigen sich öffentlich auf gemeinsamen Schlüssel, ohne ihn zu übertragen — Sicherheit beruht auf diskretem Logarithmus.
Praktisch: RSA mit ≥ 2048 Bit; für kleine Schulbeispiele p, q ≤ 13 mit kleinen Primzahlen rechnen.
Querverweis: Die Sicherheit von RSA setzt voraus, dass die Faktorisierung kein effizientes Verfahren besitzt — ein hypothetischer Beweis P = NP (Topic Theoretische Informatik) würde das Verfahren gefährden.

RSA-SCHLÜSSELERZEUGUNG

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

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

RSA-VER- UND ENTSCHLÜSSELUNG

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

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

RSA-SCHLÜSSELPAAR — VERSCHLÜSSELUNG UND ENTSCHLÜSSELUNG

Welche drei Beschriftungen in "RSA-Schlüsselpaar — Verschlüsselung und Entschlüsselung" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

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

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)` — typischer Rechenfehler.
Primzahlpaar nicht teilerfremd zu e gewählt → kein Inverses.
Vertraulichkeit und Authentizität bei RSA verwechselt — Verschlüsselung mit Empfänger-PubKey, Signatur mit Sender-PrivKey.

LK-Vertiefung

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

Hashfunktionen, MACs und digitale Signaturen#

StandardNRW-IF6BY-Inf-7

Kernpunkte

Eine kryptografische Hashfunktion H: {0,1}* → {0,1}ⁿ ist Einweg, kollisionsresistent und deterministisch — Beispiele SHA-256, SHA-3.
Eigenschaften: Pre-Image-Resistenz, 2nd-Pre-Image-Resistenz, Kollisionsresistenz; MD5 und SHA-1 gelten als gebrochen.
HMAC (Hash-based Message Authentication Code) kombiniert Hash mit geheimem Schlüssel — schützt Integrität und Authentizität.
Digitale Signatur: Hash der Nachricht wird mit Sender-PrivKey verschlüsselt; Empfänger verifiziert mit Sender-PubKey.
Hashfunktionen werden auch für Passwortspeicherung verwendet — mit Salt und langsamer KDF (bcrypt, Argon2, PBKDF2) gegen Rainbow-Table-Angriffe.
Anwendungsbereiche: Git-Commits, Blockchain (Hash-Verkettung), Code-Signaturen, Zertifikate.

Typische Fehler

Verschlüsselung und Hash vermischt — Hash ist nicht umkehrbar.
Salt vergessen → Rainbow-Table-Angriff möglich.
Signatur mit Empfänger-PrivKey beschrieben — falsch, Sender-PrivKey.

Codierung und Informationstheorie — Shannon und Huffman#

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

Kernpunkte

Shannon-Entropie H(X) = −Σ pᵢ log₂ pᵢ misst den mittleren Informationsgehalt einer Quelle in Bit pro Symbol.
Untere Schranke der verlustfreien Kompression: keine Codierung kommt unter H(X) Bit/Symbol.
Präfixcode: kein Codewort ist Präfix eines anderen — eindeutig dekodierbar ohne Trennzeichen.
Huffman-Codierung (1952): konstruiert optimalen Präfixcode bottom-up aus den Symbolwahrscheinlichkeiten; mittlere Codelänge L̄ erfüllt H(X) ≤ L̄ < H(X) + 1.
Algorithmus: in jeder Runde die zwei kleinsten Wahrscheinlichkeiten zu einem neuen Knoten zusammenfassen, bis ein Baum entsteht.
Anwendung: ZIP/Deflate (mit LZ77 kombiniert), JPEG, MP3 (in spezifischen Stufen), Hardware-Codecs.

SHANNON-ENTROPIE

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

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

MITTLERE CODEWORTLÄNGE

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

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

HUFFMAN-BAUM FÜR {A:0,4 · B:0,3 · C:0,2 · D:0,1}

Welche drei Beschriftungen in "Huffman-Baum für {A:0,4 · B:0,3 · C:0,2 · D:0,1}" sind prüfungsrelevant?

Folgeaufgabe: Skizziere dasselbe Schema ohne Beschriftungen und ergänze sie aus dem Gedächtnis.

Bottom-up zusammengefasste Wahrscheinlichkeiten; linke Kante 0, rechte Kante 1 liefert den Präfixcode.

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.
Beim Huffman-Baum die kleinsten Wahrscheinlichkeiten falsch zusammengefasst.
„Optimaler" Code = kürzeste Codewörter — tatsächlich kürzeste mittlere Codelänge.

Schlüsseltausch, PKI und Zertifikate#

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

Kernpunkte

Das Schlüsselaustauschproblem symmetrischer Verfahren: Wie vereinbaren zwei Parteien einen geheimen Schlüssel über einen unsicheren Kanal?
Diffie-Hellman löst dies: aus öffentlichen Werten g, p, A, B berechnen beide denselben Schlüssel g^(ab) mod p, ohne ihn zu übertragen — Sicherheit beruht auf dem diskreten Logarithmus.
Hybride Verschlüsselung kombiniert asymmetrisch (Schlüsseltausch) und symmetrisch (Massendaten): RSA/DH transportiert einen AES-Sitzungsschlüssel, AES verschlüsselt dann effizient.
Eine Public-Key-Infrastruktur (PKI) bindet öffentliche Schlüssel an Identitäten über Zertifikate (X.509), die von einer Zertifizierungsstelle (CA) signiert werden.
Vertrauensketten: ein Wurzelzertifikat (im Betriebssystem/Browser vorinstalliert) signiert Zwischenzertifikate, die wiederum Server-Zertifikate signieren — Validierung entlang der Kette.
Bedrohung Man-in-the-Middle: ungeschützter DH ist anfällig; erst die Authentifizierung über Zertifikate (im TLS-Handshake) bindet den Schlüssel an die echte Gegenstelle.

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.

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üsselaustausch.
Den geheimen Exponenten a/b für öffentlich gehalten — nur g, p, A, B sind öffentlich.
PKI-Vertrauen als „Browser vertraut jedem" missverstanden — nur Ketten zu hinterlegten Wurzeln gelten.
MitM-Anfälligkeit von unauthentifiziertem DH übersehen.

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).

Zahlensysteme und Datenrepräsentation#

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

Kernpunkte

Stellenwertsysteme: Dual (Basis 2), Oktal (8), Dezimal (10), Hexadezimal (16); Umrechnung über fortlaufende Division (Dezimal → Basis) bzw. Wertigkeitssumme.
Eine Hex-Ziffer fasst vier Bit zusammen (0xB = 1011) — kompakte Schreibweise für Bytes (zwei Hex-Ziffern = 8 Bit).
Zweierkomplement stellt negative Ganzzahlen dar: Bits invertieren und 1 addieren; das höchste Bit hat die Wertigkeit −2^(n−1). Vorteil: Addition funktioniert ohne Sonderbehandlung des Vorzeichens.
Wertebereich n-Bit-Zweierkomplement: −2^(n−1) bis 2^(n−1) − 1; Überlauf entsteht, wenn das Ergebnis außerhalb liegt.
Gleitkommazahlen nach IEEE 754: Vorzeichen, Exponent (mit Bias) und Mantisse; endliche Genauigkeit verursacht Rundungsfehler (0,1 ist binär nicht exakt darstellbar).
Zeichencodierung: ASCII (7 Bit), Latin-1 (8 Bit), Unicode mit der Kodierung UTF-8 (variable Länge 1–4 Byte, ASCII-kompatibel) für internationale Texte.

IEEE-754-GLEITKOMMAZAHL

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

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).
Gleitkommazahlen als exakt angenommen — Rundungsfehler bei Vergleichen mit `==` ignoriert.
UTF-8 und Unicode gleichgesetzt — Unicode ist der Zeichensatz, UTF-8 eine 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.