Prev: Estimating entropy of a stream
Next: Scalable Key Cryptography – New Cryptography for Your Perusal
From: Mok-Kong Shen on 21 Dec 2009 11:18

Decimation in crypto means selecting every tenth, and in general,
selecting every nth element from a sequence in order to hide
exploitable patterns in it. (See
http://www.ciphersbyritter.com/GLOSSARY.HTM#Decimation).

A tiny generalization in my humble view would be choosing elements from
a sequence with a probability p by a statistically good PRNG. Suppose
one chooses p=0.1, pseudo-randomly pick a starting point and "decimate"
thus the digit sequence of Pi, is there any conceivable yet practical
way that an anylist could succeed to do prediction in such cases?

Thanks,

M. K. Shen
From: Joseph Ashwood on 22 Dec 2009 03:05
"Mok-Kong Shen" <mok-kong.shen(a)t-online.de> wrote in message
news:hgo74e$kdq$00$1(a)news.t-online.com...
>
> Decimation in crypto means selecting every tenth, and in general,
> selecting every nth element from a sequence in order to hide
> exploitable patterns in it. (See
> http://www.ciphersbyritter.com/GLOSSARY.HTM#Decimation).
>
> A tiny generalization in my humble view would be choosing elements from
> a sequence with a probability p by a statistically good PRNG. Suppose
> one chooses p=0.1, pseudo-randomly pick a starting point and "decimate"
> thus the digit sequence of Pi, is there any conceivable yet practical
> way that an anylist could succeed to do prediction in such cases?

Absolutely. Although it does increase the difficulty, it does not change an
insecure PRNG to a cryptographically secure PRNG.
Joe

From: Mok-Kong Shen on 22 Dec 2009 06:27
Joseph Ashwood wrote:
> "Mok-Kong Shen" wrote:
>> Decimation in crypto means selecting every tenth, and in general,
>> selecting every nth element from a sequence in order to hide
>> exploitable patterns in it. (See
>> http://www.ciphersbyritter.com/GLOSSARY.HTM#Decimation).
>>
>> A tiny generalization in my humble view would be choosing elements from
>> a sequence with a probability p by a statistically good PRNG. Suppose
>> one chooses p=0.1, pseudo-randomly pick a starting point and "decimate"
>> thus the digit sequence of Pi, is there any conceivable yet practical
>> way that an anylist could succeed to do prediction in such cases?
>
> Absolutely. Although it does increase the difficulty, it does not change
> an insecure PRNG to a cryptographically secure PRNG.

It may be noted however that there is an "indirectness" involved, i.e.
the insecure PRNG employed is not directly used to encrypt (xor with
the plaintext), so that the analyst can't get its bits in order to
break it.

M. K. Shen

From: Cristiano on 22 Dec 2009 06:49
Joseph Ashwood wrote:
> [...] Although it does increase the difficulty, it does not
> change an insecure PRNG to a cryptographically secure PRNG.

If you decimate the output of a LFSR (which is "an insecure PRNG") you get a
cryptographically secure PRNG (self-shrinking LFSR).

Cristiano


From: Greg Rose on 22 Dec 2009 15:32
In article <4b30b227(a)news.x-privat.org>,
Cristiano <cristiano.pi(a)NSquipo.it> wrote:
>Joseph Ashwood wrote:
>> [...] Although it does increase the difficulty, it does not
>> change an insecure PRNG to a cryptographically secure PRNG.
>
>If you decimate the output of a LFSR (which is "an insecure PRNG") you get a
>cryptographically secure PRNG (self-shrinking LFSR).

No you don't. There are attacks against the SSG.

Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
 |  Next  |  Last
Pages: 1 2
Prev: Estimating entropy of a stream
Next: Scalable Key Cryptography – New Cryptography for Your Perusal