1
$\begingroup$

Let's say I want to generate my own elliptic curve with an order whose bit length is $n$ (specifically 2048, 4096, and/or 8192)? How would I do this? What needs to be done? What software can do this? How long would it take for a given size?

$\endgroup$
  • $\begingroup$ Bouncy Castle is able to generate curve domain parameters if I'm not mistaken. It takes pretty long, maybe somewhat less in Java 9 :) $\endgroup$ – Maarten Bodewes Apr 14 '16 at 21:40
  • 1
    $\begingroup$ Why the hell would you need a 1024-bit curve!? That would result in 512 bit classical security with 256 already being out of reach of mankind. And as soon as quantum computers are a thing (on a large scale). $\endgroup$ – SEJPM Apr 14 '16 at 22:03
  • 1
    $\begingroup$ @SEJPM quantum computers would need a certain amount of logical qubits to perform the attack, and with a very large curve, the required qubits could be out of reach even when quantum computers are commonplace (maybe) $\endgroup$ – Richie Frame Apr 15 '16 at 0:39
7
$\begingroup$

Let's suppose that you want to generate a classic $n$-bit curve in a prime field, with the complete curve order being prime. The process goes about thus:

  1. Get a prime $p$ of size $n$ bits. The curve will be defined in the field of integers modulo $p$. For all we know, you can use $p$ to have a "special form" that promotes more efficient computations (e.g. $p = 2^n - c$ for a very small value $c$). It is not proven that special-form $p$ do not weaken the curve, but no such weakness is known. Alternatively, if you worry about unknown attacks, select a random $p$.

    You may want to make sure that $p = 3 \pmod 4$ so that square root computations modulo $p$ are easy.

  2. Generate a random non-zero integer $b$ modulo $p$ and count the points on the curve of equation $Y^2 = X^3 - 3X + b$. If that number is not prime, start again with a new $b$, until a prime order is found.

  3. The prime curve order is $q$. Compute the trace which is $t = p + 1 - q$. If $t = 0$, then you were very unlucky and you got an anomalous curve; go back to step 2. If $t = 1$, then you were very unlucky and you got a supersingular curve; go back to step 2.

  4. The curve embedding degree is the smallest integer $k ≥ 1$ such that $q$ divides $p^k - 1$. If $k$ is very small then Weil or Tate Pairing can reduce discrete logarithm on the curve to discrete logarithm in the multiplicative group of invertible element in the finite field $\mathbb{F}(p^k)$. With a super-large curve size $n ≥ 2048$ this would not even be an issue, but if you want to be really sure, just check all values of $k$ from $1$ to $100$ (that's what ASNI X9.62 recommends). If the embedding degree is too small to your taste, go back to step 2.

And voilà! you have your own curve.

Steps 1, 3 and 4 above are simple enough to implement with any language that has some support for "big integers" (either natively or with some library). Step 2, on the other hand, is quite complex to do and will be substantially slow; it uses Schoof's algorithm. You'd better use an existing implementation.

There are various additional details that you may want to mind, such as taking care of having a twisted curve which is also of prime order. Read up on Brainpool curves for some guidance here. You may also want to forego classic Weierstraß curves for the more fashionable Edwards curves, which allow for implementations that are somewhat faster, and easier to do properly.

But really, you should first question the wisdom of generating your own curves (because this will basically kill off any interoperability), and also of using curves of such overblown size (which will hurt performance very badly for no practical security gain).

$\endgroup$
  • $\begingroup$ But really, you should first question the wisdom of generating your own curves (because this will basically kill off any interoperability)… Aren't the parameters of non-standard curves specified in one of an X.509 certificate's fields? $\endgroup$ – Melab Apr 15 '16 at 14:44
  • $\begingroup$ …and also of using curves of such overblown size (which will hurt performance very badly for no practical security gain). How much of a slowdown are we looking at? Doubling the size of ECC keys increases computation time more slowly than doubling the size of RSA keys. $\endgroup$ – Melab Apr 15 '16 at 14:46
  • $\begingroup$ Classic implementations of EC will be cubic, just like RSA (so a 2048-bit curve will imply computations 512 times slower than a 256-bit curve). You can go down to quadratic if you limit exponent size (you work in a 256-bit subgroup of the whole curve) but then generating the curve with such a subgroup will be very challenging (not counting usage issues such as point validation). With a special-format prime you can gain some cycles (Karatsuba for n*log n multiplications) but it won't show up that much for that kind of operand size. $\endgroup$ – Thomas Pornin Apr 15 '16 at 15:14

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.