ElGamal encryption

V kryptografii je šifrovací systém ElGamal asymetrický kľúčový šifrovací algoritmus pre kryptografiu s verejným kľúčom, ktorý je založený na výmene kľúčov Diffie–Hellman . Opísal ho Taher Elgamal v roku 1985. Šifrovanie ElGamal sa začalo používať v bezplatnom softvéri GNU Privacy Guard, najnovších verziách PGP a iných kryptosystémoch. ElGamal algoritmus digitálneho podpisu (DSA) je variant podpisovej schémy, ktorý by sa nemal zamieňať so šifrovaním ElGamal.

Šifrovanie ElGamal môže byť definované pre akúkoľvek cyklickú skupinu $G$, ako multiplikatívna skupina celých čísel modulo n. Jeho bezpečnosť závisí od zložitosti určitej úlohy nad touto cyklickou grupou $G$, súvisiacej s výpočtom diskrétnych logaritmov .

Algoritmus

Šifrovanie ElGamal pozostáva z troch komponentov: generátor kľúča, šifrovací algoritmus a dešifrovací algoritmus.

Generovanie kľúčov

Prvá strana, Alica, vygeneruje pár kľúčov takto:

• Vytvorí efektívny popis cyklickej grupy $G\,$ rádu $q\,$ s generátorom $g$ . Nechaj $e$ predstavuje neutrálny prvok množiny $G$ .
• Vyberie celé číslo $x$ náhodne z množiny $\{1,\ldots ,q-1\}$ .
• Vypočíta $h:=g^{x}$ .
• Verejný kľúč pozostáva z hodnôt $(G,q,g,h)$ . Alica zverejní tento verejný kľúč a ponechá si $x$ ako jej súkromný kľúč, ktorý musí zostať v tajnosti.

Šifrovanie

Druhá strana, Braňo, zašifruje správu $M$ Alici s jej verejným kľúčom $(G,q,g,h)$ nasledovne:

• Zobrazí správu $M$ ako prvok $m$ z grupy $G$ pomocou funkcie inverzného zobrazenia.
• Vyberie celé číslo $y$ náhodne z množiny $\{1,\ldots ,q-1\}$ .
• Vypočíta $s:=h^{y}$ . Toto sa nazýva zdieľaný tajný kľúč.
• Vypočíta $c_{1}:=g^{y}$ .
• Vypočíta $c_{2}:=m\cdot s$ .
• Braňo posiela šifrovaný text $(c_{1},c_{2})$ Alici.

Note that if one knows both the ciphertext  and the plaintext , one can easily find the shared secret , since . Therefore, a new  and hence a new  is generated for every message to improve security. For this reason, y is also called an ephemeral key.

Je potrebné si uvedomiť, že ak poznáme šifrovaný text $(c_{1},c_{2})$ aj pôvodný text $m$, je možné ľahko zistiť zdieľaný tajný kľúč, pretože $c_{2}\cdot s^{-1}=m$ . Z tohoto dôvodu, pre zvýšenie bezpečnosti, je pre šifrovanie každej ďalšej správy generované nové číslo $y$ a teda aj nový tajný kľúč $s$ . Preto tento tajný kľúč dostal prívlastok dočasný.

Dešifrovanie

Alica dešifruje zašifrovaný text $(c_{1},c_{2})$ s jej súkromným kľúčom $x$ nasledovne:

• Vypočíta $s:=c_{1}^{x}$ . Potom $c_{1}=g^{y}$, $c_{1}^{x}=g^{xy}=h^{y}$, a teda ide o rovnaký zdieľaný tajný kľúč, aký použil Braňo pri šifrovaní.
• Vypočíta $s^{-1}$, inverzný prvok $s$ v grupe $G$ . Dá sa to vypočítať jedným z niekoľkých spôsobov. Ak $G$ je podgrupa multiplikatívnej skupiny celých čísel modulo $n$, kde $n$ je prvočíslo, modulárne multiplikatívne inverzné číslo možno vypočítať pomocou rozšíreného euklidovského algoritmu . Alternatívou je počítať $s^{-1}$ ako $c_{1}^{q-x}$ . Toto je inverzné číslo $s$ na základe Lagrangeovej vety, keďže $s\cdot c_{1}^{q-x}=g^{xy}\cdot g^{(q-x)y}=(g^{q})^{y}=e^{y}=e$ .
• Vypočíta $m:=c_{2}\cdot s^{-1}$ . Tento výpočet vytvorí pôvodnú správu $m$, pretože $c_{2}=m\cdot s$ ; teda $c_{2}\cdot s^{-1}=(m\cdot s)\cdot s^{-1}=m\cdot e=m$ .
• Urobí zobrazenie $m$ späť na správu vo formáte obyčajného textu $M$ .

