A high-entropy randomness generator

 

This cartoon of Dilbert always has always fascinated me. You can never be sure about randomness, since the concept itself of randomness 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 would be more appropriate to say “less accurate” instead) result.  This can lead into 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, is easy to determine when a user logged into a system, and if at this time a random number is generated to, at the same time, generate some cryptographic keys, is easy to establish an interval when the user was logged (and therefore being closer to the seed of the random algorithm). Is still difficult to determine accurately the exact time, but definitely not impossible: systems of huge relevance face this problem daily.

Recently a publish in the Android Market Chinese Radicals, a program to learn Chinese. Since I need to choose randomly the Chinese radicals for the program, I decided to use it as a testbed to extend my experiment from 3 years ago. The approach is using some “contextualization” of the seed, and combining it with a probability density function. The explanation can get really complex, but I’ll try to summarize:

  1. At a certain point of execution, I categorize the accesible 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.
  2. 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.
  3. When the generation of the random number is finished, I determine the difference between that time and the time I stored in the step two. Since the memory information saved in the 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 in any Java project (Swing, Blackberry, Android, etc). You can download it from here. It works as follows:

  1. Import the jar
  2. Import the class com.randomizator.Randomizator, and create an object Randomizator by using Randomizar myObject = new Randomizator();
  3. Using randomizator.getInt( interval ) will return you a random number between 0 and the number provided.

So far only the generation of integer values is supported. Please, check it out and let me know what you think.