Cryptography Reference
In-Depth Information
Um den Satz zu beweisen, benutzten wir ein Hybridargument (vgl. auch die Bemer-
kungen am Ende von Abschnitt 5.5.2), um den Vorteil von
A
in Beziehung setzen zu
können mit dem Vorteil der zu konstruierenden Angreifer auf die Basisschemen.
Der Chiffretext
(
y
sk
,y
pt
)
,dervon
E
h
ausgegeben wird, enthält sowohl einen Chiffretext
y
sk
vom asymmetrischen Basisschema als auch einen Chiffretext
y
pt
vom symmetrischen
Basisschema und diese beiden Chiffretexte sind durch den Einmalschlüssel in gewisser
Weise verbunden. Im Hybridargument werden wir diese Verbindung »aufbrechen«. Dies
ermöglicht dann eine unabhängige Analyse von Teilproblemen, die sich entweder nur auf
das asymmetrische oder nur auf das symmetrische Schema beziehen. Damit können wir
schließlich den Vorteil von
A
mit dem Vorteil der Angreifer auf die beiden Basisschemen
in Beziehung setzen.
Das Aufbrechen der Verbindung zwischen
y
sk
und
y
pt
ist recht einfach. Statt mit
E
a
den Einmalschlüssel
k
s
zu verschlüsseln, wird einfach ein anderer zufällig gewählter
symmetrischer Schlüssel verschlüsselt. Der Klartext
x
wird aber weiterhin mit
k
s
ver-
schlüsselt. Die Idee ist, dass ein Angreifer nicht unterscheiden können sollte, ob diese
»aufgebrochene« hybride Verschlüsselung gewählt wird oder die eigentliche hybride Ver-
schlüsselung: Ist das asymmetrische Kryptoschema sicher, so sollte der Einmalschlüssel
ja geheim bleiben. Aber dann sollte man ihn auch unbemerkt durch einen anderen zu-
fällig gewählten Schlüssel austauschen können. Natürlich muss auch das symmetrische
Kryptoschema sicher sein, damit der eigentliche Klartext geheim bleibt.
Die »aufgebrochene« hybride Verschlüsselung definieren wir als Variante
E
h
von
E
h
.
Genauer enthält
E
h
einen Schalter
i ∈{
0
,
1
}
, der es erlaubt, zwischen
E
h
und der aufge-
brochenen hybriden Verschlüsselung wechseln zu können. Für
i
=0
stimmt
E
h
mit
E
h
überein und für
i
=1
entspricht
E
h
der aufgebrochenen hybriden Verschlüsselung:
E
h
(
x, k
)
1.
Bestimme zwei zufällige symmetrische Schlüssel.
k
0
=
flip
(
K
s
)
;
k
1
=
flip
(
K
s
)
2.
Bestimme, welcher dieser Schlüssel mit
E
a
verschlüsselt werden soll.
i
=
flip
()
3.
Berechne asymmetrische und symmetrische Chiffretexte.
y
sk
=
E
a
(
k
i
,k
)
y
pt
=
E
s
(
x, k
0
)
4.
Gib beide Chiffretexte aus.
gib
(
y
sk
,y
pt
)
zurück
Es bezeichne
H
das Schema, dass man erhält, wenn man in
H
den Chiffrieralgorith-
mus
E
h
durch
E
h
H
ersetzt. Man beachte, dass
mit
H
übereinstimmt, wenn
i
auf
0
H
kein Kryptoschema, da für
i
=1
die korrekte
Entschlüsselung nicht gewährleistet ist. Dies ist aber kein Problem, da wir
gesetzt wird. Streng genommen ist
H
nicht für
die Entschlüsselung einsetzen werden.
Es sei
S
H
A
S
=
H
. Offensichtlich stimmt
S
das verkürzte Experiment zu
A
und
i
=
S
A
S
b
=0
,i
=0
S
A
b
=0
0
mit
überein und somit stimmt auch
mit
überein;
S
S
analog für
b
=1
. Wir kürzen im Folgenden
b
=1
,i
=0
mit
1
,
0
ab; analog für
die anderen Werte von
b
und
i
. Wir können den Vorteil von
A
bzgl.
H
nun wie folgt
