Das El Gamal Verschlüsselungsverfahren basiert im wesentlichen auf dem Diffie-Hellmann Schlüsseltausch. Dieses asymetrische Kryptosystem eignet sich vor allem für kleine Nachrichten wie Kreditkartennummern oder URLs die zwischen Sender und Empfänger ausgetauscht werden. ElGamal erspart uns hierbei die Aufwendige Kombination von Schlüsselaustausch und einem AES oder RSA Algorithmus.

 Betrachten wir den Diffi-Hellmann Schlüsseltausch erneut in Protokollform:

Nehmen wir nun eine kleine Nachricht m (Message) die wir mit Diffie-Hellmann verschlüsseln wollen. Auf den ersten Blick wäre y = m XOR K_Sitzung eine gute Wahl. Diese Methode würde auf dem One Time Pad basieren und wäre halbwegs sicher.  Allerdings verwendet die El Gamal Verschlüsselung eine weitere Möglichkeit: y = m *  K_Sitzung

El Gamal Verschlüsselung 

• vorgeschlagen im Jahr 1985

Initialisierungsphase

1. wähle eine große Primzahl P
2. wähle primitives Element A
3. wähle privaten Schlüssel a aus { 2; 3; ... ; P - 2 }
4. berechne Β = A^α mod P
5. K_pub = ( P; A; B)

Ablauf der El Gamal Verschlüsselung

Das Protokoll hält sich nicht an den Ablauf des Diffie-Hellmann Protokolls, dies macht die Verschlüsselung effizienter da praktisch nur zwei Verbindungen nötig sind um Schlüsseltausch und Nachrichtenübertragung durchzuführen.

Korrektheit von El Gamal

wir weisen nach dass bei der Entschlüsselung wieder der Klartext  heraus kommt.

y * K_Sitzung^-1  = y * (K^α)^-1 = m * K_Sitzung * ((Aⁱ)^α)^-1 = m * Bⁱ * A^-iα = A^iα * A^-iα * m = A^iα-iα * m = A⁰ * m = m _q.e.d.

Praktische Aspekte von El Gamal

Komplexität des Algorithmus 

Angenommen Alice und Bob bleiben die gleichen, sind für jede Nachricht m die folgenden Rechenoperationen nötig:

Verschlüsselung:

• Exponentation: K_Sitzung = Bⁱ mod P
• Exponentation: K = Aⁱ mod P
• Multiplikation:  y = m *  K_Sitzungmod P

Entschlüsselung:

• Exponentation:  K^α
• Invertierung: (K^α)^-1 
• Multiplikation: m = y * (K^α)^-1

Bei der Entschlüsselung lassen sich die Exponensation und Invertierung in einem Schritt zusammenfassen:

Nach Eulers Theorem gilt A^φ(P) = 1 mod P und A^{P - 1} = 1 mod P. Daraus folgt für diese Anwendung: (K^α)^-1 = K^-α * 1 mod P = K^-α * K^P-1 = K^P-1-α mod P

Sicherheit von El Gamal

El Gamal beruht auf der Schwierigkeit den diskreten Logarithmus in Z_P^* zu berechnen, von daher sollte P > 2¹⁰²⁴ Bit sein. Des weiteren muss A gewisse Eigenschaften aufweisen auf die ich hier vorerst nicht eingehen werde.