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

[Pierre Abbat]

On Monday, January 22, 2024 7:33:47 PM EST Kyle Butt wrote:
> I've never seen a binary-ternary ladder.

Here's the code: https://github.com/phma/random-ladder .
Let's say we want to multiply g by 23. We could use these sequences of 
operations:
[21,21,21,32]
[21,21,32,21]
[21,32,21,21]
[21,32,30,21]
[32,21,21,21]
[32,21,30,21]
[32,31,32]
where 32 means multiply by 3 and add 2g and the operations are performed from 
right to left. If this is in a Weierstrass curve, the operations, as far as 
time of execution goes, are . for trivial addition or doubling, + for general 
addition, and 2 for general doubling. Converting the two-digit numbers to 
these symbols, we get
[21,21,21,32] ..2.2+2+2+
[21,21,32,21] ..2+2+2+2+
[21,32,21,21] ..2+2+2+2+
[21,32,30,21] ..2+2+2+2+
[32,21,21,21] ..2+2+2+2+
[32,21,30,21] ..2+2+2+2+
[32,31,32]    ..2.2++2++
where ..2+2+2+2+ is evaluated from left to right. Note that 2g is evaluated at 
most once in 32, though it's added twice in the last sequence:
..	Double 0, then add 0 to it
2	Double g
.	Add 2g to 0
2++	Double 2g, then add 2g to get 6g, then add g to get 6g+g=7g
2++	Double 7g, then add 7g to it, then add already computed 2g.
This is because Haskell is lazy; if there were no 32s in the sequence, it 
wouldn't evaluate 2g at all.

Now suppose we want to multiply g by 25. The sequences are:
[21,20,20,21,21] ..2+222+
[21,20,30,32]    ..2.2+22+
[21,30,20,32]    ..2.22+2+
[21,30,31,21]    ..2++2+2+
[31,20,20,32]    ..2.222++
[31,20,31,21]    ..2++22++
[31,32,32]       ..2.2++2++
The last sequence, ..2.2++2++, corresponds to both [32,31,32] and [31,32,32], 
and also [31,31,32] (22) and [32,32,32] (26).

2+ can correspond to [21] or [30], 2++ can correspond to [31] or [32,...
(32)...], and 2+2+ can correspond to [32,(no 32)] or [21,21]. These sequences 
occur many times in the ladder of a big number, leaving a side-channeler in 
doubt as to what the number is.

Pierre
-- 
ro nu co'i cortu cu nu co'a certu