Cryptography Reference
In-Depth Information
ist das Finden des geheimen Schlüssels
e
zum Lösen des
diskreten Logarithmen-
problems
äquivalent:
Bestimme aus der Kenntnis von
C
N
und
eine Zahl e mit
e
.
C
=
N
Sind
a
und
c
Elemente einer Gruppe
(
G
,
·
)
, so nennt man die kleinste nichtnega-
tive Zahl
e
mit
a
e
den
diskreten Logarithmus
(von
c
zur Basis
a
). Man schreibt dann
e
=
c
=
Log
a
(
c
)
.
Bemerkung
Ist
G
a
k
;
k
=
=
{
∈
Z
}
jedes Element von
G
einen
diskreten Logarithmus zur Basis
a
; in nicht zyklischen Gruppen ist das nicht für
alle Elemente der Fall.
a
zyklisch, so hat wegen
G
Da die Bildung von Potenzen in der Komplexitätsklasse
P
liegt (vgl. Abschnitt 6.3),
ist das diskrete Logarithmusproblem in
NP
. Die naive Herangehensweise zur
Lösung des diskreten Logarithmenproblems, also die sukzessive Bestimmung
der Potenzen
a
1
,
a
2
,
a
3
, . . . und Vergleich von
a
i
mit
c
in jedem Schritt, ist daher
exponentiell in log
e
und bei großem
e
nicht effizient.
Man kennt aber effizientere Methoden zur Bestimmung eines solchen diskreten
Logarithmus
e
. Wir werden solche Methoden in Kapitel 10 ausführlich bespre-
chen. Dennoch sind alle diese Methoden nicht polynomial.
Wir halten fest: Mit allen bekannten, allgemeinen Methoden ist es
schwierig
, die
Zahl
e
aus der Kenntnis von
a
und
c
zu bestimmen, wenn die Gruppenordnung
|
einen hinreichend großen Primteiler besitzt (siehe Kapitel 10). Wählt man
beim Pohlig-Hellman-Verfahren in Gruppen der Form
G
|
Z
p
Primzahlen von der
2
1024
, so ist man gegen die in Kapitel 10 zuammengestellten
Angriffe gefeit. Dabei muss sichergestellt sein, dass
p
Größenordnung
p
≥
−
1 einen
großen
Primteiler
besitzt.
In der Praxis wählt man die Primzahl
p
oft so, dass
1
2
selbst eine Primzahl ist.
Primzahlen mit dieser Eigenschaft nennt man auch
sichere Primzahlen
;
kleine
sichere Primzahlen sind 5, 7, 11, 23, 47.
Große
(sichere) Primzahlen zu findet ist
schwierig, mehr dazu in Kapitel 8.
p
−
6.2.4 Zur Wahl der Gruppe
Für praktische Zwecke bieten sich zwei mögliche Typen von Gruppen an, in de-
nen das Verfahren implementiert werden kann.
=
Z
p
.
•
Für eine Primzahl
p
wähle man die multiplikative Gruppe
G
Die Ordnung dieser Gruppe ist
p
1. Weil Klartexte und Geheimtexte Gruppen-
elemente, also letztlich natürliche Zahlen kleiner
p
sind, kann die Primzahl
p
−
