[Cryptography] Why doesn't elliptic curve point addition check for equality?

[Kyle Butt]

On Thu, Jan 18, 2024 at 02:52:22AM -0500, Pierre Abbat wrote:
> In 2022 I was working on a random ladder for elliptic curve point 
> multiplication, using a pure Haskell implementation of elliptic curves. It 
> takes a point multiplication problem (or an exponentiation problem in a Galois 
> field) and a random number and computes the answer in a way that someone 
> monitoring a side channel should be able to figure out only a vague idea of how 
> big the multiplier is.
> 
> I originally wrote it with the addition as the only function argument, but 
> found that (a+a) gives the wrong answer in the elliptic curve library, so I 
> added the doubling function as an argument. I know that, at least for 
> Weierstrass curves, the formula for a+b used when a and b are nonzero and have 
> different x coordinates divides by zero when a==b, and that when climbing the 
> ladder one often doubles a point. Why would an implementer not check for the 
> a==b case? It seems to me that the addition operation should give correct 
> results for all a and b, including a+a.

There are two things you can do to avoid this problem:

1. Use an Edwards or Montgomery curve that have complete addition formulas. This
guarantees that if you do happen to hit a==b, then the formula you are using
continues to work.
2. Ensure that the constant you are using as a scalar multiple of P is in the
range [0, |P|), where |P| is the order of P. You should be able to do the proof
yourself that with a standard binary ladder, you won't encounter a==b under that
guarantee. For a curve with prime order l, it is sufficient to verify that s is
in the range [0, l) and P != 0 before computing sP. For an Edwards curve of
order 4l, there are 3 other points to check. The point may well have order 2l or
4l, but if it does, then a scalar in the range [0, l) will also not hit a==b.

You may also combine the two. There are slightly faster formulas for Edwards
curves when you don't need ensure a!=b. It would be reasonable to use those
formulas for trusted input, but not for untrusted input.

> 
> Pierre
> -- 
> li ze te'a ci vu'u ci bi'e te'a mu du
> li ci su'i ze te'a mu bi'e vu'u ci
> 
> 
> 
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> https://www.metzdowd.com/mailman/listinfo/cryptography
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 297 bytes
Desc: not available
URL: <https://www.metzdowd.com/pipermail/cryptography/attachments/20240118/f792956a/attachment.sig>