0
$\begingroup$

This cofactor (as I understand it) effectively discards valid points that satisfy the curve equation over the finite field.

Why would one wish to reduce the number of possible private keys, it seems to reduce security.

What is the reasoning behind using a cofactor of 8?

$\endgroup$
3
$\begingroup$

Curve25519 was chosen to have the Montgomery shape $y^2 = x^3 + A x^2 + x$ to support the fast single-coordinate Montgomery ladder for Diffie–Hellman: given $x(P)$ and $a$, it is cheap to compute $x([a]P)$, so there is no need to pass the $y$ coordinate and implementors are not tempted to use secret-dependent conditionals to compute scalar multiplication with the naive double-and-add algorithm—that is, the shape of Curve25519 was chosen to encourage implementors of the X25519 DH function to avoid timing side channels without sacrificing performance.

Every Montgomery curve has a point of order 2 (if the equation holds for $P = (x, y)$ then it holds for $(x, -y) = -P$ so $P + (-P) = \mathcal O$), so the cofactor is always greater than 1—and when the coordinate field is $\mathbb Z/p\mathbb Z$ for $p \equiv 1 \pmod 4$ as is the case for $2^{255} - 19$, the orders of the curve and its twist are 4 and 8 or vice versa.

Curve25519 was chosen to minimize the cofactors, and when taking all the other criteria into account, the best choice had cofactor 8 for the curve and cofactor 4 for the twist. RFC 7748 gives a deterministic algorithm to search according to these criteria in Appendix A. For comparison, the Curve448 coordinate field is modulo $p = 2^{448} - 2^{224} - 1$ with $p \equiv 3 \pmod 4$, so both the curve and its twist have cofactor 4.

$\endgroup$
  • $\begingroup$ > conditionals to compute scalar multiplication with the naive double-and-add... interesting, is this why 25519 implementations tend to have constant time scalar multiplication functions? $\endgroup$ – Woodstock Nov 18 at 16:52
  • 1
    $\begingroup$ @Woodstock Yes. The curve was specifically chosen so that the most tempting implementation strategy for performance is with constant-time logic (with the usual caveats about machine integer multiplication). $\endgroup$ – Squeamish Ossifrage Nov 18 at 16:55
  • $\begingroup$ thank you my friend $\endgroup$ – Woodstock Nov 18 at 16:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.