2.5 Skalare Multiplikation von Punkten

Für die Kryptographie mit elliptischen Kurven wird, wie später zu sehen ist, häufig das vielfache Addieren eines Punktes benötigt. Daher folgt hier eine Beschreibung eines optimierten Verfahrens dieser Addition und sei skalare Multiplikation genannt.

Unter der skalaren Multiplikation ist das n-fache Addieren eines Punktes auf sich selbst zu verstehen, also P + P + .... + P + P, dies wird als n · P oder kurz nP geschrieben, wobei n in diesem Fall aus Z ist.

Für große n ist die Berechnung von n · P sehr aufwendig, da jedesmal wieder die Steigung berechnet werden muß, liegt es nahe, nach einem vereinfachten Verfahren zu suchen.

Beispiel für n = 25

Abb.2.5.1: 25 · P, eine Vereinfachung

Abbildung 2.5.1 zeigt, wie sich das Addieren der einzelnen Punkte in mehrere Teilprobleme zerlegen läßt. Die Zerlegung in Teilprobleme ist auf Grund der Assoziativität der Gruppe zulässig. So ist in der zweiten Zeile nur noch 12 · (P+P) + P statt 24 mal P zu addieren. (P + P) kann man mit einer Addition berechnen, d.h. es werden 24 - (12 +1 +1) = 10 Additionen eingespart. Die weiteren Zeilen folgen dem gleichen Schema, denn wenn erst einmal (P + P) berechnet ist, dann ist das Ergebnis von (P + P + P + P) nur eine Addition weit entfernt. Im Endeffekt werden nur noch 7 Additionen benötigt, denn

    Benötigte Additionen:
2P = P + P 1
4P = (P + P) +( P + P) 2
8P = (P + P + P + P) + (P + P + P + P) 3
16P = (P + P + P + P + P + P + P + P) + (P + P + P + P + P + P + P + P) 4

Wobei natürlich bei der Berechnung von 16P alle vorherigen skalaren Multiplikationen als "Abfallprodukt" mit berechnet werden.
Die Addition von 16P + 8P + P sind noch einmal zwei Additionen, also sind es 2 + 4 = 6 statt 24 benötigte Additionen.

Bei genauerer Betrachtung erinnert oben Beschriebenes sehr an die Binärdarstellung von Zahlen und wird verglichen; die Binärschreibweise für 25 ist 11001b. Analog dazu kann man obige Addition folgendermaßen schreiben.

1 · 16P + 1 · 8P + 0 · 4P + 0 · 2 P+ 1· 1P = 25P

Für eine beliebiges n

Allgemein berechnet sich also das Produkt einer Zahl n Î Z mit einem Punkt P folgendermaßen:

n schreibt sich in Binärdarstellung als [bz bz-1 ... b2 b1 b0].

Erst muß [bz 0 ... 0 0 0]P berechnet werden, dazu sind genau z Additionen nötig. Danach läßt sich dann

n · P =   bz · [ bz 0 ... 0 0 0]P
  + bz-1 · [0 bz-1 ... 0 0 0]P
  + ...
  + b2 · [0 0 ... b2 0 0]P
  + b1 · [0 0 ... 0 b1 0]P
  + b0 · [0 0 ... 0 0 b0]P
Gl.2.5.1

mit maximal z Addition berechnen. Also werden maximal

2z Gl.2.5.2

Additionen benötigt, wobei

  n » 2z  
Û

z » log2 n

Gl.2.5.3

ist, das ist besonders für große n eine starke Vereinfachung.

zum Anfang | Home
Copyright 1999 by Thomas Laubrock
Zurück zur letzen Seite nächste Seite