From: bear@eagle.fsl.noaa.gov (Bear Giles)
Date: Thu, 17 Jun 93 22:37:47 PDT
To: cypherpunks@toad.com
Subject: Re:  xor w/prbs
Message-ID: <9306180534.AA01952@eagle.fsl.noaa.gov>
MIME-Version: 1.0
Content-Type: text/plain


>How *do* you break this cypher?  He is generating a lot of random numbers
>between 0 and 255, and xor'ing each successive one with the next byte of plain-
>text.  I know that this is a trivial cypher to break, according to PRZ at
>least, but how do you do it?

In this case, since the modulus is a small power of 2, you can do exhaustive
search.  There is _one_ sequence of 256 distinct values.

Still want to know how long it will take to crack his ciphertext?

>#define MULTIPLIER 0x015a4e35L
>#define INCREMENT 1
>
>long RandomSeed;
>
>int GetRandomNumber(int Range)
>	{
>	RandomSeed = MULTIPLIER * RandomSeed + INCREMENT;
>	return(RandomSeed % Range);
>	}
>
>So how do you crack this cipher without trying all the keys, guys?

Since 

   max_integer / gcd (range, max_integer) > range

you can move the modulus operation around without worrying about
weird effects from the finite word size.  This is because the 
closed form of the loop is:

   seed[k] = (seed[0] * mult^k + incr * sum (j = 0 to k-1) of mult^j) % range

which is equal to

   seed[k] = (seed[0] % range) * (mult % range)^k +
			  (incr % range) * sum (j = 0 to k-1) of (mult % range)^j

and the modulus operation with a power-of-2 range simply keeps the last
n bits.  But, this also means there are effectively only "range" possible
values for the initial seed.

Even if you make the increment and multiplier part of the key, they must
(both?) be odd so you only have 22 bits of key.  Of course at this point
you can simply use the fact that this "one time pad" is actually a 
Vigenere cipher with 256 columns -- easy to crack if you have some
insight into the nature of the plaintext (e.g., English text).

For instance, 10-15 small documents (40 lines) encrypted with the same
key is enough to crack it even if the multiplier and increment are 
unknown but constant.

Bear Giles