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?

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Your result is correct. $\endgroup$
    – SEJPM
    Commented Jan 14, 2017 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
    Commented Jan 14, 2017 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
    Commented Jan 15, 2017 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 ♦
    Commented Jan 15, 2017 at 23:52

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Cheers-I was hoping my calculator was correct, after hours of programming! $\endgroup$
    – Sam Gregg
    Commented Jan 14, 2017 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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