Praktické využitie

Ako väčšina systémov s verejným kľúčom, aj kryptosystém ElGamal sa zvyčajne používa ako súčasť hybridného kryptosystému, kde je samotná správa šifrovaná pomocou symetrického kryptosystému a ElGamal sa potom používa na šifrovanie iba symetrického kľúča. Je to preto, že asymetrické kryptosystémy ako ElGamal sú zvyčajne pomalšie ako symetrické pre rovnakú úroveň bezpečnosti, takže je rýchlejšie zašifrovať správu, ktorá môže byť ľubovoľne veľká, pomocou symetrickej šifry a potom použiť ElGamal iba na zašifrovanie symetrického kľúča, ktorý je zvyčajne dosť malý v porovnaní s veľkosťou správy.

Bezpečnosť

Bezpečnosť schémy ElGamal závisí od vlastností základnej grupy $G$ ako aj akúkoľvek schému pre zarovnanie správ na požadovanú dĺžku. Ak v základnej cyklickej grupe $G$ platí výpočtový Diffie-Hellmanov predpoklad (CDH), potom je funkcia šifrovania jednosmerná .

Ak platí rozhodovací Diffie-Hellmanov predpoklad (DDH) pre $G$, potom ElGamal dosiahne sémantickú bezpečnosť . Na dosiahnutie sémantickej bezpečnosti nestačí len platnosť Diffie-Hellmanovho predpokladu.

Šifrovanie ElGamal je bezpodmienečne poddajné, a preto nie je bezpečné voči útoku na vybraný šifrovaný text . Napríklad vzhľadom na šifrovanie $(c_{1},c_{2})$ nejakej správy $m$, možno ľahko vytvoriť platné šifrovanie $(c_{1},2c_{2})$ správy $2m$ .

Na dosiahnutie bezpečnosti zvoleného šifrového textu je potrebné šifrovaciu schému ďalej upravovať alebo použiť vhodný algoritmus pre zarovnanie textu na požadovanú dĺžku. V závislosti od modifikácie môže alebo nemusí byť splnený nutný predpoklad DDH.

Boli navrhnuté aj iné schémy súvisiace s ElGamal, ktoré dosahujú bezpečnosť voči útoku na vybraný šifrovaný text. Kryptosystém Cramer–Shoup je to bezpečný voči spomínanému útoku za predpokladu, že DDH platí pre $G$ . Ďalšou navrhovanou schémou je DHAES .

Efektívnosť

Šifrovanie ElGamal je stochastické, čo znamená, že jeden otvorený text možno zašifrovať do mnohých možných šifrovaných textov, čo má za následok, že všeobecné šifrovanie ElGamal vytvára zašifrovanú správu, ktorá môže byť až dvojnásobne veľká voči pôvodnému textu.

Šifrovanie v rámci ElGamal vyžaduje dve umocňovania, avšak tieto umocnenia sú nezávislé od správy a v prípade potreby sa dajú vypočítať vopred. Dešifrovanie vyžaduje jedno umocnenie a jeden výpočet inverznej grupy, ktoré sa však dajú ľahko spojiť len do jedného umocnenia.

Ďalšie čítanie

• A. J. Menezes; P. C. van Oorschot; S. A. Vanstone. „Kapitola 8.4 Šifrovanie verejným kľúčom ElGamal“ (PDF). Príručka aplikovanej kryptografie. CRC Press.
• Dan Boneh (1998). Problém rozhodovania Diffie-Hellman. Poznámky z prednášok z informatiky. Vol. 1423. s. 48–63. CiteSeerX 10.1.1.461.9971. doi:10.1007/BFb0054851. ISBN 978-3-540-64657-0.