ElGamal-kryptering

ElGamal-kryptering är inom kryptografin ett system som baseras på asymmetrisk kryptering och Diffie-Hellmans nyckelöverföring. Systemet uppfanns av Taher Elgamal 1984. ElGamal används bl.a. av GNU Privacy Guard (GPG), nyare versioner av Pretty Good Privacy (PGP).

ElGamal-kryptering kan definieras med hjälp av en cyklisk grupp $G$. Krypteringens säkerhetsnivå beror på svårigheten på ett problem i $G$ relaterat till beräkning av diskreta logaritmer.

Algoritmen

ElGamal-kryptering består av tre komponenter: nyckelgeneratorn, krypteringsalgoritmen och dekrypteringsalgoritmen.

Nyckelgeneratorn fungerar enligt följande, i en situation där Bob vill kunna ta emot krypterade meddelanden:

• Bob genererar en effektiv beskrivning av en cyklisk grupp $G$ av ordning $q$ och generator $g$.
• Bob tar ett slumpmässigt utvalt $x$ från $\{0,\ldots ,q-1\}$.
• Bob beräknar

$\left.h=g^{x}\right.$.

• Bob delar ut $h$ tillsammans med beskrivningen av $G,q,g$ som sin publika nyckel. Bob behåller $x$ som sin privata nyckel, som hålls hemlig.

När Alice vill skicka ett hemligt meddelande $M$ till Bob, krypterar hon det med hans publika nyckel $(G,q,g,h)$, enligt krypteringsalgoritmen:

• Alice konverterar $M$ till ett element $m$ i $G$.
• Alice väljer ett slumpmässigt $y$ ur $\{0,\ldots ,q-1\}$, och beräknar sedan

$\left.c_{1}=g^{y}\right.$ och

$c_{2}=m\cdot h^{y}.$

• Alice sänder chiffertexten $(c_{1},c_{2})$ till Bob.

För att dekryptera chiffertexten $(c_{1},c_{2})$ använder Bob sin privata nyckel $x$, enligt dekrypteringsalgoritmen:

• Bob beräknar $m=c_{2}\cdot c_{1}^{-x}$.

Detta fungerar eftersom

$c_{2}\cdot c_{1}^{-x}=m\cdot h^{y}\cdot g^{-xy}=m\cdot g^{xy}\cdot g^{-xy}=m.$

Om meddelandet $M$ är för stort för $G$ kan det delas upp i flera delar, där varje del kan krypteras individuellt.