PRNG

Am 01.06.2012 18:57, schrieb Tim Wescott:
> On Fri, 01 Jun 2012 17:02:10 +0100, Thomas Womack wrote:
>
>> In article<a2s3v7Fv1fU1@mid.individual.net>, Thomas Heller
>> <theller@ctypes.org>  wrote:
>>> I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
>>> random numbers.
>>>
>>> Can I use a LFSR of sufficient length (31 bit, for example), and get a
>>> new random number on each clock by using the 10 least significant bits,
>>> or do I have to use 10 independent LFSR's of different length, one for
>>> each bit?
>>
>> How important is it that the numbers are uncorrelated?  The 10 LSBs of
>> an LFSR at time t+1 will be nine of the bits from time t and one new
>> one, so if you saw 100 at time t you know it's either 200 or 201 next
>> go.  If that's OK, use the end of one LFSR; if not, use several.
>>
>> But if it's actually important that the random numbers are
>> unpredictable, don't use LFSRs: given 3n bits from a length-n LFSR you
>> can pretty much write down the rest of the sequence.
>
> I've only scratched the surface of cryptographicaly secure random number
> generation -- are there any schemes that are amenable to working on an
> FPGA?

FYI:  I found interesting papers about true (and pseudo) random number
generation in FPGAs.  They are using ff metastability or PLL jitter
for this:

http://people.csail.mit.edu/devadas/pubs/ches-fpga-random.pdf

http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm03.pdf

Thomas

Am 01.06.2012 18:02, schrieb Thomas Womack:
> In article<a2s3v7Fv1fU1@mid.individual.net>,
> Thomas Heller<theller@ctypes.org>  wrote:
>> I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
>> random numbers.
>>
>> Can I use a LFSR of sufficient length (31 bit, for example), and get
>> a new random number on each clock by using the 10 least significant
>> bits, or do I have to use 10 independent LFSR's of different length, one
>> for each bit?
>
> How important is it that the numbers are uncorrelated?  The 10 LSBs of
> an LFSR at time t+1 will be nine of the bits from time t and one new
> one, so if you saw 100 at time t you know it's either 200 or 201 next
> go.  If that's OK, use the end of one LFSR; if not, use several.

My requirements are (I guess) pretty weak.  The use case is difficult
to explain; I'll try with this model:

I will collect the numbers into a histogram; the counts in the
histogram bins should increase 'statistically', without any visible
pattern.

Thanks for all the suggestions; will give me some interesting thoughts
over the weekend.

Thomas

Thomas Heller wrote:

> I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
> random numbers.
> 
> Can I use a LFSR of sufficient length (31 bit, for example), and get
> a new random number on each clock by using the 10 least significant
> bits, or do I have to use 10 independent LFSR's of different length, one
> for each bit?
Well, obviously, if your use one LFSR, at each clock, you only get
ONE new bit, all the others are old, just moved to another position.
That's not too random.

Jon

In article <jqb17h$mj3$1@speranza.aioe.org>,
glen herrmannsfeldt  <gah@ugcs.caltech.edu> wrote:
>The outputs of ten 32 bit LFSRs is more closely related
>to ten bits of a 320 bit LFSR, though.

Not really; in particular the period is 2^32 rather than 2^320.  Of
course period 2^32 is good enough for many applications, and the
original poster's task doesn't require cryptographic quality.

>As you note, for the most randomness use ten LFSRs of
>ten different lengths. Again, equivalent to an appropriate
>LFSR of the total number of bits.

Not quite if the lengths aren't coprime (a 4-bit period-15 and 6-bit
period-63 LFSR produce a cycle length of 315, which you can't do with
an LFSR of ten bits no matter what polynomial you choose.

(or is the EE definition of LFSR different from the mathematical one?
I reckon that an LFSR is anything defined by f(t) as a XOR together of
the values of f(t-a_i) for some fixed set of a_i)

Tom

Thomas Heller wrote:

>
> My requirements are (I guess) pretty weak. The use case is difficult
> to explain; I'll try with this model:
>
> I will collect the numbers into a histogram; the counts in the
> histogram bins should increase 'statistically', without any visible
> pattern.

