Kryptografische Protokolle

Das Verschlüsselungsverfahren von ElGamal [ElG 85] ist im Prinzip nichts anderes als eine Diffie-Hellman-Schlüsselvereinbarung mit anschließendem Senden einer Nachricht, die mit dem vereinbarten Schlüssel verschlüsselt ist.

Prinzip

Öffentlich bekannt ist wiederum eine Primzahl p und eine Zahl g. Zunächst wird das Diffie-Hellman-Protokoll ausgeführt; beide Kommunikationspartner verfügen anschließend über den gemeinsamen Schlüssel k. Danach verschlüsselt der Sender B den Klartext m mit dem gemeinsamen Schlüssel k und sendet den resultierenden Geheimtext c an A. Der Empfänger A entschlüsselt den Geheimtext c mithilfe des gemeinsamen Schlüssels k und erhält den Klartext m zurück.

A		C		B
		Primzahl p Zahl g mit 1 < g < p-1
wählt    Zufallszahl u				wählt    Zufallszahl v
berechnet    a = gu mod p				berechnet    b = gv mod p			Diffie-Hellman
berechnet    k = bu mod p				berechnet    k = av mod p
				Verschlüsseln
				berechnet    c = k·m mod p
Entschlüsseln
berechnet    k -1·c mod p = k -1·k·m mod p = m mod p

Das Verschlüsseln des Klartextes m mit dem Schlüssel k entspricht einer Multiplikation

c  =  k · m  mod p.

Das Entschlüsseln des Geheimtextes c mit dem Schlüssel k entspricht der Multiplikation

m  =  k^-1 · c  mod p.

Realisierung

In der tatsächlichen Realisierung finden die Berechnungen und Übertragungen von Daten gegenüber dem obigen Diagramm zeitlich versetzt statt (siehe Bild 2).

A		C		B
Schlüssel erzeugen
wählt    Primzahl p    Zahl g mit 1 < g < p-1    Zufallszahl u
berechnet    a = gu mod p
Schlüssel veröffentlichen
		p, g, a
				Verschlüsseln
				wählt    Zufallszahl v
				berechnet    b = gv mod p    k = av mod p
				berechnet    c = k·m mod p
Entschlüsseln
berechnet    k -1 = b-u mod p
berechnet    k -1·c mod p = k -1·k·m mod p = m mod p

A erzeugt die Zahlen p, g und a und veröffentlicht diese als seinen öffentlichen Schlüssel, hält aber die Zahl u als privaten Schlüssel geheim.

Von diesem Zeitpunkt an kann ein beliebiger Sender B einen Klartext m mit dem öffentlichen Schlüssel des Empfängers A verschlüsseln, indem er zunächst k berechnet und daraufhin m mit k verschlüsselt. Zusätzlich zum eigentlichen Geheimtext c sendet er nun die Zahl b an den Empfänger A. Dieser kann mithilfe seines privaten Schlüssels u die Zahl k^-1 berechnen und den Klartext m zurückgewinnen.

Sicherheit

Die Sicherheit des Verschlüsselungsverfahrens von ElGamal beruht auf der Sicherheit der Diffie-Hellman-Schlüsselvereinbarung. Wichtig ist hier, dass g erzeugendes Element von ℤ_p* ist.

Anhand von Bild 1 lässt sich erkennen, dass der Klartext m aus dem Geheimtext c nur durch Kenntnis des Schlüssels k zurückgewonnen werden kann. Die Zahl k aber lässt sich aus den öffentlich bekannten Zahlen p, g, a und b nicht effizient berechnen (Problem des diskreten Logarithmus).

Durch eine Known-Plaintext-Attack allerdings, also bei Kenntnis eines Klartextes m und des zugehörigen Geheimtextes c, lässt sich k berechnen, nämlich durch

k  =  c · m^-1  mod p

Daher ist es wichtig, den Schlüssel k immer nur ein einziges Mal zu verwenden. Dies geschieht dadurch, dass der Sender B bei jeder neuen Verschlüsselung eine neue Zufallszahl v wählt, sodass jedes Mal ein neues k und ein neues b erzeugt werden.

Auch wenn ein längerer Klartext in Zahlen m₀, m₁, m₂ usw. zerlegt wird, die einzeln verschlüsselt werden, muss jedes Mal eine neue Zufallszahl v verwendet werden.

Effizienz

Für die Verschlüsselung einer Zahl m sind zwei modulare Exponentiationen und eine modulare Multiplikation erforderlich.

Für die Entschlüsselung ist eine modulare Exponentiation und eine modulare Multiplikation erforderlich. Die Berechnung b^-u mod p lässt sich nämlich, sofern u < p gewählt wird, als modulare Exponentiation b^p-1-u mod p ausführen, denn es ist (modulo p gerechnet)

b^p-1-u   =   b^p-1 · b^-u   =   1 · b^-u   =   b^-u.

Beispiel

Literatur

Der Originalartikel ist

[ElG 85]   T. ElGamal: A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, 31, 469-472 (1985)

Darüber hinaus bieten folgende Bücher gute Darstellungen des ElGamal-Verschlüsselungsverfahrens.

[Bu 00]   J.A. Buchmann: Introduction to Cryptography. Springer (2000)

[BNS 05]   A. Beutelspacher, H.B. Neumann, T. Schwarzpaul: Kryptografie in Theorie und Praxis. Vieweg (2005)

[Wät 04]   D. Wätjen: Kryptographie. Spektrum (2004)

[Lan 18]   H.W. Lang: Kryptografie für Dummies. Wiley (2018)

[Weitere Informationen]