Überblick über das Verfahren

Das Problem des diskreten Logarithmus auf elliptischen Kurven wird von einigen Public-Key-Kryptosystemen benutzt, da sich, gegeben $P \in E(\mathbbm{F}_q)$, die Koordinaten von $n P$ in $O(\log n \log^3 q)$ Bitoperationen berechnen lassen ([Kob94] Proposition VI.2.1.), wenn die elliptische Kurve als Weierstraß-Gleichung (wie in (1)) gegeben ist, aber, wie oben schon erwähnt, im allgemeinen Fall keine polynomialen Algorithmen zur Berechnung des DLOGs bekannt sind. Konkrete Beschreibung von Kryptoverfahren, die auf elliptischen Kurven beruhen, findet man in der in 1 erwähnten Literatur.

Hier soll nun ein Verfahren zur polynomialen Berechnung des diskreten Logarithmus in bestimmten Sonderfällen vorgestellt werden, das I. A. Semaev in [Sem98] beschreibt und an dessen Artikel sich auch diese Ausarbeitung hält.

Im folgenden sei der diskrete Logarithmus von einem Punkt $Q$ zur Basis $P$ gesucht, $n:= \mathop{\rm dlog} \nolimits _P(Q)$ oder $Q = nP$. Das Verfahren von Semaev ist dann anwendbar, wenn die von $P$ erzeugte zyklische Untergruppe die Mächtigkeit der Charakteristik¹ des der elliptischen Kurve zugrundeliegenden Körpers besitzt. Liegt dieser Fall vor, gibt es einen effizient zu berechnenden Monomorphismus² (im folgenden $\phi$ genannt) von $\langle P \rangle \subset E(\mathbbm{F}_q)$ in die additive Gruppe des Körpers $\mathbbm{F}_q$, in der wir bekanntlich recht leicht rechnen können.

Auf die Gleichung $Q = nP$ unseres gegebenen Problems wenden wir nun diesen Monomorphismus $\phi$ an und erhalten $\phi(Q) = n \phi(P)$, was wir nun, da wir uns in $\mathbbm{F}_q$ befinden, leicht zu $n = \frac{\phi(Q)}{\phi(P)}$ auflösen können, womit wir den diskreten Logarithmus durch zweimaliges Auswerten von $\phi$ und einer kurzen Rechnung in $\mathbbm{F}_q$ erhalten.

Wenn wir nun, wie im folgenden dargelegt wird, $\phi$ in polynomialer Zeit berechnen können, können wir in unserem betrachteten Spezialfall diskrete Logarithmen effizient berechnen und machen diese Fälle damit unbrauchbar für die Anwendung in Kryptosystemen.