Cryptography Reference
In-Depth Information
Algorithmus 10.1 Invertierer im Beweis zu Satz 10.4.1, allgemeiner Fall
I
((
n, e
)
,y
)):
1.
Initialisierung des Zählers für Orakelanfragen
j
=
1
2.
Raten der Anfrage, in der
y
als Hashwert zurückgegeben werden soll.
i
=
flip
(
{
0
,...,q−
2
}
)
3.
Simulation von
−
E
S
FDH-RSA
F
E
S
FDH-RSA
F
mit folgenden Änderungen:
a. Die Schlüsselgenerierung wird nicht simuliert.
b. Jede Anfrage
z
an das Zufallsorakel wird mit h-Sim
(
z
)
(siehe unten) beantwortet.
c. Jede Anfrage
z
an das Signierorakel wird mit s-Sim
(
z
)
(siehe unten) beantwortet.
d. Wenn
F
das Nachrichten-Signatur-Paar
(
x, s
)
, für eine Nachricht
x
und eine
Signatur
s
,ausgibt,danngibt
I
die Signatur
s
aus und hält.
h-Sim
(
x
)
:
1.
Wurde bereits eine Anfrage mit Nachricht
x
an die Orakel geschickt?
r
=min(
{j
+1
}∪{r ≤ j | A
m
[
r
]=
x}
)
2.
Speichere
x
in
A
m
j
=
j
+1
;
A
m
[
j
]=
x
3.
Fallunterscheidung
falls
r
=
j
,so
-
x
ist neu
falls
j
=
i
,so
-
i
-te Anfrage, also wird
y
zurückgeliefert
A
h
[
j
]=
y
sonst
- Bestimme Hashwert und Signatur wie besprochen
A
s
[
j
]=
flip
(
Z
n
)
A
h
[
j
]=(
A
s
[
j
])
e
mod
n
sonst
-
x
wurde bereits angefragt
falls
j
=
i
,so
-
i
-te Anfrage, Hashwert kann man nicht mehr auf
y
setzen
halte mit Ausgabe »Fehler«
sonst
- Setze Werte entsprechend vorheriger Ausgabe
A
s
[
j
]=
A
s
[
r
]
A
h
[
j
]=
A
h
[
r
]
4.
Ausgabe
gib
A
h
[
j
]
zurück
s-Sim
(
x
)
:
1.
Aufruf der Simulation des Zufallsorakels
h-Sim
(
x
)
- Die von h-Sim gelieferte Ausgabe wird verworfen
2.
Fallunterscheidung
falls
j
=
i
,so
halte mit Ausgabe »Fehler«
sonst
gib
A
s
[
j
]
zurück
