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.

 

Bookmark the permalink.

2 Comments

  1. Thank you for the Comer link, Sam. I’ve been familiar with the liimts of java.util.Random but I find it fascinating how the visualization illustrates patterns in the data. The site may be a useful pedagogical tool to drive home the point to students that they shouldn’t trust software-based random numbers.I’ve read some thing about hardware assisted random generators which use environmental factors, such as humidity and temperature, to seed a software generator. Its not foolproof, but I bet it is close enough for this fool.

  2. / Hello! Someone in my Facebook group shared this wesbite with us so I came to give it a look. I’m definitely loving the information. I’m bookmarking and will be tweeting this to my followers! Great blog and great design and style.

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>