ecc.c: representing the point at infinity in affine coordinates
Nick
nick at kousu.ca
Thu May 30 19:40:26 CEST 2019
In elliptic curves, the group operation needs an extra off-the-page point as the group identity, known conventionally as "infinity" or "the point at infinity" [0]. This point is, formally, unrepresentable as a pair (x,y) because it has no coordinates.
But you need to have some way to deal with and check for this value. It is a legitimate -- and important -- part of EC arithmetic. Some standards, IEEE P1363, ANSI X9.62, and also secg [3] by choosing the single byte '\x00' to be infinity -- when serialized at least [5]. pycoin's ecc implementation similarly defines infinity at runtime as (None, None) [1] and then checks for it and handles it with special cases during addition [2].
I want to propose adopting the same idea into GnuK. Currently, `struct jpc` can handle points at infinity (and the arithmetic in jpc.c checks for ->z == 0 and behaves appropriately) but `struct ac` cannot. Instead, infinity is represent as an error code, e.g. `jpc_to_ac` says "Return -1 on error (infinite)" [4]. But this isn't really an error, it's just a representation in a side-channel. It would simplify much if this case was represented directly in the struct itself, since that could be passed around directly, and it wouldnt't get conflated with other kinds of errors.
ac = {x: 0, y: 0} is unused in GnuK. It *must* be unused, since for an elliptic curve y^2 = x^3 + ax + b, if x = y = 0, then b = 0, but no supported elliptic curve has b = 0. This value could be repurposed as the point at infinity, and then the arithmetic would not need to have any error returns. Another representation would be to add a `bool infinite` flag to `struct ac`. The key thing is that I want to be able to return `ac`s the same way I can return `jpc`s and assume everything will check out.
What do you all think about this? I wanted to run it by the experts here before I spent time editing a lot of parts of GnuK.
[0]: https://en.wikipedia.org/wiki/Elliptic_curve#The_group_law
[1]: https://github.com/richardkiss/pycoin/blob/facf208aafbe07d4d51d25b250a6f468c6c4198c/pycoin/ecdsa/Curve.py#L46
[2]: https://github.com/richardkiss/pycoin/blob/facf208aafbe07d4d51d25b250a6f468c6c4198c/pycoin/ecdsa/Curve.py#L74-L101
[3]: http://www.secg.org/sec1-v2.pdf#subsubsection.2.3.3
[4]: https://salsa.debian.org/gnuk-team/gnuk/gnuk/blob/177ef67edfa2306c2a369a037362385c354083e1/src/jpc.c#L188-L189
[5]: https://crypto.stackexchange.com/questions/6156/how-is-the-x-coordinate-of-a-point-at-infinity-encoded-in-a-secp256k1-signatur
More information about the Gnuk-users
mailing list