Cryptography Reference
In-Depth Information
S
FDH-RSA
ist wie in Abschnitt 10.1 definiert. Allerdings gehen wir
nun davon aus, dass alle beteiligten Algorithmen - der Fälscher
F
, der Signieralgorithmus
T
und der Validierungsalgorithmus
V
- Zugriff auf H haben. Der Wahrscheinlichkeits-
raum des Experimentes
E
S
FDH-RSA
F
Die Sicherheit von
enthält natürlich nun auch die von H verwendeten
Zufallsbits.
10.4.3
Beweisbare Sicherheit des FDH-RSA-Schemas
Wir beweisen nun die Sicherheit des FDH-RSA-Signierschemas unter der RSA-Annahme
(vgl. Annahme 6.4.1), d. h., unter der Annahme, dass RSA eine Familie von Einwegfunk-
tionen mit Hintertür ist.
In der Formulierung des folgenden Satzes verwenden wir den Begriff des
q
-beschränk-
ten Fälschers für das FDH-RSA-Signierschema. Ein Fälscher
F
heißt
q
-beschränkt
,wenn
im Experiment
E
S
FDH-RS
F
insgesamt maximal
q
Anfragen an das Zufallsorakel gestellt
werden. Anfragen an das Signierorakel zählen dabei mit, da jede solche Anfrage auch einer
Anfrage an das Zufallsorakel bedarf. Zudem stellt auch der Validierungsalgorithmus, der
zum Schluss des Experimentes aufgerufen wird, eine Anfrage an das Zufallsorakel. Auch
diese Anfrage wird mitgezählt. Es folgt, dass
F
selbst zusammen maximal
q
−
1
Anfragen
an die Zufalls- und Signierorakel stellen darf.
Satz 10.4.1.
Es seien
l>
0
gerade,
q ≥
1
,und
S
FDH-RSA
das
l
-FDH-RSA-Signier-
schema. Weiter bezeichne
F
einen
q
-beschränkten Fälscher für
S
FDH-RSA
. Dann exis-
tiert ein Invertierer
I
für RSA, interpretiert als Familie
E
RSA
von Einwegfunktionen mit
Hintertür (mit Parameter
l
), so dass
adv
Sig
(
F,S
FDH-RSA
)
≤ q ·
adv
Inversion
(
I,E
RSA
)
(10.4.2)
gilt.
Der Ressourcenverbrauch von
I
im Vergleich zu
F
soll in Aufgabe 10.7.7 genauer un-
tersuchtwerden;erwirdähnlichseinzudemvon
F
. Dieser Satz reduziert damit, in
üblicher Weise, die Sicherheit des FDH-RSA-Signierschemas auf die RSA-Annahme: Gilt
die RSA-Annahme, d. h., ist adv
Inversion
(
I
, E
RSA
)
für alle Invertierer
I
(mit geeigneter
Ressourcenbeschränkung) klein, so muss auch der Vorteil jedes (ähnlich) ressourcenbe-
schränkten Fälschers für das FDH-RSA-Signierschema klein sein. Muss man annehmen,
dass
q
groß ist, so wird man
l
und damit den Modul des
l
-FDH-RSA-Signierschemas
entsprechend groß wählen müssen, damit der durch den Satz garantierte maximale Vor-
teil eines Fälschers für das
l
-FDH-RSA-Signierschema ausreichend klein ist. Eine präzise
Quantifizierung der Sicherheit des FDH-RSA-Signierschemas gemäß Definition 10.1.4 soll,
wie gesagt, in Aufgabe 10.7.7 durchgeführt werden.
Im Rest dieses Unterabschnitts wenden wir uns dem Beweis des Satzes zu. Die prinzi-
pielle Vorgehensweise ist wie üblich: Wir nehmen an, dass wir einen (guten) Fälscher für
S
FDH-RSA
gegeben haben und konstruieren daraus einen (guten) Invertierer für
E
RSA
.
Spezialfall. Zunächst beweisen wir den Satz für einen Spezialfall, den wir später zur
Aussage des Satzes verallgemeinern werden. Im Spezialfall nehmen wir an, dass
F
genau
einmal das Zufallsorakel, aber niemals das Signierorakel aufruft; es bezeichne
x ∈{
0
,
1
}
∗
