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 1985^[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 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, ..., q – 1}.
• Bob beräknar h = g^x.
• Bob delar ut h tillsammans med beskrivningen av G, q och 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, ..., q – 1}, och beräknar sedan c₁ = g^y och c₂ = m ⋅ h^y.
• Alice sänder chiffertexten (c₁, c₂) till Bob.

För att dekryptera chiffertexten (c₁, c₂) använder Bob sin privata nyckel x, enligt dekrypteringsalgoritmen:

• Bob beräknar m = c₂ ⋅ c₁^-x.

Detta fungerar eftersom c₂ ⋅ c₁^-x = m ⋅ h^y ⋅ g^-xy = m ⋅ g^xy ⋅ 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.