3
$\begingroup$

For an elliptic curve $y^2=x^3+ax+b$, I have $a=1, b=1, G=(3,10)$ private key of User $B$ as $4$. To calculate his public key, I have the formula: $Pb=nb \times G = 4(3,10)$.

This makes my calculation$=4G= (3,10)+(3,10)+(3,10)+(3,10)$

I got $(7,10)$ for the first addition. Then, $(14,18)$. Final answer as $(9,3)$. Is this answer correct?

Also, I have to do this in an exam by hand. Calculating this is a bit lengthy. Is there a faster way to calculate $4G$? For example, to calculate $(5^{-1} \times 7)\pmod {23}$ in the first part of the calculation requires me to go from 1-22 to find 14 as its modular inverse and then use it as $(5 \times 14)\pmod{23}=6$? All of this takes time. Is there some way I can speed this up?

$\endgroup$
  • $\begingroup$ For hand calculations such as here you can calculate the modular inverses easily enough with Euclid or "by observation": Listing numbers congruent to $1$ modulo $23$ gives: $1,24,47,70$ Bingo! $70$ is divisible by $5$, so from $1=70=5\cdot14$ we have the answer. Calculating modular inverses IS a problem when both $p$ and $B$ have 100 digits or thereabouts, and double-and-add algorithm (that DRF is describing +1) calls for a few hundred inversions modulo $p$. Some savings can be achieved by using projective coordinates. But I don't recommend them to you. At least not yet. $\endgroup$ – Jyrki Lahtonen Jun 2 '15 at 21:39
  • $\begingroup$ I also agree with Álvaro (+1). Something went wrong in your calculations. $$9^3+9+1=739=690+46+3\equiv 3\pmod{23}.$$ But $3\equiv 49=7^2$, so $(9,3)$ is not even a point on the curve. $(9,7)$ and $(9,-7)=(9,16)$ are, but something may have gone wrong earlier... $\endgroup$ – Jyrki Lahtonen Jun 2 '15 at 21:44
1
$\begingroup$

Calculating modular inverse certainly shouldn't be done by enumeration of possibilities. It's what you have Euclid's algorithm for.

As for general speed up; if you are computing $4P $ it's certainly more efficient to compute $2 (2P) $ than adding 4 times. This is true in general, you should be using a binary expansion of the scalar multiple and use double and add.

I'd assume using jacobite projective coordinates is probably not efficient nor is Montgomery multiplication for these sizes and when doing it by hand.

Edit The general method for doing efficient scalar multiplication on an elliptic curve in short weierstrass form (ignoring issues with inverses, projective coordinates and the like) is to perform what is usually called the double and add algorithm.

Suppose you want to compute $155$. If you try doing it by addition you end up having to perform $154$ additions. That is incredibly inefficient.

Instead what you want to do is realize that you can write $155$ as $10011011_2$ (in binary). This means $155=2^7+2^4+2^3+2^1+2^0$ so $$155P=(2^7+2^4+2^3+2^1+2^0)P=(1+2(1+2^2(1+2(1+2^3))))P=P+2(P+2^2(P+2(P+2^3P)))$$

Now to compute $155P$ you just compute $2P=Q_1$, $2Q_1=Q_2$, $2Q_2=Q_3$ now note $Q_3=2^3P$, next $P+Q_3=Q_4$, $2Q_4=Q_5$, $P+Q_5=Q_6$, $2Q_6=Q_7$, $2Q_7=Q_8$, $P+Q_8=Q_9$, $2Q_9=Q_{10}$, $P+Q_{10}=Q_{11}=155P$. Notice I only used $10$ operations as opposed to $154$.

$\endgroup$
  • $\begingroup$ Can you explain the 2(2P) method? By a small example maybe? $\endgroup$ – user2816215 Jun 2 '15 at 20:31
  • $\begingroup$ I also didn't get 'then adding four times' part. $\endgroup$ – user2816215 Jun 2 '15 at 20:37
  • $\begingroup$ @user2816215 That second bit would be because the auto filler on my phone put in a then instead of a than. $\endgroup$ – DRF Jun 2 '15 at 20:55
  • $\begingroup$ I got that, thanks. I read it somewhere else as well. Do you mean point doubling for P once and point doubling again, if we particularly consider 2(2P)? $\endgroup$ – user2816215 Jun 3 '15 at 8:31
  • $\begingroup$ Okay, i got the answer. Thank you! $\endgroup$ – user2816215 Jun 3 '15 at 8:57
1
$\begingroup$

If I am correct to assume that you are doing addition on $E:y^2=x^3+x+1$ over $\mathbb{F}_{23}$, then no, your calculation was not correctly done. If $G=(3,10)$, then $$2G=(7 , 12), \ 3G = (19, 5), \ 4G = (17 , 3).$$ I used Magma myself to do this:

F:=GF(23);

g:=Generator(F);

E:=EllipticCurve([0,0,0,g,g]);

G:=E![3, 10];

2*G; 3*G; 4*G;

$\endgroup$
  • $\begingroup$ I did get (7,12). Wrote it wrong here. I'll check my calculations from the second addition. $\endgroup$ – user2816215 Jun 2 '15 at 20:34
  • $\begingroup$ Thanks for pointing out Magma. I got the correct answer. :) $\endgroup$ – user2816215 Jun 3 '15 at 8:57
  • $\begingroup$ Uh, I wish I could accept both the answers. :/ $\endgroup$ – user2816215 Jun 3 '15 at 8:58

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.