Cryptography Reference
In-Depth Information
festlegen wollten, der Hashwert sowie die Signatur zur Anfrage allerdings schon festste-
hen. Der Grund, dass in s-Sim
(
x
)
ein Fehler im Fall
j
=
i
ausgegeben wird, ist, dass für
die
i
-te Anfrage der Hashwert von
I
auf
y
gesetzt wurde, aber keine Signatur festgelegt
wurde. Damit kann
I
die Anfrage von
F
nicht beantworten; die »Hoffnung« von
I
war ja,
dass
F
in diesem Fall selbst eine Signatur und damit das Urbild
y
d
mod
n
zu
y
liefert.
In beiden der gerade besprochenen Fälle hatte der Invertierer also »Pech« bei der Wahl
von
i
.
Wir beweisen nun die im Satz 10.4.1 behauptete Beziehung zwischen dem Vorteil
von
F
und demjenigen von
I
. Dazu bilden wir, ähnlich wie im Beweis des Spezialfalls,
Läufe von
E
E
RS
I
ab. Zur Erinnerung der Definition der beiden
Experimente verweisen wir auf den Spezialfall.
Es sei also
α
ein Lauf von
E
S
FDH-RSA
F
auf Läufe von
E
S
FDH-RSA
F
,sodassindiesemExperiment
1
ausgegeben
wird, d. h.,
E
S
FDH-RSA
F
(
α
)=1
. Wir definieren einen korrespondierenden Lauf
α
von
E
E
RS
I
wie folgt: Der Algorithmus für die Parametergenerierung verwende im Lauf
α
die
gleichen Zufallsbits wie der Algorithmus für die Schlüsselgenerierung in
α
. Es bezeichne
((
n, e
)
,
(
n, d
))
das resultierende Schlüssel/Index-Paar. Es bezeichne
(
x, s
)
das von
F
im
Lauf
α
ausgegebene Nachrichten-Signatur-Paar. Wir nehmen an, dass
F
im Lauf
α
die
Nachricht
x
in der
i
-ten Anfrage, für ein
i
∈{
, an das Zufallsorakel geschickt
hat, wobei
i
minimal gewählt sei. (Nach Annahme (*) existert ein solches
i
.) Wir setzen
in
α
deshalb
i
=
i
. Des Weiteren sei
α
so definiert, dass für die Simulation von
F
(durch
den Invertierer
I
)in
α
die gleichen Zufallsbits verwendet werden, wie
F
in
α
verwendet.
Es bezeichne
h
=
H
(
x
)
den im Lauf
α
gewählten Hashwert für
x
; nach Definition von
i
wird dieser in der
i
-ten Anfrage an das Zufallsorakel gewählt. Analog zum Spezialfall
setzen wir
x
=
h
d
0
,...,q
−
2
}
mod
n
in
α
; dann gilt
y
=
x
e
mod
n
=
h
in
α
.Istin
α
die
j
-te
=
i
, die Nachricht
x
und der zugehörige Hashwert
h
, dann definieren
wir
α
so, dass
A
s
[
j
]=
h
d
Anfrage, für
j
mod
n
gilt, was dann auch
A
h
[
j
]=
A
s
[
j
]
e
mod
n
=
h
impliziert.
Es gilt, dass die Sicht von
F
in
α
und die Sicht des (simulierten) Fälschers
F
in
α
identisch sind, da i) sich nach Konstruktion Schlüssel- und Parametergenerierung in bei-
den Läufen entsprechen und die von
F
verwendeten Zufallsbits ebenfalls in beiden Läufen
gleich sind und ii) alle Orakelanfragen von
F
in beiden Läufen gleich beantwortet werden,
denn: Für die
j
-te Anfrage mit
j<i
(=
i
)
sind die Antworten in beiden Läufen nach Kon-
struktion gleich. Die
j
-te Anfrage für
j
=
i
ist nach Definition von
i
die erste Anfrage
für die Nachricht
x
,wobei
x
die Nachricht ist, die
F
später im Nachrichten-Signatur-Paar
ausgeben wird. Da die Berechnung von
F
im Lauf
α
nach Annahme zulässig ist, ist diese
Anfrage eine Anfrage an das Zufallsorakel, nicht an das Signierorakel. Weil (nach Wahl
von
i
)
x
vorher nicht angefragt wurde, tritt in h-Sim der Fall
r
=
j
auf und es wird
kein Fehler ausgegeben. Nach Konstruktion von
α
und
I
wirddeshalbinbeidenLäufen
derselbe Hashwert, nämlich
h
, zurückgeliefert. Für
j>i
sind nach Konstruktion von
α
und
I
die Antworten auf neue Anfragen sowie alte Anfragen
=
x
wieder in beiden Läufen
gleich. Wegen der Zulässigkeit der Berechnung von
F
wird
x
höchstens als Anfrage an das
Zufallsorakel gestellt, wofür die Antworten aber in beiden Läufen gleich sind, nämlich
h
.
Es folgt, dass auch der simulierte Fälscher
F
in
α
das Nachrichten-Signatur-Paar
(
x, s
)
ausgibt, wenn
F
in
α
dieses Paar ausgibt. Nach Annahme (
E
S
FDH-RSA
F
(
α
)=1
)ist
(
x, s
)