[boost] Re: Proposal: random number library

From: Greg Colvin (gcolvin_at_[hidden])
Date: 2000-02-20 20:16:59

From: Mark Borgerding <mborgerding_at_[hidden]>
> ...
> Using /dev/random is great for systems that have it, but what about the
> other systems?  What do you think of adding a default random_device
> implementation for systems that do not have /dev/random?  The following
> is platform-independent code, but unfortunately the quality of the
> numbers it creates is somewhat platform dependent.  Perhaps it can be
> improved.  The idea is based upon an algo from Schneier's Applied
> Cryptography.  Count until some system parameter changes (e.g. clock()
> ), and then use the lsb of the counter as a random bit.
> 
> unsigned char rand_byte(int nbits)
> {
>    unsigned char result = 0;
>    if (nbits>8)
>       nbits=8;
> 
>    for (int i=0;i<nbits;++i) {
>       unsigned int counter=0;
>       clock_t start = clock();
>       do {
>          ++counter;// keep counting until the clock changes
>       }while (start == clock());
> 
>       result <<= 1;  // left shift 1 bit
>       result |= (counter&1);
>       // put the LSB from the counter into the LSB of the result
>    }
>    return result;
> }

I've been playing around with this, and made a small modification
so that you can vary the quality of the result by specifying nbits
other than 8.  Also made it compile as C (:-)

   unsigned char rand_byte(int nbits)
   {
      unsigned int result=0;
      int i;
      for (i=0; i<nbits; ++i) {

         // keep counting until the clock changes
         unsigned int counter=0;
         clock_t start = clock();
         do {
            ++counter;
         } while (start == clock());

         // rotate low byte left 1 bit and XOR in counter
         result = (((result << 1) | (result >> 7))) ^ counter;
      }
      return result & 0xFF;
   }

I didn't mask off the higher bits of the counter on that theory
that we might as well extract all the entropy there is, and any
lack of entropy in the higher bits will be covered up by whatever
entropy we find in the lower bits.  If I'm wrong please teach me.

I've noticed that if your clock() function is fast enough you get
no entropy at all, no matter how high you set nbits, and if it's
slow enough you can get away with nbits < 8.

I also made a Win32-specific version that has the virtue of not
tying up the CPU so much:

   unsigned char rand_byte(int nbits)
   {
      unsigned int result=0;
      int i;
      LARGE_INTEGER clicks;
      for (i=0; i<nbits; ++i) {
         Sleep(1);
         QueryPerformanceCounter(&clicks);

         // rotate low byte left 1 bit and XOR in LSB of counter
         result = (((result << 1) | (result >> 7)) & 0xFF) ^ (clicks.LowPart);
      }
      return result;
   }

You could substitute for the Sleep() call with most anything else
that takes some time.  I've seen a Java version of this that spawns
a bunch of threads and jumps around to create some churn.