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

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

Korektnost algoritmu

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

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

${\displaystyle \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í.