3
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
5
  • 1
    $\begingroup$ The papers by Reinier Bröker are the most accessible to accomplish this, imo. $\endgroup$ May 10, 2021 at 19:28
  • $\begingroup$ @SamuelNeves thanks, It seems that the only citer that works on this is Elliptic Curves of Fibonacci order over that I don't see a relation with Cryptography, though. $\endgroup$
    – kelalaka
    May 10, 2021 at 19:34
  • $\begingroup$ @SamuelNeves did you ever see an implementation of Reinier Bröker's around. I couldn't see one. $\endgroup$
    – kelalaka
    May 10, 2021 at 20:24
  • 2
    $\begingroup$ This is pretty janky, but mostly works. $\endgroup$ May 10, 2021 at 23:38
  • 2
    $\begingroup$ Found this which seems to implement Reinier's paper $\endgroup$
    – MeV
    May 10, 2021 at 23:44
0
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I don't see how that answers the question; while Dan was looking for a curve with an order that met certain requirements (e.g. a prime times the unavoidable cofactor), those requirements were met with nontrivial probability with a random order - adding the requirement must be of the form $2^kn + 1$ for $k \ge 128$ would make this no longer true; hence a different search strategy would be required $\endgroup$
    – poncho
    May 10, 2021 at 13:10

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.