Cryptography Reference
In-Depth Information
- Der Signieralgorithmus
T
ist wie folgt definiert:
T
(
x,
(
k
h
, k
)) =
T
(
p
(
h
k
h
(
x
))
, k
)
X
und
(
k
h
, k
)
K
priv
.
für alle
x
∈
∈
- Der Validierungsalgorithmus
V
ist gegeben durch:
V
(
x, t,
(
k
h
,k
)) =
V
(
p
(
h
k
h
(
x
))
,t,k
)
X
,
t
}
∗
und
für alle
x
∈
∈{
0
,
1
K
pub
.
(
k
h
,k
)
∈
Das Schema HashSign
[
H ,p,S
]
wird
Hash-then-Sign-Schema
mit Basis-Signierschema
S
, Füllfunktion
p
und Hashfamilie
H
genannt.
Wir wollen nun analog zum Hash-then-MAC-Ansatz die Sicherheit eines Hash-then-
Sign-Schemas auf die Sicherheit seiner Bestandteile zurückführen, d. h., auf die Sicherheit
des Basis-Signierschemas und die Sicherheit der Hashfamilie.
Für die Definition der Sicherheit des Basis-Signierschemas greifen wir einfach auf die
Definitionen aus Abschnitt 10.1 zurück. Für die Hashfunktionen benötigen wir die (star-
ke) Kollisionsresistenz gemäß Abschnitt 8.2. Schwache Kollisionsresistenz wie für den
Hash-then-MAC-Ansatz reicht leider nicht, da, wie bereits erwähnt, dem Fälscher durch
den öffentlichen Schlüssel bekannt ist, welche Hashfunktion verwendet wird.
Es sei nun
S
=
HashSign
[
]=(
X
,K
,G
,T
,V
)
das gemäß Definition 10.3.1
H
,p,
S
durch
H
=
{
h
k
}
k∈K
H
,
p
und
S
=(
X,K
S
,G,T,V
)
induzierte Signierschema. Für den
S
nehmen wir, wie üblich, an, dass wir einen (guten) Fälscher
Beweis der Sicherheit von
F
für
S
gegeben haben und benutzen diesen Fälscher, um einen guten Fälscher
F
auf
S
zu konstruieren. Die Konstruktionen und
Beweise sind dabei fast identisch zu denjenigen im Fall des Hash-then-MAC-Ansatzes.
Wir werden deshalb die Konstruktionen ohne große Erläuterungen und ohne Beweise
angeben. Wie immer wird unser Ziel sein, den Vorteil von
F
durch denjenigen von
F
(adv
Sig
(
F,S
)
)und
C
(adv
Coll
(
C,H
)
) zu beschränken.
Der Fälscher
F
ist wie folgt definiert:
und einen guten Kollisionsfinder
C
auf
H
r
l
,k
r
}
∗
F
(
s
:
{
0
,
1
}
→{
0
,
1
}
∈
K
pub
):
{
0
,
1
}
×{
0
,
1
1.
Wähle Hashfunktion
k
h
=
flip
(
K
H
)
2.
Simuliere
F
.
F
mit dem öffentlichen Schlüssel
(
k
h
,k
)
und folgenden Änderungen:
a. Eine Anfrage
x
von
F
an das Signierorakel wird wie folgt beantwortet:
1
v
=
h
k
h
(
x
)
x
=
p
(
v
)
Gib
s
(
x
)
zurück an den simulierten Algorithmus
F
b. Wenn
F
das NSP
(
x, t
)
ausgibt, ersetze die Ausgabe wie folgt:
v
=
h
k
h
(
x
)
x
=
p
(
v
)
gib
(
x
,t
)
zurück
F
übergebenen Signierorakel.
1 Dies entspricht genau dem an