Cryptography Reference
In-Depth Information
6 Exponentiationschiffren
Das
Pohlig-Hellman-Verfahren
ist eine sogenannte
Exponentiationschiffre
. Ein Klar-
text
, aufgefasst als Element einer Gruppe
G
, wird verschlüsselt, indem eine
Potenz von
N
N
N →N
e
. Die Zahl
e
ist dabei der geheime Schlüs-
gebildet wird:
e
wird dann durch den Empfänger ent-
schlüsselt, indem die Umkehrabbildung dieser Potenzfunktion
f
e
:
a
C
=
N
sel des Senders. Der Geheimtext
a
e
ange-
wandt wird. Im Fall einer endlichen Gruppe ist dies wieder eine Potenzfunktion
f
d
→
a
d
. Der Exponent
d
ist dabei so zu wählen, dass
d
e
d
gilt.
Es ist
d
der geheime Schlüssel des Empfängers. Wir werden sehen, dass ein sol-
ches
d
unter geeigneten Voraussetzungen immer existiert und effizient bestimmt
werden kann.
Das Ver- und Entschlüsseln erfolgt beim
Pohlig-Hellman-Verfahren
durch Potenz-
bildung, daher der Begriff
Exponentiationschiffre
.
Im Allgemeinen sind bei einer Exponentiationschiffre hohe Potenzen von Grup-
penelementen zu bilden. Wir zeigen, wie diese Potenzbildung effizient mit der
sogenannten
schnellen Exponentiation
durchgeführt werden kann.
Die algebraische Grundlage des Pohlig-Hellman-Verfahrens wie auch aller wei-
teren Exponentiationschiffren, die wir in den folgenden Kapiteln vorstellen, bil-
det der
Satz von Lagrange
mit seinen wichtigen Folgerungen, die auch als
Sätze
von Euler
und
Fermat
bekannt sind. Diese Sätze bilden das Fundament jeder Ex-
ponentiationschiffre und damit den algebraischen Schwerpunkt dieses Kapitels.
Wir werden in einem ersten Abschnitt diese Sätze wie auch zahlreiche weitere
Ergebnisse, die wir im Folgenden benötigen werden, herleiten.
:
a
→
C
=(
N
)
=
N
6.1 Algebraische Grundlagen der Exponentiationschiffren
Wir leiten in diesem Abschnitt viele wichtige Aussagen für (endliche, abelsche)
Gruppen her, wobei einige Aussagen aus der Vorlesung zur linearen Algebra be-
kannt sind. Dieser Abschnitt ist grundlegend für alle modernen Verfahren der
Kryptologie.
Das neutrale Element einer Gruppe
G
bezeichnen wir im Allgemeinen mit 1. Die
Mächtigkeit
|
G
|
nennen wir die
Gruppenordnung
.
6.1.1 Ordnungen von Gruppenelementen
(
·
)
Für jedes Element
a
einer Gruppe
G
,
ist die Menge
a
n
;
n
=
{
∈
Z
} ⊆
a
:
G
eine Untergruppe von
G
- man nennt sie die von
a
erzeugte
Untergruppe von
G
.
Eine Gruppe
G
heißt
zyklisch
, wenn es ein
a
∈
G
mit
a
=
G
gibt.
