Lösung_04

TECHNISCHE UNIVERSITÄT DARMSTADT
Einführung in die
Kryptographie
FACHGEBIET THEORETISCHE INFORMATIK
PROF. JOHANNES BUCHMANN
DR. JULIANE KRÄMER
WS 2015/ 2016
4. Lösungsblatt — 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.
Lösung. Sei das Kryptosystem perfekt geheim. Sei (P0 , P1 ) ein beliebiges Klartextpaar. Wir wenden den Satz von Bayes
an und erhalten
Pr(C | P0 ) =
Pr(P0 ) Pr(C)
Pr(P0 | C) Pr(C)
=
= Pr(C)
Pr(P0 )
Pr(P0 )
und analog Pr(C | P1 ) = Pr(C), also Pr(C | P0 ) = Pr(C | P1 ).
Gelte nun umgekehrt Pr(C | P0 ) = Pr(C | P1 ) für alle Klartextpaare (P0 , P1 ). Dann gilt für alle Klartexte P Pr(C) = Pr(C | P)
und deshalb
Pr(P | C) =
Pr(C | P) Pr(P)
Pr(C) Pr(P)
=
= Pr(P).
Pr(C)
Pr(C)
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?
Lösung. Die Wahrscheinlichkeit dafür, dass der Chiffretext a auftritt, ist
Pr(a) = Pr(0, A) + Pr(1, B) = Pr(0) Pr(A) + Pr(1) Pr(B) =
1
9
5
+
= .
16 16
8
Damit ist
Pr(0 | a) =
Pr(0 ∩ a)
=
Pr(a)
1
4
·
5
8
1
4
=
1
1
6= = Pr(0).
10
4
Also ist das Verschlüsselungssystem nicht perfekt sicher.
1
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.
Lösung. Ob ein Kryptosystem perfekte Geheimhaltung bieten kann, lässt sich mit Hilfe des Satzes von Shannon prüfen.
Betrachten wir zunächst diesen Satz. Dort werden folgende Bedingungen genannt:
• Die Anzahl Klar-, Chiffretexte und Schlüssel muss übereinstimmen. Dies lässt sich dadurch gewährleisten, dass
man eine Teilmenge K0 ⊆ K verwendet, für die |K0 | = |P| gilt,
• Die Bedingung, dass die Schlüssel gleichverteilt gewählt werden, lässt sich realisieren indem jedesmal ein neuer
Schlüssel gleichverteilt gewählt wird.
• Allerdings lässt sich die Forderung
∀p ∈ P ∀c ∈ C ∃1 A ∈ K0 EA(p) = c
0
nicht erfüllen, wie man durch Gegenbeispiele zeigen kann: Für p = c = 0 = ... nämlich genügen alle Matrizen A
0
der Gleichung: EA(p) = Ap = 0 = c , während für p = 0, c 6= 0 keine Matrix die Gleichung erfüllt.
Deshalb kann die Hill-Chiffre nicht perfekte Geheimhaltung bieten.
Alternative
kurze Lösung: Die Definition der perfekten Geheimhaltung (siehe P1) ist für die Klar-/ Schlüsseltexte p =
0
.. nicht gegeben, da p = 0 für jeden Schlüssel auf c = 0 abgebildet wird (und c = 0 eindeutig festlegt, dass
.
der zugehörige Klartext p = 0 war).
c=0=
0
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.
Lösung. Das Verfahren ist dann nicht mehr perfekt sicher, da aus der Tatsache, dass ein Chiffretext C beobachtet wurde,
geschlossen werden kann, dass C nicht die verschlüsselte Nachricht gewesen sein kann. Formeller heißt das, dass für
jeden Klartext P gilt, dass Pr(P | P) = 0 6= Pr(P), ein Widerspruch zur perfekten Geheimhaltung.
Ein möglicher Angriff ist folgender. Angenommen es ist bekannt, dass die selbe Nachricht mehrfach mit verschiedenen
Schlüsseln verschlüsselt wurde. Beobachtet man nun eine Menge an Chiffretexten M , so kann man folgern, dass die
Nachricht in P \ M liegt, wobei P der Klartextraum ist. Jeden neuen Chiffretext den man beobachtet kann man nun als
mögliche Nachricht ausschliessen.
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.
Lösung. Da das für jeden Schlüssel gilt, stellt das kein Problem dar, da man lediglich lernt dass der Schlüssel verschlüsselt
wurde, aber nicht welcher.
2
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|.
Lösung. Da die Verschlüsselungsfunktionen injektiv sind (um wieder korrekt entschlüsseln zu können), gilt für den
Chiffretextraum C, dass |C| ≥ |P|. Angenommen es sei |K| < |P| ≤ |C|. Dann gibt es für alle Klartexte P ∈ P einen
Chiffretext C P ∈ C, sodass für alle Schlüssel K ∈ K gilt, dass EncK (P) 6= C P . (Das sieht man wie folgt ein: Da
|{EncK (P) | K ∈ K}| ≤ |K| < |C|, gilt {EncK (P) | K ∈ K} ( C.) Also gilt Pr(P | C P ) = 0 6= Pr(P), und daher bietet das
Verschlüsselungssystem keine perfekte Geheimhaltung.
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?
Lösung. Nein, die Wahrscheinlichkeitsverteilung bleibt nicht die Gleichverteilung. Die Auswahl eines Schlüssels
hängt von den vorher ausgewählten Schlüsseln ab.
(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?
Lösung.
• | K| = 23 = 8.
• Nein, vollständige Suche ist keine Bedrohung, weil sie alle möglichen Klartexte liefert und die Wahrscheinlichkeitsverteilung auf dem Klartextraum sich nicht ändert.
(c) Kann man gegen das Vernam-OTP mit einem known-/chosen-Plaintext-Angriff erfolgreich sein?
Lösung. Nein, weil jedes mal ein neuer Schlüssel gewählt wird.
3

Download Report