Prev: Applied Computing 2010: 1st call extension until 25 June 2010
Next: Simple Paper and Pencil Cipher
From: unruh on 9 Jun 2010 14:36
On 2010-06-09, MrD <mrdemeanour(a)jackpot.invalid> wrote:
> unruh wrote:
>> On 2010-06-09, MrD <mrdemeanour(a)jackpot.invalid> wrote:
>>> unruh wrote (citing Mr. Chicks):
>>>>> One implication of the "full period" is that when the random
>>>>> number generator is initialized, we can initialize the seed to
>>>>> any value, because the "cycle" is all of the 2^32 bit patterns
>>>>> of the seed. So there are no worries about "short cycles".
>>>> Another implication is that this a very weak generator, and is
>>>> NOT pseudo-random. ( a true random generator will have the same
>>>> probability of repeating a number as of getting any other number.
>>>> This one never repeats a number.)
>>> Aren't you confusing PRNG and TRNG here? An LCG is a type of PRNG,
>>> according to all the previous discourse on the subject that I am
>>> familiar with. But nobody has claimed that this LCG is a TRNG.
>>>
>> A good prng acts like a true rng with respect to most statistical
>> tests. never repeating until the whole cycle is NOT a feature of any
>> TRNG and thus should not be a feature of any PRNG. Having that
>> feature makes the PRNG weak.
>
> An LCG is then a weak PRNG (from a crypto POV), and therefore it is
> indeed a PRNG, according to what you've just said; which conflicts with
> your assertion that an LCG is not pseudo-random. Right?

By your definition a program which puts out the numbers in order is a
PRNG. If that is what you want, then fine, use that as your definition.
I said that such a PRNG was weak, and was not pseudo-random, since it
did not comply with at least one feature of a random generator, that the
probability of the next character be independent (in some sense) of the
preceeding stream.


>
> Not all pseudo-random generators (PRNG) are intended for crypto. In fact
> *no* linear-congruential generators are considered suitable for crypto,
> as far as I'm aware; but they may be eminently suitable for producing
> numbers for simulations, etc.

They can be.
That is not the discussion here however.



>
> Also, with respect to the repeating/non-repeating characteristic: if a
> certain LCG never repeats an output value until it has completed a cycle
> of N, then another LCG can be created from it simply by taking its
> output modulo some X :: X<N; and this derived generator will repeat, if
> you consider repetition to be desirable.

??? repetition is not in and of itself desireable or not. It is a
symptom.

>
> BTW: Saying that a PRNG having some property that isn't shared by any
> TRNG makes it a bad PRNG seems to me to be poor reasoning. What you say
> may be true, but it isn't evident to me. Would you argue, for example,
> that a good PRNG should exhibit bias? Many (most?) TRNGs exhibit bias.

An RNG should be such that the probability of the next output is
independent of the value of the last N characters. Now, clearly this
cannot be true, since the generator itself provides the link between the
last N outputs and the current one. But, it should be infeasible given
just the output to discover that lack of independence.
A physical implimentation of a TRNG may exhibit biases, and to that
extent it is NOT a TRAG.


>
> Would you also argue that a PRNG should repeat output values, even at
> the expense of a shortened cycle? My modulo-X derived LCG repeats output
> values at the cost of a shortened cycle, and I'm not convinced that it's
> a worse (or better) PRNG for that fact. In fact I think the quality of a
> PRNG should be evaluated properly, in the context in which it is to be
> used, and not at all by analogy to a TRNG.

Or course. For some purposes the ouput 1 2 3 4 5 6 7 8 9 10.... is
exactly what you want. But insofar as you want a Random number
generator, the comparison with a TRNG is exactly the right metric.


From: MrD on 10 Jun 2010 05:38
unruh wrote:
> On 2010-06-09, MrD <mrdemeanour(a)jackpot.invalid> wrote:
>> unruh wrote:
>>> On 2010-06-09, MrD <mrdemeanour(a)jackpot.invalid> wrote:
>>>> unruh wrote (citing Mr. Chicks):
>>>>>> One implication of the "full period" is that when the
>>>>>> random number generator is initialized, we can initialize
>>>>>> the seed to any value, because the "cycle" is all of the
>>>>>> 2^32 bit patterns of the seed. So there are no worries
>>>>>> about "short cycles".
>>>>> Another implication is that this a very weak generator, and
>>>>> is NOT pseudo-random. ( a true random generator will have the
>>>>> same probability of repeating a number as of getting any
>>>>> other number. This one never repeats a number.)
>>>> Aren't you confusing PRNG and TRNG here? An LCG is a type of
>>>> PRNG, according to all the previous discourse on the subject
>>>> that I am familiar with. But nobody has claimed that this LCG
>>>> is a TRNG.
>>>>
>>> A good prng acts like a true rng with respect to most statistical
>>> tests. never repeating until the whole cycle is NOT a feature of
>>> any TRNG and thus should not be a feature of any PRNG. Having
>>> that feature makes the PRNG weak.
>> An LCG is then a weak PRNG (from a crypto POV), and therefore it is
>> indeed a PRNG, according to what you've just said; which conflicts
>> with your assertion that an LCG is not pseudo-random. Right?
>
> By your definition a program which puts out the numbers in order is a
> PRNG.

