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 $13 \, P$ 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: $$13 \, P = (8 + 4 + 1) \, P = 8 \, P + 4 \, P + 1 \, P$$

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

Dieser Trick nennt sich Double and Add-Verfahren. In unserem Beispiel wird damit $13 \, P$ 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 $N \, P$ 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 $N \, P$ 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 $N \, P$ 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