Elgamal-encryptiesysteem
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. Het wordt gebruikt voor zowel encryptie van gegevens als het genereren van digitale handtekeningen.

Systeemsetup 

Beschrijf een cyclische groep  van orde , gegenereerd door .

Kies een willekeurige . Dit is je privésleutel.

Bereken . Je publieke sleutel is nu .

Encryptie 

Vertaal een bericht  naar elementen uit .

Kies nu een willekeurige .

Versleutel de tekst als volgt:
.

Decryptie 
Een gegeven  van vorm  wordt als volgt ontsleuteld:
. 

Uitgeschreven is dit gelijk aan 
. 

Omdat  kunnen we dit verder uitschrijven als 
.

Voorbeeld 
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 

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 
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 
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. Als de gekozen groep zwakker is (i.e. een naïever versleutelde tekst) zijn aanvallen waarschijnlijker. 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 

Cryptografie