A high-entropy randomness generator
This cartoon of Dilbert has always fascinated me. You can never be sure about randomness, since the concept of randomness itself provides uncertainty to the process. A few years ago, I even wrote a post on how to achieve randomness using deterministic methods. Nowadays, entropy can always be improved to obtain a more accurate (in this case, it would be more appropriate to say “less accurate” instead) result. This can lead to many philosophical discussions, which are not my purpose.
The traditional approach has been to take contextual information (such as the UNIX time) to create a seed for the algorithm and give more uncertainty to the process. This might be sufficient for 99% of our purposes, but leads to more complex problems: For instance, it is easy to determine when a user logged into a system, and if at this time a random number is generated to generate some cryptographic keys at the same time, it is easy to establish an interval when the user was logged in (and therefore be closer to the seed of the random algorithm). It is still difficult to determine accurately the exact time, but definitely not impossible: systems of huge relevance face this problem daily.
Recently, I published in the Android Market Chinese Radicals, a program to learn Chinese. Since I need to randomly choose the Chinese radicals for the program, I decided to use it as a testbed to extend my experiment from 3 years ago. The approach uses some “contextualization” of the seed, and combines it with a probability density function. The explanation can get really complex, but I’ll try to summarize:
- At a certain point of execution, I categorize the accessible memory of the thread where the software is running (size and number of memory blocks). This information is stored and modeled for the density function.
- Afterwards, I take the UNIX time of the system. I apply a probability distribution to the model saved in the first step, and then combine it with this second point. I store the current time, and apply a first pass.
- When the generation of the random number is finished, I determine the difference between that time and the time I stored in step two. Since the memory information saved in point 1 (the entropy of the system) might differ, this time will likely be different. Then I apply a second pass to generate, with more certainty, the random number.
I have released this generator as a Java .jar. You can include it in any Java project (Swing, Blackberry, Android, etc). You can download it from here. It works as follows:
- Import the jar
- Import the class com.randomizator.Randomizator, and create an object Randomizator by using Randomizator myObject = new Randomizator();
- Using randomizator.getInt( interval ) will return you a random number between 0 and the number provided.