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íŠablona:Fakt/dne, 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}modq$, 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}modq$, $K=(k_B^{pub}{)}^{k_A}modq$ a $Q=P\circ Kmodq$ a pošle pár $Q,k_A^{pub}$ uživateli $B$.
• Uživatel $B$ spočte $K=(k_A^{pub}{)}^{k_B}modq$ 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}modq$.

Korektnost algoritmu

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

• $\mathrm{\forall }i,j\in \mathbb{N},\mathrm{\forall }g$- generátor, $q$ - modul $\in {\mathbb{Z}}_q^{\circ },$ cyklická grupa v modulu q.
• $k_i⟺0<k_i<q,k_j⟺0<k_j<q$
  • $k_i$ a $k_j$ jsou soukromé klíče $i$ a $j$
• $k_i^{pub}=g^{k_i}modq\wedge K=(k_i^{pub}{)}^{k_j}modq$ 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}modq=(g^{k_j}{)}^{k_i}modq=g^{k_i\cdot k_j}modq$
• $Q\circ K^{-1}modq=P\circ K\circ K^{-1}modq=Pmodq$

$◻$

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