Compressing EC private keys

Question

For reasonable security, EC private keys are typically 256-bits. Shorter EC private keys are not sufficiently secure. However, shorter symmetric keys (128-bits, for example) are comparably secure.

I have a case where I need to regenerate an EC private key (that can be constructed by a special method) with as little stored information as possible. Fewer than 128-bits is not possible without compromising security against an exhaustive search.

I'm curious if I can use the following method:

1. Generate a random 128-bit value. This is the value I would store to recreate the private key.

2. Use a 256-bit hash, say SHA256, of the random value as the private key. (I have a method to do this that doesn't bias any keys over any others.)

3. The corresponding public key would be made public.

Thus, I can regenerate the private key from the 128-bit value. It seems to me that the private key and 128-bit value should be just as secure as using a random 256-bit value for the private key and storing that. Exhaustive search is clearly impractical, and the properties of the EC key shouldn't be capable of being walked backwards either from the public key or through the hash. In principle, the EC search space is halved, but it doesn't seem like there would be any practical way to take advantage of this.

Is there anything I'm missing? Is there any reason this wouldn't be just as secure as storing the full 256-bit key? Assume the public key and the algorithm are known to potential adversaries. The adversary's goal is to get the private key. It seems to me that this is obviously as secure as the underlying algorithms, but I know enough not to trust myself.

Answer 1

What you suggest is valid. Here is a way to show it:

In a fully implemented signature system (things are similar for asymmetric encryption), there are three modules:

• a key pair generator, which produces a pseudo-random key pair;
• a signature generator, which uses the private key to produce a signature over some piece of data;
• a signature verifier, which verifies a signature over some piece of data, using the public key.

It is acceptable that the key pair generator is a deterministic algorithm, provided that it is "cryptographically strong" and works over a "long enough" secret seed. "Long enough" means: a string of length at least $t$ bits if a security level of $2^t$ must be achieved.

What you suggest is simply storing the PRNG seed instead of storing the output of the key pair generator. You run the PRNG again each time you want to use the private key. Since the PRNG is deterministic, this yields the exact same signatures that you would have obtained if you had stored the private key, so, from the outside, this is indistinguishable from the "normal" setup. Hence the security.

The concept is applicable to any asymmetric algorithm, not just EC-based algorithms. You could do so with, e.g., RSA, using the PRNG to regenerates the primes $p$ and $q$. However, for RSA, the cost would be high (generating a private key is considerably more expensive than actually computing a signature) and the generation process is susceptible to partial leakage through timing attacks, so this would be a bit delicate. For algorithms such as DSA, Diffie-Hellman or ElGamal, or their EC variants, a private key is just a random value modulo a given $q$ (the group order), so that's fast.

The only tricky point is to show that "one SHA-256 invocation" is a suitable, cryptographically strong PRNG, when you only want 256 bits of pseudo-alea. In the random oracle model, no problem. In a practical world of standard compliance and administrative acceptance, you might want to use an Approved PRNG, in particular HMAC_DRBG (that's the one NIST considers to be "the strongest").

Note: it is not strictly necessary to have an unbiased selection of the private key. For (EC)DSA, there is a private key $x$, and, for each signature, a new random $k$ modulo $q$ must be generated. It is crucial that $k$ is negligibly biased; but for $x$, you can be a bit more lenient. For instance, for a curve where the subgroup order $q$ has size 256 bits or more, it suffices to generate a single 256-bit integer, and reduce it modulo $q$. Some values may have a twice higher chance of being selected than others, or, if the size of $q$ is greater than 256 bits, some values have probability zero of being selected; but this is not an issue for $x$. For $k$, this would be a very serious problem.