[curves] Climbing the elliptic learning curve (was: Re: Finalizing XEdDSA)

[Mike Hamburg]

Hi Ron,

I think your questions are appropriate for this mailing list.  It’s not always easy to find information on elliptic curves and other cryptography, sometimes even for people who work on them frequently.

DJB has an unfortunate habit of omitting information he deems irrelevant, such as background and motivation.  So it’s not surprising to me that he doesn’t mention cofactor much in his work.  It’s disappointing that HEHCC isn’t better.

> On Nov 1, 2016, at 12:20 PM, Ron Garret <ron at flownet.com> wrote:
> 
> "For primes congruent to 1 mod 4, the minimal cofactors of the curve and its twist are either {4, 8} or {8, 4}.”
> 
> Where the heck did *that* come from?  Digging through the references, I happened to stumble upon this:
> 
> http://www.hpl.hp.com/techreports/97/HPL-97-128.pdf
> 
> which seems like it’s the answer to that particular question.  But even this (apparently) elementary fact seems to be almost deliberately obscured in the literature.  Even https://safecurves.cr.yp.to doesn’t mention it, which is another indication that all this is just taken to be common knowledge.

No, cofactor-1 is fine.  It would even be preferable on its own.  It’s used by the NIST and Brainpool curves.  It’s just that curve shapes with nicer formulas and fewer corner cases (Montgomery, Edwards, Huff, Jacobi quartic, etc) all have cofactors divisible by 4.

For example, an Edwards curve has 4-way rotational symmetry.  The center (0,0) of the rotation isn’t on the curve, and in fact all points on the curve are mapped to exactly 3 other, distinct points.  This means that the number of points on the curve must be divisible by 4.

The article you’re referring to is about curves with *trace* 1, which is completely different.  The trace (aka “trace of Frobenius”) is p+1-#E, where p is the order of the underlying field and #E is the number of points on the curve.  So the danger in the Smart article is curves with exactly p points on them, over a field of size p.  This is a very special case indeed.

The reason for the {4,8} thing is that trace(E) = -trace(quadratic twist of E).  Plugging in the definition, #E + #(twist E) = 2p + 2.  When p == 1 mod 4, then 2p+2 == 4 mod 8.  This means that #E and #(twist E) can’t both be of the form 4*(large prime), because then their sum would be 4*(odd + odd), which would be divisible by 8.  So if E has cofactor 4, then twist-E must have cofactor at least 8 and vice versa.

For X25519 (the usual DH protocol over Curve25519), the protocol has to be secure on the twist as well, because you don’t check if the point is on the curve.  So you want to minimize cofactor on both, and {4,8} or {8,4} is the best you can do.  Bernstein chose {8,4} so that security measures on the curve would automatically protect the twist as well.

If you run through the above math with p == 3 mod 4, you get that both E and twist E can have cofactor 4.  This is why Ed448-Goldilocks and its twist can both have cofactor 4, but Curve25519 has cofactor 8.

Cheers,
— Mike
-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 3693 bytes
Desc: not available
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20161101/d4c07980/attachment.bin>