Asymmetrische Authentifizierungsverfahren: Digitale Signaturen - Moderne Kryptographie - page 265

Aufgabe 10.7.2 (Eigenschaften des Zufallsorakels) . Wir betrachten ein Zufallsorakel mit
endlichem Definitions- und Bildbereich. Schätzen Sie analog zu Lemma 10.4.1 den Vorteil
eines Angreifers für die Zweites-Urbild-Resistenz sowie die Urbild-Resistenz eines Zufalls-
orakels möglichst gut ab. Verwenden Sie dazu Ihre Definition aus Aufgabe 8.6.1.

Aufgabe 10.7.3 (MACs und Zufallsorakel) . Vervollständigen Sie die durch (10.4.1) ange-
deutete Konstruktion eines MACs aus einem Zufallsorakel und beweisen Sie die Sicherheit
Ihrer Konstruktion im Sinne der Sicherheitsdefinition aus Abschnitt 9.2.
Bemerkung: Wie bereits in Aufgabe 9.8.8 gezeigt, wäre diese Konstruktion unsicher,
wenn das Zufallsorakel durch eine konkrete iterierte Familie von MD-Hashfunktionen
ersetzt werden würde.

Aufgabe 10.7.4 (Zufallsorakel und CPA-sichere Verschlüsselung) . Es sei l> 0 und H ein
Zufallsorakel mit Bildbereich

l . Wir betrachten das folgende RSA-basierte asym-
metrische Kryptoschema für Nachrichten m

{ 0 , 1 }

l .Essei ( n, e ) ein öffentlicher RSA-
Schlüssel. Eine Nachricht m wird unter ( n, e ) verschlüsselt, indem zunächst ein r

∈{ 0 , 1 }

∈ Z n

zufällig gewählt wird und dann der Chiffretext ( r e

mod n, H ( r ) ⊕ m ) ausgegeben wird;

entschlüsselt wird in offensichtlicher Weise.
Beweisen Sie unter der RSA-Annahme, dass dieses Kryptoschema sicher ist (im Sinne
von Definition 10.1.3), d. h., beschränken Sie den Vorteil eines Angreifers A auf dieses
Schema durch den Vorteil eines geeignet konstruierten Invertierers I .
Hinweis: Betrachten Sie das Ereignis, dass A das bei der Berechnung der Probe ge-
wählte r zu irgendeinem Zeitpunkt als Anfrage an das Zufallsorakel schickt. Tritt dieses
Ereignis nicht ein, so kann man zeigen, dass der Vorteil von A klein sein muss. Tritt
dieses Ereignis ein, so kann man den Vorteil von A durch den Vorteil eines geeignet
konstruierten Invertierers I beschränken.

Aufgabe 10.7.5 (Realisierung des Zufallsorakels) . In Abschnitt 10.4.1 wurde diskutiert,
dass sich Zufallsorakel in der Praxis nicht realisieren lassen. Vertiefen Sie diese Diskussion
und nennen Sie weitere Probleme, die bei dem Versuch ein Zufallsorakel zu realisieren,
auftreten würden.

Aufgabe 10.7.6 (RSA und Hash-then-Sign-Ansatz) . Begründen Sie informell, dass die in
Abschnitt 10.2 besprochenen Angriffe auf das durch RSA induzierte Signierschema nicht
mehr möglich wären, falls nicht die Nachricht selbst, sondern der Hashwert der Nachricht
signiert werden würde, gemäß dem Hash-then-Sign-Ansatz aus Abschnitt 10.3.

Aufgabe 10.7.7 (Quantifizierung der Sicherheit des FDH-RSA-Signierschemas) . Schätzen
Sie die Unsicherheit des FDH-RSA-Signierschemas durch die Unsicherheit von RSA als
Einwegfamilie mit Hintertür gemäß Definition 10.1.4 nach oben ab. Verwenden Sie dazu
Satz 10.4.1 bzw. den Beweis dieses Satzes.

Aufgabe 10.7.8 (Alternativer Beweis zur Sicherheit des FDH-RSA-Signierschemas) . Es
seien l> 0 gerade, q

≥ 1 und F ein q -beschränkter Fälscher für das l -FDH-RSA-

Signierschema S FDH-RSA .BetrachtenSiedasEreignis E ,dass F in einem Lauf von

E S FDH-RS F das Nachrichten-Signatur-Paar ( x, s ) ,fürein x und ein s , ausgibt, aber das
Zufallsorakel nicht zuvor mit x angefragt hat.