Page 1 of 1

Making Pseudo-Random Number Generators More Random Techniques for improving a psuedo-random generators randomess Rate Topic: -----

#1 salindor  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 46
  • View blog
  • Posts: 301
  • Joined: 10-November 06

Posted 11 June 2007 - 07:22 PM

Improving the randomness of a psuedo-random number generator

For some reason I have never been satisfied with the normal random number generators. Prior to learning cryptography, I came up with some interesting methods for increasing randomness. This tutorial will focus on the more practical ones, many of them can be used with the cryptographic techinques to improve their security.

Prerequisite
This tutorial assumes you have read Random Number Generation 102, Coding a Linear Congruential Generator first as it is extremely good, and I could not do a better job myself.

As such it will not repeat any of the information found there.

A review of non-deterministic functions and their importance to random numbers
A deterministic function is a function which always produces the same output based on the same input.

Contrary, a non-deterministic function, is a function that does not always produce the same output based on the same input. For example, the function max, is a deterministic function. The function time() is a non-deterministic function. Other non-deterministic functions could include, the key being pressed (and when), the id of the process being run, the velocity of the mouse cursor, the seed, current processor utilization.

Seeding your random number generator
One of my great ideas, was to seed often. However, my first attempt at this I made a small mistake and here is what it looked like:
int myRand()
{
	 srand ( time(NULL) );
	 return rand();
}


The problem with this method is it replaces the seed with the current time every single time. In essence, your always going to return an offset from the current time... probably not what you want.

This leads to the first improvement to the function:
int myRand()
{
	 srand ( rand() ^ time(NULL) );
	 return rand();
}


The nice thing about this particular modification is it is constantly building upon previous values. This is only slightly better than only seeding once. From some of the tests I have run, depending on the frequency of calling this function, each time you call the time function you get maybe a quarter bit of randomness. Using a more finite clock will give more bits that are non-deterministic.

The next improvement that can be made, is to add more than just time to the seed. Whenever a non-deterministic event occurs, reseed/store the value for later consumption.
typedef struct seedInfo SEED_INFO;

struct seedInfo
{
   SEED_INFO * next;
   time_t when;
   long what;
};

class random
{
   SEED_INFO * moreSeeds
public:
   int addSeed(long val)
   {
	   SEED_INFO * t = malloc(sizeof(seedInfo));
	   time(&t->next);
	   t->what = val;
	   t->next = moreSeeds;
	   moreSeeds = t;
   }

	int rand()
	{
		if (moreSeeds==0)
		   srand ( rand() ^ time(NULL) );
		else
		{

			 long val = moreSeeds->when << 16 | moreSeeds->what;

		}
	   return rand();
	}
};



Is This A Good Question/Topic? 0
  • +

Replies To: Making Pseudo-Random Number Generators More Random

#2 NickDMax  Icon User is offline

  • Can grep dead trees!
  • member icon

Reputation: 2250
  • View blog
  • Posts: 9,245
  • Joined: 18-February 07

Posted 21 July 2007 - 10:23 PM

Thank you salindor for your tutorial and the nod to mine. I would like to make some notes:

First of all, although my tutorial on LCG's may be a good background for pseudorandom number generators, LCG's are NOT cryptographic grade. Even with various obfuscation techniques LCG's are not to be trusted. There are better systems such a the Mersenne twister (which Voodoo Doll was nice enough to put in the snippets) .

Although it is true that given the exact same input a deterministic will give the exact same answer, and a nondeterministic function may give a different answer, this definition is a little misleading. For example the time() function is in point of fact a deterministic function. If you ran the function at exactly the same time on two computers it would generate the same result (in theory at least). It may seem like I am splitting hairs here, but using the time() function to reseed a random number generator is not a statistically safe (especially using an LCG) practice.

Of course often the idea of a cryptographically secure pseudorandom number generator is that it will be deterministic. :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1