6
$\begingroup$

By Hasse's theorem we know that range of the group order of the elliptic curve. And similarly, there exist a theorem on the admissible order of elliptic curves. Suppose by the theorem on the admissible order of elliptic curve we know there exist a curve of desired order then how to determine the curve parameters. For example in case of simplified/short Weierstrass equation the value of the parameters $a,b$.

My question: is there a theorem to determine the curve parameters based on the group order? Does the form of the curve matter? The different forms of the curve are Weierstrass, Montgomery, and Edwards.

$\endgroup$
  • $\begingroup$ Note: I'm pretty sure that if you can count the points on an Edwards curve, then you can also count them on a Montgomery curve (and vice versa) as the two are usually birationally equivalent. BTW: Schoof's algorithm $\endgroup$ – SEJPM Apr 18 '16 at 19:56
  • 5
    $\begingroup$ @SEJPM: actually, he isn't asking "given a curve, how many points on it"; instead, he's asking "given a target number of points (that's not impossible), how can I generate a curve with precisely that many points?" $\endgroup$ – poncho Apr 19 '16 at 1:19
7
$\begingroup$

There is a method known as "Complex Multiplication". However, it is not simple at all, and tends to be overly expensive for most target orders. See this article for some details. There is also the (theoretical) concern that a curve constructed that way may have a special structure though could possibly be leveraged into an attack one day; generally speaking, cryptographers do not like special cases and prefer the immunity of the herd by relying on random values in big sets (unless there is a performance advantage to be had with the special structure, in which case to Hell with it, let's milk the precious clock cycles -- that's how modern curves tend to be defined in fields of prime order $2^m-c$ with a very small $c$).

CM has been used to define pairing-friendly curves (curves that have a demonstrated special structure which is on the verge of being a weakness, but also enables nifty three-way protocols).

$\endgroup$
1
$\begingroup$

There can be much simpler methods than CM for group orders of a specific form. For exemple if $p \equiv 2 \pmod 3$ and $b \not\equiv 0 \pmod p$, the curve $Y^2 = X^3 + b$ over $\mathbf{F}_p$ has $p+1$ points. (The proof of this is easy and left as an exercise.) Such methods are also used to easily construct "good enough" pairing-friendly curves.

As Thomas notes in the commants, the low embedding degree of those curves makes them simultaneously good for pairings and bad for elliptic-curve discrete-log based systems. Use with caution.

$\endgroup$
  • $\begingroup$ Take care that these curves have embedding degree 2, so they are much weaker than usual curves for "normal sizes" (e.g. 256 bits). This is a nice curve if you want to use a pairing and know what you are doing. $\endgroup$ – Thomas Pornin Apr 19 '16 at 20:19

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.