What's wrong with this curve (generation algorithm)?

Question

In this tweet, Paulo Barreto proposes the following elliptic curve over $\mathbb{F}_{2^{255}-19}$:

$$ E_\mathrm{PB} : y^2 = x^3 - 3x + 13318 $$

with $G_\mathrm{PB} = (-7, 114)$. Now I would like to try to verify the curve by trying to generate it over some sensible domain. For this I am using this algorithm from this website.

I also require that $n$ (the order of $E_\mathrm{PB}$) is prime, and that the cofactor $h$ is 1. After programming for some time I have come up with the following algorithm for generating elliptic curves:

#!/usr/bin/env sage

F = GF(2^255 - 19)
for i in range(15000):
    if i % 100 == 0:
        print('Progress: {}'.format(i))
    try:
        E = EllipticCurve(F, [-3, i])
    except ArithmeticError:
        # Curve probably has a singularity
        continue
    n = E.order()

    # Only accept curves of prime order
    if not is_prime(n): continue

    # Start selecting random points for the rest of the search
    for x in range(-256, 256):
        for y in range(256):
            try:
                G = E(x, y)
            except TypeError: # (x, y) is not a valid point
                continue
            t = G.order()
            # Cofactor MUST be 1
            if n == t:
                bits = int(log(float(E.order()))/log(2.0))
                print('Found prime order for a_6 = {} ({} bits)'.format(i, bits))
                print('Generator G = {}'.format(G))

After a short time it gives me the following curve:

$$ E_{DS} : y^2 = x^3 - 3x + 101 $$

with $G_\mathrm{DS} = (-4, 7)$, which is not Paulo's curve. I expect that Paulo did not make a mistake, so my question is:

What is wrong with my generated elliptic curve $E_\mathrm{DS}$?

Answer 1

As a lone curve, yours is not bad. But Barreto's proposal offers an extra property, which is that the quadratic twist also has prime order.

In general, in a given finite field $K$, if you have a non-quadratic residue $d$ (i.e. a field element which is not a square), then, for the curve $E$: $$ E: Y^2 = X^3 + aX + b $$ then you can define another curve called its "quadratic twist": $$ E^d:Y^2 = X^3 + ad^2X + bd^3 $$ It can be seen that if $X$ is a valid first coordinate for one curve, then it is not for the other, and vice versa. It implies that that if field $K$ has cardinal $q$ (in your case, $q = 2^{255}-19$), curve $E$ has order $n_1$, and $E^d$ has order $n_2$, then $n_1 + n_2 = 2(q + 1)$. It also implies that the exact choice of $d$ does not matter much, in that all twisted curves you may get all have the same order, hence they are all "the same curve" in some sense (they are isomorphic to each other). This is why we talk of the quadratic twist.

(When $p = 3 \pmod 4$, it is convenient to use $d = -1$, but in your case, $-1$ is a quadratic residue because $2^{255}-19 = 1 \pmod 4$.)

Note that the quadratic twist of the quadratic twist is the original curve (or something isomorphic to it).

Quadratic twists may matter because in some cases they allow to avoid point validation. If you consider normal ECDH with point compression, both parties will send the $X$ coordinates of their public points to each other. Normally, each receiving party would then rebuild $Y$ from the received $X$, and check that indeed they got a point on the curve. That process would go thus: receive $X$, compute $X^3+aX+b = Y^2$, then apply a square root algorithm to get $Y$. If the received $X$ does not correspond to a point on the curve, then the recomputed $Y^2$ is not a square: this is where point validation happens.

Historically, a number of implementations have got validation wrong and blindly kept on computing with whatever point they had. In practice, if you get an $X$ that does not map to a point on the curve, then you are really computing on the quadratic twist. Therefore, it seems to be a good idea if the curve and its quadratic twist both have a prime order.

In Barreto's proposed curve, both the curve and its twist have prime order. In your curve, the twist's order is not prime. That's what is "wrong" with your curve.

---

In my opinion, the issue about validation is overrated. Point validation is not hard; it uses up negligible CPU compared to the actual computations you are about to do, and the code size overhead is small. Implementations that do not point validation are basically sloppy, and sloppiness, like love, knows no limit. However, if you can have some extra protection against sloppiness at low cost, then why not?