ElGamal-kryptering

Från Rilpedia

(Omdirigerad från ElGamal)
Hoppa till: navigering, sök
Wikipedia_letter_w.pngTexten från svenska WikipediaWikipedialogo_12pt.gif
rpsv.header.diskuteraikon2.gif

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

För att dekryptera chiffertexten (c1,c2) 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.

Fotnoter

  1. Taher ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", IEEE Transactions on Information Theory, v. IT-31, n. 4, 1985, pp469–472 or CRYPTO 84, pp10–18, Springer-Verlag.


Personliga verktyg