From: Matthew J Ghio <mg5n+@andrew.cmu.edu>
Date: Tue, 5 Oct 93 19:20:07 PDT
To: cypherpunks@toad.com
Subject: Re: Need Suggestions for Random Numbers
In-Reply-To: <9310060114.AA13172@toad.com>
Message-ID: <IggWg0W00Vp=NOUEhj@andrew.cmu.edu>
MIME-Version: 1.0
Content-Type: text/plain


Eli Brandt <ebrandt@jarthur.Claremont.EDU> writes:

> This is a very simple linear congruential generator:
> 	a_n = a_n-1 + a_n-2	mod 10
> It is decidedly *not* suitable for "producing an `acceptable' random
> file to be xor'd with the plaintext."  It's not a cryptographically
> strong PRNG (it's not even a particularly good PRNG).

The pseudo-random number generator:

     a_n = a_n-1 + a_n-2   mod 10

is easy to break.  One could guess the pattern from only a few numbers
of the series.  My point is that that series can be used as a basis for
better PRNGs.  I suggested using something like:

     if a_n-2 < 195  then  a_n = a_n-4 + a_n-3   mod 256
     if a_n-2 > 194  then  a_n = a_n-4 + a_n-3 + a_n-1   mod 256

This is considerably less easy to break.  Even if one could surmise that
the (n-1) term was being added in sometimes and not others, you'd still
have to examine a large section of the series to figure out exactly what
method was being used to determine when the extra term was being
inserted (you'd have to see an example where a_n-2=194 and note that the
term was not included, and you'd have to see the situation a_n-2=195 and
note that it was included.  Plus, double-encryption could be used to
increase the security.

What PRNGs would you suggest using?