Buggy square-and-multiply

[kousu]

djb warns that, with secp256r1 (and, I believe, secp256k1, which are the only two curves implemented in pycoin), you need to be careful with your group operation, because for a point P, 2P requires special addition code.

Generator.raw_mul() implements square-and-multiply:

https://github.com/richardkiss/pycoin/blob/994c4c714f599c795f4b7d7f305926ca6cdd0349/pycoin/ecdsa/Generator.py#L87-L97

(with part of the implementation precached in a different part of the code:

https://github.com/richardkiss/pycoin/blob/994c4c714f599c795f4b7d7f305926ca6cdd0349/pycoin/ecdsa/Generator.py#L26-L29

)

and though it addresses a timing attack (awesome!), it doesn't seem to special-case doubling, either in computing the _powers nor in P + _powers[i].

Maybe doubling is handled in the guts of the __add__ arithmetic:

https://github.com/richardkiss/pycoin/blob/994c4c714f599c795f4b7d7f305926ca6cdd0349/pycoin/ecdsa/Curve.py#L57-L65

but unless I'm misreading that, it doesn't handle p0 == p1. It seems like you would need:

        if (x0 - x1) % p == 0:
            if (y0 - y1) % p == 0:
                < DOUBLING SPECIAL CASE>
            elif (y0 + y1) % p == 0:
                return infinity
            else:
slope = ((3 * x0 * x0 + self._a) * self.inverse_mod(2 * y0, p)) % p

[richardkiss]

The slope = ((3 * x0 * x0 + self._a) * self.inverse_mod(2 * y0, p)) % p is the special case for doubling.

If x0 and x1 are the same, either then y0 * y0 == y1 * y1, so there are two cases: y0 == y1 or y0 == p - y1. I think all is handled correctly. If you can find a counterexample that fails, I'd be very eager to see it (and fix it).

[richardkiss]

Closing as I think this is okay.