Cryptography Reference
In-Depth Information
E
E
RSA
I
E
E
RSA
I
lautet die Antwort
y
. Diese Antwort ist aber in
auch ein zufällig gewähltes
Z
n
,denn
y
=
x
e
mod
n
für ein zufällig aus
Element aus
Z
n
gewähltes Element
x
und
e
mod
n
ist eine Bijektion auf
·
Z
n
.
Damit ist es leicht, eine Bijektion
β
von der Menge der Läufe von
E
S
FDH-RSA
F
in die
E
E
RSA
I
E
S
FDH-RSA
F
zu definieren:
2
Ist
α
ein Lauf von
Menge der Läufe von
,sowähltman
E
E
RS
I
so, dass
G
()
in
α
die gleichen Zufallsbits verwendet
wie
G
()
in
α
und
F
in
α
die gleichen Zufallsbits verwendet wie
F
in
α
. Liefert in
α
das
Zufallsorakel in der ersten Anfrage die Antwort
h
,fürein
h
den entsprechenden Lauf
α
von
∈
Z
n
, so setzt man in
α
den
Wert für
x
auf
h
d
mod
n
,denndannist
y
=
x
e
mod
n
=
h
.Somitwird
h
(
=
y
)in
α
als Argument an
I
übergeben und nach Definition von
I
wird dieses Argument von
I
als
Antwort des (simulierten) Zufallsorakels zurückgeliefert. Man sieht leicht, dass die gerade
beschriebene Abbildung
β
in der Tat eine Bijektion ist und dass die Wahrscheinlichkeit
für das Auftreten von
α
in
E
S
FDH-RSA
F
gleich der Wahrscheinlichkeit für
α
=
β
(
α
)
in
E
E
RS
I
ist.
Des Weiteren gilt für
α
und
α
Folgendes: Wenn das von
F
in
α
ausgegebene Nach-
richten-Signatur-Paar
(
x, s
)
gültig ist, dann gilt
s
=(
H
(
x
))
d
mod
n
nach Definition von
S
FDH-RSA
,mitH
(
x
)=
h
für ein
h
. Im korrespondierenden Lauf
α
wird
h
als Argument
an
I
übergeben und
I
liefert
s
als Antwort zurück. Somit ist
I
in
α
erfolgreich, da
s
das
Urbild von
y
=
h
ist. Damit erhalten wir sofort:
adv
Sig
(
F,
S
FDH-RSA
)
≤
adv
Inversion
(
I,
E
RSA
)
.
Insbesondere folgt Satz 10.4.1 im betrachteten Spezialfall.
Allgemeiner Fall.
Für den allgemeinen Fall sei nun
F
ein (beliebiger)
q
-beschränkter
Fälscher für
S
FDH-RSA
. Wir werden aber folgende Annahme bzgl.
F
treffen (*): Wenn
F
in einem Lauf von
E
S
FDH-RS
F
ein Nachrichten-Signatur-Paar der Form
(
x, s
)
ausgibt,
dann hat
F
in diesem Lauf zuvor das Zufallsorakel mit
x
angefragt. (Insbesondere muss
für einen solchen Fälscher
q ≥
2
gelten.)
Erfüllt
F
diese Eigenschaft nicht für jeden Lauf, so können wir einen anderen Fäl-
scher
F
betrachten, der
F
simuliert und der, bevor er das von
F
gelieferte Nachrichten-
Signatur-Paar
(
x, s
)
ausgibt (und hält), das Zufallsorakel mit
x
anfragt. Es ist klar, dass
adv
Sig
(
F
,
S
FDH-RSA
)
gilt. Da
Fq
-beschränkt ist, ist
F
(
q
+1)
-
beschränkt. Zudem hat
F
eine lediglich geringfügig größere Laufzeit als
F
. Insgesamt ist
der Ressourcenverbrauch von
F
im Vergleich zu
F
also fast unverändert, was die Annah-
me (*) motiviert. Wir werden aber am Ende des Beweises nochmal auf diese Annahme
zurückkommen, um sie für die Abschätzung (10.4.2) entsprechend zu berücksichtigen,
denn die Abschätzung soll ja für alle
q
-beschränkten Fälscher
F
gelten.
Die Konstruktion des Invertierers
I
für
S
FDH-RSA
)=
adv
Sig
(
F,
E
RSA
aus
F
folgt nun der Idee im Spezialfall:
E
S
FDH-RS
F
. Wir wissen, laut Annahme (*), dass, falls
F
ein
Nachrichten-Signatur-Paar der Form
(
x, s
)
ausgibt,
F
zuvor das Zufallsorakel mit
x
ange-
fragt hat. Für diese Anfrage sollte, wie im Spezialfall, das von
I
simulierte Zufallsorakel
I
simuliert im Wesentlichen
2 Wie üblich fassen wir die Wahrscheinlichkeitsräume zu diesen Experimenten als Produkträume auf
(vgl. Abschnitt 4.6.2). Entsprechend werden Läufe als Tupel repräsentiert.