Are you familiar with the Mersenne Twister?
I used some GPL VHDL code in a project a long time ago.

http://www.ht-lab.com/freecores/mt32/mersenne.html

Pete

Thomas Womack <twomack@chiark.greenend.org.uk> wrote:
> In article <jqb17h$mj3$1@speranza.aioe.org>,

(snip, I wrote)
>>The outputs of ten 32 bit LFSRs is more closely related
>>to ten bits of a 320 bit LFSR, though.

> Not really; in particular the period is 2^32 rather than 2^320.  Of
> course period 2^32 is good enough for many applications, and the
> original poster's task doesn't require cryptographic quality.

Yes. If you need enough random numbers, or even just enough
randomness, to notice the period of 2**32. Using the low bits
off a 32 bit LFSR gives short term correlations, where ten 32 bit
LFSR's, started appropriately, doesn't.

>>As you note, for the most randomness use ten LFSRs of
>>ten different lengths. Again, equivalent to an appropriate
>>LFSR of the total number of bits.

> Not quite if the lengths aren't coprime (a 4-bit period-15 and 6-bit
> period-63 LFSR produce a cycle length of 315, which you can't do with
> an LFSR of ten bits no matter what polynomial you choose.

Yes, I should have put more "sort of" in there. Actually, I am
not so sure I know how it works if you choose a non-primitive
polynomial. It is usual to discuss only the maximal length cycle,
but the hardware doesn't require that.

> (or is the EE definition of LFSR different from the mathematical one?
> I reckon that an LFSR is anything defined by f(t) as a XOR together of
> the values of f(t-a_i) for some fixed set of a_i)

Well, LFSR pretty much describes a physical system, not a logical
(mathematical) one. It might be that the EE definition includes
any combination of XOR gates and shift registers. The math is
usually done in terms of factoring polynomials modulo 2, which
is more restrictive.

-- glen

On Jun 1, 2:36=A0pm, Thomas Heller <thel...@ctypes.org> wrote:
> Am 01.06.2012 18:57, schrieb Tim Wescott:
>
>
>
>
>
>
>
>
>
> > On Fri, 01 Jun 2012 17:02:10 +0100, Thomas Womack wrote:
>
> >> In article<a2s3v7Fv1...@mid.individual.net>, Thomas Heller
> >> <thel...@ctypes.org> =A0wrote:
> >>> I need a multi-bit PRNG which generates a sequence of 10-bit pseudo
> >>> random numbers.
>
> >>> Can I use a LFSR of sufficient length (31 bit, for example), and get =
a
> >>> new random number on each clock by using the 10 least significant bit=
s,
> >>> or do I have to use 10 independent LFSR's of different length, one fo=
r
> >>> each bit?
>
> >> How important is it that the numbers are uncorrelated? =A0The 10 LSBs =
of
> >> an LFSR at time t+1 will be nine of the bits from time t and one new
> >> one, so if you saw 100 at time t you know it's either 200 or 201 next
> >> go. =A0If that's OK, use the end of one LFSR; if not, use several.
>
> >> But if it's actually important that the random numbers are
> >> unpredictable, don't use LFSRs: given 3n bits from a length-n LFSR you
> >> can pretty much write down the rest of the sequence.
>
> > I've only scratched the surface of cryptographicaly secure random numbe=
r
> > generation -- are there any schemes that are amenable to working on an
> > FPGA?
>
> FYI: =A0I found interesting papers about true (and pseudo) random number
> generation in FPGAs. =A0They are using ff metastability or PLL jitter
> for this:
>
> http://people.csail.mit.edu/devadas/pubs/ches-fpga-random.pdf
>
> http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm...
>
> Thomas

I haven't read the papers, but typically any digital "true" random
number generator is not "truly" random.  When it is measured and
analyzed critically it has biases which allow a degree of
predictability.  I have read about other attempts based on diode noise
which resulted in easily measurable biases.

Rick

rickman <gnuarm@gmail.com> wrote:

(snip, someone wrote)
>> >>> Can I use a LFSR of sufficient length (31 bit, for example), and get a
>> >>> new random number on each clock by using the 10 least significant bits,
>> >>> or do I have to use 10 independent LFSR's of different length, one for
>> >>> each bit?

