[CFRG] Re: RFC7748

[Michael Scott <[e-mail]>]

Hello Dan,

Thanks for the very complete answer and the clarification.

Mike

On Sun, Jun 9, 2024 at 5:56 PM D. J. Bernstein <[e-mail]> wrote:

> 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
>
> _______________________________________________
> CFRG mailing list -- [e-mail]
> To unsubscribe send an email to [e-mail]
>