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.

 

cvBlob library for Android

I recently moved to Barcelona to start working in here. Although I’m not working in any computer-vision based project, I still keep a high interest in this field, trying to conduct as many personal projects as possible. My work team is highly motivated and full of professionals, and we all keep our personal projects besides our work.

Recently I met Fegabe in Barcelona, who’s a member of the GTUG Barcelona core team and an Android Developer. We decided to start together a Sudoku Solver for Android. Although there are already many of them published in the Market, we just wanted to do it for fun and to get a bit deeper into computer vision and pattern recognition. There is an OpenCV port for Android, but we decided to keep our implementation pure Java.

The following steps are applied in order to capture, detect and solve the Sudoku:

-The user must take a picture of the Sudoku using the camera of the device.

-After the picture is taken, a Threshold is applied to the image, so we can get a black and white version. Of course, there is some preprocessing involved. Things like smoothing out noise, some morphological operations, etc.

-When the picture has been taken, we apply a blob detection in order to detect the biggest segment of the image. We work under the assumption that this segment will be the outer line of the Sudoku table.

-Afterwards, we can use the Hough transform to get lines in the image. It returns lines in mathematical terms. So after this step, we’ll know exactly where a lines lies… and not just the pixels where it lies.

-When the lines has been detected, it will be easier to locate each individual cell. The number inside will be recognized using a neural network.

-The last step is the easiest: we just solve the sudoku by using any of all the known algorithms

The Sudoku Solver is still to be finished, but the cvBlob library is working fine, so I decided to publish it. The implementation is based on Dr. Andrew Greensted suggestion for Blob Detection.

I shared the project with a GPL license in Google Code. All the technical information can be found there, besides the source code and a binary file for Android. If you wanna try out, I would highly appreciate any feedback

 

blob detection

 

Generación de números aleatorios

La generación de números aleatorios con métodos computacionales es una de las técnicas básicas utilizadas en multitud de disciplinas como la criptografía, los videojuegos, la estadística, la simulación… Existen dos métodos de generación de números aleatorios, básicamente: los números pseudo-aleatorios, que generan una secuencia partiendo de un primer número semilla, o los aleatorios, que siguen unos algoritmos de generación más complejos, tomando generalmente datos del contexto informático en el que se generan (tales como posición del puntero, porcentaje de ocupación de la RAM, etc) para tener suficiente entropía. En este post, trataré sobre los primeros.

Como ya he mencionado, utilizando este tipo de métodos escogeremos una semilla o valor aleatorio inicial, a partir del cual generaremos el resto de números (combinar este método con uno aleatorio real para generar una ristra de números aleatorios verdaderos es otra opción, en la que ahorraremos potencia de cálculo al generar un número aleatorio tan sólo inicialmente).

Como veremos en el siguiente código, declararemos una variable “semilla” que inicializaremos a un valor dado. Será idealmente una variable estática, es decir, una variable global accesible sólo por las rutinas de este mismo archivo.

#include  

static long _random= 0;

//Valor inicial o semilla que proporcionaremos al algoritmo
void InicializaRnd(long l)
{
  _random = l;
}

//Rnd() generará números aleatorios
double Rnd()
{
  _random= (25173L * _random + 12849L) % 65536L;
  return double(_random) / double(65536);
}

//Llamada a main
void main()
{
  int i;
  InicializaRnd(100);  

  cout << endl << "Diez números aleatorios :"  <

Con la sección de código

    cout << int(Rnd()*100) +1 << "  ";

generaremos los números aleatorios entre los valores que nosotros deseemos.