Das Problem des diskreten Logarithmus auf elliptischen Kurven wird von einigen Public-Key-Kryptosystemen benutzt, da sich, gegeben , die Koordinaten von in 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 zur Basis gesucht, oder . Das Verfahren von Semaev ist dann anwendbar, wenn die von erzeugte zyklische Untergruppe die Mächtigkeit der Charakteristik1 des der elliptischen Kurve zugrundeliegenden Körpers besitzt. Liegt dieser Fall vor, gibt es einen effizient zu berechnenden Monomorphismus2 (im folgenden genannt) von in die additive Gruppe des Körpers , in der wir bekanntlich recht leicht rechnen können.
Auf die Gleichung unseres gegebenen Problems wenden wir nun diesen Monomorphismus an und erhalten , was wir nun, da wir uns in befinden, leicht zu auflösen können, womit wir den diskreten Logarithmus durch zweimaliges Auswerten von und einer kurzen Rechnung in erhalten.
Wenn wir nun, wie im folgenden dargelegt wird, 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.
Stefan Röhrich stefan@roehri.ch