Cryptography Reference
In-Depth Information
Lemma 10.4
Es seien G
1
=
=
g
1
und G
2
g
2
endliche zyklische Gruppen mit teilerfremden
Ordnungen. Weiter sei g
=(
g
1
,
g
2
)
ein erzeugendes Element der zyklischen Gruppe
×
=(
)
∈
=
Log
g
(
)
G
1
G
2
, und es sei a
:
a
1
,
a
2
G. Für x
a
gilt:
≡
Log
g
i
(
)(
|
|
)
=
x
a
i
mod
G
i
für i
1, 2 .
Beweis.
Da
x
der diskrete Logarithmus von
a
zur Basis
g
ist, gilt
g
x
=
a
,d.h.
g
1
,
g
2
)=(
(
)
a
1
,
a
2
. Somit gilt nach (ii) in Lemma 6.1 (b):
g
Log
g
i
(
a
i
)
i
g
i
=
a
i
=
,d.h.
x
≡
Log
g
i
(
a
i
)(
mod
|
G
i
|
)
für
i
=
1, 2 .
Damit ist bereits alles gezeigt.
=
Log
g
i
(
)
=
Kennt man die diskreten Logarithmen
x
i
a
i
für
i
1, 2, so kann man
=
Log
g
(
)
|
|
also den diskreten Logarithmus
x
a
wegen der Teilerfremdheit von
G
1
|
|
und
mithilfe des chinesischen Restsatzes 7.4 berechnen. Mit Lemma 10.4 ist
somit das DLP in einer endlichen zyklischen Gruppe
G
auf das DLP in zyklischen
Gruppen von Primzahlpotenzordnung zurückgeführt. Hierbei sind eigentlich die
Kosten
für den chinesichen Restsatz zu berücksichtigen, aber die sind bekanntlich
nicht sehr hoch.
G
2
Beisp
ie
l
Es ist 5 eine Primitivwurzel modulo der Primzah
l
p
Z
7
3
=
=
73, d. h.
5
.Wir
=
=
Log
5
(
)
bestimmen den diskreten Logarithmus von
a
58, d. h.
x
58
. Es gilt
G
2
=
Z
8
×
Z
9
, wobei
Z
p
=
G
1
×
5
9
5
8
G
1
=
=
10
mit
|
G
1
|
=
8 und
G
2
=
=
2
mit
|
G
2
|
=
9.
=
×
Für das Element
a
58 erhalten wir in
G
1
G
2
die Darstellung
58
9
, 58
8
=
=(
)=(
)
a
58
51, 55
.
Wir bestimmen
nu
n die
einfach
zu bestimmenden Logarithmen
x
1
=
Log
10
(
51
)
=
Log
2
(
)
und
x
2
55
in den Gruppen
G
1
und
G
2
z. B. mit Pollards
-Methode und
erhalten:
=
Log
10
(
)=
=
Log
2
(
)=
x
1
51
3 und
x
2
55
7.
Nun erhalten wir den gesuchten diskreten Logarithmus, indem wir mit dem chi-
nesischen Restsatz die kleinste positive Lösung des folgenden Kongruenzglei-
chungssystems bestimmen:
X
≡
3
(
mod 8
)
,
X
≡
7
(
mod 9
)
.
46, und tatsächlich gilt 5
43
Wir erhalten
x
=
=
58.
