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

[Pierre Abbat]

On Thursday, January 18, 2024 7:36:54 PM EST Kyle Butt wrote:
> 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.

I don't think I tried an Edwards or Montgomery curve, but if addition works in 
all cases, the function will work. My question is why the Weierstrass 
implementation of point addition doesn't work right if the points are equal. 
Is it that hard to test if they're equal, and if so, to use the doubling 
formula?

> 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 want to add |P|, or a small multiple of |P|, so that, if you happen to 
get a small number, like around 2^240 for a 256-bit curve, the multiplication 
doesn't take noticeably less time. Also, this isn't a standard binary ladder; 
it's a binary-ternary ladder, with the 2 or 3 at each rung determined by a 
random number.

Pierre

-- 
sei do'anai mi'a djuno puze'e noroi nalselganse srera