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 $2(n-1)$, also weniger als $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

Exkurs: Double and Add-Verfahren ohne Zischenspeicherung

Bei dem bisher beschriebenen Double and Add-Verfahren müssen Zwischenergebnisse zunächst zwischengespeichert werden, was bei großen Zahlen sehr speicherintensiv sein kann. Durch einen kleinen Trick kann man eine solche Zwischenspeicherung jedoch wie folgt vermeiden.
Als Beispiel wollen wir $25 P$ berechnen. Dazu erzeugen wir zunächst die Binärdarstellung von 25 duch den folgenden Algorithmus, bei dem sukkzessive ganzzahlig durch 2 mit Rest dividiert wird: $$ \begin{eqnarray} 25 \div 2 &=& 12 \text{ Rest } 1 \\ 12 \div 2 &=& 6 \text{ Rest } 0 \\ 6 \div 2 &=& 3 \text{ Rest } 0 \\ 3 \div 2 &=& 1 \text{ Rest } 1 \\ 1 \div 2 &=& 0 \text{ Rest } 1 \cr \end{eqnarray} $$ Wir erhalten also für die Binärdarstellung von 25 die Ziffernfolge $11101_2$.
Umgekehrt bekommen wir die Dividenden in den obigen Gleichungen von unten nach oben wieder zurück, indem wir die Binärdarstellung von 25 von links nach rechts durchlaufen und ausgehend von der Zahl $0$ jeweils mit 2 multiplizieren und gegebenenfalls noch eine 1 addieren, wenn die entsprechende Ziffer eine 1 ist: $$ 0 \stackrel{1}{\rightarrow} 1 \stackrel{1}{\rightarrow} 3 \stackrel{0}{\rightarrow} 6 \stackrel{0}{\rightarrow} 12 \stackrel{1}{\rightarrow} 25 $$ Dabei stehen über den Pfeilen die jeweilige Ziffern der Binärdarstellung von 25. Die Ziffern bedeuten dabei jeweils folgendes:

• Für eine 0 auf einem Pfeil wird die Zahl links vom Pfeil verdoppelt, um die Zahl rechts vom Pfeil zu erhalten.
• Für eine 1 auf einem Pfeil wird die Zahl links vom Pfeil verdoppelt und anschließend nohc 1 addiert, um die Zahl rechts vom Pfeil zu erhalten.

Für die Addition von Punkten auf elliptischen Kurven erhalten wir also analog dazu: $$ O \stackrel{1}{\rightarrow} P \stackrel{1}{\rightarrow} 3P \stackrel{0}{\rightarrow} 6P \stackrel{0}{\rightarrow} 12P \stackrel{1}{\rightarrow} 25P $$ Für eine 1 auf einem Pfeil sind zwei Addtionen nötig, während für eine 0 auf einem Pfeil nur eine Addition notwendig ist. Den ersten Schritt von $0$ auf $P$ können wir dabei vernachlässigen, da er gar keine Addition erfordert. Damit haben wir also $25 P$ mit insgesamt nur $7$ Additionen berechnet, ohne dabei alle Zwischenergebnisse speichern zu müssen.

Aufgabe 2