4
$\begingroup$

I see a lot of Q/A where persons are trying to generate a specific key pair using static data such as a password. Now say we use a known PRNG (dangerous assumption), seeded with a the data as a static seed, would this always generate the same key pair?

I presume it would generate the same key pair if you would use the exact same generation method - the application would be deterministic. I would however expect differences between implementations. The random data could be used differently, the sizes of p and q could differ and there may be subtle differences when choosing the prime numbers themselves.

Improve this question
$\endgroup$
6
  • $\begingroup$ Sorry for partly answering .y own question. And no, I would never do this myself... $\endgroup$
    – Maarten Bodewes ♦
    Sep 6, 2013 at 23:00
  • 1
    $\begingroup$ Maybe this answers your question: crypto.stackexchange.com/questions/1662/… $\endgroup$
    – lxgr
    Sep 6, 2013 at 23:10
  • $\begingroup$ @lxgr It comes very close to answering the question, except that I would like a confirmation of my belief that switching to even a slightly different RSA key pair generation function (that still complies to the RSA standard) would generate a different key pair. $\endgroup$
    – Maarten Bodewes ♦
    Sep 6, 2013 at 23:16
  • $\begingroup$ Removed the last part of the question as that part has already been answered in above link by @lxgr. $\endgroup$
    – Maarten Bodewes ♦
    Sep 6, 2013 at 23:20
  • $\begingroup$ Obviously, a 2048 bit two-prime RSA modulus can't have any factors in common with a 1024 bit two-prime RSA modulus, so, yes, changing the parameters might entail different output. The same goes for implementation details: E.g. using a sieve or generating every candidate at random will also lead to different output even if the DRBG sequence is the same. $\endgroup$
    – Henrick Hellström
    Sep 7, 2013 at 7:56

1 Answer 1

Reset to default
2
$\begingroup$

To begin with, we have to assume your deterministic random bit generator is adequate for generating practically indefinite bit sequences given a single seed, and that your prime generation algorithm is such that it will always output a prime eventually, given any such indefinite pseudo random bit sequence.

Obviously, a 2048 bit two-prime RSA modulus can't have any factors in common with a 1024 bit two-prime RSA modulus, so, yes, changing the parameters might entail different output. Given my initial assumptions you will get an output in both cases, and they can't be the same for purely arithmetic reasons.

The same goes for implementation details: E.g. using a sieve or generating every candidate at random will also (likely) lead to different output, even if the DRBG sequence is the same.

Consequently, if you are asking e.g. because you want a way to store RSA private keys in a compressed format, your compressed format must contain an unambiguous indication of the number of primes to be generated, the bit sizes of these primes, the algorithm to be used for generating them, as well as any other parameter of the algorithm that might influence the output.

OTOH, if the problem is rather that you are looking for ways to tell if a given implementation suffers from RNG failures and has historically generated predictable RSA private keys, I am afraid this answer doesn't necessarily help much. In such case the conclusion would be that, no, you can't infer that your RNG is safe, just because your RSA private key generation procedure hasn't historically generated any prime number collisions.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Do you mind if I remove that last paragraph from your answer? Personally I don't find it to be on topic (just like the last paragraph in my own question). I primarily asked the question here for a location to point to when somebody (again) directly generates a key pair from a key or password instead of encrypting the private key. $\endgroup$
    – Maarten Bodewes ♦
    Sep 14, 2013 at 14:32
  • $\begingroup$ @owlstead: No problem, edit away, but perhaps you should narrow down your question, so that it becomes clear my then last paragraph is the adequate answer. $\endgroup$
    – Henrick Hellström
    Sep 14, 2013 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.