17
$\begingroup$

I'm having a rough time understanding the math behind elliptic curves.
I want to implement ECDH where user can define a, b, and p parameters of elliptic curve.

How can I calculate generator base point G? Is it any point that satisfies elliptic curve equation $ y^2 \equiv x^3 + ax + b \pmod p$?

Also, how can I calculate order n and cofactor h given the base point?

$\endgroup$
  • 7
    $\begingroup$ Be careful. There are many conditions that one has to take into account generating ECC pararmeters. See safecurves.cr.yp.to. $\endgroup$ – mephisto Sep 4 '15 at 15:30
  • 2
    $\begingroup$ This answer of mine explains how to compute the order of an elliptic curve. $\endgroup$ – yyyyyyy Sep 4 '15 at 18:38
  • $\begingroup$ also see eprint.iacr.org/2015/366.pdf, for a new method to generate parameters for ECC. $\endgroup$ – 111 Sep 7 '15 at 22:06
  • $\begingroup$ eprint.iacr.org/2015/659.pdf and csrc.nist.gov/groups/ST/ecc-workshop-2015/presentations/… should be useful $\endgroup$ – ddddavidee Sep 9 '15 at 11:44
  • 2
    $\begingroup$ Bouncy Castle contains methods of generating EC parameters. I agree with SEJPM that this should not be taken lightly. You should only do this if you really don't trust NIST or the Brainpool curves. I don't think that the NIST curves have been backdored, but personally I trust a consortium of companies and universities from Germany a hell of a lot more than NIST, especially after the Dual-DRBG fiasco. Or you could use one of the safe safecurves of course. $\endgroup$ – Maarten - reinstate Monica Sep 12 '15 at 13:34
8
+100
$\begingroup$

It is possible to find the desired values in an acceptable amount of time.

TL;DR: Find the curve order, factor it, select a (random) point until you have one with the desired order and calculate the cofactor as quotient of curve and point order.

First, you can use yyyyyyy's answer to find the order $n$ of the described curve using Schoof's algorithm. Please note that this order should be prime or a small multiple (4x-8x) of the a prime for enhanced security but it doesn't have to have those properties for the schemes to work.

In the next step, you need to actually factor that order. This is feasible as this order usually will be around 500 bits of length (or a lot less if you're not going for the 256-bit security level), which can be done and was done for FREAK. Of course, if the curve order is prime or a small multiple of a prime (4x-8x) the factorization may not need to be obtained with the GNFS but may be either given (prime case) or findable by trial division (small multiple case).

Finally you just select a curve point and determine its order until you hit one with the desired order $t$ which will also yield the cofactor as $h=n/t$. Usually you'll want to have $h\leq 8$ and usually you'll also start with the points having small x-Coordinates and try all incrementally until you reach one fullfilling your conditions.


The algorithm for this can be found in a variety of places in the literature and I'll quickly restate the one from the Handbook of Applied Cryptography, assuming we're testing the point A and that $n=p_1^{e_1}\cdot p_2^{e_2} \cdot\cdot\cdot p_k^{e_k}$:

  1. Set $t\gets n$
  2. For $i$ from $1$ to $k$ do the following:
    1. Set $t\gets t/p_i^{e_i}$
    2. Compute $A_1\gets t\cdot A$
    3. While $A_1\neq \mathcal O$ do the following: compute $A_1\gets p_i*A_1$ and set $t\gets t\cdot p_i$
  3. Output $t$ as the order of $A$

Please note: I strongly recommend against using custom curves where the parameters are chosen by the user. These may be vulnerable to attacks documented in the safe curves project. Standardized curves (like Curve448 or Curve25519) should be preferred for easier implementation and better analyzed security properties.

$\endgroup$
  • 3
    $\begingroup$ You do not need to factor the order of the group of $\mathbf F_p$-rational points, you just need to make sure this order is prime (or four times a prime for Montgomery or Edwards curves). This can be done much more efficiently than factoring. Considering that one would have to test a lot of curves before finding a suitable one, trying to factor all the orders would be a waste of time. $\endgroup$ – Calodeon Sep 11 '15 at 23:29
  • $\begingroup$ @Calodeon, "Make sure the order is prime or four times a prime." - I consider that part of factoring: Find out whether it's prime and if not try small factors first and the OP explicitely stated that he doesn't choose $a,b,p$ himself but rather gets these values supplied so the answer may not assume anything about $a,b,p$ or $n$. $\endgroup$ – SEJPM Sep 12 '15 at 13:03
  • $\begingroup$ I assume that $(a,b,p)$ is a valid triple for ECCDH (if not, then ECCDH is not secure), then $n$ must be prime. So Calodeon has right. If $n$ is not a large prime, Pohlig-Hellman is applied. Since the OP is interesting in ECCDH, the domain parameters have many constraints (one is that $n$ is a prime number). $\endgroup$ – 111 Sep 16 '15 at 2:13
  • 1
    $\begingroup$ @111, the OP says that the user chooses the parameters $(a,b,p)$, which means he can't influence them, meaning he can't reject any set of parameters and the task to find out whether the parameters would be secure is delegated to the user. Furthermore the OP didn't use the word "secure" or "safe" or something similar at any point in his question. Because of this the answer won't assume $n$ to be prime (or a small multiple of a prime). But to come to your point: The answer indeed strongly suggest that using standardized curves is alot better. $\endgroup$ – SEJPM Sep 16 '15 at 20:18

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.