ecc.c: representing the point at infinity in affine coordinates

[Nick]

May 30, 2019 10:19 PM, "NIIBE Yutaka" <gniibe at fsij.org> wrote:

> Hello,
> 
> "Nick" <nick at kousu.ca> wrote:
> 
>> 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.
> 
> [...]
> 
> I wonder if it's worth a try, in the codebase of Gnuk. I'm afraid not.
> Because users of Gnuk don't use classic ECC key, except a (very) minor
> use case of secp256k1. Another reason of my reluctance is that the
> special case of the point at infinity in classic ECC is considered a
> weakpoint which invites side-channel attacks to implementations. It
> would be hard to review such changes if it's large. On the other hand,
> with no support of the point at infinity, size of code to audit for this
> special case might be smaller.

I don't envision the change being super invasive. I think I can just

static const struct ac INFINITY = {0, 0};

add a ac_is_null() function that checks for this value, and then everywhere the arithmetic currently interprets this point, use/check for this value.

For example

-  if (bn256_is_zero (A->z))
-    return -1;
+  if (bn256_is_zero (A->z)) {
+     *X = INFINITY;
+     return 0;
+  }
 
or

-    if (FUNC(jpc_to_ac) (P3, Q1) < 0) /* Never occurs, except coding errors.  */
-      return -1;
+    FUNC(jpc_to_ac) (P3, Q1);
+    if(FUNC(ac_is_null)(P3)) /* Never occurs, except coding errors.  */
+      return -1;

We could also set INFINITY = {-1, 1} or {3, 4} or any other value that's unused. It could be defined per-curve, even.


> Well, let me explain the ECC situation in Gnuk. (This is a kind of
> duplicate, (IIRC, I wrote about it once somewhere), but perhaps, not
> here.)
> 
> I implemented the ECC routines for the curve of NIST P-256 in 2013 and
> 2014, because it's faster and key size is smaller than RSA (I thought it
> were useful). It is my own implementation selecting among possible
> algorithms, so that I wouldn't be suffered from patent issues.
> 
> But, then, around 2014, it was concluded that NIST P-256 is questionable
> to use, and it can not be recommended.
> 
> In 2014, I extended the routines to support the curve of secp256k1.
> 
> The intention was that Gnuk Token could be used for Bitcoin transactions
> (by developing a tool for that). And I proposed a way to publish a
> public key in OpenPGP format, so that people can make sure a Bitcoin
> address belongs to a person.
> 
> At that time, I assumed a user (well, most of users) were in control of
> his private key when making Bitcoin transactions. Well, my assumption
> was simply wrong. It's not, for many of "Bitcoin users". And it seems
> that mostly nobody needs a representation in OpenPGP format binding
> Bitcoin public key to email address.
> 
> And then, after Mt. Gox incident which happened in Japan, it made me
> difficult to keep working for anythong around Bitcoin support. Thus, I
> never wrote a tool issuing Bitcoin transaction with Gnuk Token.

I see. That must have been discouraging.

Thank you for the history lesson. Having the context and seeing the lineage of things is really helpful.