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 . Krypteringens säkerhetsnivå beror på svårigheten på ett problem i relaterat till beräkning av diskreta logaritmer.

Algoritmen redigera

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   av ordning   och generator  .
  • Bob tar ett slumpmässigt utvalt   från  .
  • Bob beräknar
 .
  • Bob delar ut   tillsammans med beskrivningen av   som sin publika nyckel. Bob behåller   som sin privata nyckel, som hålls hemlig.

När Alice vill skicka ett hemligt meddelande   till Bob, krypterar hon det med hans publika nyckel  , enligt krypteringsalgoritmen:

  • Alice konverterar   till ett element   i  .
  • Alice väljer ett slumpmässigt   ur  , och beräknar sedan
  och
 
  • Alice sänder chiffertexten   till Bob.

För att dekryptera chiffertexten   använder Bob sin privata nyckel  , enligt dekrypteringsalgoritmen:

  • Bob beräknar  .

Detta fungerar eftersom

 

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

Fotnoter redigera

  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.