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íč y_{i} a vypočte veřejný klíč k^{pub}_i jakog^{y_i} \mod \quad q Pokud potom posílá A zprávu P uživateli B (zpráva musí být menší než q), probíhá komunikace podle následujícího schématu.

  • je zvoleno náhodné číslo k.
  • A spočte g^{k} \mod q a  Q = P \circ (g^{y_B})^{k} \mod \quad q a obě tato čísla pošle uživateli B.
  • Uživatel B spočte (g^k)^{y_B} \mod q a k tomuto číslu určí inverzní prvek (vzhledem k operaci \circ ).
  • Uživatel B spočte zprávu P jako P = Q \circ ((g^k)^{y_B})^{-1}.

Korektnost algoritmu[editovat | editovat zdroj]

S využitím vět algebry za daných předpokladů platí: (P \circ (g^{y_B})^{k} \circ ((g^k)^{y_B})^{-1}  ) \mod \quad q = (P \circ (g^{y_B})^k \circ ((g^{y_B})^k )^{-1}  ) \mod \quad q = P

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