0
$\begingroup$

For an assignment, we have to calculate how many field computations are needed to calculate kG in an elliptic curve. They want us to show this for two different ways of calculating kG. The first way:

2G = G+G

3G = 2G + G

...

kG = (k-1)G + G

The other way is the double-and-add algorithm.

The question: Compute how many field operations (multiplications, additions, subtractions, divisions) we have to execute for both algorithms, assuming that we use affine coordinates for the elliptic curve.

I ran into some problems while trying to answer this question and I cannot quite seem to find the answer here or on some other part of the internet (I have to admit I'm not that good at googling).

Can anyone help me with this? Thanks in advance

$\endgroup$
  • $\begingroup$ How precise do you need to be? Does it suffice to calculate this for the average $k$ or is there a given $k$ for which you have to output the required number of computations? $\endgroup$ – SEJPM May 29 '16 at 13:24
2
$\begingroup$

Given two points $P_1 = (x_1,y_1)$ and $P_2 = (x_2, y_2)$ on an elliptic curve $y^2 = x^3 + ax +b$, the sum $P_3$ of $P_1$ and $P_2$ is $P_3 = P_1 + P_2 = (x_3,y_3)$ where $x_3 = \lambda^2 - x_1 - x_2$ and $y_3 = y_1 + \lambda(x_3 - x_1)$ where $\lambda = (y_1 - y_2)/(x_1 - x_2)$ if $P_1 \neq P_2$ and $\lambda = (3x_1^2 + a)/(2y_1)$ if $P_1 = P_2$. The case $P_1 \neq P_2$ is called point addition and the case $P_1 = P_2$ is called point doubling.

Let $M, A, S, D$ denote the operation of multiplication, addition, subtraction, and division in the underlying field. Then we see that with the previous formulas,

  • the evaluation of $x_3$ requires $1M + 2S$;
  • the evaluation of $y_3$ requires $1M + 1A + 1S$;
  • the evaluation of $\lambda$ requires $2S + 1D$ if $P_1 \neq P_2$ and $1M + 4A + 1D$ if $P_1 = P_2$ [I assume here that $3x_1^2$ is evaluated as $x_1^2 + x_1^2 + x_1^2$ ($2A$) and $2y_1$ as $2y_1 = y_1+y_1$ ($2A$)].

Hence, we obtain that

  • a point addition requires $2M + 1A + 5S + 1D$;
  • a point doubling requires $3M + 5A + 3S + 1D$.

Back to your question now,

  1. the evaluation of $kG$ requires $k-1$ point additions using the first method, that is, $2(k-1)M + (k-1)A + 5(k-1)S + (k-1)D$;
  2. letting $\ell$ the binary length of $k$ (i.e., $\ell = \lfloor\log_2 k\rfloor + 1$) and $h$ the Hamming weight of $k$ (i.e., the number of bits equal to $1$ in the binary representation of $k$), the evaluation of $kG$ requires $\ell$ point doublings and $h$ point additions using the double-and-add method, that is, $(3\ell+2h)M + (5\ell+h)A + (3\ell+5h)S + (\ell+h)D$. On average, for a random $\ell$-bit integer $k$, we have $h = \ell/2$; in which case, we get $4\ell M + 5.5\ell A + 5.5\ell S + 1.5\ell D$.

It is worth noting that the first method is completely impractical for cryptographic applications since $\ell$ is typically $256$ and thus $k \approx 2^{256}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.