Kryptografie (7) : El-Gamal

Der Algorithmus von El-Gamal basiert auf das Schlüsselaustauschverfahren von Diffie-Hellman und stellt eine asymmetrische Verschlüsselung dar. Zunächst wird mit dem Protokoll von Diffie-Hellman jeweils ein Schlüsselpaar generiert, sodass zwei Kommunikationspartner sicher Nachrichten austauschen können [1].

Als Beispiel möchten wir, der Sender, eine Nachricht m verschlüsselt an dem Empfänger zusenden. Dafür benötigen wir seinen Public-Key den er uns mitteilen muss. Die Parameter p,g,k des Empfängers wurden bereits mithilfe von Diffie-Hellman bestimmt.

Kurze Wiederholung

p ist die Zahl die den endlichen Körper bildet, g ist ein Element des endlichen Körpers und k ist eine zufällige Zahl, wobei 1 < k < p-1 gilt.

Rechenbeispiel

Nehmen wir mal ein paar konkrete Werte. Der Empfänger veröffentlicht uns seinen Public-Key mit den Tupel (p,g,a)=(23,7,17). Das a wird mit g^k mod p = 7^5 mod 23 = 17 berechnet, wobei die zufällige Zahl des Empfängers k=5 lautet.

Nun möchte der Sender seine Nachricht m=8 mit den Public-Key des Empfängers verschlüsseln und zusenden. Der Sender wählt hierfür seinerseits eine zufällig Zahl k=3 aus 1 < k < p-1 und berechnet
b=g^k mod p=7^3 mod 23 = 21 und i=a^k mod p=17^3 mod 23=14 (gemeinsamer Schlüssel aus Diffie-Hellman), um das Chiffrat
c=i * m mod p = 14 * 8 mod 23 = 20 zu bestimmen. Dann sendet der Sender den Geheimtext welcher aus den Tupel (b,c)=(21,20) besteht an den Empfänger.

Der Empfänger berechnet zunächst inv(k)=b^(p-1-k) mod p = 21^(22-5) mod 23 = 5 und anschließend entschlüsselt er den Geheimtext mit m=inv(k) * c mod p = 5 * 20 mod 23 = 8. Somit gilt m=m -> 8=8. Die Ver- und Entschlüsselung der Nachricht m war erfolgreich. Jetzt könnte der Empfänger noch dem Sender antworten. Dafür benötigt er den Public-Key des Senders und dieser Prozess wiederholt sich.

• Quelle
  Tsiounis, Yiannis; Yung, Moti. On the Security of ElGamal Based Encryption. 1998. pp. 119 und 120.
  https://www.researchgate.net/publication/221010812_On_the_Security_of_ElGamal_Based_Encryption