Elgamal-encryptiesysteem

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Het ElGamal-cryptosysteem is een asymmetrisch encryptieschema om gegevens te versleutelen, vergelijkbaar met RSA. In tegenstelling tot RSA is de veiligheid van ElGamal gebaseerd op het discreet logaritme in cyclische groepen. Het is ontworpen door Taher Elgamal en in 1985 voor het eerst gepubliceerd[1]. Het wordt gebruikt voor zowel encryptie van gegevens als het genereren van digitale handtekeningen.

Encryptie[bewerken]

Beschrijf een cyclische groep G van orde q, gegenereerd door g.

Kies een willekeurige x \in \{0,...,q-1\}. Dit is je privésleutel.

Bereken e=g^x. Je publieke sleutel is nu g,q,e.

Vertaal een bericht m naar elementen uit G.

Kies nu een willekeurige y \in \{0,...,q-1\}

Versleutel de tekst als volgt: m_e = (c1, c2) = (g^y, m \cdot e^y)

Decryptie[bewerken]

Een gegeven m_e van vorm (c1,c2) wordt als volgt ontsleuteld:

m = \frac{c_2}{c_1^x}.

Uitgeschreven is dit gelijk aan

m = \frac{c_2}{c_1^x} = \frac{m \cdot e^y}{g^{x \cdot y}}.

Omdat e=g^x kunnen we dit verder uitschrijven als

m = \frac{m \cdot g^{x \cdot y}}{g^{x \cdot y}}.

Voorbeeld[bewerken]

Alice en Bob communiceren met elkaar en versleutelen hun berichten met ElGamal. Bob heeft zijn publieke sleutel aan Alice doorgegeven, maar zijn privésleutel x geheimgehouden. Alice wil een bericht naar Bob versturen. Ze heeft de publieke sleutel van Bob en weet dus g,q,e. Deze hebben respectievelijk de waarde 7,15,343. Ze wil het bericht m=8 versturen. Ze kiest een willekeurige y \in \{0,...,q-1\} = 4. Ze berekent nu

(c1,c2) als (7^4, 8 \cdot 343^4) = (2401, 110730297608)

en verstuurt dit naar Bob. Bob kan het ontvangen bericht nu als enige ontsleutelen met zijn geheime sleutel x=3. Hiervoor berekent hij

m=\frac{c_2}{c_1^x} = \frac{110730297608}{2401^3} = 8.

Veiligheid[bewerken]

De veiligheid van teksten die zijn versleuteld met ElGamal hangt voornamelijk af van de cryptografische sterkte van G. Bij een sterke G is ElGamal veilig tegen standaard methodes van cryptanalyse[2]. Als de gekozen groep zwakker is (i.e. een naïever versleutelde tekst) zijn aanvallen waarschijnlijker[3]. Hierbij moet wel vermeld worden dat eventuele kraakalgoritmen nog verre van efficiënt zijn. Mede door dit feit wordt de veiligheid van ElGamal op dit moment als hoog beschouwd. Als het Diffie-Hellman-probleem opgelost zou kunnen worden zou daardoor de veiligheid van ElGamal ook in het geding zijn.

Voetnoten[bewerken]

  1. Elgamal, T., "A public key cryptosystem and a signature scheme based on discrete logarithms", IEEE Transactions on Information Theory, v. 31, n. 4, 1985, pp. 469-472
  2. Claus Peter Schnorr and Markus Jakobsson: "Security of Signed ElGamal Encryption", Advances in Cryptology - Asiacrypt 2000: 6th International Conference on the theory and application of Cryptology and Information Security
  3. Dan Boneh, Antoine Joux, Phong Q. Nguyen, "Why Textbook ElGamal and RSA Encryption Are Insecure", Advances in Cryptology - ASIACRYPT 2000: 6th International Conference on the Theory and Application of Cryptology and Information Security, Kyoto, Japan, December 2000. Proceedings