ElGamal-kryptering

ElGamal-kryptering är inom kryptografin ett system som baseras på asymmetrisk kryptering och Diffie-Hellmans nyckelöverenskommelse. 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.