[CFRG] Re: RFC7748

["D. J. Bernstein" <[e-mail]>]

Michael Scott writes:
  [ regarding Montgomery A^2-4 being a non-square ]
> In Appendix A of RFC7748 a script is provided for generating suitable
> Montgomery curves, but the above condition is not specified.

Meanwhile the RFC specifies other conditions; so, before asking about
the safety of a hypothetical curve meeting the RFC's conditions and not
having A^2-4 being square, one might try to actually construct such a
curve, to show that the discussion isn't vacuous.

A natural way to investigate would be to start with small fields, as in
the following Sage script, which runs through all odd primes p < 1000,
printing out all elliptic curves y^2 = x^3+Ax^2+x meeting the cofactor
conditions in the RFC (group order 8*prime for base field 1 mod 4, group
order 4*prime for base field 3 mod 4, twist order 4*prime in any case),
and noting for each curve whether A^2-4 is a non-square:

   #!/usr/bin/env sage
   for p in primes(3,1000):
     F = GF(p)
     cofactor = 8 if p%4 == 1 else 4
     twistcofactor = 4
     for A in F:
       if A == 2 or A == -2: continue
       E = EllipticCurve(F,[0,A,0,1,0])
       n = E.cardinality()
       twistn = 2*(p+1)-n
       if n%cofactor != 0: continue
       if not ZZ(n/cofactor).is_prime(): continue
       if twistn%twistcofactor != 0: continue
       if not ZZ(twistn/twistcofactor).is_prime(): continue
       print(not (A^2-4).is_square(),'p',p,'A',A,'n',n,'twistn',twistn)

The output shows 2007 elliptic curves. The only squares A^2-4 appear for
base fields of size <=17. At that point one might reasonably formulate
a hypothesis that, actually, the curves in question don't exist over
larger fields.

Looking more closely at the square cases, one might notice that in each
case the "n" output is 8 or 16; i.e., the prime in "group order 8*prime"
or "group order 4*prime" is specifically the prime 2. So one might
formulate a more specific hypothesis that a Montgomery curve with

   * group order 8*(odd prime) for base field 1 mod 4,
   * group order 4*(odd prime) for base field 3 mod 4, and
   * twist order 4*(odd prime)

must have A^2-4 being non-square. (The RFC doesn't say "odd" here; but,
by Hasse's theorem, large fields won't give group orders 16 or 8. We ask
for much larger fields and much larger group orders in ECC.)

