OpenSSL - creating random elliptic curve and measuring performance

Question

I want to generate random elliptic curves (over $\mathbb F_p$ and $\mathbb F_{2^m}$) using OpenSSL, that's my task.

At first curves over $\mathbb F_p$. Now I am able to generate prime $p$, $a$ and $b$. Then I need to get random point and measure time of adding and multiplying points.

To get random point:

1. I need to know order of the group. So I should count it with Schoof–Elkies–Atkin algorithm, right?

2. I need to have generator (base point), right? So I have to find it. It can't be random point, but it should be point which generates as much as possible points on the curve, right? (depends on cofactor, if is it = 1, then generator generates all the points, if it is 2, then it generates 1/2 of points, etc).

I found I can find generator with this algorithm:

1. $|E(\mathbb F_p)| = k \cdot r$ with a prime $r$.
2. Choose a random element $x_0 \in \mathbb F_p, 0 < x_0 < p$.
3. If $x_0^3 + a x_0 + b$ is square in $\mathbb F_p$, we denote by $y_0$ a square root of $x_0^3 + a x_0 + b$ in $\mathbb F_p$. Otherwise we choose new random values $x_0$ until we succeed.
4. We may assume $1 \leq y_0 \leq p − 1$. $y_0$ may be computed using Shank’s RESSOL algorithm.
5. $(x_0, y_0)$ is a point in $E(\mathbb F_p) \setminus \{\mathcal O\}$.
6. If $k \cdot (x_0, y_0) \ne \mathcal O$, then $G := k \cdot (x_0, y_0)$ is a point of order $r$, $r \cdot G = \mathcal O$.

This algorithm is from this paper (PDF), page 11.

Is all what I wrote correct, or is there any other easier way how to get generator (base point) and order of the group? (Maybe there are some functions in OpenSSL but I didn't find it.)

EDIT: Exists some code in C of SEA algorithm? I need to generate elliptic curves (so I have to find the order of the group because I want to find base point) on devices with constraint resources (rasp pi etc). It have to be multiplatform. I thought I could copy some code to my appliacation.

Answer 1

Yes. The hard part is of course to find the order of the elliptic group and its factorisation. Ideally, if the order of the group is a prime number (use a primality test), you know that $k = 1$, and any point on the curve is a good generator.

That said, it is not because you have found an elliptic group with prime order, that it is a cryptographically safe group. For instance, if the order of the group equals p when you are working over $F_p$, you have a cryptographically weak curve.

There are other conditions that give rise to cryptographically weak curves. Generating a cryptographically good curve is somewhat tricky.

If this is for a toy example, with relatively small curves for illustrative purposes only, then as others said, use Sage.