4
$\begingroup$

I'm referencing RFC-6090 for an attempt at implementing ECC in my spare-time project.

In the RFC, pseudo-code examples are given to illustrate how to handle points-at-infinity in point arithmetic, and this involved several special cases. This is because the point doubling and point add formula in affine and homogeneous coordinates cannot correctly handle point at infinity.

So I want to ask: is there a coordinates system where the point doubling and adding formula can handle point at infinity cases?

Improve this question
$\endgroup$
2
  • $\begingroup$ What are you trying to implement exactly ? generic point operations or a specific crypto function ? $\endgroup$
    – Ruggero
    Commented Jan 14, 2022 at 10:11
  • $\begingroup$ @Ruggero Point addition and doubling, but with less case labels for point at infinity. I assumed there may be a special coordinates system that can make this easy. $\endgroup$
    – DannyNiu
    Commented Jan 15, 2022 at 1:48

1 Answer 1

Reset to default
4
$\begingroup$

For the homogenous coordinate systems it is possible to use addition and doubling formulas which are complete and exception-less for all odd order elliptic curves. These were originally derived by Bosma and Lenstra and optimized more recently by Renes et al. in this paper.

The main issue is that they are slower than incomplete formulas. The limitation of being valid only on odd order curves is not significant as most standards constains only prime-order short weierstass.

Here's a table, from the paper, describing the required field operation and comparing it with standard Jacobian: Table 3

Improve this answer
$\endgroup$
3
  • $\begingroup$ How much slower is the complete formula? By how many orders of magnitude? Or are they slower than side-channel-masked described in RFC-6090? $\endgroup$
    – DannyNiu
    Commented Jan 17, 2022 at 13:34
  • 1
    $\begingroup$ @DannyNiu I've added a table showing the field operation required by this complete formulas vs incomplete Jacobian, they should be <2x slower. The authors also implemented them in openssl in a windowed ladder and it was 1.4x slower. $\endgroup$
    – Ruggero
    Commented Jan 19, 2022 at 9:44
  • $\begingroup$ I was going to request a Markdown version of the table, since my national firewall doesn't like Imgur which hosted the screenshot of the table. But anyway the table is too complex to be formatted in Markdown, and it's in the paper. I'll look into it. $\endgroup$
    – DannyNiu
    Commented Jan 19, 2022 at 10:13

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.