How to safely and randomly iterate a key derived from Scrypt?

I'm developing a way to deterministically generate private keys for arbitrary elliptic curves based on some user-input (a brain-wallet). Currently, I'm using the Scrypt password hashing algorithm with robust difficulty parameters to hash a number of input parameters into a key.

The output of Scrypt should be uniformly distributed among $[0, 2^{b})$ where ${b}$ is the number of output bits used from the Scrypt algorithm output. But valid elliptic curve private keys must be less than the curve's finite field order $N$, distributed evenly among $[0, N)$. Thus, using the output of Scrypt directly as a private key mod $N$ would create a small bias in the resulting keys that are generated - bad news, so I need to avoid that.

Normally if you were generating private keys using a secure RNG, you would simply retry the RNG until you got a number less than $N$, and you could safely use that as a private key.

Is there a safe way to deterministically iterate the output of Scrypt, such that we preserve the pseudo-random distribution of Scrypt's output, without having to re-run Scrypt with new parameters?

One way I considered was hashing the output of scrypt with SHA256 or SHA512 until it was less than $N$, but this wouldn't work so well for curves larger than 512 bits, such as P521.

Another less elegant solution is to simply reject any input parameters which produce a key larger than $N$. It should be very rare for it to ever occur, so perhaps I can get away with it? Are there any common curves out there whose order $N$ is not a significant fraction of its next-highest power of two?

First, using a private key that's deterministically derived from a password is almost always wrong. Passwords are often compromised or forgotten and therefore need to be changed. If changing the password requires more than updating a small amount of data in one place, you have major operational difficulties. So normally the only thing you should do with a key that's derived from a password is key wrapping, i.e. the password-derived key is only used to symmetrically encrypt a file containing the “real” keys. Those real keys are stored, and they aren't deterministically generated from anything, they're just randomly generated. When the user updates the password, re-encrypt that file with the new password-derived key and delete the previous version.

That being said, to derive an elliptic curve key deterministically, the first step is to consider the curve type.

• For Curve25519 and Curve448, keys are calculated from a fixed uniformly distributed bit string as specified in RFC 7748 §5. There is a precise process taking a 256-bit or 448-bit uniformly distributed input, forcing certain bits, interpreting the bits as a number (little-endian), and reducing to the canonical representative modulo $p$. Because $p$ is extremely close to the next power of $2$, the modulo reduction leaves the number unchanged with overwhelming probability. Implementations of Curve25519/Curve448 typically (“MUST”) accept keys in non-canonical form, so you don't have to do anything other than provide the uniformly distributed 32-byte or 56-byte string.

• For Ed25519 and Ed448, private keys are specified in RFC 8032 §5.1.5 and §5.2.5 as a uniform 32-byte or 57-byte string respectively. The signature process starts by hashing this input (concatenated with other strings) and uses the result as an integer.

• For NIST curves and generally curves in Weierstrass form, there is no single universally accepted process to go from bit strings to private keys. FIPS 186-4 §B.4 describes two possible methods to generate a private key from the output of a random generator, and these methods are equally applicable to deriving a private key from a uniformly distributed bit stream obtained from a symmetric key derivation algorithm. To derive a private key on a curve whose order $p$ is an $n$-bit prime:

  1. (“Extra random bits”) Obtain $n + 64$ bits of uniformly distributed ((pseudo-)random) secret input. Interpret that input as a big-endian integer, reduce it modulo $p-1$ and add $1$ to obtain a number in the range $[1, p-1]$. Some keys are very slightly more likely than others, but since the bias is about $2^{-64}$, it offers no practical advantage to an adversary.
  2. (“Testing candidates”) Obtain $n$ bits of uniformly distributed ((pseudo-)random) secret input. Interpret that input as a big-endian integer. If the result is $\ge p-1$, start the process again from the beginning. Otherwise add $1$. This has no bias at all, and doesn't require manipulating numbers larger than $n$ bits, but it has the downside that you don't know in advance how much uniformly distributed input you'll need: it's potentially unbounded.

  The first method is generally more convenient since you know exactly how much (pseudo-)random input is needed.

If you really need to chain this with a password-based key derivation algorithm such as scrypt, there are two methods.

• The direct method is to request as much input as you need from scrypt. For Weierstrass curves, this makes the testing-candidates method impractical. So get 32 bytes from scrypt for Curve25519 or Ed25519; 40 bytes for P256R1 or P256K1; 56 bytes for P384R1 or P384K1; 57 bytes for Ed448, etc.
• The indirect method is to request a fixed number of bits from scrypt. This needs to be enough to not be guessable by brute force. 128 bits (16 bytes) will do nicely. Use this as a seed to an ordinary (not password-based) key derivation function such as one from NIST SP 800-108 or HKDF, or as a seed to a pseudorandom generator algorithm such as one from NIST SP 800-90A. Use that PRNG output to derive the private key.