fastpool.cpp

pgp soucecode pgp soucecode

/*
 * Fastpool.cpp - a high-quality entropy-accumulation pool for random
 * number generation that supports fast addition of new data.
 * This is for high-speed input.  The output quality does not suffer
 * from this.
 * 
 * Theory of operation:
 * A pool of POOLSIZE 32-bit words is maintained.  Each additional word is
 * hashed into the pool using a good, although not cryptographically strong,
 * hash.  This consists of using a degree-POOLSIZE primitive polynomial
 * over GF(2) as a scrambler polynomial over all 32 bits in parallel to
 * smear the contents of a given bit over the whole pool.  Before
 * being written back, the word is rotated left one bit to provide
 * feedback between the various bits in the pool.  (This idea is stolen
 * from SHA.)
 * 
 * To generate random numbers, as needed an additional 16 bytes of random
 * data is generated by taking an SHA hash of the entire pool.  To change
 * the pool state before taking the next random numbers, the hash just
 * extracted is added back in.  Since the hash depends in complex ways on
 * every bit of the input, this helps mix up the information in the pool.
 */

#include "PGPFone.h"
#include "CHash.h"
#include "SHA.h"
#include "fastpool.h"

#include <string.h>	/* For memset, memcpy */

/*
 * The pool is stirred with a primitive polynomial of degree 128
 * over GF(2), namely x^128 + x^99 + x^59 + x^31 + x^9 + x^7 + 1.
 * For a pool of size 64, try x^64+x^62+x^38+x^10+x^6+x+1.
 */
#define POOLSIZE 128	/* Power of 2 */
#if POOLSIZE == 128
#define TAP1	99	/* The polynomial taps */
#define TAP2	59
#define TAP3	31
#define TAP4	9
#define TAP5	7
#elif POOLSIZE == 64
#define TAP1	62	/* The polynomial taps */
#define TAP2	38
#define TAP3	10
#define TAP4	6
#define TAP5	1
#else
#error No primitive polynomial available for chosen POOLSIZE
#endif

static ulong pool[POOLSIZE];
static unsigned poolindex = 0;

void
randPoolAddWord(ulong w)
{
	unsigned i;

	poolindex = i = (poolindex - 1) & (POOLSIZE-1);

	/* XOR in the various taps */
	w ^= pool[(i+TAP1)&(POOLSIZE-1)];
	w ^= pool[(i+TAP2)&(POOLSIZE-1)];
	w ^= pool[(i+TAP3)&(POOLSIZE-1)];
	w ^= pool[(i+TAP4)&(POOLSIZE-1)];
	w ^= pool[(i+TAP5)&(POOLSIZE-1)];
	w ^= pool[i];
	/* Rotate w left 1 bit (stolen from SHA) and store */
	pool[i] = (w << 1) | (w >> 31);
}

void
randPoolAddBytes(uchar const *p, unsigned len)
{
	ulong w;

	/* Add full words */
	while (len >= 4) {
		w = (unsigned long)((unsigned)p[0] << 8 | p[1]) << 16 |
		                   ((unsigned)p[2] << 8 | p[3]);
		p += 4;
		len -= 4;
		randPoolAddWord(w);
	}

	/* Add remaining partial word */
	if (len) {
		w = 0;
		do {
			w = (w << 8) | *p++;
		} while (--len);
		randPoolAddWord(w);
	}
}

/*
 * Copy random bytes out of "buf", hashing the pool to refill it as
 * necessary.
 */
void
randPoolGetBytes(uchar *p, unsigned len)
{
	static uchar buf[20];
	static unsigned avail = 0;	/* Bytes avail in buf */

	while (len > avail) {
		memcpy(p, (uchar *)buf+sizeof(buf)-avail, avail);
		len -= avail;
		p += avail;

		/* Compute a hash of the pool */
		SHA hash;
		hash.Init();
		hash.Update((uchar *)pool, sizeof(pool));
		avail = hash.mHashSize;
		hash.Final(buf);
		randPoolAddBytes(buf, avail);
	}

	memcpy(p, (uchar *)buf+sizeof(buf)-avail, len);
	memset((uchar *)buf+sizeof(buf)-avail, 0, len);
	avail -= len;
}

#if 0

#include <stdio.h>

void
dumprand(unsigned count)
{
	uchar c;

	printf("%u random bytes:\n", count);

	while (count--) {
		randPoolGetBytes(&c, 1);
		printf("%02x ", (unsigned)c);
	}
	putchar('\n');
}

int
main(int argc, char **argv)
{
	int len;

	while (--argc) {
		len = strlen(*++argv);
		printf("Adding \"%.*s\\0\" to pool.\n", len, *argv);
		randPoolAddBytes((uchar *)*argv, len+1);
	}
	dumprand(100);
	return 0;
}

#endif