# Re: PRNG Breaking

**From:** George Marsaglia (*geo_at_stat.fsu.edu*)

**Date:** 09/21/04

**Next message:**Cristiano: "Re: a new very fast hash algorithm (160 bits), with a technique of "overlapping sums""**Previous message:**Tom St Denis: "Re: a new very fast hash algorithm (160 bits), with a technique of "overlapping sums""**In reply to:**Jean-Luc Cooke: "Re: PRNG Breaking"**Next in thread:**David Wagner: "Re: PRNG Breaking"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

Date: Tue, 21 Sep 2004 15:01:30 -0400

"Jean-Luc Cooke" <jlcooke@engsoc.org> wrote in message

news:cipj03$7vf$1@driftwood.ccs.carleton.ca...

*>
*

*> Papers have been written stating that *any* LFSR (and I can only assume
*

*> that this applies to all linear PRNGs) PRNG can be broken with a small
*

*> number of outputs.
*

*>
*

*> I can't find the paper right now, sorry, but here's some discussion
*

*> allong the same idea:
*

*> http://www.ciphersbyritter.com/NEWS5/MACLAR.HTM
*

*>
*

Since points

(x_i, x_{i+1},...,x_{i+k}),

coordinates successive values from a congruential RNG,

fall on a lattice, it is easy to find the a,k and m for the generator

x_{i+1} = a*x_i+k mod

that produces segments of the sequence. Usually half a dozen 3-tuples will

serve.

I have used this method since I established that lattice structure

in the 1960's, and you will find a recent description with an

example and a test problem in

http://tbf.coe.wayne.edu/jmasm/vol2_no1.pdf

George Marsaglia

**Next message:**Cristiano: "Re: a new very fast hash algorithm (160 bits), with a technique of "overlapping sums""**Previous message:**Tom St Denis: "Re: a new very fast hash algorithm (160 bits), with a technique of "overlapping sums""**In reply to:**Jean-Luc Cooke: "Re: PRNG Breaking"**Next in thread:**David Wagner: "Re: PRNG Breaking"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]