19
$\begingroup$

I am reading up on ECC and having trouble understanding how these are related.

In a finite field, all point operations are taken modulo $p$.

$n$ is the order of the generator $G$ — which apparently is the number of different points on the curve which can be generated by multiplying a scalar with $G$. This is clear. But —

  • How is this $n$ chosen? Is $G$ chosen so that $n$ is a certain number?
  • Does $n$ effect the security of the curve?
  • Do all the points of the crypto operations with a given $G$ fall in the set of $n$ points for that $G$?

$h$ is the cofactor which is the $\#E(\mathbb F_p)/n$.

  • What is the significance of this?
  • $\#E(\mathbb F_p)$ is the number of points of the curve apparently. Why is dividing that with $n$ interesting?
$\endgroup$

1 Answer 1

23
$\begingroup$

The prime $p$ is chosen to make arithmetic in a choice of field $k$ efficient. Typically $k = \mathbb F_p$ or $k = \mathbb F_{p^2}$. Popular choices of $p$ are near powers of two, e.g. the Mersenne primes $2^{127} - 1$ used by FourQ and $2^{521} - 1$ used by E-521 and NIST P-521, or $2^{255} - 19$ used by Curve25519. Other popular choices differ from a power of two by a small linear combination of of powers of two, e.g. $2^{224} - 2^{96} - 1$ used by NIST P-224 or $2^{448} - 2^{224} - 1$ used by Curve448.

The field $k$, the curve shape, and the parameters of the curve shape determine an elliptic curve $E/k$. Every elliptic curve over a field of characteristic ${>}3$ has a representation in short Weierstrass form $y^2 = x^3 - a x + b$ for parameters $a, b \in k$. Some curves also have representations in Montgomery form $B y^2 = x^3 + A x^2 + x$ or twisted Edwards form $a x^2 + y^2 = 1 + d x^2 y^2$.

The choice of curve shape affects performance and security properties of the curve, e.g. Montgomery curves have fast $x$-restricted scalar multiplication by the Montgomery ladder whereas the best single-coordinate ladder on curves that have no Montgomery form is the much slower Brier-Joye ladder. The curve parameters often also affect performance, because, e.g., the Montgomery parameter $A$ figures into the Montgomery ladder as a multiplier, so smaller values of $A$ make the Montgomery ladder faster.

A field $k$ and curve $E/k$ determines a group of $k$-rational points $E(k)$. These are loosely the points in $k$ satisfying the curve equation, and $\mathcal O$, an identity element. (In more algebraic-geometric jargon, these are the points fixed by the coordinatewise action of the automorphism group of $\overline k$ that fixes $k$; that definition also works with projective coordinates, which are all-around much nicer to think about than affine coordinates.) This is the group in which we do arithmetic, and define scalar multiplication of a point $P \in E(k)$ by $[u]P = P + \cdots + P$, the $u$-fold sum of $P$ with itself, with $[0]P = \mathcal{O}$.

The number of $k$-rational points $\#E(k)$ is an upper bound on the number of possible values we can get by scalar multiplication, and thus the maximum defense against ECDLP attacks: it is the maximum possible order of any element $P \in E(k)$. So scalars are equivalent modulo $\#E(k)$: $[a]P = [b]P$ if $a \equiv b \pmod{\#E(k)}$. The order of the field $k$ puts bounds on possible values of $\#E(k)$ by Hasse's theorem: $$|\#E(k) - (\#k + 1)| \leq 2\sqrt{\#k}.$$ So in order for $\#E(k)$ to be large enough to resist Pollard's rho, $\#k$ must be large too; for $k = \mathbb F_{p^e}$, $\#k = p^e$, and since $e$ is usually 1 or 2, $p$ must be large as well. This is also why the high-order digits of the primes in the NIST curves may naively appear suspiciously the same as the high-order digits of the orders of the NIST curves.

We don't pick $\#E(k)$ in advance; rather, we pick $p$, a field, a curve shape, and curve parameters, and then compute $\#E(k)$ by Schoof's algorithm. In order to resist small-subgroup attacks, we want $\#E(k)$ to be prime or nearly prime, so that $E(k)$ has at worst only negligibly small subgroups. So we either randomly search the parameters to the curve, or find the smallest/fastest values, that make $\#E(k)$ the product of a large prime $n$ with a small cofactor $h = \#E(k)/n$. Some curves are chosen with $h = 1$ so that $\#E(k) = n$ is itself prime; others are not, e.g. because every Montgomery curve has a cofactor $h > 1$.

Finally, we pick a base point or generator $G$ of prime order $n$. This can also be done randomly or deterministically, e.g. picking the smallest nonnegative integer $x$ that is the $x$ coordinate of a point $G$ of order $n$, which we test by multiplying $[n]P$ and seeing if we get back $\mathcal O$. The choice of which base point in an order-$n$ subgroup is immaterial, so there's no reason to even be tempted to choose this at random.

The attacker's job, which we hope to make hard, is to find a secret scalar $u$ given a multiple $[u]P$ of some point $P$ known to the attacker. The legitimate user normally reveals $[u]G$ as their public key, so the subgroup generated by $G$ needs to have large order to resist Pollard's rho offline, and prime order to resist Pohlig–Hellman offline.

For ECDH, the legitimate user will also reveal $[u]P$ for an attacker-chosen $P$, which exposes them to Lim–Lee active small-subgroup attacks in which the attacker feeds in points $P$ in small subgroups where the ECDLP is easy. If $\#E(k)$ is prime, then $n = \#E(k)$ and there are no nontrivial subgroups. If $\#E(k) = h n$ is near prime, with, say, $h = 8$, then there are nontrivial subgroups, but the amount of information revealed by $[u]P$ is at most $\lceil\log_2 h\rceil$ bits—and sensible ECDH systems such as X25519 pick secret scalars $u \equiv 0 \pmod h$ so that $[u]P = \mathcal O$ for any point $P$ of low order, and the active attack reveals nothing. (For more about choosing secret scalars for X25519 or Ed25519 or more exotic applications, see this answer.)

There is a host of other considerations you need to worry about, and they depend on what cryptosystem you're using: e.g., ECDH/EdDSA and pairing-based cryptography have completely different constraints. You can find a reasonably comprehensive listing of criteria for curves safe for ECDH and EdDSA at SafeCurves, which also addresses twist security, completeness of addition laws, rigidity of selection process, and various other criteria for choosing curves.

Note that novel uses of curves sometimes require further criteria beyond SafeCurves, or careful handling beyond the standard DH or signature schemes. For example, the cryptocurrency Monero was badly surprised by distinct but equivalent signatures enabled by the small subgroups implied by a cofactor $h > 1$.

For further references, and for some more detail about X25519 in particular, see an earlier answer I wrote.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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