Finding an elliptic curve of specific order

Question

I wish to use elliptic curves for cryptographic operations like commitments etc. I see that most standard elliptic curves like $\operatorname{secp256k1, sect571r1}$ have a certain specific and fixed order of the corresponding bit-length.

However, I require groups of non-standard order like say $q = (2^k)n +1$ for a certain $k,n$ for $k =128, 300$ etc.

Is there a way I can generate/form an elliptic curve group of any given order? Of course, I require solving discrete-log to be hard in the group.

Answer 1

There are many academic works on finding a curve for a given order.

• 1994 - Georg-Johann LayHorst G. Zimmer - Constructing elliptic curves with given group order over large finite fields

  A procedure is developed for constructing elliptic curves with given group order over large finite fields. The generality of the construction allows an arbitrary choice of the parameters involved. For instance, it is possible to specify the finite field, the group order or the class number of the endomorphism ring of the elliptic curve. This is important for various applications in computational number theory and cryptography.

  The task solved in this paper are;

  1. Given an integer $m > 3$, find a prime $p$ and an elliptic curve E over the finite field Fp of order $\#E(\mathbb F_p) = m$.
  2. Given two integers $n$ and $c_{max}$, find an elliptic curve $E$ over the finite field $\mathbb F_{2^n}$ with $\#E(\mathbb F_{2^n}) = c \cdot q$ with $q$ a prime and $c \leq c_{max}$. ( Note that binary curves are off)
  3. Given an integer $n > 1$, decide whether or not there is a prime $p > 3$ and an elliptic curve $E$ over $\mathbb F_p$ with structure $E(\mathbb F_p) \sim (\mathbb Z/n \mathbb Z) \times (\mathbb Z/n \mathbb Z)$.
  4. Given a prime $p > 3$ and an integer $m$ with $|p+ 1 - m < 2 \sqrt p$ , build an elliptic curve over $\mathbb F_p$ whose group order is m and whose endomorphism ring has small class number.

• 2001 : Erkay Savaş, Thomas A. Schmidt, and Çetin K. Koç Generating Elliptic Curves of Prime Order

  A variation of the Complex Multiplication (CM) method for generating elliptic curves of known order over finite fields is proposed. We give heuristics and timing statistics in the mildly restricted setting of prime curve order. These may be seen to corroborate earlier work of Koblitz in the class number one setting

The citers of the first one should help if there is a specific work directly your case.

• 2007 : Reinier Broker, Peter Stevenhagen Constructing elliptic curves of prime order

  We present a very efficient algorithm to construct an elliptic curve E and a finite field F such that the order of the point group $E(F)$ is a given prime number N. Heuristically, this algorithm only takes polynomial time $\mathcal{\tilde{O}}((\log N)^3)$, and it is so fast that it may profitably be used to tackle the related problem of finding elliptic curves with point groups of prime order of prescribed size. We also discuss the impact of the use of high-level modular functions to reduce the run time by large constant factors and show that recent gonality bounds for modular curves imply limits on the time reduction that can be obtained.

Answer 2

In the Paper for the curve25519 Bernstein described how he got the parameters for the curve. For security reasons it was important for him to have prime orders, for efficiency reasons it was important to have small parameters for the curve. He then iterated over parameters starting at zero to find an elliptic curve with a wanted order. I think this is still the best method, but I may oversee some further papers.