18
$\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?

Improve this question
$\endgroup$
7
  • 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
    Commented Sep 4, 2015 at 15:30
  • 2
    $\begingroup$ This answer of mine explains how to compute the order of an elliptic curve. $\endgroup$
    – yyyyyyy
    Commented Sep 4, 2015 at 18:38
  • $\begingroup$ also see eprint.iacr.org/2015/366.pdf, for a new method to generate parameters for ECC. $\endgroup$
    – 111
    Commented Sep 7, 2015 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
    Commented Sep 9, 2015 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 Bodewes ♦
    Commented Sep 12, 2015 at 13:34

1 Answer 1

Reset to default
10
+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:
  3. Set $t\gets t/p_i^{e_i}$
  4. Compute $A_1\gets t\cdot A$
  5. 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$
  6. 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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Sep 11, 2015 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
    Commented Sep 12, 2015 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
    Commented Sep 16, 2015 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
    Commented Sep 16, 2015 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.