4.2 ElGamal

Das ElGamal-Verfahren beruht auf der Schwierigkeit, diskrete Logarithmen zu berechen, also der Bestimmung von a aus bekanntem β = α^a(mod p), wobei p eine Primzahl ist.

Wie beim RSA-Verfahren können mit der hier vorgestellten Form nur Zahlen verschlüsselt werden; Texte müssen wieder entsprechend kodiert werden.

Das ElGamal-Verfahren besteht aus drei Schritten

1. Schlüsselerzeugung:
• Wähle eine große Primzahl p (vgl. 2.3.2), so daß (p - 1) / 2 ebenfalls Primzahl ist^* (vgl. 2.3.1).
  N sei die Anzahl der Bits von p.
• Wähle eine Basis α < p.
• Wähle einen geheimen Schlüssel a < p.
• Berechne β = α^a(mod p)
• Veröffentliche p, α und β als öffentlichen Schlüssel.



2. Verschlüsselung einer Nachricht:
• Zerlege den Klartext in Blöcke zu je N - 1 Bit (evtl. auffüllen).
• Wähle geheime Zufallszahl k, die zu p - 1 teilerfremd ist, also  ggT(k, p - 1) = 1 (vgl. 2.1)
• Berechne für jeden Block x den Geheimtext
  
      e (x, k) = (y₁, y₂),   wobei
      y₁ = α^k(mod p)   und   y₂ = β^kx (mod p).
  Dabei sind y₁ und y₂ jeweils Geheimtextblöcke der Länge N.



3. Entschlüsselung:
• Zerlege den Geheimtext in N-Bit Blöcke
• Für jeweils zwei aufeinanderfolgende Blöcke y₁ und y₂ löse
      y₁^a x = y₂ (mod p)
  nach x auf. Also ist
      d (y₁, y₂) = x = y₂ (y₁^a )^-1 (mod p)
  der gesuchte Klartextblock.

^* Für den Spezialfall, daß (p - 1) / 2 ebenfalls eine Primzahl ist, gibt einen effizienten Algorithmus zur Berechnung des diskreten Logarithmus.


4.2 ElGamal: Beispiel-Applet für kleine Zahlen


source

4.3 Elliptische Kurven