Přeskočit na obsah

ElGamal

Z Wikipedie, otevřené encyklopedie

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í.