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 <r...@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
smime.p7s
Description: S/MIME cryptographic signature
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves
