Cryptography Reference
In-Depth Information
12.3.3 Angriffe
Das Ablehnen der Signatur im Fall
R
1 verhindert einen naheliegen-
den Angriff. Im Folgenden gehen wir wieder von der Situation des ElGamal-
Verfahrens aus, es sei
>
p
−
(
p
,
g
,
A
)
der öffentliche Schlüssel und
a
der geheime
Schlüssel.
Erzeugen von Signaturen aus bekannten Signaturen.
Es ist manchmal mög-
lich, mithilfe einer bekannten ElGamal-Signatur
(
N
,
R
,
s
)
eine gültige Signatur
R
,
s
)
N
zu erstellen. Jedoch gilt dann fast immer
(
für ein beliebiges Dokument
R
>
−
≤
≤
−
1 also nicht eingehalten,
so kann es sein, dass aus einer bekannten Signatur eine neue Signatur konstruiert
wurde. Wir schildern das Vorgehen eines Angreifers, der dies zum Ziel hat.
Einem Angreifer
A
sei ein Dokument
p
1. Wird die Größenbeschränkung 1
R
p
N
mit der Signatur
(
R
,
s
)
bekannt. Und
N
ein weiteres Dokument, das
A
im Namen von
E
signieren will. Falls
das Element
es sei
N
, aufgefasst als Element des Restklassenringes
Z
p
−
1
, invertierbar
N∈
Z
p
−
1
oder anders ausgedrückt ggT
(
N
−
)=
ist, d. h.
,
p
1
1, so erreicht der
Angreifer
A
sein Ziel, indem er wie folgt vorgeht:
≡N
N
−
1
(
(
−
))
A
berechnet
U
mod
p
1
.
A
ermittelt
s
als Lösung von
X
≡
(
(
−
))
sU
mod
p
1
.
(
−
)=
A
berechnet mit dem chinesischen Restsatz (beachte ggT
p
1,
p
1) eine
Lösung
R
des Systems von Kongruenzgleichungen:
X
≡
RU
(
mod
(
p
−
1
))
und
X
≡
R
(
mod
p
)
.
R
,
s
)
N
angeben.
A
kann nun
(
als gültige Signatur zum Klartext
Ein Teilnehmer
T
verifiziert die gefälschte Signatur, es gilt nämlich:
A
R
s
g
N
.
R
)
A
RU
R
sU
g
U
(
aR
+
ks
)
=
g
U
N
=
(
=
=
Nun begründen wir, dass für das
R
der so erhaltenen Signatur im Allgemeinen
R
>
1 gilt. Angenommen, es gilt
R
≤
R
(
−
−
≡
)
p
p
1. Dann folgt aus
R
mod
p
R
, also
schon
R
=
≡
(
(
−
))
⇔
(
−
)
≡
(
(
−
))
R
RU
mod
p
1
R
U
1
0
mod
p
1
⇔
(
p
−
1
)
|
R
(
U
−
1
)
.
N
=
N
.
Im Fall ggT
(
R
,
p
−
1
)=
1 kann man
R
kürzen, es folgt
U
=
1 und damit
(
−
)
=
Ein Angreifer hat dadurch nichts erreicht. Gilt aber ggT
R
,
p
1
1, so muss
U
N
speziell gewählt werden. Dass dies eintreten kann, zeigt das
folgende Beispiel.
und damit auch