# Relation between key size and PRNG state size

Some (supposedly) cryptographically secure PRNGs have an internal state of only 160 bits or less. When the algorithm is otherwise properly designed, that seems like enough to generate a 128 bit key for e.g. AES.

Can the PRNG also be used for the generation of longer keys, e.g. RSA keys with 1024 bits?

My intuition is that it would take (on average) a brute force attack of 2^159 key generations to find the same key, which is probably harder than factoring the 1024 bit key (according to various key length comparisons).

Is there an easier way to crack an RSA key generated using such a PRNG? The OpenSSL PRNG documentation states that an internal state of at least 4096 bits is required to securely generate an RSA-4096 key; that would contradict my intuition.

-
+1 interesting question. "bits" in RSA and symmetric crypto mean vastly different things. 4096 bits in RSA means the size of the semiprime, while 160 bits in symmetric crypto means a keyspace with $2^{160}$ elements. Do you really need a keyspace of 4096 bits in RSA to achieve 4096 bits of security in RSA, or is say 128 bits enough, assuming that you use that keyspace to generate 4096 bit semiprimes? –  nightcracker Sep 10 at 5:38
I'd use a pool size twice the security level to avoid collisions during the one-way function step. The trickier part are the additional accumulator pools a fortuna like construction needs. –  CodesInChaos Sep 10 at 7:28
@nightcracker Generating an RSA 1024 key from a 128 bit seed is completely fine. For 4096 bit RSA I'd use a 256 bit seeds. –  CodesInChaos Sep 10 at 7:31