i
i
main”—2013/4/10—15:19—page67—#79
i
i
i
i
i
i
Das ElGamal-Kryptosystem 67
Für ein zufälliges g gilt g
(p1)/q
≡ 1modp mit Wahrscheinlichkeit 1 1/q.Damit
besteht ein zufälliges Element
g fast sicher den Test g
(p1)/q
≡ 1modp,undq ist
ein Teiler der Ordnung von
g.
Alice und Bob einigen sich auf die Werte
p und g. Diese müssen nicht geheim
bleiben. Sie können also etwa per E-Mail übertragen werden. Jeder für sich erzeugt
jetzt eine geheim zu haltende Zufallszahl
a bzw. b aus der Menge {2,...,p 1}.Alice
berechnet
A = g
a
mod p und Bob B = g
b
mod p.NunschicktAliceA öffentlich an
Bob, und Bob sendet
B öffentlich zurück an Alice. Als geheimen Schlüssel K für die
weitere Kommunikation verwenden beide:
K = (A
b
mod p) = g
ab
= g
ba
= (B
a
mod p) ∈{1,...,p 1}
Das folgende Beispiel benutzt sehr kleine Zahlen, insbesondere ist q = 11.In
der tatsächlichen Anwendung werden Zahlen mit mehreren Hundert Dezimalstellen
benutzt.
Beispiel 2.3. Alice und Bob einigen sich auf
p = 23 und g = 5.Esgiltg
2
2mod
23
.AlsoistdieOrdnungvong in (Z/23Z)
mindestens 11. Tatsächlich ist g sogar
ein Erzeuger von
(Z/23Z)
und hat damit die Ordnung 22. Alice wählt die Zufallszahl
a = 6.Bobwähltb = 13. Alice berechnet A 5
6
8mod23, und sendet A = 8
an Bob. Bob berechnet B 5
13
21 mod 23, und sendet B = 21 an Alice. Alice
berechnet
K = 21
6
mod 23 = 18. Bob berechnet K = 8
13
mod 23 = 18. Jeder
darf die Zahlen 23, 5, 8 und 21 mithören, aber der geheime Schlüssel
K = 18 bleibt
verborgen.
Die Sicherheit des Verfahrens basiert auf dem Problem, den diskreten Logarith-
mus zu berechnen. In der Praxis werden sehr große Primzahlen v e rwendet. Die Si-
cherheit kann weiter erhöht werden, wenn
q = (p 1)/2 ebenfalls eine Primzahl
ist (
p ist dann eine Sophie-Germain-Primzahl (nach Sophie Germain, 1776–1831) und
für
g kann man 2 verwenden). Die Werte p, g, A, B sind jedem Lauscher bekannt,
aber das Diffie-Hellman-Problem ist,
K zu berechnen. Es ist lösbar, wenn man den
diskreten Logarithmus
a von A g
a
mod p oder den diskreten Logarithmus b von
B g
b
mod p berechnen kann. Eine andere Methode ist bisher nicht bekannt.
Allerdings könnte sich eine dritte Partei Oskar zwischen Alice und Bob stellen
und sich Alice und Bob gegenüber jeweils für den anderen Partner ausgeben, ohne
dass diese es merken. Um dies zu verhindern, können Alice und Bob alle Nachrichten
mit einer elektronischen Unterschrift versehen. Wie dies geht, behandeln wir in dem
Abschnitt 2.13.
2.10 Das ElGamal-Kryptosystem
Das ElGamal-Verfahren wurde 1985 von Taher ElGamal (geb. 1955) entwickelt und
dient sowohl der Signaturerzeugung wie auch der Verschlüsselung [34]. Wie bei RSA

Get Diskrete algebraische Methoden now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.