Cryptography Reference
In-Depth Information
Z
p
).
Es sei
p>
2
eine Primzahl und
g
Lemma 6.5.1 (Jacobi-Symbol und ElGamal in
ein Erzeuger von
Z
p
.Danngilt:
x ←
Z
p
{
J
p
(
x
)=
−
1
}
=
1
Prob
,
x ←
Z
p
{
J
p
(
x
)=1
}
=Prob
(6.5.1)
2
und
J
p
(
g
ab
)=max
{
J
p
(
g
a
)
,
J
p
(
g
b
)
}
für alle
a, b ∈
Z
p−
1
,
(6.5.2)
J
p
(
x
)=J
p
(
x · g
ab
)
·
J
p
(
g
ab
)
für alle
x ∈
Z
p
,
a, b ∈
Z
p−
1
.
(6.5.3)
Beweis.
Aussage (6.5.1) folgt unmittelbar aus Satz 6.3.10.
Aussage (6.5.2) ist äquivalent zu:
J
p
(
g
ab
)=1
genau dann, wenn
J
p
(
g
a
)=1
oder
J
p
(
g
b
)=1
.Nunistaber
J
p
(
g
ab
)=1
, und damit
J
p
(
g
ab
mod (
p−
1)
mod
p
)=1
,nach
Satz 6.3.10 äquivalent zu
(
ab
mod
(
p
1)
äquivalent
zu
ab
mod
2=0
ist. Analog ist
J
p
(
g
a
)=1
bzw.
J
p
(
g
b
)=1
äquivalent zu
a
mod
2=0
bzw.
b
mod
2=0
.Da
ab
mod
2=0
genau dann wahr ist, wenn
a
mod
2=0
oder
b
mod
2=0
gilt, ist nun nichts weiter zu zeigen.
Zum Beweis von (6.5.3): Aus der Multiplikativität des Jacobi-Symbols folgt
J
p
(
xg
ab
)
=
J
p
(
x
)J
p
(
g
ab
)
. Daraus folgt aber die Behauptung, da alle Faktoren zu
−
1))
mod
2=0
, was wegen
2
|
(
p
−
{−
1
,
1
}
gehören.
Wegen (6.5.3), in Verbindung mit (6.5.2), kann die Eigenschaft »Jacobi-Symbol ist
1
«
leicht vom Chiffretext abgelesen werden. Dies ist nach (6.5.1) eine nicht-triviale Eigen-
schaft, denn die Hälfte aller Klartexte besitzt sie. Aus diesem Grund ist ElGamal für
die Einheitengruppen
Z
p
kein sicheres asymmetrische Kryptoschema. In der Tat ist es,
analog zum RSA-Kryptoschema, leicht, auf Basis von Lemma 6.5.1, einen erfolgreichen
Angreifer zu konstruieren (siehe Aufgabe 6.7.20).
Vielleicht zunächst überraschend ist auch die Tatsache, dass die Elemente
g
ab
für
zufällig gewählte Elemente
a, b
∈
Z
p−
1
nicht gleichverteilt sind: Wären sie dies, so müsste
J
p
(
g
ab
)=1
mit Wahrscheinlichkeit
1
/
2
gelten, was, wie das folgende Lemma zeigt, aber
nicht der Fall ist. Die Maskierung des Klartextes in der ElGamal-Funktionsfamilie durch
g
ab
ist demnach unausgewogen.
Z
p
.Danngilt:
Lemma 6.5.2.
Es sei
p
eine Primzahl und
g
ein Erzeuger von
J
p
(
g
ab
)=1
=
3
4
Prob
a,b ←
Z
p−
1
.
(6.5.4)
J
p
(
g
ab
)=
−
1
=
4
Beweis.
Wir zeigen, dass
Prob
a,b ←
Z
p−
1
gilt. Aus Lemma 6.5.1 erhalten
wir, dass
J
p
(
g
ab
)=
1
genau dann gilt, wenn
J
p
(
g
a
)=
1
und
J
p
(
g
b
)=
−
−
−
1
gilt, w
as
aber jeweils nach Lemma 6.5.1 nur mit Wahrscheinlichkeit
2
eintritt.
Z
p
nicht zu einem sicheren
ElGamal-Kryptoschema führt. Wie besprochen ist das wesentliche Problem, dass aus dem
Chiffretext das Jacobi-Symbol des Klartextes abgelesen werden kann. Dieses Problem
Wir wissen nun, dass die Klasse der Einheitengruppen
