Path: utzoo!mnetor!uunet!husc6!bloom-beacon!oberon!bbn!rochester!PT.CS.CMU.EDU!NL.CS.CMU.EDU!mlm
From: mlm@NL.CS.CMU.EDU (Michael Mauldin)
Newsgroups: sci.crypt
Subject: Non-linear random number generators
Message-ID: <852@PT.CS.CMU.EDU>
Date: 11 Feb 88 05:47:21 GMT
Sender: netnews@PT.CS.CMU.EDU
Organization: Carnegie-Mellon University, CS/RI
Lines: 78
Keywords: one-time-pad random generator non-linear

I'm trying to find good ways to combine linear congruential random
number generators in non-linear ways to generate one-time-pads.
Denning (Cryptography and Data Security, 1982) points out the pitfalls
of using linear generators, and then shows how to use DES as a
non-lnear transform to build such streams.  Given the existence of
special hardware for DES, I'd like to avoid using it.

I'd like (1) suggestions for non-linear ways to combine 2 or more LCRGs,
(2) any pointers to analyses of such combinations, and
(3) comments on a possible scheme based on Knuth's Algorithm M as follows:

----------------------------------------------------------------

Given a set of n LCRGs such that

	R(k,i+1) = ( A[k] * R(k,i) + O[k] ) mod M[k],     k in [0..m-1]

	Let Randint(k,m) be R(k) mod m (that is, a random integer
	  from [0..m-1] based on the next number from kth sequence).

Use the transposition table idea from Knuth's algorithm M (volume II)
to define a one-time-pad generating function:

	# define TBLSIZ /* some prime number from 100 to 200 */
	# define BYTSIZ 256
	# define N	/* Number of LCRG sequences, 0..N-1 */

	/* Initial settings of arrays form the "key" */	
	int mlt[N] = { ... };
	int off[N] = { ... };
	int mod[N] = { ... };
	int rnd[N] = { ... };
	
	# define RAND(K)      (rnd[K] = (mlt[K] * rnd[K] + off[K]) % mod[K])
	# define RANDINT(K,M) (RAND(k) % M)

	one_time_pad ()
	{ int seq = 0, tbl[TBLSIZ], ind;

	  /* Initialize tbl by filling with random numbers in [0..BYTSIZ-1] */
	  for (i=0; i<TBLSIZ; i++)
	  { tbl[i] = Randint (i%N, BYTSIZ); }

	  /* Generate one-time-pad */
	  while (NEED_MORE_PAD)
	  { seq = Randint (seq, N);
	    ind = Randint (seq, TBLSIZ);
	    putchar (tbl[ind]);
	    tbl[ind] = Randint (seq, BYTSIZ);
	  }
	}

----------------------------------------------------------------

Thus for each character of one-time-pad, there are three random numbers
generated, and the sequences are used in random order, with a
transposition table to stir up things a bit.

The "key" is the initial settings of the n LCRGs, or 4n integers.
There may have to be some trickery here to assure that the individual
LCRGs are well-behaved.

The time needed to encrypt is independent of the number of sequences
used, so you can use a long a "key" as you like.  Obviously the normal
caution for one-time-pads holds, a different key for each file, each
time it is changed.

Is there any attack that is better than searching through WORDSIZE**4n 
possible initial settings of the LCRGs?  How many sequences would you
have to use to be "safe"?

I'd be glad to make a simple "challenge" ciphertext, if anyone would
care to try attacking it.  Send mail, if you would be willing.

----------------------------------------------------------------
Michael L. Mauldin (Fuzzy)		Department of Computer Science
ARPA: Michael.Mauldin@NL.CS.CMU.EDU	Carnegie-Mellon University
Phone: (412) 268-3065			Pittsburgh, PA  15213-3890