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í, 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 \Z_q^\circ, tzn. celé číslo q, tzv. +more 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 a vypočte veřejný klíč k^{pub}_i jako k^{pub}_i = 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^{pub}_B. Poté probíhá komunikace podle následujícího schématu.

* A zvolí náhodné číslo k_A takové, že 0 . * A spočte k^{pub}_A=g^{k_A} \mod q, K = (k^{pub}_B)^{k_A} \mod q a Q = P \circ K \mod q a pošle pár Q, k^{pub}_A uživateli B. +more * Uživatel B spočte K = (k^{pub}_A)^{k_B} \mod q a k tomuto číslu určí inverzní prvek K^{-1} (vzhledem k operaci \circ v grupě \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 \N, \forall g - generátor, q - modul \in \Z_q^\circ, cyklická grupa v modulu q. * k_i \iff 0 **k_i a k_j jsou soukromé klíče i a j * k^{pub}_i = g ^ {k_i} \mod q \and K = (k^{pub}_i) ^{k_j} \mod q a ekvivalentně pro k^{pub}_j ** k^{pub}_i 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í.

Kategorie:Kryptografické algoritmy Kategorie:Kryptografie s veřejným klíčem