One might then check what the literature says about the structure of
Montgomery curves, and, based on that, formulate a proof of the
hypothesis, perhaps along the following lines:

   * Consider any A where A^2-4 is a nonzero square.

   * Consider the Montgomery curves E_{M,A,B}: By^2 = x^3+Ax^2+x for
     nonzero B. If B is square then E_{M,A,B} is isomorphic to E_{M,A,1}
     so #E_{M,A,B} is the "group order" above. If B is non-square then
     #E_{M,A,B} is the "twist order" above.

   * E_{M,A,B} has three points of order 2, namely (0,0) and
     ((-A+-sqrt(A^2-4))/2,0).

   * On E_{M,A,A+2}, the point (1,1) has order 4, so #E_{M,A,A+2} has to
     be a multiple of 8.

   * For base field 3 mod 4, we're done at this point: the group order
     or twist order is a multiple of 8, contradicting the assumption
     that both orders are 4*(odd prime). So assume base field 1 mod 4
     from now on. Fix a square root i of -1 in the field.

   * By assumption the twist order is 4*(odd prime), so E_{M,A,A+2} is
     isomorphic to E_{M,A,1}, so A+2 is a square, and (1,sqrt(A+2)) has
     order 4 on E_{M,A,1}.

   * By assumption, the group order is 8*(odd prime). Since there are
     exactly three points of order 2, the order-8 subgroup is isomorphic
     to \Z/4 times \Z/2. In particular, there are exactly 3 points of
     order 4, and 0 points of order 8.

   * Note that E_{M,A,1} is birationally equivalent to the Edwards curve
     with coefficient d = (A+2)/(A-2).

   * By Theorem 3.1 of https://eecm.cr.yp.to/eecm-20111008.pdf, there
     are exactly four points of order 4 on the Edwards curve doubling to
     (0,-1), since d is a square.

   * By the same theorem, if either square root of 1/d were a square,
     then there would be further points of order 4, contradiction. So
     +-sqrt(1/d) aren't squares.

   * By Theorem 3.2 of https://eecm.cr.yp.to/eecm-20111008.pdf, there
     are points of order 8 on this Edwards curve if there exists x in
     the field with dx^4-2x^2+1 = 0 or with dx^4-2dx^2+1 = 0.

   * Pick a square root s of A+2. Then s^2-4 = A-2 is a square (since
     A^2-4 is a square), so 4-s^2 is a square (since -1 is a square);
     i.e., 4-s^2 = r^2 for some r.

   * Note that s is nonzero (since A=-2 wouldn't be elliptic).

   * Write m = (2-r)/s. Then m^2 = (2-r)^2/s^2 = (2-r)^2/(4-r^2) =
     (2-r)/(2+r), so m^2+1 = 4/(2+r), so r = 4/(m^2+1)-2.

   * Note that m is nonzero (since r=2 would give s=0), so
     s = (2-r)/m = 4m/(m^2+1).
  
   * Now d = -4m^2/(m^2-1)^2, and the square roots of 1/d are
     +-i(m^2-1)/2m, so i(m^2-1)/2m isn't a square.

   * If (1-m^2)/2 were square, say x^2, then dx^4-2x^2+1 would be 0,
     giving a point of order 8, contradiction. So (1-m^2)/2 isn't
     square.

   * If (m+1)^2/2m were square, say x^2, then dx^4-2dx^2+1 would be 0,
     giving a point of order 8, contradiction. So (m+1)^2/2m isn't
     square; i.e., 2m isn't square.

   * The product of three non-squares is a non-square, so 2i is a
     non-square. But that's contradicted by quadratic reciprocity:
     fields 1 mod 8 have 2 and i both being squares; fields 5 mod 8
     have 2 and i both being non-squares; either way 2i is a square.

Q.E.D.

One might then say, wait, that's a rather long proof, and there are a
bunch of steps that could have gone wrong. One might then address this
by double-checking the steps, or writing a Sage script with numerical
sanity checks of each step, or writing a computer-checked proof. People
vary in how far they need to go before they're willing to confidently
say that these curves don't exist.

> In the safecurves site it is made a condition for a safe Montgomery
> curve that A^2-4 should be a non-square.

No. The SafeCurves ladder requirement is as follows:

   SafeCurves requires curves to support simple, fast, constant-time
   single-coordinate single-scalar multiplication, avoiding conflicts
   between simplicity, efficiency, and security. This is not a
   requirement specifically to use Montgomery curves: there are other
   types of curves that support simple, fast, constant-time ladders.
   "Fast" means that implementations of scalar multiplication for the
   same curve cannot be much faster, and "simple" means that reasonably
   fast implementations of scalar multiplication for the same curve
   cannot be much more concise. At this time there are no examples close
   enough to the edge to warrant quantification of "much". 

The SafeCurves completeness requirement is as follows:

   SafeCurves requires curves to support simple, fast, _complete_,
   constant-time single-coordinate single-scalar multiplication. This
   includes the SafeCurves ladder requirement but goes further by
   requiring completeness. SafeCurves also requires curves to support
   simple, fast, _complete_, constant-time multi-scalar multiplication.

The mention of A^2-4 being non-square is in the SafeCurves review of
relevant history:

   2006 Bernstein had shown a more limited form of completeness for the
   Montgomery ladder on Montgomery curves y^2=x^3+Ax^2+x with a unique
   point of order 2, i.e., with A^2-4 not a square.

---D. J. Bernstein