4
$\begingroup$

Looking at a reference implementation it shows that the key pair generation simply does: read X bytes from RNG and then derive another value from these X bytes thus producing private key with derived public key.

However nowhere in documentation I see mention of what qualifies as a “good” private key (or in this case RNG). Does it mean that any [random] N between 0 and up to 64 byte max value is a “good” private key? Or did I miss any description of how the good quality keys should be generated?

Asking this because this is rather different from for example how RSA keys are generated.

$\endgroup$
  • $\begingroup$ Well, it had better be uniformly random, not, say, binomially random… $\endgroup$ – Squeamish Ossifrage Apr 12 at 1:37
6
$\begingroup$

Yes.

In order to understand why, you need to understand how the public key is computed.

The secret key is a scalar. A fixed base point is multiplied by that scalar, and no matter what that scalar value is, you will always end up with a point in the same group as the base point.

You may want to avoid an all-zero secret key but the key space is so large that if the scalar comes from a PRG, this is not something you have to worry about.

The order of the group is 2^252 + 27742317777372353535851937790883648493. The secret should be considered modulo that value. Any secret key between 0 and that value will produce a unique public key.

The secret key can be a uniform value in that range but applications usually just generate a 256 bit key, which doesn't make any practical difference.

Note that most Ed25519 implementations mask the lower 3 bits ("clamping"). So 1 will produce the same public key as 2 or 3. This is a simple way to prevent small-subgroup attacks. But once again, most applications usually just generate 256 random bits, and don't really have to care about this.

$\endgroup$
  • $\begingroup$ Note that this is not specific to the Ed25519 curve. Also note that the chance of creating a value of 253 zeros followed by 3 bits that can have any value is abysmally small; the only practical way that will ever happen is if the RNG is broken and is outputting only zeros. $\endgroup$ – Maarten Bodewes Oct 28 '17 at 10:17
  • 1
    $\begingroup$ @MaartenBodewes You mean "253 zeros"? $\endgroup$ – lovesh Apr 11 at 6:31
  • $\begingroup$ Probably, switching keyboards slightly too often (my computer is on the diner table for now and my UHK is taking up too much space - not portable enough) :) $\endgroup$ – Maarten Bodewes Apr 11 at 8:51

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.