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 a g co nejvyššího řádu. I-tý účastník si volí svůj tajný klíč $y_{i}$ a vypočte veřejný klíč $k^{pub}_i$ 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 $(q^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 ((q^k)^{y_B})^{-1}$.

Korektnost algoritmu

S využitím vět algebry za daných předpokladů platí: $(P \circ (q^{y_B})^{k} \circ ((q^k)^{y_B})^{-1} ) \mod \quad q = (P \circ (q^{y_B})^k \circ ((q^{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