Elliptic curves: multiplication by scalar
Written by Dominik Joe Pantůček on 2018-04-12
curvesmultiplicationcryptographyAs we are heading towards the actual cryptography using elliptic curves, we need to define an operation that allows us to combine numbers and points. This operation is called scalar multiplication and allows us to - yes - multiply a point by a scalar value (that is - a number). Using this technique, we are getting closer to the ultimate goal of using elliptic curves for some cryptography to secure our online communication.
We have already defined two basic operations that can be performed with points of the elliptic curve over given field. Be it real numbers plane or some prime finite field, the operations defined so far are:
- point negation[1]:
$R=-P \Leftrightarrow R=[P_x,-P_y]$
- point addition[2]:
$R=P+Q \Leftrightarrow R=[R_x,R_y]$ $R_x=d^2-P_x-Q_x$ $R_y=-P_y-d(R_x-P_x)$ $d=\frac{Q_y-P_y}{Q_x-P_x}$
- point doubling[3]:
$R=P+P \Leftrightarrow R=2P \Leftrightarrow R=[R_x,R_y]$ $R_x=d^2-2P_x$ $R_y=-P_y-d(R_x-P_x)$ $d=\frac{3x^2+a}{2y}$ With these operations at hand, we can generalize the point addition by saying that multiplying a point $P$ on the elliptic curve $E$ by natural number (scalar) $n$ means adding it $n\times$ together. $\forall P\in E,~n\in N:\quad nP=\overbrace{P+P+\cdots+P+P}^{n\times}$ There is nothing particularly hard about this. As you can see in the Video 1, you really just keep adding the point P to the intermediate results and your scalar multiplication is there and just works.
Video 1: Scalar multiplication of the point $P\approx[1.31,1.28]$ on the elliptic curve $y^2=x^3-2x+2$.
And that was about it. If we used rational numbers in place of real numbers, we could use this as a reasonable basis for asymmetric cryptography, but even that way it would have some downsides. Therefore next week we are about to look at how streamline this operation into something more usable. See ya next week!