I didn't offer a definition of a PRNG. I was just trying to interpret
your remarks.

> If that is what you want, then fine, use that as your definition. I
> said that such a PRNG was weak, and was not pseudo-random, since it
> did not comply with at least one feature of a random generator, that
> the probability of the next character be independent (in some sense)
> of the preceeding stream.

Isn't that true of any PRNG?

Another difference (or perhaps, a more general formulation of the same
distinction) between a PRNG and a TRNG is that only the output from the
latter is actually random.

[snip]

>
>> Also, with respect to the repeating/non-repeating characteristic:
>> if a certain LCG never repeats an output value until it has
>> completed a cycle of N, then another LCG can be created from it
>> simply by taking its output modulo some X :: X<N; and this derived
>> generator will repeat, if you consider repetition to be desirable.
>
> ??? repetition is not in and of itself desireable or not. It is a
> symptom.

OK, fine. So in this case, you are saying that the non-repetition is a
symptom of some property of the LCG that makes it weak. My understanding
is that the principal (cryptographic) weakness of the LCG is that given
a small number of successive output bits, the entire cycle can be
induced. Is this fact related to the non-repetition property? Does an
LCG that does repeat (such as the modulo X variant) have greater
resistance to cycle induction? Or is the non-repetition property related
to some additional weakness?
>
>> BTW: Saying that a PRNG having some property that isn't shared by
>> any TRNG makes it a bad PRNG seems to me to be poor reasoning. What
>> you say may be true, but it isn't evident to me. Would you argue,
>> for example, that a good PRNG should exhibit bias? Many (most?)
>> TRNGs exhibit bias.
>
> An RNG should be such that the probability of the next output is
> independent of the value of the last N characters. Now, clearly this
> cannot be true, since the generator itself provides the link between
> the last N outputs and the current one. But, it should be infeasible
> given just the output to discover that lack of independence. A
> physical implimentation of a TRNG may exhibit biases, and to that
> extent it is NOT a TRAG.
>
>
>> Would you also argue that a PRNG should repeat output values, even
>> at the expense of a shortened cycle? My modulo-X derived LCG
>> repeats output values at the cost of a shortened cycle, and I'm not
>> convinced that it's a worse (or better) PRNG for that fact. In fact
>> I think the quality of a PRNG should be evaluated properly, in the
>> context in which it is to be used, and not at all by analogy to a
>> TRNG.
>
> Or course. For some purposes the ouput 1 2 3 4 5 6 7 8 9 10.... is
> exactly what you want. But insofar as you want a Random number
> generator, the comparison with a TRNG is exactly the right metric.

This seems overly simplistic; it's hardly ever the case that someone
actually wants a random number generator. What they want might be a
sequence of numbers such that given the first N outputs, it is
infeasible to predict the N+1th output. Or they may want a sequence of
numbers having certain statistical properties. Or they may not care
about the properties of the sequence at all, and may instead be
concerned entirely with the process by which the sequence is produced
(e.g. gambling systems).

With regard to the '1 2 3 4...' observation, that sequence is more
likely to emerge from an arbitrarily-chosen TRNG source than from any
serious PRNG. Should a PRNG then be considered weak because it doesn't
share that property with a TRNG? I would have thought that *in that
respect* a PRNG may actually be stronger (from a crypto POV) than a
TRNG. That is, we expect that sometimes the output from a TRNG will
mimic non-random output; whereas the output from most PRNGs will never
do that, by design.

Of course, if what you want is a PRNG that is as similar as possible to
a TRNG, then it's trivially the case that comparing candidates'
behaviour with that of a TRNG is "exactly the right metric". But why
would anyone want such a thing? It's much more likely that they want a
sequence of numbers that shares certain properties with the output of a
TRNG. Knowing what those properties are is a prerequisite to evaluating
the strength/weakness of the PRNG. No?

--
MrD.
First  |  Prev  | 
Pages: 1 2
Prev: Applied Computing 2010: 1st call extension until 25 June 2010
Next: Simple Paper and Pencil Cipher