?

Log in

No account? Create an account
penrose orange

stephenw32768


/var/log/stephen

cat /var/log/stephen >/dev/eyes


Random number generator
penrose orange
stephenw32768
Block ciphers in "counter" mode can be used as pseudo-random number generators. You pick some seed (e.g. the time of day) to use as either a key or an initialization vector, depending on the cipher. You then encrypt a block of zeros with that key/IV, and use the ciphertext as your first block of pseudo-random numbers. To generate more, you combine the key/IV with the value of a counter, encrypt a block of zeros, and use the result. You carry on like this, incrementing the counter and re-running the cipher, until you've got enough random data.

Linux's C library has the aging DES cipher algorithm built in. I decided to have a go at writing a PRNG based on it. It seems to work. The program takes one argument, which is the number of pseudo-random bytes to generate. Output is sent to stdout.

The output does seem to be random. As a test, one can try compressing the output data. Random data shouldn't be compressible, because there are no patterns for the compression algorithm to detect and eliminate:
[thalassa.~/src/c/nysarng] ./nysarng 10240000 | gzip -9 | wc -c
10241583


/*
 * nysarng.c
 * Random number generator using DES in counter mode
 *
 * Copyright (c) 2007 Stephen Williams, all rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. The name of the copyright holder may not be used to endorse or
 *    promote products derived from this software without specific prior
 *    written permission.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
 * IN NO EVENT SHALL THE COPYRIGHT HOLDER BE LIABLE FOR ANY DIRECT,
 * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
 * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

static char RCS_ID[] =
  "@(#) $Id: nysarng.c,v 1.1 2007/07/15 13:26:56 stephen Exp $";

#include <sys/types.h>
#include <stdio.h>
#include <string.h>
#include <rpc/des_crypt.h>
#include <sys/time.h>


static char key[] = "whocares"; /* fixed key */


/* Returns microseconds since the epoch */
static int64_t get_microtime(void)
{
  struct timeval tv;

  gettimeofday(&tv, 0);
  return (tv.tv_sec * 1000000) + tv.tv_usec;
}


/*
 * Entry point.
 *
 * Process:
 * - Initialize counter to zero
 * - For each random eight-byte block required:
 *   - set cipher initialization vector to program start time xor
 *     counter;
 *   - increment counter;
 *   - encrypt zeroed buffer using fixed key and generated IV.
 */
int main(int argc, char *argv[])
{
  char buf[8];
  int64_t ctr = 0, iv;
  const int64_t initial_iv = get_microtime();
  int i, j, required;

  if(argc != 2) {
    fprintf(stderr, "%s\nUsage: %s bytes_required\n", RCS_ID, argv[0]);
    return 1;
  }
  required = atoi(argv[1]);
  if(required < 1) {
    fprintf(stderr, "\"%s\" does not parse as a positive integer\n", argv[1]);
    return 1;
  }

  des_setparity(key);

  for(i = 0; i < required; i += 8) {
    iv = initial_iv ^ ctr++;
    memset(buf, 0, 8);
    cbc_crypt(key, buf, 8, DES_ENCRYPT, (char *)&iv);
    for(j = 0; (j < 8) && ((i + j) < required); j++)
      fputc(buf[j], stdout);
  }

  return 0;
}