Cryptography Reference
In-Depth Information
a) Zeigen Sie:
Prob
=1
,E
1
2
l−
1
E
S
FDH-RSA
F
≤
.
b) Reduzieren Sie nun, unter Benutzung von a), die Sicherheit von
S
FDH-RSA
auf die
RSA-Annahme analog zum Beweis von Satz 10.4.1, aber ohne die Annahme zu machen,
dass
F
bei Ausgabe von
(
x, s
)
zuvor immer das Zufallsorakel mit
x
angefragt hat.
Aufgabe
10.7.9 (DSA)
.
Zeigen Sie, dass DSA (siehe Definition 10.5.1) ein Signierschema
im Sinne von Definition 10.1.1 ist. Überprüfen Sie insbesondere die Korrektheitseigen-
schaft. Spezifizieren Sie zudem den Schlüsselerzeugungsalgorithmus
G
genauer, indem
Sie ein Verfahren angeben, um
p
,
q
und
g
zu wählen. (Wir lassen zu, dass der Algorith-
mus mit geringer Wahrscheinlichkeit erfolglos abbricht.)
Hinweis: Der Algorithmus
G
sollte zunächst eine Primzahl
q
mit
2
159
<q<
2
160
wäh-
len und dann eine zufällig gewählte Zahl
b
mit
2
1023
<b<
2
1024
. Daraus sollte dann ein
p
bestimmt werden, so dass die Bedingungen an
p
und
q
erfüllt sind, bis auf die Eigenschaft,
dass
p
eine Primzahl ist. Schließlich sollte überprüft werden, ob
p
eine Primzahl ist. Um
einen Erzeuger
g
für die Untergruppe mit Ordnung
q
zu wählen, bestimmen Sie zunächst
einen Erzeuger der Gruppe
Z
p
. Berechnen Sie daraus einen Erzeuger der Untergruppe
mit Hilfe von Lemma 6.3.3.
Aufgabe
10.7.10 (Sicherheit von DSA)
.
Zeigen Sie, dass, wenn man zwei DSA-Signaturen
auf verschiedene Nachrichten
x
0
und
x
1
besitzt, die mit dem gleichen privaten Schlüssel
berechnet wurden und zu deren Berechnung zudem das gleiche
k
verwendet wurde (siehe
Definition 10.5.1), dann kann man aus den Signaturen ezient den privaten Schlüssel be-
rechnen. Es ist also wichtig, dass
k
tatsächlich zufällig gewählt wird, da der beschriebene
Fall dann nur mit verschwindend geringer Wahrscheinlichkeit auftritt.
Aufgabe
10.7.11 (Sicherheit des CRP)
.
Überlegen Sie sich, wie man die Sicherheit der
CRPs, die wir in Abschnitt 10.6 kennengelernt haben, definieren kann. Geben Sie dazu
wie üblich jeweils ein Experiment an und definieren Sie den Vorteil eines Angreifers.
Im Experiment sollte ein Angreifer versuchen, Alice davon zu überzeugen, dass er den
privaten Schlüssel zu einem öffentlichen Schlüssel besitzt, obwohl der Angreifer lediglich
den öffentlichen Schlüssel kennt. Modellieren Sie dabei, dass Alice genau eine Instanz
des Protokolls laufen lässt und der Angreifer auf keine weiteren Instanzen des Protokolls
zugreifen kann.
Beweisen Sie unter der Annahme, dass das verwendete asymmetrische Kryptoschema
im Sinne von Abschnitt 6.2 sicher ist bzw. das Signierschema im Sinne von Abschnitt 10.1
sicher ist, dass die angegebenen CRPs in dem zuvor definierten Sinne sicher sind.
Bemerkung: Wie in Abschnitt 10.6.1 erläutert, bieten die betrachteten CRPs im Allge-
meinen keine ausreichende Sicherheit, falls mehrere Instanzen des Protokolls gleichzeitig
ablaufen können.
Aufgabe
10.7.12 (PoP)
.
Wie in Abschnitt 10.6 diskutiert, kann man in vielen Fällen auf
einen PoP verzichten. Dennoch kann man Anwendungen konstruieren, bei denen es ohne
PoP zu Problemen kommt. Überlegen Sie sich mindestens eine solche Anwendung.
