ElGamal je jeden z algoritmů asymetrické kryptografie, má ovšem nevýhodu, že šifrovaná data jsou dvakrát delší než data nešifrovaná. To je možná důvodem, proč není jeho nasazení tak masivní[zdroj?], jako nasazení algoritmu RSA, který tímto nedostatkem netrpí. Opírá se o problém výpočtu diskrétního logaritmu.

Konstrukce systémuEditovat

Nechť jsou zvolena veřejně známá čísla q, tzv. modul[zdroj?], a g co nejvyššího řádu. Potom si i-tý účastník volí svůj tajný klíč   a vypočte veřejný klíč   jako   Pokud potom posílá A zprávu P uživateli B (zpráva musí být menší než  ), probíhá komunikace podle následujícího schématu.

  • je zvoleno náhodné číslo  .
  • A spočte   a   a obě tato čísla pošle uživateli B.
  • Uživatel B spočte   a k tomuto číslu určí inverzní prvek (vzhledem k operaci  ).
  • Uživatel B spočte zprávu P jako  .

Korektnost algoritmuEditovat

S využitím vět algebry za daných předpokladů platí:  

AnalýzaEditovat

Na prolomení toho systému by musel útočník vyřešit problém diskrétního logaritmu, což je považováno za výpočetně složitý problém.