ElGamal

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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ť 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íč a vypočte veřejný klíč jako Pokud potom posílá A zprávu P uživateli B (zpráva musí být menší než ), probíhá komunikace podle následujícího schématu.

  • je zvoleno náhodné číslo .
  • A spočte a a obě tato čísla pošle uživateli B.
  • Uživatel B spočte a k tomuto číslu určí inverzní prvek (vzhledem k operaci ).
  • Uživatel B spočte zprávu P jako .

Korektnost algoritmu[editovat | editovat zdroj]

S využitím vět algebry za daných předpokladů platí:

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 výpočetně složitý problém.