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 het Discrete Logaritme Probleem 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.

Encryptie

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

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

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

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