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 velké, 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í.
Odkazy
Reference
Kategorie:Kryptografické algoritmy Kategorie:Kryptografie s veřejným klíčem