wichtiges Verfahren zur asymmetrischen Verschlüsselung, dessen Sicherheit auf der Schwierigkeit der Bestimmung des diskreten Logarithmus’ in der Gruppe der Punkte einer elliptischen Kurve über einem endlichen Körper beruht.

Während das RSA-Verfahren deshalb vertrauenswürdig ist, weil die Bestimmung der Ordnung eines Elementes in Restklassenringen ℤ_n mit n = pq schwer ist, beruht die Sicherheit des ElGamal- Verfahrens auf dem Logarithmusproblem in der multiplikativen Gruppe eines Restklassenkörpers ℤ_p. Dieses läßt sich sich auch auf andere Gruppen übertragen.

Man nennt in Analogie zum Körper den diskreten Logarithmus eines Elements a ∈ G einer abelschen Gruppe G zur Basis b diejenige ganze Zahl m, für die m·b = a ist. Ebenso wie man durch Quadrieren und Multiplizieren in einem Körper schnell potenzieren kann, lassen sich in einer abelschen Gruppe die ganzzahligen Vielfachen durch Verdoppeln und Addieren berechnen: Für \( m=\underset{i}{\mathop \sum}\,{{m}_{i}}{{2}^{1}} \) mit m_i ∈ {0, 1} benötigt man für die Berechnung von \begin{eqnarray} m\,.\,b=\underset{i}{\mathop \sum}\,{{m}_{i}}.\left({{2}^{i}}.\,b \right) \end{eqnarray}\( \left\lfloor {{\log}_{2}}m \right\rfloor \) Verdoppelungen und maximal \( \left\lfloor {{\log}_{2}}m \right\rfloor \) Additionen.

Da sich die Verdoppelungen und Additionen der Punkte einer elliptischen Kurve über einem endlichen Körper schnell berechnen lassen, kann man viele kryptographische Verfahren auch effizient auf die abelsche Gruppe der Punkte der Kurve übertragen. Dies wurde erstmalig 1985 unabhängig von Neal Röblitz und Victor Miller vorgeschlagen. So gibt es EC-Analoga für das ElGamal-Verfahren, für die digitale Signatur (ECDSA) und das Diffie-Hellman-Verfahren.

Bei letzterem einigen sich Alice und Bob auf eine öffentliche elliptische Kurve und einen Punkt großer Ordnung P. Beide wählen sich zufällig jeweils eine ganze Zahl a und b und tauschen a · P und b · P über den öffentlichen Kanal aus. Der gemeinsame geheime Schlüssel ist die "-Koordinate des Punktes (ab)·P. Wenn die Ordnung der Gruppe der Punkte einer zufällig gewählten elliptischen Kurve über einem endlichen Körper GF(q) einen großen Primteiler enthält, dann ist das diskrete Logarithmusproblem schwer. Genauer gesagt haben die bisher bekannten Algorithmen eine exponentielle Laufzeit \begin{eqnarray} \exp \left(\left(1+0\left(1 \right. \right) \right)(\ln \,{{\left. p \right)}^{0.5}}\left(\ln \ln p \right)\left. ^{0.5} \right). \end{eqnarray} Deshalb kommt man gegenüber dem RSA-Verfahren (bei dem subexponentielle Algorithmen bekannt sind) bei der Verschlüsselung mit elliptischen Kurven mit kleineren Schlüssellängen aus. Für die gleiche Sicherheit wie bei einem RSA- Verfahren mit 1024 Bit reicht für die Punktegruppe eine Ordnung von etwa 190 Bit. Dabei werden elliptische Kurven über Körpern GF(2^k) der Charakteristik 2 und über Restklassenkörpern ℤ_p verwendet.

Der öffentliche Schlüssel besteht aus allgemeinen Parametern, wie den Koeffizienten der Kurvengleichung und einem Punkt P großer Ordnung m der Punktegruppe, sowie einem individuellen öffentlichen Schlüsselpunkt A = a · P. Der geheime Schlüssel ist der diskrete Logarithmus a = log_PA.

Die Auswahl der allgemeinen Parameter muß sorgfältig erfolgen, da für bestimmte Kurven (beispielsweise solche mit Spur t = 1) das Logarithmusproblem in Polynomialzeit lösbar ist.