close

Anmelden

Neues Passwort anfordern?

Anmeldung mit OpenID

8 Folien/Blatt

EinbettenHerunterladen
¨
Kryptographie I - Ubung
4
1/8
¨
Kryptographie I - Ubung
4
2/8
Shannon-Informationstheorie
Grundlage: CTO-Szenario, d.h. Angreifer
Charlie
kennt die Definition der Chiffre
x ∈ Σn
beobachtet Kryptogramm y ∈ C
Kryptographie I (FSS 09)
¨
Ubung
4
Alice
will zugeh¨
origen Klartext bestimmen
E
y ∈ Σn
k
D
x
k
Bob
Schl¨
usselquelle
Wir modellieren Klartext, Chiffretext bzw. Schl¨
ussel als Zufallsvariablen
X , Y bzw. K .
Zus¨atzliche Annahmen:
Schl¨
usselmenge K endlich und alle Schl¨
ussel gleich wahrscheinlich,
1
d.h. Pr[K = k] = |K|
24. M¨arz 2009
X und K unabh¨angig, d.h.
Pr[X = x, K = k] = Pr[X = x] · Pr[K = k]
Angreifer kennt Pr[X = x] und Pr[K = k] f¨
ur alle x ∈ P und alle
k ∈ K.
¨
Kryptographie I - Ubung
4
3/8
¨
Kryptographie I - Ubung
4
4/8
Wie n¨utzlich ist das berechnete x ∗ ?
Bayes-Entscheidung
Wir betrachten zwei Extremf¨alle:
Charlie
1
x ∈ Σn
y ∈ Σn
E
Alice
k
D
Pr[X = x|Y = y ] ist Punktverteilung, d.h.
x
Pr[X = x|Y = y ] =
Bob
k
Schl¨
usselquelle
2
f¨
ur ein x ∈ P
X , Y unabh¨angig, d.h.
Pr[X = x|Y = y ] = Pr[X = x] f¨
ur alle x ∈ P
Pr[X = x ∗ |Y = y ] = max Pr[X = x|Y = y ] .
x∈P
⇒ y liefert keine Information u
¨ber den gesuchten Klartext.
Chiffren mit dieser Eigenschaft heißen perfekt.
Wir wissen aus der Vorlesung:
Pr[X = x ] · |{k ∈ K : Ek (x ) = y }|
,
Pr[X = x] · |{k ∈ K : Ek (x) = y }|
Beispiel f¨
ur eine perfekte Chiffre: Vernam-Chiffre
x∈P
d.h. ein Angreifer mit unbeschr¨ankter Berechnungskraft kann
berechnen.
falls x = x
falls x = x
⇒ Gesuchter Klartext ist eindeutig bestimmt.
Beste Angreiferstrategie: Bayes-Entscheidung, d.h. bestimme
x ∗ ∈ P mit
Pr[X = x |Y = y ] =
1
0
Insgesamt: Je n¨aher Pr[X = x|Y = y ] an einer Punktverteilung ist,
desto besser f¨
ur den Angreifer.
x∗
¨
Kryptographie I - Ubung
4
5/8
Bedingte Entropie
¨
Kryptographie I - Ubung
4
6/8
Perfekte Chiffren in der Praxis
Beobachtung:
F¨
ur Zufallsvariablen X : Ω → A und Y : Ω → B definiere X Y =y als
die durch Y = y bedingte Zufallsvariable X , d.h.
Pr[X Y =y = a] := Pr[X = x|Y = y ] =
Chiffre perfekt ⇒ H(K ) ≥ H(X ) ⇒ Schl¨
ussell¨ange ≥ Textl¨ange
Umgekehrt: Schl¨
ussell¨ange < Textl¨ange ⇒ Chiffre nicht perfekt
Pr[X = x, Y = y ]
.
Pr[Y = y ]
Insbesondere: Chiffren mit konstanter Schl¨
ussell¨ange und beliebiger
Textl¨ange, z.B. praktisch eingesetzte Blockchiffren,
nicht perfekt.
Dann definiert man die bedingte Entropie durch
Pr[Y = y ] · H(X Y =y ) .
H(X |Y ) :=
Wir betrachten f¨
ur die Charakterisierung solcher Chiffren das
folgende Szenario:
y ∈B
Nachrichtenquelle X produziert Nachrichten (Xn )n∈N
beliebiger L¨ange u
¨ber {0, 1}
Schl¨
usselmenge K ⊆ {0, 1}k mit k konstant
Beobachtung: Chiffre perfekt ⇔ H(X |Y ) = H(X )
¨
Kryptographie I - Ubung
4
7/8
Schl¨usselequivokation als Sicherheitsparameter
Wichtiger Sicherheitsparameter: Schl¨
usselequivokation
SE(n) := H(K |Y1 . . . Yn )
Beobachtungen:
H(K ) ≥ SE(n) ≥ 0
H(K ) = SE(n) tritt ein, gdw. K und Y1 . . . Yn unabh¨angig.
Chiffren mit dieser Eigenschaft heißen ideal.
SE(n) ist monoton fallend in n.
F¨
ur Random Ciphers (und damit n¨aherungsweise f¨
ur praktisch
eingesetzte Blockchiffren) gilt
SE(n) ≈ H(K ) − ρ · n
mit ρ ∈ [0, 1] Redundanz der Nachrichtenquelle.
¨
Kryptographie I - Ubung
4
Eindeutigkeit des Schl¨ussels
)
Folgerung: SE(n) ≈ 0 f¨
ur n ≥ nu := H(K
ussel ist ab
ρ , d.h. Schl¨
bestimmter Textl¨ange (Eindeutigkeitspunkt) eindeutig durch
Kryptogramm bestimmt. Dann liefert
K := {}
for all k ∈ K do
if Dk (Y1 . . . Yn ) ∈ S then
K := K ∪ {k}
end if
end for
return K
mit S := {sinnvolle Nachrichten} eine eindeutige L¨
osung.
Satz: Chiffren u
¨ber der bin¨aren symmetrischen Quelle (BSS), d.h.
alle Nachrichten sinnvoll und gleich wahrscheinlich und damit
ρ = 0, sind ideal.
→ Idee: Verringere die Redundanz der Nachrichtenquelle, z.B.
durch Quellencodierung.
8/8
Document
Kategorie
Gesundheitswesen
Seitenansichten
10
Dateigröße
114 KB
Tags
1/--Seiten
melden