Cryptography Reference
In-Depth Information
den Wert
y
zurückliefern, wobei
y
, wie oben, das Element aus
Z
n
ist, zu dem
I
das
Urbild bestimmen möchte. Wie im Spezialfall gibt
I
die Signatur
s
aus, in der Hoffnung,
dass es das Urbild zu
y
ist. Ist
s
eine gültige Signatur zu
x
, dann ist, wie im Spezialfall,
s
tatsächlich das gesuchte Urbild zu
y
. Es stellen sich nun zwei Fragen:
1. Woher weiß der Invertierer
I
,wanner
y
als Antwort auf eine Anfrage an das Zufalls-
orakel zurückliefern soll? Genauer: Woher weiß
I
, in welcher Anfrage
F
die Nachricht
an das Zufallsorakel schickt, die
F
später im Nachrichten-Signatur-Paar ausgeben
wird? Die Antwort ist einfach: Ohne die Simulation von
F
bis zum Ende durchlau-
fen zu lassen, weiß
I
das nicht. Der Invertierer
I
wird deshalb schlicht am Anfang
desLaufesraten,inwelcherder(maximal)
q −
1
Anfragen von
F
an das von ihm
simulierte Zufallsorakel er
y
als Wert zurückliefern sollte - in der Hoffnung, dass
er richtig liegt. (Man beachte, dass
Fq
-beschränkt ist und deshalb selbst maximal
q −
1
Anfragen an das Zufallsorakel stellt;
I
sollte in einer dieser Anfragen
y
»ein-
schmuggeln«.) Das Raten wird, wie wir sehen werden, die Erfolgwahrscheinlichkeit
von
I
im Vergleich zu
F
um den Faktor
1
/
(
q −
1)
reduzieren.
2. Die zweite Frage ist, wie
E
S
FDH-RS
F
simuliert wird? Dies mag zunächst offensichtlich
erscheinen, ist aber bei genauerem Hinsehen nicht trivial. In der Simulation von
E
S
FDH-RS
F
muss
I
auch das Signierorakel simulieren, dazu bräuchte
I
den Signier-
schlüssel, den
I
aber nicht kennt. Glücklicherweise kann man dieses Problem durch
einen Trick lösen, der darin besteht,
I
das Zufallsorakel geschickt simulieren zu las-
sen: Immer wenn das Zufallsorakel mit einer Nachricht
z
aufgerufen wird (und egal,
ob
z
später signiert werden soll oder nicht, was ohnehin nicht immer klar ist), dann
wählt
I
zunächst einen zufälligen Wert
s
aus
Z
n
. Dieser wird als Signatur für
z
die-
nen, falls für
z
später eine Signatur berechnet werden soll. Als Hashwert für
z
wird
H
(
z
)=
s
e
mod
n
festgelegt. Damit ist
(
z,s
)
ein gültiges Nachrichten-Signatur-Paar,
denn es gilt
s
e
mod
n
=
H
(
z
)
. Man beachte, dass, da
s
zufällig aus
Z
n
gewählt
e
mod
n
eine Bijektion über
Z
n
ist, auch H
(
z
)=
s
e
mod
n
ein zufällig
wurde und
·
Z
n
gewähltes Element ist.
3
aus
Nun fällt es leicht, den Invertierer
I
anzugeben. Wie erwähnt, simuliert
I
das Experiment
E
S
FDH-RS
F
abgesehen von einigen Modifikationen, die für das eigentliche Invertieren zu-
ständig sind. Zur Simulation des Zufallsorakels und des Signierorakels verwendet
I
drei
Felder, bezeichnet mit
A
m
,
A
h
und
A
s
, jeweils der Länge
q
1
.DasFeld
A
m
speichert
die an die Hash- und Signierorakel gesendeten Nachrichten. In
A
h
und
A
s
werden die
zugehörigen Hashwerte bzw. Signaturen abgelegt. Zur Simulation der Orakel selbst ruft
I
die Funktionen h-Sim und s-Sim auf. Der Invertierer samt dieser Funktionen ist in
Algorithmus 10.1 angegeben.
Die der Konstruktion von
I
zugrunde liegende Intuition sollte nach den obigen Erklärun-
gen klar sein. Es sei bemerkt, dass in 3. der Definition von h-Sim für den Fall
r
=
j
und
j
=
i
ein Fehler ausgegeben wird, da wir für den Fall
j
=
i
eigentlich als Hashwert
y
−
3 Interessanterweise war in Abschnitt 10.2 einer der Gründe dafür, dass RSA selbst kein sicheres
Signierschema ist, dass
(
z
e
mod
ein gültiges Nachrichten-Signatur-Paar ist, welches man of-
fensichtlich ohne Kenntnis des privaten Schlüssels berechnen kann. Nun gereicht uns diese Tatsache
zum Vorteil.
n, z
)
