1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You may find it easier to do all this with Sage than with OpenSSL. OpenSSL is intended for cryptography applications that use standard algorithms and curves, not for exploration in the math and curve selection. $\endgroup$ – Squeamish Ossifrage Dec 2 '17 at 23:45
  • $\begingroup$ @SqueamishOssifrage Thanks, you mean this? $\endgroup$ – Daniel Herbrych Dec 3 '17 at 9:31
  • $\begingroup$ Yes, that's the Sage I mean. You can see an example of its use in elliptic curve design at SafeCurves: safecurves.cr.yp.to/verify.html $\endgroup$ – Squeamish Ossifrage Dec 3 '17 at 16:57
  • $\begingroup$ Why do you want to generate curves on devices with resource constraints? What is your actual goal here? $\endgroup$ – Squeamish Ossifrage Dec 8 '17 at 3:12
  • $\begingroup$ @SqueamishOssifrage Because it's my diploma thesis... And I think now it's not as easy as I thought. For example curves over Fp, I generate a, b, p. But if I want to compute base point, I need to know order of the curve what should be done with SEA algorithm. And I can't find code of SEA, maybe I have to implement myself in C. Not easy, or? $\endgroup$ – Daniel Herbrych Dec 8 '17 at 11:03
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks!! So for example, if mod p = 11, then group is {0,1,2,3,4,5,6,7,8,9,10} and every number can generate all other numbers, except 0? And order of the group is p-1 = 10? So all numbers are generators (except 0). Is that right? You said if I have group over Fp, then order of the group equals p isn't much safe. This mean I shouldn't use group F_p^1 but power of prime number p, for example F_p^5? Because if I have group F_p^1, then order of the group is p-1. Isn't it? Thanks a lot! $\endgroup$ – Daniel Herbrych Dec 3 '17 at 13:34
  • 1
    $\begingroup$ @DanielHerbrych Be careful ! Don't confuse the elliptic group with the modular multiplicative group of the field ! If $p = 11$ for $F_p$, then you're right that the order of the multiplicative group of $F_p$ is 10 (namely $p-1$). But that's not necessarily the order of the elliptic group of a specific curve (with a chosen $a$ and $b$). Hasse's theorem tells us that this order is not very far away from 11, but it doesn't have to be 11 at all. For big elliptic groups, it is not easy to find their order (Schoof's algorithm must be used). $\endgroup$ – entrop-x Dec 3 '17 at 15:37

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.