5
$\begingroup$

As the title says, I have some doubts about the term "cofactor" used to describe elliptic curves.

AFAIK, it's a factor of the curve order, but why is it explicitly specified in some parameter lists then?

How does it apply to the curve point addition / etc. algorithms?

$\endgroup$
  • $\begingroup$ Is your question addressed by crypto.stackexchange.com/a/51352/49826? The cofactor normally doesn't figure into curve arithmetic (point addition, scalar multiplication, etc.), though it may figure into scalar arithmetic depending on whether you're doing arithmetic in the whole curve's composite-order scalar ring or just the scalar ring of the prime-order subgroup generated by the standard base point. $\endgroup$ – Squeamish Ossifrage Mar 11 '18 at 19:31
12
$\begingroup$

In cryptography, an elliptic curve is a group which has a given size $n$. We normally work in a subgroup of prime order $r$, where $r$ divides $n$. The "cofactor" is $h = n/r$.

For every point $P$ on the curve, the point $hP$ is either the "point at infinity", or it has order $r$; i.e., when taking a point, multiplying it by the cofactor necessarily yields a point in the subgroup of prime order $r$.

The cofactor matters inasmuch as it is not equal to $1$:

  • When the cofactor is $1$, then the subgroup is the whole curve. Any non-zero point is a generator. Any incoming point $(x,y)$ that fulfills the curve equation is part of the subgroup. Everything is fine.

  • When the cofactor is not $1$, then the subgroup of prime order is a strict subset of the curve. When considering a point, verifying that the curve coordinates match the curve equation is not sufficient to guarantee that the point is on the appropriate subgroup. Moreover, there will be points whose order is not a multiple of $r$. This is what happens, for instance, with Curve25519, which has a cofactor of $8$. Such curves require some extra care in the protocol that uses them. For instance, when doing a Diffie-Hellman key exchange over Curve25519, the Diffie-Hellman private keys must be chosen as multiples of 8 (which is expressed as: "set the three least significant bits to zero"); this ensures that the points will be in the proper subgroup.

$\endgroup$
  • $\begingroup$ "when taking a point, multiplying it by the cofactor necessarily yields a point in the subgroup". IMO, "a point" should belong to the subgroup for this statement to be true. Please confirm. An initial impression was that you're talking about any point on the curve. $\endgroup$ – Oleg Gryb Aug 7 at 23:13

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.