>> FYI: &#4294967295;I found interesting papers about true (and pseudo) random number
>> generation in FPGAs. &#4294967295;They are using ff metastability or PLL jitter
>> for this:

>> http://people.csail.mit.edu/devadas/pubs/ches-fpga-random.pdf

>> http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm...

> I haven't read the papers, but typically any digital "true" random
> number generator is not "truly" random.  When it is measured and
> analyzed critically it has biases which allow a degree of
> predictability.  

If you put enough state bits into the calculation, you should be
able to keep the predictability long enough that, in a practical
time frame, it isn't noticed. 

> I have read about other attempts based on diode noise
> which resulted in easily measurable biases.

I used to have the paper about an Intel chip with a built-in
noise source based generator. There is logic to remove at least
the first order bias. (Equal ones and zeros.) It should be possible
to remove any specific bias if you know about it and try to
remove it. You need to know which biases the specific problem
is sensitive to.

I do remember stories about many of the early generators that
weren't so bad except when taken in triplets there was some
correlation between triplets. That turned out bad when used to
generate points in 3D space. Once known, it can be fixed.

There is always a tradeoff between randomness and time needed
by the generator.

-- glen

On Jun 5, 4:17=A0pm, glen herrmannsfeldt <g...@ugcs.caltech.edu> wrote:
> rickman <gnu...@gmail.com> wrote:
>
> (snip, someone wrote)
>
> >> >>> Can I use a LFSR of sufficient length (31 bit, for example), and g=
et a
> >> >>> new random number on each clock by using the 10 least significant =
bits,
> >> >>> or do I have to use 10 independent LFSR's of different length, one=
 for
> >> >>> each bit?
> >> FYI: I found interesting papers about true (and pseudo) random number
> >> generation in FPGAs. They are using ff metastability or PLL jitter
> >> for this:
> >>http://people.csail.mit.edu/devadas/pubs/ches-fpga-random.pdf
> >>http://www.cse.cuhk.edu.hk/~phwl/mt/public/archives/papers/tprng_fccm..=
.
> > I haven't read the papers, but typically any digital "true" random
> > number generator is not "truly" random. =A0When it is measured and
> > analyzed critically it has biases which allow a degree of
> > predictability.
>
> If you put enough state bits into the calculation, you should be
> able to keep the predictability long enough that, in a practical
> time frame, it isn't noticed.
>
> > I have read about other attempts based on diode noise
> > which resulted in easily measurable biases.
>
> I used to have the paper about an Intel chip with a built-in
> noise source based generator. There is logic to remove at least
> the first order bias. (Equal ones and zeros.) It should be possible
> to remove any specific bias if you know about it and try to
> remove it. You need to know which biases the specific problem
> is sensitive to.
>
> I do remember stories about many of the early generators that
> weren't so bad except when taken in triplets there was some
> correlation between triplets. That turned out bad when used to
> generate points in 3D space. Once known, it can be fixed.
>
> There is always a tradeoff between randomness and time needed
> by the generator.
>
> -- glen

Yes, it all depends on what you need.

I was watching a local government cable channel once about a state
hearing where a representative of a gambling machine company was
trying to explain to the regulating board how this machine was
different from the machines prohibited in this state.  It seems that
there were machines that for some amount of coin would give you a pre-
printed ticket that told you your winnings, if any.  Because the
sequence was pre-arranged and once the prizes have all sold out (the
barkeeper would know when that happens) the remaining tickets were all
losers and further play was no longer "gambling".  So the gaming board
banned these machines.

This spokesperson claimed that the microprocessors in the machine
always produced random results and so was not like the illegal pre-
printed ticket machines.  We all know that this is nonsense and that
they actually were using something like an LFSR, possibly with a time
based modification that would not produce truly random results.  For
example, I expect their machines would never produce a sequence of 100
big winners no matter how long you played.  A real random machine
would produce this sequence eventually if played long enough.

I don't know what the outcome of the hearing was.  I suspect the
gaming commission got more info from other sources and learned that a
microprocessor does not produce random results.

Rick