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

[Kyle Butt]

On Fri, Jan 19, 2024 at 05:40:32AM -0500, Pierre Abbat wrote:
> 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. 

You'd have to check the formulas.

> Is it that hard to test if they're equal, and if so, to use the doubling 
> formula?

It's not hard to check that they're equal. It's bad, because it leaks timing
information. I was pointing out that under a lot of common scenarios, it is safe
to omit the checks.

> 
> > 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.

Whatever technique you use, the (secret) scalar should never have any observable
side effects at all. Not the cache lines read, not the timing, not the power
used by different portions of the CPU.

I've never seen a binary-ternary ladder.

For fields of odd characteristic, my favorite technique is the
signed-all-bits-set window with constant time table lookup and constant time
conditional negation.
See: https://eprint.iacr.org/2012/309.pdf for a detailed overview. As a quick
summary, by adjusting the representation of the scalar, you can use a table of
size 2^k to handle (k+1) bits, where the high bit is the sign bit, and you
always either add or subtract the looked up value. For a known point, like the
base point for generating a signature, or a public key where you are checking
multiple signatures, you can generate a comb, which greatly reduces the number
of doublings.

One advantage it has is that the representation requires that you go through all
of the 2^k bits for a k bit curve. So there is no temptation to quit early if
all the remaining bits are 0. (Technically you only have to go through all
2^(k-c) bits of l, where the number of rational points on the curve is l*2^c).

It also avoids any use of the identity point O, and (stated without verification
or proof) should avoid the case where a==b

With all of this, remember that I'm just a random person on the internet, and
the advice you get is worth what you paid for it.

> 
> Pierre
> 
> -- 
> sei do'anai mi'a djuno puze'e noroi nalselganse srera
> 
> 
> 
> _______________________________________________
> 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/20240122/af0a068a/attachment.sig>