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
Aufgabe 1
- Wie viele Additionen sind mit dem Double and Add-Verfahren notwendig, um $1023 \, P$ zu berechnen?
- Wie viele Additionen sind mit dem Double and Add-Verfahren notwendig, um $4095 \, P$ zu berechnen?
Lösung
-
$$1023 = 2^{10}-1 = 11.1111.1111_2 = 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1$$
Diese Summe $1023\,P$ kann also durch die folgenden Schritte berechnet werden:
$$\begin{eqnarray}
1P & = & P \\
2P & = & P + P \\
4P & = & 2P + 2P \\
8P & = & 4P + 4P \\
16P & = & 8P + 8P \\
32P & = & 16P + 16P \\
64P & = & 32P + 32P \\
128P & = & 64P + 64P \\
256P & = & 128P + 128P \\
512P & = & 256P + 256P \\
1023P & = & 512P + 256P + 128P + 64P + 32P + 16P + 8P + 4P + 2P + 1P
\end{eqnarray}$$
Es sind also insgesamt $9+9=18$ Additionen statt der ursprünglichen $1023$ notwendig, um $1023 \, P$ zu berechnen.
Die Anzahl der Addition lässt sich durch die Anzahl von Einsen in der binären Darstellung von $N$ nach oben abschätzen: $\log_2 1023 < 10$. Also Anzahl der Additionen kleiner als $ 2 \cdot 10 = 20$. -
$$4095=2^{12}-1 = 1111.1111.1111_2 = 2048 + 1024 + 512 + 256 + 128 + 64 + 32 + 16 + 8 + 4 + 2 + 1$$
Es sind also insgesamt lediglich $11+11=21$ Additionen statt der ursprünglichen $4095$ notwendig, um $4095 \, P$ zu berechnen.
Abschätzung der Anzahl an Addtionen: $\log_2 4095 < 12$. Also Anzahl der Additionen kleiner als $ 2 \cdot 12 = 24$.
