Übung_04

TECHNISCHE UNIVERSITÄT DARMSTADT
FACHGEBIET THEORETISCHE INFORMATIK
PROF. JOHANNES BUCHMANN
DR. JULIANE KRÄMER
Einführung in die
Kryptographie
WS 2015/ 2016
4. Übungsblatt — 05.11.2015
Ankündigung
-
P1 Perfekte Geheimhaltung
Beweisen Sie folgenden Satz. (Tipp: Verwenden Sie den Satz von Bayes.)
Ein Kryptosystem ist genau dann perfekt geheim (auch: perfekt sicher, engl. perfectly secure), wenn für alle Paare (P0 , P1 )
von Klartexten und für alle Schlüsseltexte C gilt:
Pr(C | P0 ) = Pr(C | P1 ), wenn also die Wahrscheinlichkeit dafür, dass beim Verschlüsseln ein Chiffretext C ensteht unabhängig vom verschlüsselten Klartext ist.
P2 Perfekte Geheimhaltung
Betrachte das folgende simple Verschlüsselungssystem. Der Klartextraum ist P = Z2 und die Verteilung darauf ist definiert
durch Pr(0) = 14 und Pr(1) = 34 . Der Schlüsselraum ist K = {A, B} und die Verteilung der Schlüssel ist gegeben durch
Pr(A) = 41 und Pr(B) = 34 . Der Chiffretextraum ist C = {a, b}. Die Verschlüsselungsfunktion ist gegeben durch
Enc(A, 0) = a, Enc(A, 1) = b, Enc(B, 0) = b, Enc(B, 1) = a.
Ist das angegebene Verschlüsselungssystem perfekt sicher?
P3 Perfekte Geheimhaltung
Die Hill-Chiffre ist ein Kryptosystem (P, C, K, Enc, Dec) mit folgenden Eigenschaften:
• P = C = Σn , wobei Σ = Zm mit m, n ∈ N und m, n ≥ 2,
• K besteht aus einer Teilmenge aller modulo m invertierbaren (n × n)-Matrizen über Σ,
• Enc = {EA : A ∈ K}, wobei EA : P → C, x 7→ Ax mod m,
• Dec = {DA : A ∈ K}, wobei DA : C → P, x 7→ A−1 x mod m.
Untersuchen Sie, ob dieses Kryptosystem perfekte Geheimhaltung bieten kann.
P4 Vernams One-Time-Pad
Alice verwendet Vernams One-Time-Pad (OTP) zur Verschlüsselung und stellt Folgendes fest: Wenn sie als Schlüssel den
String verwendet, der nur aus Nullen besteht, wird die Nachricht auf sich selbst verschlüsselt. Deswegen modifiziert sie
den KeyGen Algorithmus, so dass dieser gleichverteilt aus allen Schlüsseln außer dem Null-String wählt.
Hat Alice damit die perfekte Geheimhaltung des One-Time-Pads kompromittiert? Falls ja, verdeutliche dies durch einen
möglichen Angriff. Falls nein, zeige, dass die modifizierte Version immer noch perfekte Geheimhaltung bietet.
1
P5 Vernams One-Time-Pad
Bei der Verschlüsselung mit dem One-Time-Pad entsteht bei der Verschlüsselung des Schlüssels selbst immer der NullString als Chiffretext. Wenn ein Angreifer den Null-String als Chiffretext beobachtet, kann er sich also sicher sein, dass
der geheime Schlüssel verschlüsselt wurde. Erkläre, warum das kein Widerspruch zur perfekten Sicherheit des One-TimePads ist.
H1 Perfekte Geheimhaltung
Zeige, dass es für ein Verschlüsselungsverfahren mit perfekter Geheimhaltung notwendig ist, dass der Schlüsselraum
mindestens so gross ist wie der Klartextraum. Es ist also zu seigen, dass für den Klartextraum P und den Schlüsselraum
K gilt: |K| ≥ |P|.
H2 Vernams One-Time-Pad
(a) Wir verändern das Vernam-OTP, so dass wir jeden Schlüssel mehrfach verwenden können. Bleibt das System perfekt
geheim?
(b) Betrachten Sie das Vernam-OTP mit binären Nachrichten der Blocklänge 3. Wie groß ist der Schlüsselraum? Ist
vollständige Suche (engl. brute force) eine Bedrohung für die Sicherheit des Verfahrens?
(c) Kann man gegen das Vernam-OTP mit einem known-/chosen-Plaintext-Angriff erfolgreich sein?
2

Download Report