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^[1]. 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 ${\displaystyle G}$. Krypteringens säkerhetsnivå beror på svårigheten på ett problem i ${\displaystyle 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 ${\displaystyle G}$ av ordning ${\displaystyle q}$ och generator ${\displaystyle g}$.
• Bob tar ett slumpmässigt utvalt ${\displaystyle x}$ från ${\displaystyle \{0,\ldots ,q-1\}}$.
• Bob beräknar

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

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

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

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

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

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

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

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

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

Detta fungerar eftersom

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

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

Fotnoter