Cryptography Reference
In-Depth Information
die Nachricht, mit der
F
das Zufallsorakel aufruft. Damit ist
F
insbesondere
2
-beschränkt,
also
q
=2
(eine Anfrage an das Zufallsorakel durch
F
und eine durch den Validierungs-
algorithmus am Ende des Experimentes
E
S
FDH-RS
F
). Wir nehmen weiter an, dass
F
das
(möglicherweise ungültige) Nachrichten-Signatur-Paar
(
x, s
)
,fürein
s
, ausgibt. Die Nach-
richt, für die
F
versucht, eine Signatur zu fälschen, ist, nach Annahme, also genau dieje-
nige, auf die
F
das Zufallsorakel angewendet hat.
Für einen solchen Fälscher
F
konstruieren wir einen Invertierer
I
wie folgt:
I
((
n, e
)
,y
)):
Simuliere
E
S
FDH-RSA
F
.
E
S
FDH-RS
F
mit folgenden Änderungen:
a. Die Schlüsselgenerierung wird nicht simuliert.
b. Die Anfrage
x
von
F
an das Zufallsorakel wird mit
y
beantwortet.
c. Wenn
F
das Nachrichten-Signatur-Paar
(
x, s
)
ausgibt, dann gib
s
aus und
halte.
Die Idee dieser Konstruktion ist die folgende: Ist das vom (simulierten)
F
im Lauf von
E
E
RS
I
ausgegebene Nachrichten-Signatur-Paar
(
x, s
)
gültig, dann gilt
s
=(
H
(
x
))
d
mod
n
nach Definition von
S
FDH-RSA
. Da, nach Definition von
I
, H
(
x
)=
y
gilt, ist
s
genau das
Urbild von
y
. Mit anderen Worten: Ist
F
erfolgreich, so auch
I
.
Um dies zu beweisen, vergleichen wir zunächst
E
S
FDH-RSA
F
E
E
RSA
I
und
. Um den Vergleich
zu vereinfachen, stellen wir diese Experimente im Folgenden dar:
E
S
FDH-RS
F
:
{
0
,
1
}
1.
Schlüsselgenerierung
((
n, e
)
,
(
n, d
)) =
G
()
2.
Berechnung eines Nachrichten-Signatur-Paares
(
x, s
)=
F
(
H
(
)
d
mod
n,
(
n, e
))
·
3.
Auswertung
falls H
(
x
)=
s
e
mod
n
gilt und
F
das Signierorakel niemals mit
x
aufgerufen
hat, dann gib
1
, sonst
0
zurück.
E
E
RSA
I
:
{
0
,
1
}
1.
Parametergenerierung
((
n, e
)
,
(
n, d
)) =
G
()
2.
Nachrichtenwahl
x
=
flip
(
Z
n
)
,
y
=
x
e
mod
n
3.
Ratephase
s
=
I
((
n, e
)
,y
)
4.
Auswertung
falls
s
e
mod
n
=
y
,sogib
1
, sonst
0
zurück
E
S
FDH-RSA
F
Die Schlüsselgenerierung von
,die
I
nicht simuliert, entspricht genau der Pa-
E
S
FDH-RSA
F
durch das Zufallsorakel mit einem zufällig gewählten Element aus
Z
n
beantwortet. In
E
E
RSA
I
rametergenerierung in
. Die Anfrage
x
von
F
an das Zufallsorakel wird in
