Kryptografie (7) : El-Gamal

in education •  yesterday 

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.

Authors get paid when people like you upvote their post.
If you enjoyed what you read here, create your account today and start earning FREE MELEK!