1
$\begingroup$

Let $\mathbb{E}$ be the elliptic curve $y^2 = x^3 + 6x \text{ mod } 11$ and consider the point $P = (2, 3)$ on it. How do I compute $3P$?

I have been able to figure out what $2P$ is, $2P = (5,10)$. However I am unsure if even knowing $2P$ is helpful, or do I just compute $3P$ from knowing the original $P$?

$\endgroup$
  • 1
    $\begingroup$ Have you looked at how addition is defined on elliptic curves, specifically point addition and point doubling? E.g. you can use point doubling to compute $Q = 2P$ and then use point addition to compute $3P = Q + P$. $\endgroup$ – puzzlepalace May 25 '16 at 23:14
  • 2
    $\begingroup$ $3P=2P+P=(7,0)$. $\endgroup$ – user94293 May 25 '16 at 23:26
4
$\begingroup$

On standard way to compute scalar multiplication is to use Double-and-add algorithm:

The idea is to take the binary representation of your scalar $b = b_0 ... b_m$in your case $b = 3$ gives $b_0b_1 = 11$.

First you initialize your result $Q$ with $0$.

Then for each increasing bit index $i$, you set $Q = 2Q$ (computed with the doubling formula) and if $b_i = 1$ you set $Q = Q + P$ (computed with the addition formula).

In your example you have:

  1. $Q = 0$

  2. $Q = 2Q = 0$, $b_0 = 1$ then $Q = Q + P = P$

  3. $Q = 2*Q = 2P$, $b_1 = 1$ then $Q = Q + P = 3P$

It is the generalization of user94293 comment. If your implementation is critical, be careful since the algorithm above is not time constant. You may prefer the Montgomery ladder in critical cases.

$\endgroup$
  • 3
    $\begingroup$ Note: There are also other techniques to hide timing information including blinding. $\endgroup$ – SEJPM May 26 '16 at 9:12

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.