If you want a cryptographically strong random number in Java, you use SecureRandom. Unfortunately, SecureRandom can be very slow. If it uses /dev/random on Linux, it can block waiting for sufficient entropy to build up. How do you avoid the peformance penalty?
Has anyone used Uncommon Maths as a solution to this problem?
Can anybody confirm that this performance problem has been solved in JDK 6?
I haven't hit against this problem myself, but I'd spawn a thread at program start which immediately tries to generate a seed, then dies. The method which you call for randoms will join to that thread if it is alive so the first call only blocks if it occurs very early in program execution.
The problem you referenced about /dev/random is not with the SecureRandom algorithm, but with the source of randomness that it uses. The two are orthogonal. You should figure out which one of the two is slowing you down.
UncommonMaths page that you linked explicitly mentions that they are not addressing the source of randomness.
You can try different JCE providers, such as BouncyCastle, to see if their implementation of SecureRandom is faster.
A brief search also reveals Linux patches that replace the default implementation with Fortuna. I don't know much more about this, but you're welcome to investigate.
I should also mention that while it's very dangerous to use a badly implemented SecureRandom algorithm and/or randomness source, you can roll your own JCE Provider with a custom implementation of SecureRandomSpi. You will need to go through a process with Sun to get your provider signed, but it's actually pretty straightforward; they just need you to fax them a form stating that you're aware of the US export restrictions on crypto libraries.
If you want true random data, then unfortunately you have to wait for it. This includes the seed for a SecureRandom PRNG. Uncommon Maths can't gather true random data any faster than SecureRandom, although it can connect to the internet to download seed data from a particular website. My guess is that this is unlikely to be faster than /dev/random where that's available.
If you want a PRNG, do something like this:
SecureRandom.getInstance("SHA1PRNG");
What strings are supported depends on the SecureRandom SPI provider, but you can enumerate them using Security.getProviders() and Provider.getService().
Sun is fond of SHA1PRNG, so it's widely available. It isn't especially fast as PRNGs go, but PRNGs will just be crunching numbers, not blocking for physical measurement of entropy.
The exception is that if you don't call setSeed() before getting data, then the PRNG will seed itself once the first time you call next() or nextBytes(). It will usually do this using a fairly small amount of true random data from the system. This call may block, but will make your source of random numbers far more secure than any variant of "hash the current time together with the PID, add 27, and hope for the best". If all you need is random numbers for a game, though, or if you want the stream to be repeatable in future using the same seed for testing purposes, an insecure seed is still useful.
On Linux, the default implementation for SecureRandom is "NativePRNG" (source code here), which tends to be very slow. On Windows, the default is "SHA1PRNG", which as others pointed out you can also use on Linux if you specify it explicitly.
"NativePRNG" differs from "SHA1PRNG" and Uncommons Maths' AESCounterRNG in that it continuously receives entropy from the operating system (by reading from /dev/urandom). The other PRNGs do not acquire any additional entropy after seeding.
AESCounterRNG is about 10x faster than "SHA1PRNG", which IIRC is itself two or three times faster than "NativePRNG".
If you need a faster PRNG that acquires entropy after initialisation, see if you can find a Java implementation of Fortuna. The core PRNG of a Fortuna implementation is identical to that used by AESCounterRNG, but there is also a sophisticated system of entropy pooling and automatic reseeding.
Use the secure random as initialization source for a recurrent algorithm; you could use then a Mersenne twister for the bulk work instead of the one in UncommonMath, which has been around for a while and proven better than other prng
http://en.wikipedia.org/wiki/Mersenne_twister
Make sure to refresh now and then the secure random used for the initialization, for example you could have one secure random generated per client, using one mersenne twister pseudo random generator per client, obtaining a high enough degree of randomization
If you want truly "cryptographically strong" randomness, then you need a strong entropy source. /dev/random is slow because it has to wait for system events to gather entropy (disk reads, network packets, mouse movement, keypresses, etc.).
A faster solution is a hardware random number generator. You may already have one built-in to your motherboard; check out the hw_random documentation for instructions on figuring out if you have it, and how to use it. The rng-tools package includes a daemon which will feed hardware generated entropy into /dev/random.
If a HRNG is not available on your system, and you are willing to sacrifice entropy strength for performance, you will want to seed a good PRNG with data from /dev/random, and let the PRNG do the bulk of the work. There are several NIST-approved PRNG's listed in SP800-90 which are straightforward to implement.
It sounds like you should be clearer about your RNG requirements. The strongest cryptographic RNG requirement (as I understand it) would be that even if you know the algorithm used to generate them, and you know all previously generated random numbers, you could not get any useful information about any of the random numbers generated in the future, without spending an impractical amount of computing power.
If you don't need this full guarantee of randomness then there are probably appropriate performance tradeoffs. I would tend to agree with Dan Dyer's response about AESCounterRNG from Uncommons-Maths, or Fortuna (one of its authors is Bruce Schneier, an expert in cryptography). I've never used either but the ideas appear reputable at first glance.
I would think that if you could generate an initial random seed periodically (e.g. once per day or hour or whatever), you could use a fast stream cipher to generate random numbers from successive chunks of the stream (if the stream cipher uses XOR then just pass in a stream of nulls or grab the XOR bits directly). ECRYPT's eStream project has lots of good information including performance benchmarks. This wouldn't maintain entropy between the points in time that you replenish it, so if someone knew one of the random numbers and the algorithm you used, technically it might be possible, with a lot of computing power, to break the stream cipher and guess its internal state to be able to predict future random numbers. But you'd have to decide whether that risk and its consequences are sufficient to justify the cost of maintaining entropy.
Edit: here's some cryptographic course notes on RNG I found on the 'net that look very relevant to this topic.
You should be able to select the faster-but-slightly-less-secure /dev/urandom on Linux using:
-Djava.security.egd=file:/dev/urandom
However, this doesn't work with Java 5 and later (Java Bug 6202721). The suggested work-around is to use:
-Djava.security.egd=file:/dev/./urandom
(note the extra '/./')