# What are the requirements for a random number generator to a be safe to use in cryptography?

When I look at most RNG's (random number generators), I see a disclaimer that looks similar to this:

Caution: Mersenne Twister is basically for Monte-Carlo simulations - it is not cryptographically secure "as is".

1. What are the requirements for a (pseudo-) RNG to be 'cryptographically secure'? What tests/logic is used to decide that a RNG is secure for this purpose or not?

2. What are the general differences between secure and non-secure RNGs? Are secure RNGs usually just far more complex/include larger seeds and more manipulation of data? Is it ever possible to make a non-secure RNG secure by adding a series results obtained from it or using a result as a seed to produce new results that are 'more random'?

3. What is the problem with using non-secure RNGs for cryptography? I have no doubt that the cryptography would be much easier to break, but how is this actually done? Does the cracker somehow recognize a pattern in the data that is characters of a certain RNG and use this to help 'remove' the randomness from the clear-text?

NOTE: Please leave a comment if you think this question should be broken up; I know the different parts are related, but if they are complex enough to merit more specific treatment I will gladly separate them across multiple posts. :D

• I'd also add that the basic requirement is that you cannot create a predictor function, i.e. you cannot create a function such that `P(f(G(s)|1..n) = G(s)|n+1) > 0.5 + epsilon` where `f` is your predictor, `G` is your RNG and `s` is the seed without `f` knowing `s`. – Polynomial Apr 21 '12 at 15:12
• As long as you quantify "better than 0.5" as "0.5 plus some non-negligable value", then that's correct. I'd also go as far as saying that you don't need to qualify it as polynomial time - a break is anything with a lower time complexity than a bruteforce, which includes some NP solutions (e.g. `n log(n)`) – Polynomial Apr 22 '12 at 11:02