4
$\begingroup$

I am relatively new to ECC, but my understanding is that the result of a point multiplication must still be a point on the curve. I have implemented an ECC calculator in Python, to add and multiply points on any curve mod p.

My misunderstanding is about the curve defined $y^2=x^3+2x+2 \pmod{17}$, with $\# E=19$. As $19$ is prime, Lagrange's theorem implies that all points except the point at infinity are generator points for the cyclic group. Considering the generator point $p=(5,1)$, my program says the result of $891p$ is $(6,14)$, while other online calculators say the result is $(11,3)$, but this point is not even on the curve!. Nearly always, both my own and online programs agree on the resultant point, but occasionally, like in this example, they do not.

Any help on this issue is appreciated, as to who is correct?

$\endgroup$
  • 1
    $\begingroup$ Your result is correct. $\endgroup$ – SEJPM Jan 14 '17 at 19:29
  • $\begingroup$ What an odd bug! As @yyyyyyy (this is a hard to quote name), getting to know some Sage commands could be very useful. It would for example allow you to check the correctness of your program relative to Sage's output. Sage is written in Python, so that shouldn't be hard. $\endgroup$ – CurveEnthusiast Jan 14 '17 at 20:18
  • 5
    $\begingroup$ Just to clear up a misunderstanding (or perhaps it was only a typo): you say that all points are generators, because $17$ is prime. This is wrong: the reason that all points are generators is that $19$ is prime. $\endgroup$ – TonyK Jan 15 '17 at 0:31
  • 2
    $\begingroup$ In general, I'd be extremely cautious in using online implementations of cryptographic protocols. Usually they are just used by amateurs with little or no experience in the field (nothing wrong with amateurs in general) or published simply to generate traffic. I've seen countless examples of people matching their output to online generators ending up on StackOverflow only to find out that the website is simply wrong. $\endgroup$ – Maarten Bodewes Jan 15 '17 at 23:52
7
$\begingroup$

The (very useful!) computer algebra system sage says the correct result is indeed $(6,14)$:

sage: E = EllipticCurve(Zmod(17), [2, 2])
sage: E
Elliptic Curve defined by y^2 = x^3 + 2*x + 2 over Ring of integers modulo 17
sage: P = E(5, 1)
sage: 891 * P
(6 : 14 : 1)

Those "online calculators" you used appear to be broken.

$\endgroup$
  • $\begingroup$ Cheers-I was hoping my calculator was correct, after hours of programming! $\endgroup$ – Sam Gregg Jan 14 '17 at 19:51

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.