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

Encryptie

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=3$ 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$.

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 $H$. De gebruikte hashfunctie is publiek.

Neem nu $e=g^{x}{\pmod {q}}$.

Vertaal een bericht $m$ naar elementen uit $G$.

Kies nu een willekeurige $k\in \{1,...,q-1\}$. Deze $z$ kan maar een keer gebruikt worden.

Bereken $z=g^{k}{\pmod {q}}$.

Genereer de handtekening als volgt:

$s=k^{-1}(H(m)-x\cdot z){\pmod {q-1}}$.

De uiteindelijke handtekening is dan $(z,s)$.

Het bericht $(m,s)$ kan geverifieerd worden door te kijken of het volgende klopt:

$g^{H(m)}=e^{z}\cdot z^{s}$.

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

Als de willekeurige $k$ hergebruikt wordt, is het mogelijk om de privésleutel te achterhalen. Sinds $q,e$ en $z$ bekend zijn, is het mogelijk om privésleutel $x$ uit $s$ te krijgen, gegeven $(m_{1},(z,s_{1}))$ en $(m_{2},(z,s_{2}))$:

$H(m)=xz+sk{\pmod {q}}$

$xz=H(m)-sk$

$H(m_{1})-s_{1}k=H(m_{2})-s_{2}k$

$H(m_{1})-H(m_{2})=(s_{1}-s_{2})k$

Dit is op te lossen voor $k$ (te controleren door te kijken of $g^{oplossing}$ gelijk is aan $z$). Zodra $k$ gevonden is, kan $x$ gevonden worden:

$x={\frac {H(m)-sk}{z}}$.

Voorbeeld

Bob wil nu een bericht $m=7$ naar Alice sturen, en haar ervan verzekeren dat hij het bericht verstuurd heeft. Hij neemt als hashfunctie $H(m)=m$. Zijn publieke sleutel is $g=2,q=11,e=8$, en zijn privésleutel is $x=3$. Hij kiest als random waarde $k=4$ met als gevolg dat $z=2^{4}=5$. Bob berekent nu zijn handtekening als volgt:

$s=4^{-1}(H(7)-3\cdot 5)=3(7-4)=9{\pmod {10}}$

De handtekening is dan $(5,9)$. Bob stuurt naar Alice het volgende: $(7,(5,9))$. Als Alice will achterhalen moet ze kijken of het volgende klopt:

$2^{H(7)}=8^{5}\cdot 5^{9}{\pmod {11}}$

$7=10\cdot 9$

$7=7$

Mocht Bob naar Alice een tweede bericht $(8,(5,1))$ met identieke $z$ sturen, dan kan Alice zodanig zijn privésleutel achterhalen:

$7-8=(9-1)k{\pmod {11}}$

$10=8k$

$k=4$

$x={\frac {7-9\cdot 4}{5}}={\frac {4}{5}}=4\cdot 5^{-1}=4\cdot 9=3$

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.