In the past I have used the Chi-squared test to check the statistical randomness of my generator. Is this a good test to use? Are there other tests?
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Section 5.4 "Statistical tests" of Handbook of Applied Cryptography lists several such tests. However, note that if you're after a provably secure PRNG, such tests are far from being perfect.
For a provably secure PRNG, you need to formally prove the indistinguishability of its output from a truly-random sequence. See chapter 3 of Foundations of Cryptography for more info.
Checking statistical randomness is a semi-good test. What I mean by that is that if a given PRNG does not look good statistically, then it is utterly proven to be pure junk. On the other hand, good statistical randomness does not tell you much with regards to cryptographic security. Cryptographic security is about whether the PRNG output could be predicted by a sentient attacker who knows the in and outs of your algorithm (but not its internal state). Statistical randomness is about whether the PRNG output could be predicted by a trained monkey.
"Diehard tests" used to be popular for testing non-cryptographic PRNG. During the AES competition (a dozen years ago), NIST ran them on all AES candidates, and found nothing, and the general opinion among cryptographers was that it was mostly a waste of time.
A Linear Feedback Shift Register has handsome results with Diehard -- and using it for cryptography is immediate failure.
That depends on what exactly you mean by “working correctly”.
You can do statistical tests to check for various statistical flaws your random number generator might be subject to, but you have be aware of the fact that statistical testing cannot serve as a substitute for cryptanalysis… meaning: when it comes to cryptographic security, you’ll have to dive into cryptanalysis, like I described in another answer to a somewhat related question.
Of course… besides the Chi-squared test you already know and mentioned in your question, there are whole batteries of statistical tests available! All you have to do is to pick your favorite poison:
There might be other solutions out there which may or may not be interesting to look at, but – to limit the scope to a usable level – I decided to only mention some of the (more prominent) statistical test suites.