3

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?

Jyrki Lahtonen
  • 133,153
user2816215
  • 133
  • 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. – Jyrki Lahtonen Jun 02 '15 at 21:39
  • 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... – Jyrki Lahtonen Jun 02 '15 at 21:44

2 Answers2

1

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$.

DRF
  • 5,167
1

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;

Álvaro Lozano-Robledo
  • 15,390