[curves] Generating nonces for Schnorr signatures

[Trevor Perrin]

So Ed25519 and Goldilocks are similar in generating the private scalar
and signing nonce from a "master key":

Ed25519
--------
private_scalar[32], nonce_key[32] = SHA512(master_key[32])
sig_nonce[32] = SHA512(nonce_key[32] || message) % q

Goldilocks
--------
private_scalar[56] = SHA512("derivepk" || masterkey[32])
sig_nonce[56] = SHA512("signonce" || masterkey[32] || message ||
masterkey[32]) % q


Qs
 * Is it weird that the range for Goldilocks private scalar and nonce
is size 2^256, rather than the size of the main subgroup (~2^446)?

 * Goldilocks uses envelope-MAC for the nonce, Ed25519 doesn't care
about length extension.  I can't think of a reason length extension
matters?

 * Seems like it would be more traditional for nonce derivation to pad
the secret key out to a full SHA512 block (128 bytes), HMAC-style.

 * Is there any worry that a pair of messages could be chosen to
produce a sig_nonce collision but different hash values for the
Schnorr signature, thus leaking the private key?  Is that an argument
for *also* adding some per-signature random data into nonce
derivation?  I suppose prefixing the secret key makes
collision-finding hard.  (But note that the IETF's attempt at this,
RFC 6979, hashes the message by itself for nonce derivation, so would
be unsafe with Schnorr signatures.)

 * Suppose you're given an existing private scalar.  What's the best
way to do nonce generation from that?
  - sig_nonce = HASH(PAD(private_scalar) || message)
  - sig_nonce = HASH(PAD(private_scalar) || random() || message)
  - sig_nonce = HMAC(private_scalar, random() || message)
  - nonce_key = HMAC(private_scalar, random()),
sig_nonce=HMAC(nonce_key, message)

Something else?


Trevor