Cryptography Reference
In-Depth Information
Hellman in ihrem bereits erwähnten, bahnbrechenden Artikel 1976 vorgestellt haben. Im
Folgenden werden wir zunächst das ElGamal-Kryptoschema einführen und anschließend
seine Sicherheit diskutieren.
6.5.1
Das ElGamal-Kryptoschema
Um das ElGamal-Kryptoschema zu erläutern, schauen wir uns zunächst das erwähnte
Schlüsselvereinbarungsprotokoll von Di
e und Hellman an.
Im Di
e-Hellman-Schlüsselvereinbarungsprotokoll wollen Alice und Bob einen gehei-
men Schlüssel vereinbaren, der dann im Weiteren zur Verschlüsselung vertraulicher Nach-
richten benutzt werden kann. Dazu einigen sich Alice und Bob zunächst auf eine zyklische
endliche Gruppe
G
(z. B.
Z
p
für eine Primzahl
p
) und einen Erzeuger
g
von
G
.BeidePa-
rameter sind öffentlich bekannt. Nun wählt Alice zufällig eine Zahl
a
∈{
0
,...,
|G| −
1
}
,
welche sie geheim hält, und schickt
g
a
an Bob. Analog wählt Bob zufällig eine Zahl
, welche er geheim hält, und schickt
g
b
an Alice. Wenn Bob
g
a
emp-
fängt, berechnet er
(
g
a
)
b
. Analog berechnet Alice, nachdem sie
g
b
empfangen hat,
(
g
b
)
a
.
Damit teilen sich Alice und Bob nun den Schlüssel
g
a·b
.
Für geeignet gewählte Gruppen
b
∈{
0
,...,
|G| −
1
}
nimmt man an, dass es schwer ist, aus
g
a
und
g
b
das Gruppenelement
g
a·b
zu berechnen. Hört also Eva die Kommunikation zwischen Alice
und Bob ab, so ist es ihr (mit realistischem Aufwand) nicht möglich, den Schlüssel
g
a·b
zu bestimmen.
Damit lässt sich nun leicht ein asymmetrisches Kryptoschema konstruieren, nämlich
das ElGamal-Kryptoschema: Es seien
g
b
und
b
der öffentliche bzw. private Schlüssel von
Bob. Will nun Alice an Bob eine Nachricht
x ∈G
schicken, so wählt sie
a
und berechnet
g
a
G
wie oben und schickt dann den Chiffretext
(
g
a
,x
(
g
b
)
a
)
an Bob, also ein Paar von
·
Gruppenelementen aus
. Im Licht des oben beschriebenen Schlüsselvereinbarungsproto-
kolls ist
g
a
der Schlüsselanteil von Alice. Der Schlüsselanteil von Bob ist Bobs öffentlicher
Schlüssel. Daraus ergibt sich der gemeinsame Schlüssel
g
a·b
. Mit diesem wird
x
verschlüs-
selt, indem
x
mit
g
a·b
multipliziert wird; man sagt auch, dass
x
mit
g
a·b
»maskiert« wird.
Der Chiffretext, den Alice an Bob schickt enthält somit Alices Schlüsselanteil und die
Maskierung des Klartextes
x
.
Wir halten das gerade beschriebene ElGamal-Kryptoschema in folgender Definition
fest. In dieser Definition verwenden wir einen zufallsgesteuerten Algorithmus GroupGen,
der Tupel der Form
(
G
eine zyklische Gruppe ist, genauer die
endliche Beschreibung einer solchen Gruppe,
n
die Ordnung von
G
,n,g
)
erzeugt, wobei
G
G
und
g
ein Erzeuger
von
. Wie eine Beschreibung einer Gruppe aussieht, hängt dabei davon ab, welche
Klasse von Gruppen betrachtet wird. Kommen zum Beispiel nur Einheitengruppen
G
Z
p
für Primzahlen
p
(bestimmter Länge) in Frage, so reicht als Beschreibung einer Gruppe
die Primzahl
p
. Die von GroupGen erzeugten Tupel wären also von der Form
(
p, p
−
1
,g
)
,
Z
p
ist.
wobei
g
ein Erzeuger von
Definition 6.5.1 (ElGamal-Kryptoschema). Das
GroupGen-ElGamal-Kryptoschema
ist
das Tupel
S
ElGamal
=(
X,K,G,E,D
)
,
