Elliptic curves: double and add
Last time we have shown how to perform scalar multiplication of point on elliptic curve in simple Weierstrass form over a finite field. We have also shown that all the required properties hold for all rational points of the curve – which is a good thing. The problem we have not tackled yet is the complexity of the scalar multiplication operation. Today we are about to present a method of performing fast scalar multiplication in which the complexity of the operation grows much slower than the size of the scalar.
Of course – as usual – if you are here just to see the video, you can jump straight to it.
The definition of scalar multiplication is fine and shows us nicely all the features of the Abelian group[1] we have created from the set of rational points of the elliptic curve and our addition operation defined in terms of point negation[2], doubling[3] and plain addition[4]. The problem is that for any scalar value the number of operations required to perform the scalar multiplication[5] grows linearly. To state it really simply – the higher the scalar, the longer the operation. Why would this constitute a problem?
If we would want to use 256-bit values for multiplying points on some elliptic curve over much bigger finite field, the worst case of multiplication would require $2^{256}-1$ steps to perform. Although modern computers are pretty fast and can easily perform a million of such operations per second, it would take about $10^{64}$ years to perform such multiplication. As the universe is only about $13.8\cdot10^{9}$ years old, this does not look feasible.
But we can look at the binary representation of the scalar number and leverage the fact, that the doubling or addition operations cost roughly the same (time complexity-wise). The algorithm built with this approach is called double-and-add. All we need is to calculate the points representing the powers of two multiplies of the generator and just sum those which form the number in binary form (have ones at given positions). Although formal definitions are better for exact explanations, a simple example might help here and afterwards we will show the pseudo-code. Suppose we want to multiply the generator $G$ to produce the point $13G$. The binary representation of the number $13$ is:
$13_{10}=8_{10}+4_{10}+1_{10}=1101_2$
Thus we only use three doublings and one two additions to get the result:
$8G+4G=12G$
$12G+G=13G$
This particular multiplication is depicted in Picture 1 with the last addition highlighted.
Picture 1: the double and add paths
The pseudo-code for the algorithm multiplying point $G$ by scalar value $n$ is as follows:
- $R\gets O$
- repeat
- if n mod 2 == 1 then
- $R\gets R+G$
- end if
- $G\gets 2G$
- $n\gets n/2$
- until n=0
We see that at worst we need to perform total $2(\log_2n-1)$ doubling and addition operations at worst. Therefore we say, that the complexity[6] of the scalar multiplication using the double-and-add method is $O(\log_2n)$.
An example of the algorithm in action can be seen in Video 1 below.
Video 1: double and add in action
As we are nearing towards the end of this series, you can see that things are actually getting simpler. That is because the basic of elliptic curve cryptography is really easy to comprehend and anyone is able to see how to at least play with the basic building blocks. I can only hope you are having fun reading this series which were conceived while we were creating a new level of security in online communication (we are getting also close to revealing what it is gonna be so stay tuned) and I am definitely looking forward seeing you here next week. Cheers!
References
1. Wikipedia contributors. (2018, March 2). Abelian group. In Wikipedia, The Free Encyclopedia. Retrieved 14:32, May 2, 2018, from https://en.wikipedia.org/w/index.php?title=Abelian_group&oldid=828470797
2. https://trustica.cz/en/2018/03/08/elliptic-curves-point-negation/
3. https://trustica.cz/en/2018/03/22/elliptic-curves-point-doubling/
4. https://trustica.cz/en/2018/03/15/elliptic-curves-point-addition/
5. https://trustica.cz/en/2018/04/12/elliptic-curves-multiplication-by-scalar/
6. Wikipedia contributors. (2018, May 1). Big O notation. In Wikipedia, The Free Encyclopedia. Retrieved 14:35, May 2, 2018, from https://en.wikipedia.org/w/index.php?title=Big_O_notation&oldid=839074752