Direkt zum Inhalt

Lexikon der Mathematik: ElGamal-Verfahren

eine asymmetrische Verschlüsselung, die das Potenzieren in einem endlichen Körper ℤp benutzt, und bei der die Sicherheit auf der algorithmischen Schwierigkeit der Bestimmung des diskreten Logarithmus in diesem Körper beruht.

Die Grundidee des von Taher ElGamal entwickelten Verfahrens ist ähnlich wie die des Diffie-Hellman-Verfahrens. Öffentlicher Schlüssel sind hier eine große Primzahl p (beispielsweise 1024 Bit), ein Element g mit hoher Ordnung aus dem endlichen Körper ℤp (beispielsweise ein primitives Element) und ein Element ga mod p. Der Exponent a ist der zugehörige geheime Schlüssel.

Will Bob eine Nachricht m für Alice verschlüsseln, so wählt er eine Zufallszahl r und berechnet \begin{eqnarray}{c}_{1}={g}^{r}\,\mathrm{mod}\,p\,\,\text{und}\,\,{c}_{2}=m{({g}^{a})}^{r}\,\mathrm{mod}\,p\end{eqnarray} mit Hilfe des öffentlichen Schlüssels von Alice. Beide Werte bilden zusammen das Chiffrat (c1, c2), aus dem Alice durch Berechnung von \begin{eqnarray}{({({c}_{1})}^{a})}^{-1}{c}_{2}\,\mathrm{mod}\,p=m\end{eqnarray} den Klartext entschlüsselt.

Um das ElGamal-Verfahren brechen zu können, reicht es aus, wenn man den diskreten Logarithmus berechnen kann. Der beste dafür gegenwärtig bekannte Algorithmus hat allerdings eine Laufzeit von \begin{eqnarray}{e}^{(1+O(1)){(\mathrm{ln}p)}^{0.5}{(\mathrm{ln}\,\mathrm{ln}\,p)}^{0.5}},\end{eqnarray} so daß das Problem für hinreichend große Zahlen p faktisch unlösbar ist.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.