Cryptography Reference
In-Depth Information
Z
p
ν
Wir haben begründet, dass die Gruppen
für jede Primzahl
p
=
2 und jede
ν
∈
natürliche Zahl
zyklisch sind. In jeder solchen Gruppe existiert damit ein
a
Z
p
ν
mit
Z
p
ν
=
p
ν
)=(
p
ν−
1
.
(
)=
ϕ
(
−
)
a
, es gilt
o
a
p
1
Dies ist eine reine Existenzaussage, wie man konkret ein solches erzeugendes
Element
a
zu einer Primzahlpotenz
p
ν
berechnet, ist dabei noch völlig offen. Das
Problem ist, Erzeuger von
Z
p
zu finden, dann zeigt der Beweis, wie man Erzeu-
Z
p
ν
gewinnen kann.
Es ist keine Formel bekannt, nach der ein erzeugendes Element
a
von
ger von
Z
p
be-
stimmt werden kann. Im Allgemeinen ist es sehr mühsam, ein passendes
a
zu
ermitteln. Für unsere (eher theoretischen) Zwecke ist das Wissen über die Exis-
tenz eines solchen Elements aber meistens völlig ausreichend.
Ist
Z
n
zyklisch, so nennt man jedes
Z
n
erzeugende Element
a
, d. h., es gilt
a
=
Z
n
, eine
Primitivwurzel
modulo
n
.
Bemerkung
Nach C. F. Gauß ist bekannt, für welche Zahlen
n
die Gruppe
Z
n
zyklisch sind:
Z
n
p
ν
oder
=
=
=
Die Gruppe
ist genau dann zyklisch, wenn n
2
oder n
4
oder n
2
p
ν
mit einer ungeraden Primzahl p und natürlichen Zahl
n
=
ν
(vgl. Korollar 13.12
in [14]).
6.2 Das Pohlig-Hellman-Verfahren *
In den Sätzen von Euler und Fermat steckt die Idee für ein Verschlüsselungsver-
fahren, bei dem das Verschlüsseln wie auch das Entschlüsseln durch Potenzbil-
dung erfolgt.
Z
p
6.2.1 Das Pohlig-Hellman-Verfahren in
Z
p
des
Wir erläutern das
Pohlig-Hellman-Verfahren
in der multiplikativen Gruppe
endlichen Körpers
Z
p
.
Gegeben ist eine Primzahl
p
. Der zu verschlüsselnde Klartext
N
sei als ein Ele-
Z
p
dargestellt. Das ist eine (zyklische) multiplikative Gruppe mit
p
−
ment von
1
Elementen (siehe Satz 6.12). Nun erzeugen wir die beiden Schlüssel
e
(zum Ver-
schlüsseln) und
d
(zum Entschlüsseln):
Für die Zahl
e
wählt man eine zu
p
−
1 teilerfremde natürliche Zahl. Nach
Satz 4.20 existiert eine natürliche Zahl
d
mit
≡
(
−
)
ed
1
mod
p
1
,
die man mithilfe des euklidischen Algorithmus (siehe Satz 4.10) berechnen kann.
