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 )
Search WWH ::




Custom Search