1
$\begingroup$

I'm new to cryptography and am most intrigued by mathematically based pseudo random number generators. With reference to the Blum Micali algorithm:

$X_{i+1} = G^{X_i} \bmod P$

can security be reduced to a simple stated seed size? I've seen claims that a 20 digit seed was sufficient to pass diehard test.

I've also read analysis that mentions the difficulty threshold of the algorithm is found in the number of operations required to solve the discrete logarithm problem. I'm unclear how this calculation directly correlates to seed size. If a given "hard" threshold is say $2^{64}$ operations, does that correlate to a $2^{64}$ bit sized seed?

Finally, does the security of Blum Micali required secrecy of G and P? I have not seen the secrecy of G and P mentioned in any analysis of security, however, this concern comes about by events such as Dual_EC_DRBG.

Improve this question
$\endgroup$
2
  • $\begingroup$ I guess most PRNG's are "mathematically based". 20 digits is about (20 /3 * 10) ~ 64 bits. That's quite a lot so it is little wonder if it is enough to pass most tests. However, any PRNG will have some internal state. You can have a 1024 bit seed, but that won't translate to 1024 bits of security. OK, that's for the generic remarks, now I've got to read Blum Micali :) $\endgroup$
    – Maarten Bodewes ♦
    Commented Jan 16, 2015 at 18:29
  • $\begingroup$ Perhaps then a better description would be a "pen and paper" type algorithm for random number generating. I just meant to differentiate my interest from other RNG such as hardware RNG's or any type that cannot be reduced to a simple mathematical statement. $\endgroup$
    – 0rob
    Commented Jan 16, 2015 at 19:28

0

Reset to default

Your Answer

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