Cryptography Reference
In-Depth Information
Beispiel
Wir benutzen die Daten aus dem Beispiel von Seite 213. Der Angreifer wählt
N
=
10 und
s
=
14 und erhält
U
=
12. Dann ist
(
14, 12
)
eine gültige Signa-
tur, wie man leicht nachrechnet.
Signieren von zufälligen Datensätzen.
Ein Angreifer kann einen
zufälligen
Da-
tensatz signieren: Er wählt Zahlen
i
,
j
∈{
0, . . . ,
p
−
2
}
mit ggT
(
j
,
p
−
1
)=
1 und
berechnet
g
i
A
j
≡
(
)
R
mod
p
,
Rj
−
1
≡−
(
(
−
))
s
mod
p
1
,
Rij
−
1
N≡−
(
(
−
))
mod
p
1
.
(
)
N
Es ist dann
R
,
s
die gültige Signatur des Dokuments
, da gilt:
)
−
Rj
−
1
A
R
g
−
Rij
−
1
A
−
R
g
N
.
A
R
R
s
A
R
g
i
A
j
=
(
=
=
Bemerkung
Ein vorgebenes
N
zu signieren, erfordert das Auflösen der Gleichung:
A
R
R
s
g
N
Z
p
=
in
nach
(
R
,
s
)
.
Es gibt keinen Anhaltspunkt dafür, wie man das machen könnte, aber auch kein
bekanntes Problem, zu dem es äquivalent ist.
Kennt man
k
, so kennt man
a
;
k
darf also nur einmal verwendet werden.
Die
beim ElGamal-Signaturverfahren zufällig gewählte Zahl
k
mit
g
k
R
darf nur
einmal verwendet werden. Wird
k
nämlich zwei Mal benutzt, sind also
=
(
)
R
,
s
1
eine Signatur zu
N
1
sowie
(
R
,
s
2
)
eine Signatur zu
N
2
, so gilt
A
R
R
s
1
g
N
1
und
A
R
R
s
2
g
N
2
.
=
=
Es folgt
g
N
2
−N
1
A
R
R
s
2
R
−
s
1
A
−
R
R
s
2
−
s
1
g
k
(
s
2
−
s
1
)
=
=
=
Wegen
o
(
g
)=
p
−
1 erhalten wir hieraus
N
2
−N
1
≡
(
−
)(
(
−
))
k
s
2
s
1
mod
p
1
.
(
−
−
)=
Falls ggT
s
2
s
1
,
p
1
1, so kann man
k
aus dieser Konguenzgleichung be-
stimmen. Gilt zudem ggT
1, so erhält man aus
k
dann den geheimen
Schlüssel
a
von
E
aus der Kongruenzgleichung
(
R
,
p
−
1
)=
N
1
−
aR
≡
ks
1
(
mod
(
p
−
1
))
.
Bemerkung
Im Beispiel oben konnte ein Angreifer selbst einen Datensatz signieren, wenn
R
und
p
−
1 nicht teilerfremd sind. Genau aus diesem Grund kompromittiert das
den geheimen Schlüssel
nicht
, obwohl dasselbe
R
verwendet wird.
