# Can A PRNG Be Used To Generate Multiple Private Keys for ECDSA?

Suppose Alice seeds a cryptographically strong Pseudo Random Number Generator with a truly random number, and keeps it secret. Alice then uses the output of the PRNG to generate several 256-bit numbers in sequence. Each of those 256-bit numbers is then used as an ECDSA private key, public keys are generated from them, and those public keys are sent out in the open. The private keys are either kept secret, or destroyed.

An attacker, Mallory, collects a bunch of public keys, some of which belong to Alice. Two questions:

1. If not told explicitly, can Mallory figure out which keys belong to Alice?

2. If Mallory does know which keys belong to Alice, can he figure out any of the private keys (or the initial seed)?

My concern is that, since the private keys are mathematically related, information about their relation may be leaked through the ECDSA public key generation (Q = kG). Most implementations of ECDSA I have seen use a PRNG that is frequently re-seeded, like OpenSSL. Presumably, though, one could generate multiple keys sequentially without a re-seed occurring. That being the case, I assume the above is safe. I am, however, having a hard time coming up with a proof for it.

• That was my intuition as well, and thank you for the response. Here is my issue: If a and b are sequential outputs from a CSPRNG, calculating b from a should be intractable or impossible. This is as you said, and is indeed the requirement for a CSPRNG. However, I cannot figure out a way to logically prove that calculating public key Qb from Qa must also be intractable, given the above, and given that Qb = b*G and Qa = a*G. I agree with your intuition that it must be so ... but I just can't figure out a logical proof for it. – Xor May 13 '12 at 18:59
• According to WikiPedia, the only requirements for a CSPRNG are passing the "next-bit test" and withstanding "state compromise extensions". Qa does not give you information about a. So, being able to calculate Qb from Qa does not allow you to predict b from a. Thus, it does not violate either of the two requirements for a CSPRNG. Example: Suppose PRF(0) = 0, PRF(i) = PRF(i-1) + 1. It can be shown that Qb = Qa + G, and that b = a + 1. But neither b nor a can be calculated. – Xor May 14 '12 at 20:57