Some (supposedly) cryptographically secure PRNGs have an internal state of only

Question

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.

Explanation / Answer

Your intuition is correct.

While more bits of entropy is better when generating a key, attacking RSA through the key generation process is an independent attack of factoring the modulus, and is predicated on a different computational hardness assumption, search of the keyspace compared to the hidden subgroup problem for finite Abelian groups (for factoring or discrete logarithm.) Factoring at least seems subexponential but superpolynomial, so is significantly easier than search; Many search problems appear to be NP hard, with exponential time complexity in the average case.

The attack on the key generation process depends on the cryptographic strength of the PRNG, and is analogous to attacking a symmetric ciphers in many ways. Since the attacks against PRNG's are so similar to attacks against symmetric ciphers, you can use the guides at keylength for symmetric ciphers as guides to the minimum state for key generation as its entirely appropriate. If you're using RSA for key exchange, and your symmetric key length is smaller than the key length of your PRNG seed, they won't bother attacking the key generation process.

The question does highlight a very important concern about prudent cryptography however, and that is that key generation is highly vulnerable to attack by poor implementation. A cryptographically secure PRNG is essential if using a PRNG for key generation.

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.