ElGamal

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 $\mathbb {Z} _{q}^{\circ }$, tzn. celé číslo $q$, tzv. modul grupy, a celé číslo $g$, tzv. generátor dané grupy. Potom si i-tý účastník volí svůj tajný klíč $k_{i}$, tak, že $0<k_{i}<q$ a vypočte veřejný klíč $k_{i}^{pub}$ jako $k_{i}^{pub}=g^{k_{i}}\mod q$, jenž zveřejní. Pokud potom chce poslat uživatel $A$ zprávu $P$ uživateli $B$ (zpráva musí být menší než $q$), $A$ musí znát veřejný klíč $B$, tzn. $k_{B}^{pub}$. Poté probíhá komunikace podle následujícího schématu.

• $A$ zvolí náhodné číslo $k_{A}$ takové, že $0<k_{A}<q$.
• $A$ spočte $k_{A}^{pub}=g^{k_{A}}\mod q$, $K=(k_{B}^{pub})^{k_{A}}\mod q$ a $Q=P\circ K\mod q$ a pošle pár $Q,k_{A}^{pub}$ uživateli $B$.
• Uživatel $B$ spočte $K=(k_{A}^{pub})^{k_{B}}\mod q$ a k tomuto číslu určí inverzní prvek $K^{-1}$ (vzhledem k operaci $\circ$ v grupě $\mathbb {Z} _{q}^{\circ }$).
• Uživatel $B$ spočte zprávu $P$ jako $P=Q\circ K^{-1}\mod q$.

Korektnost algoritmu

S využitím vět algebry platí:

• $\forall i,j\in \mathbb {N} ,\forall g$- generátor, $q$ - modul $\in \mathbb {Z} _{q}^{\circ },$ cyklická grupa v modulu q.
• $k_{i}\iff 0<k_{i}<q,k_{j}\iff 0<k_{j}<q$
  • $k_{i}$ a $k_{j}$ jsou soukromé klíče $i$ a $j$
• $k_{i}^{pub}=g^{k_{i}}\mod q\land K=(k_{i}^{pub})^{k_{j}}\mod q$ a ekvivalentně pro $k_{j}^{pub}$
  • $k_{i}^{pub}$ je veřejný klíč a $K$ je soukromý sdílený klíč pro šifrování komunikace mezi $i$ a $j$
• $K=(g^{k_{i}})^{k_{j}}\mod q=(g^{k_{j}})^{k_{i}}\mod q=g^{k_{i}\cdot k_{j}}\mod q$
• $Q\circ K^{-1}\mod q=P\circ K\circ K^{-1}\mod q=P\mod q$

$\square$

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