ElGamal

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ému

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íč $y_{i}$ a vypočte veřejný klíč $k_{i}^{pub}$ jako $g^{y_{i}}\mod \quad q$ Pokud potom posílá A zprávu P uživateli B (zpráva musí být menší než $q$), probíhá komunikace podle následujícího schématu.

• je zvoleno náhodné číslo $k$.
• A spočte $g^{k}\mod q$ a $Q=P\circ (g^{y_{B}})^{k}\mod \quad q$ a obě tato čísla pošle uživateli B.
• Uživatel B spočte $(g^{k})^{y_{B}}\mod q$ a k tomuto číslu určí inverzní prvek (vzhledem k operaci $\circ$).
• Uživatel B spočte zprávu P jako $P=Q\circ ((g^{k})^{y_{B}})^{-1}$.

Korektnost algoritmu

S využitím vět algebry za daných předpokladů platí: $(P\circ (g^{y_{B}})^{k}\circ ((g^{k})^{y_{B}})^{-1})\mod \quad q=(P\circ (g^{y_{B}})^{k}\circ ((g^{y_{B}})^{k})^{-1})\mod \quad q=P$

Analýza

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.