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í.
Zdroj
Poslední aktualizace obsahu: 2023-12-03 01:42:38
Zdroj: Wikipedia (autoři článku ElGamal)
Licence textu: CC-BY-SA-3.0 Unported
Tento článek byl automaticky přejat z Wikipedie. Na obrázcích nebyly provedeny žádné změny. Obrázky se zobrazují ve zmenšené velikosti (jako miniatury). Kliknutím na obrázek získáte další informace o autorovi a licenci. Byly změněny prvky designu, odstraněny některé odkazy specifické pro Wikipedii (např. odkazy na Editaci a nebo na neexistující hesla) a provedena optimalizace pro rychlé načítání.