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ť je zvolena veřejně známá cyklická grupa, tzn. celé číslo , tzv. modul grupy, a celé číslo , tzv. generátor dané grupy. Potom si i-tý účastník volí svůj tajný klíč , tak, že a vypočte veřejný klíč jako , jenž zveřejní. Pokud potom chce poslat uživatel zprávu uživateli (zpráva musí být menší než ), musí znát veřejný klíč , tzn. . Poté probíhá komunikace podle následujícího schématu.
zvolí náhodné číslo takové, že .
spočte , a a pošle pár uživateli .
Uživatel spočte a k tomuto číslu určí inverzní prvek (vzhledem k operaci v grupě ).
Uživatel spočte zprávu jako .
Korektnost algoritmu
S využitím vět algebry platí:
- generátor, - modul cyklická grupa v modulu q.
a jsou soukromé klíče a
a ekvivalentně pro
je veřejný klíč a je soukromý sdílený klíč pro šifrování komunikace mezi a
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 nepolynomiální problém, protože v současnosti neexistuje algoritmus, který by zvládl vypočítat diskrétní logaritmus v cyklické grupě s polynomiální složitostí.
Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.