Elgamal-encryptiesysteem

(Doorverwezen vanaf Elgamal)

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 de discrete 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.

Systeemsetup bewerken

Beschrijf een cyclische groep   van orde  , gegenereerd door  .

Kies een willekeurige  . Dit is je privésleutel.

Bereken  . Je publieke sleutel is nu  .

Encryptie bewerken

Vertaal een bericht   naar elementen uit  .

Kies nu een willekeurige  .

Versleutel de tekst als volgt:  .

Decryptie bewerken

Een gegeven   van vorm   wordt als volgt ontsleuteld:

 .

Uitgeschreven is dit gelijk aan

 .

Omdat   kunnen we dit verder uitschrijven als

 .

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   geheimgehouden. Alice wil een bericht naar Bob versturen. Ze heeft de publieke sleutel van Bob en weet dus  . Deze hebben respectievelijk de waarde  . Ze wil het bericht   versturen. Ze kiest een willekeurige  . Ze berekent nu

  als  

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

 .

In de praktijk wordt een asymmetrisch encryptieschema zoals ElGamal gebruikt om een sleutel voor een symmetrisch encryptieschema uit te wisselen tussen Alice en Bob. Het symmetrische encryptieschema wordt dan gebruikt voor verdere communicatie.

Digitale handtekening bewerken

Neem een cryptografische hashfunctie  . De gebruikte hashfunctie is publiek.

Neem nu  .

Vertaal een bericht   naar elementen uit  .

Kies nu een willekeurige  . Deze   kan maar een keer gebruikt worden.

Bereken  .

Genereer de handtekening als volgt:

 .

De uiteindelijke handtekening is dan  .

Het bericht   kan geverifieerd worden door te kijken of het volgende klopt:

 .

Als dit zo is, dan is het zeker dat het bericht   gestuurd is door iemand die privésleutel   heeft.

Als de willekeurige   hergebruikt wordt, is het mogelijk om de privésleutel te achterhalen. Sinds   en   bekend zijn, is het mogelijk om privésleutel   uit   te krijgen, gegeven   en  :

 
 
 
 

Dit is op te lossen voor   (te controleren door te kijken of   gelijk is aan  ). Zodra   gevonden is, kan   gevonden worden:

 .

Voorbeeld bewerken

Bob wil nu een bericht   naar Alice sturen, en haar ervan verzekeren dat hij het bericht verstuurd heeft. Hij neemt als hashfunctie  . Zijn publieke sleutel is  , en zijn privésleutel is  . Hij kiest als random waarde   met als gevolg dat  . Bob berekent nu zijn handtekening als volgt:

 

De handtekening is dan  . Bob stuurt naar Alice het volgende:  . Als Alice will achterhalen moet ze kijken of het volgende klopt:

 
 
 

Mocht Bob naar Alice een tweede bericht   met identieke   sturen, dan kan Alice zodanig zijn privésleutel achterhalen:

 
 
 
 

Veiligheid bewerken

De veiligheid van teksten die zijn versleuteld met ElGamal hangt voornamelijk af van de cryptografische sterkte van  . Bij een sterke   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