4
$\begingroup$

I'm working on a cryptosystem based on ECC (elliptic curve cryptography). I need to choose several (~10) curve points which should be used as generators, and it's important that their relation is unknown, i.e. no one should be able to obtain one generator by multiplying another one by some scalar.

So that just choosing all the generators in a random manner isn't good idea, because some may suspect that they're not actually random, and their relation is known.

Natural solution is to create all the generators by using hashing scheme, i.e. pick several strings and create all the generators by hashing them (or hash each generator in order to create the next). This should convince everyone that their relation is unknown.

However it's also important that the obtained curve points are indeed generators, i.e. each one forms a cyclic group which spans all the curve points.

Now, this is where I'm confused. I've read once that selecting right points isn't a trivial task, there exists an algorithm to test the rank of a point, but it's somewhat complex to implement. However I've also heard that most of the points on an elliptic curve are generators, and when selected in a pseudo-random manner it's very unlikely to fall onto a bad point.

So, what is right to do? Is it ok just to pick random points and hope for the best?

Is there an "online resouce" which can test the selected points? I mean, I can define the problem (curve formula, the prime for the underlying field order), give the point, and get its rank?

Improve this question
$\endgroup$
3
  • $\begingroup$ See datatracker.ietf.org/doc/draft-irtf-cfrg-hash-to-curve for ways to hash strings to points. $\endgroup$
    – poncho
    Apr 5, 2018 at 21:23
  • $\begingroup$ @poncho: Thanks, but this is not what I need. There's no problem to hash string to receive points, it doesn't have to be secure (obscured) in my case, all the hashes and points are not secret. My concern is about the validity of the obtained points for what I need. $\endgroup$
    – valdo
    Apr 5, 2018 at 21:27
  • $\begingroup$ You may just want to hash a single 32 bit counter, otherwise you could be running as many sentences as you like, and just keep the result that you like best. $\endgroup$
    – Maarten Bodewes ♦
    Apr 6, 2018 at 12:23

1 Answer 1

Reset to default
5
$\begingroup$

Now, this is where I'm confused. I've read once that selecting right points isn't a trivial task, there exists an algorithm to test the rank of a point, but it's somewhat complex to implement. However I've also heard that most of the points on an elliptic curve are generators, and when selected in a pseudo-random manner it's very unlikely to fall onto a bad point.

Actually, finding a generator is typically a lot easier than what you've read, at least in practice.

In crypto, we generally use curves that have an order of the form $hq$, where $q$ is a large prime, and $h$ is a small integer.

So, what you do is:

  • Run your hashing function to create an arbitrary point $H$

  • Multiply it by the cofactor $h$ to find the point $H' = hH$ (which is totally trivial for those curves with $h=1$; not that difficult for curves with larger cofactors)

  • Verify that $H'$ is not the neutral element (aka the identity aka the point at infinity).

If $H'$ is not, then that's your generator; it's guaranteed to be of order $q$, and to have no known relationship with other points (assuming that your original point $H$ didn't)

Improve this answer
$\endgroup$
6
  • $\begingroup$ I see, thanks. I'm using the curve defined in secp256k1 (used by bitcoin). They provide the order of the group for the generator they suggest, and it's very close to 2^256. However they don't claim it's a prime number (at least I didn't notice this), hence - what's the co-factor? $\endgroup$
    – valdo
    Apr 6, 2018 at 7:25
  • $\begingroup$ See here where it states h=01. $\endgroup$
    – Maarten Bodewes ♦
    Apr 6, 2018 at 12:20
  • $\begingroup$ @poncho If I'm not mistaken the chance of generating the point at infinity is abysmally low, right? And multiplying may still involve some math to make sure that H' is of the right order, correct? $\endgroup$
    – Maarten Bodewes ♦
    Apr 6, 2018 at 12:24
  • $\begingroup$ @poncho: Thanks for the link. So, does it actually mean that any point on the curve is either zero (inf), or has the same rank (which is a prime number)? $\endgroup$
    – valdo
    Apr 6, 2018 at 12:34
  • 1
    $\begingroup$ @valdo: yes, for curves with cofactor 1, that is, a curve where there is a prime number of points, then all points (other than the PoI) generates the entire curve, and thus is the same prime order $\endgroup$
    – poncho
    Apr 6, 2018 at 12:49

Your Answer

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

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