Einwegfunktion

Multiplikation mit einer natürlichen Zahl als Einwegfunktion

Für große Zahlen $N$ ist die Vervielfachung $NP$ eines Punktes $P$ auf einer elliptischen Kurve zunächst sehr aufwendig, da $N$ wiederholte Additionen ausgeführt werden müssen.

Zum Beispiel müsste zur Berechnung von $13P$ der Punkt $P$ insgesamt $13$ mal zu sich selbst addiert werden. Allerdings gibt es hierfür einen Trick, der die Berechnung deutlich beschleunigt. Dazu wird die Zahl $13$ zunächst in ihre binäre Darstellung umgewandelt: $$13={1101}_2=8+4+1$$

Wegen der Rechengesezte für die Addition auf elliptischen Kurven gilt nun: $$13P=(8+4+1)P=8P+4P+1P$$

Diese Summe kann nun durch die folgenden Schritte berechnet werden: $$\begin{array}{rcl}2P& =& P+P\\ 4P& =& 2P+2P\\ 8P& =& 4P+4P\\ 13P& =& 8P+4P+1P\end{array}$$

Dieser Trick nennt sich Double and Add-Verfahren. In unserem Beispiel wird damit $13P$ in insgesamt nur noch $5$ Schritten statt der ursprünglichen $13$ Schritte berechnet.

Effizienz des Double and Add-Verfahrens

Die Anzahl der Additionen, die für die Berechnung von $NP$ mit dem Double and Add-Verfahren notwendig sind, hängt von der Anzahl der Einsen in der binären Darstellung von $N$ ab. Für eine natürliche Zahl $N$ mit $n$ Einsen in der binären Darstellung sind insgesamt höchstens $2n$ Additionen notwendig, um $NP$ zu berechnen.

Damit lässt sich für eine natürliche Zahl $N$ die Anzahl an Additionen nach oben wie folgt abschätzen. Die Anzahl $n$ an Einsen in der binären Darstellung von $N$ ist kleiner als ${\log }_{2}N$. Also ist die Anzahl der Additionen kleiner als $2\cdot {\log }_{2}N$.

Das Double and Add-Verfahren hat also die Ordnung $O(\log N)$, was bedeutet, dass die Anzahl der Additionen für die Multiplikation mit einer natürlichen Zahl $N$ logarithmisch mit $N$ wächst. Da der Logarithmus eine sehr langsame Wachstumsrate hat, wächst die Anzahl der Additionen also nur sehr langsam mit der Größe der Zahl $N$.

Einwegfunktion

Da bei der Rückrechnung die binäre Darstellung von $N$ unbekannt ist, bleibt nur die Brute-Force-Möglichkeit, alle möglichen Summen $NP$ für alle natürlichen Zahlen $N$ zu berechnen und mit der gegebenen Summe zu vergleichen. Dies ist jedoch aufgrund der großen Anzahl an möglichen Summen so ineffizient, dass es in der Praxis nicht durchgeführt werden kann.

Aufgabe 1

Aufgabe 2