mlm@NL.CS.CMU.EDU (Michael Mauldin) (02/11/88)
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