Edge cases for point multiplication

[dkoreshkov]

Hello! I tried to verify your uECC_point_mult() routine (using secp256r1) against the test vectors at http://point-at-infinity.org/ecc/nisttv. For k=1, k=n-1 and k=n-2 the routine generated the zero point. Other values of k seemed to generate correct points. I also tried to disable regularize_k (setting the bit count to numBits(k) as early versions of micro-ecc did) and noticed something different. For k=1 the routine generated the same point as it should for k=3. For k=n-1 it generated the zero point. Oher values of k were ok. Is this intrinsic to the algorithms you used, or perhaps some code is faulty?

[kmackay]

It's due to the Co-Z Montgomery ladder.

[balchick]

Even at the expense of a performance hit, can you write/offer a version that doesn't use the Co-Z ladder that may handle these cases? I ran into the same issue and found that it occurs for all curves. To be acceptable, the algorithm should process all possible keys. I guess it is a small price to pay, but a user should not have to check for a wider range of unacceptable keys besides 0 and n. I guess the guy that wrote the paper you got the equations from never tested any implementation. It sounds great that it works on paper, but not handling 1, n-1, and n-2 should not be acceptable. It also makes it hard to believe that there are not any other keys that don't work (although I strongly feel that there are only 5 total possibilities that give 0,0 - 0 and n (produce same regularized k), 1, n-1, and n-2. These are the 4 bit patterns in the last 2 bits of regularized k that don't work. 0 and n are expected. The others are not. Thanks!