Cryptography Reference
In-Depth Information
Aufgaben
12.1
Wie kann man aus dem Rabin-Verfahren ein Signaturverfahren machen?
12.2
Es ist
g
=
3 eine Primitivwurzel modulo der Primzahl
p
=
2011
. De
r ge-
N
=
heime Schlüssel von
E
ist 101. Das zu signierende Dokument ist
1111. Be-
stimmen Sie die ElGamal-Signatur mit
k
=
1000 und verifizieren Sie diese.
=
Z
p
≡
(
)
=
−
=
12.3
Es sei
p
3
mod 4
eine Primzahl, und
G
g
mit
p
1
g
a
sei
gq
,
g
,
q
∈
N
. Für
A
=
(
G
,
g
,
A
)
der öffentliche Schlüssel eines ElGamal-
→
Z
p
−
1
gegeben durch
Signaturverfahrens. Dabei sei
f
:
G
x
,
=
−
falls
x
p
1
(
)=
f
x
.
0 ,
falls
x
=
p
−
1
Zeigen Sie:
(a)
q
p
−
3
≡
g
(
mod
p
)
;
2
(
√
g
mit
g
q
γ
≡
a
q
γ ∈
Z
(
)
)
(b)
mod
p
kann mit der Komplexität
O
bestimmt
werden.
(c) Mit
s
p
−
3
=
(
N−
γ
)
(
)
N
q
ist
q
,
s
eine gültige Signatur für
.
2
12.4 Das Protokoll von Fait-Shamir
Es sei
n
=
pq
mit Primzahlen
p
,
q
. Der Teilnehmer
T
wählt ein geheimes Element
s
2
und veröffentlicht
∈
Z
n
, berechnet
v
:
=
(
)
, um seine Identität etwa ge-
genüber C nachzuweisen. Dazu durchlaufen sie
t
-mal (
t
s
v
,
n
∈
N
) folgendes
Protokoll
:
r
2
und übermittelt
x
an C;
∈
Z
n
, berechnet
x
=
T wählt zufällig
r
C wählt zufällig
b
∈{
0, 1
}
und schickt
b
an T;
s
b
r
an C;
=
T schickt
u
C prüft
u
2
v
b
x
.
=
Zeigen Sie:
(a) Wer
s
kennt, kann das Protokoll erfolgreich durchlaufen.
(b) Wie groß ist die Betrugswahrscheinlichkeit für jemanden, der
s
nicht kennt?
(c) Beim Ablauf des Protokolls entsteht eine Folge
x
i
,
b
i
,
u
i
)
i
=
1,...,
t
. Diese Folge
kann auch in polynomialer Zeit
simuliert
werden, ohne dass man
s
kennt.
Daher kann keine Information über das Geheimnis übertragen worden sein.
Man spricht von einem
Zero-Knowledge-Protokoll.
(
