padrand(); /* random numbers from one-time pads */

[Istvan Mohos]

In article <2260 at lectroid.sw.stratus.com> cme (Carl Ellison) writes:
>In article <2208 at ux.acs.umn.edu> dhoyt at vx.acs.umn.edu writes:
>> I'll try to find a
>>difference between noise and a pad.  Could it have something to do with noise
>>being additive and the pad is an exclusive or?  Statistical quantum theory?

>It's nothing so difficult.  After either XOR or ADD with a true random
>1-time pad, every possible cyphertext value is *exactly equally* likely.
>Therefore, every possible plaintext value is *exactly equally* likely.

The C source of the padrand() routine posted here, is hereby placed in
the Public Domain.  A primitive driver (main) is enclosed for convenient
testing.  The verbal description of the algorithm immediately below, is
"Copyright 1990, Istvan Mohos, All Rights Reserved".

An often cited and axiomatic observation of cryptology is the security
of information encrypted using one-time pads as keys.  Practical
one-time pads are non-cyclic non-monotone text, of sufficient length to
mask the plaintext.  An instance of a one-time pad represents a
perfectly random selection of a single key out of a potentially infinite
number of choices.  One should be able to capture and use this "perfect
randomness" in seeking other goals than security of encryption.  The
random number generator described here defines an alternate utility of
one-time pads.

Although the text of one-time pads is non-cyclic, the byte stream is
subject to regularities of character distribution as the function of the
language.  Two methods of combating uneven distribution are implemented
in the padrand() routine.  Firstly, the *minimum* of information is
extracted from each pad byte, evaluating only whether the (ASCII) value
of the byte is even or odd.  The second method simply increments the
value of every other pad byte by one, with a "limping adder".

If the pad stream contains an equal number of even and odd bytes, the
adder flips a (statistically) equal number of even bytes to odd and odd
bytes to even, so the overall distribution remains the same.  If there
is an imbalance of even/odd bytes in the pad stream, half of the
additional (even or odd) bytes causing the imbalance is likely to be
converted to the opposite, dampening the divergence.

The resulting even/odd flags are shifted into a binary bit field; the
user can select the width of the field.

The routine opens and reads the specified pad file, "using up"
bitfield-width-bytes at each call for generating a new random number.
The value returned is between 0 and the maximum value that can fit in
the selected bit width.  When the pad is exhausted, the routine closes
the file and returns -1.  At the next call, the (new or reused) file is
opened and the process starts again.

The program is somewhat wasteful of pad text, and is intended for Unix
environments where on-line text is abundant (as evidenced by directories
/usr/dict, /usr/man, ~TeX/TeXdoc and the like) but hardware random
number generators are absent.  Accordingly, "int" is assumed to be
32-bits wide; bits 1 through 31 are used for controlling the range of
the generated numbers.  A different magnitude may be selected at every
call.  Requests for larger ranges are silently masked down to 31 bits.

As additional controls, (char *)NULL passed for the pad name closes an
open pad in preparation for switching to a new pad; negative field
widths (not subject to the range limitation) are interpreted as commands
to bump the file pointer by the absolute value of the negative field;
zero field width flips the "limping adder" to its complement.  Control
operations or I/O failures return small negative int values specific to
the operation or to the failure, and do not produce random numbers.

#include <stdio.h>
main ()
{
	char namebuf[1024];
	register char *name = namebuf;
	register int bits, rand;

	for (;; name = namebuf) {
		fprintf(stderr, "bit width: "), gets(name), bits = atoi(name);
		fprintf(stderr, "file name: "), gets(name);
		if (!strlen(name))
			name = NULL;
		do
			printf("%d\n", rand = padrand(name, bits)), fflush(stdout);
		while (rand >= 0);
	}
}

/********************************************
* generate random numbers from text
* Istvan Mohos, 1990 --- in the Public Domain
*********************************************/
#define INTWID 32
int
padrand (pad, bits)
char *pad;
register int bits;
{
	FILE *fopen();
	static FILE *fp = NULL;
	static int silkie = 0;
	register int rand = 0;
	register int chr;

	if (pad == NULL) {
		if (fp != NULL)
			(void) fclose (fp), fp = NULL;
		silkie = 0;
		return (-6);
	}
	if (fp == NULL && (fp = fopen (pad, "r")) == NULL) {
		silkie = 0;
		return (-5);
	}
	if (bits < 0) {
		if (fseek (fp, (long)abs(bits), 1) == 0)
			return (-4);
		(void) fclose (fp);
		fp = NULL;
		silkie = 0;
		return (-3);
	}
	if ((bits &= INTWID-1) == 0) {
		silkie = !silkie;
		return (-2);
	}
	for (; --bits >= 0; silkie = !silkie) {
		if ((chr = fgetc (fp)) == EOF) {
			(void) fclose (fp);
			fp = NULL;
			silkie = 0;
			return (-1);
		}
		chr += silkie;
		rand <<= 1;
		rand += chr&1;
	}
	return (rand);
}
-- 
        Istvan Mohos
        ...uunet!pyrdc!pyrnj!hhb!istvan
        1000 Wyckoff Ave. Mahwah NJ 07430 201-848-8000
======================================================