Elliptic curves for ECDSA: choosing "generator"

Question

G(Gx, Gy) -- which is also called generator -- is a point on Elliptic Curve (EC) on Finite field. Finite field size = p -- prime modulus.

Say we have an EC(Fp): y**2 = x**3 + ax + b (mod p)
How should the point G be selected on it?

Does every point has to be found on EC(Fp) and then chosen one of those?
Or Gx\ Gy have to be somehow specific?

The only thing i know: G's order must be a prime number.

P.S. Sorry for my English and Thank you.

Abridge

Not every elliptic curve group has a generator. Some are cyclic, but others are the product of two cyclic groups. But the question is really too mathematical for stack overflow. You can already avoid these tricky mathematics by using one of the predefined curves in FIPS 186-3. May I ask: what are you trying to do? – Grider

@GregS, Thank you for the FIPS 186-3. Found there:"value of G should be generated canonically (verifiably random)." Are you sure about:"Not every elliptic curve group has a generator"? # about the question in the end: trying to implement curve generation for ECDSA; – Abridge

Yes, I am sure. Not every elliptic curve is cyclic. As I said, the discussion is too mathematical for SO. Whether or not a point generates the curve group is not significant anyway. What matters is the order of the group generated by the point. – Grider

@GregS, OK then. Remains to discover how to choose a point on curve with a prime order. Thanks again. – Abridge

Seems like a generator may be selected randomly and then multiplied by the cofactor = (curve cardinality)/(point order), where cardinality is a number of the points on the curve. – Abridge

Yes, that is the usual way to do it. The hard part is generating a new curve and finding the order of the curve group. You can pick a random curve and count the points with the Schoof-Atkins-Elkies algorithm. The curve may turn out to have an unsuitable order, in which case you must try again with another random curve. Lots of computation there. Or, you can create a curve with complex multiplication (CM) with a known order. Lots of tricky math there unless you can find an existing package. – Grider

Hi Ted, Try crypto.stackexchange.com next time for these kind of questions. – Bedchamber

Hello Owlstead i did try and wouldn't have written here if i had received an answer there. Still thank you – Abridge

I heard people saying that Miracl SDK has C++ implementation of function for generating new elliptic curves and finding out curve order. – Autotrophic

Answer 1

The usual practical solution is to use a precomputed set of parameters. You'll find some in sec2v2 section 2. A popular choice for IT security is secp256r1. That gives p, a, b, and a standard G. The order of that G is the prime n.

For Gx and Gy strip the leading 04 byte in the uncompressed version of G, and split the remaining 64 bytes into two 32-byte bytestring, which are Gx and Gy in big-endian binary.

How should the point G be selected on it?

Since the cofactor h for that curbe is 1 (as for all the curves in sec2v2 section 2), any point on the curve that is not the point at infinity also has order the prime n. One can be found by taking a random x, computing y**2 mod p by applying the curve equation, until that's a quadratic residue as testable by the Legendre symbol. One of two suitable y can then be found by extracting a modular square root e.g. with Tonelli–Shanks.

Coming up with your own parameters of cryptographic interest usually involves the Schoof–Elkies–Atkin algorithm. It's build into PARI/GP, and from that available in SageMath. Beware there are other desirable criteria beyond cofactor 1 and prime order to choose a secure Elliptic Curve.

For toy parameters, one option is to find the order of a random point on a random Elliptic Curve (determined as for G) until finding one of prime order.

Regulable