compressing randomly-generated numbers

[james hughes]

On Aug 9, 2006, at 8:44 PM, Travis H. wrote:

> Hey,
>
> I was mulling over some old emails about randomly-generated numbers
> and realized that if I had an imperfectly random source (something
> less than 100% unpredictable), that compressing the output would
> compress it to the point where it was nearly so.  Would there be any
> reason to choose one algorithm over another for this application?

This is neither correct nor a good idea.

Taking almost random information and compressing it will lead to less  
random results.

Specifically, I will give the general LZW case and then go to the BZ2  
case.

1) For LZW (even ignoring the magic numbers), if a byte does not  
match anything in the dictionary (it starts with a dictionary of all  
0s, so the probability of a match on the first byte is low) then that  
byte will get a header of a 0 bit. That byte now becomes 9 bits. The  
next byte will have a dictionary of the previous byte and all zeros.  
The chance of a match will still be small and putting that into the  
dictionary will be a 9 bit field with 0s. So in the first 2 bytes, I  
can almost guarantee I know where 2 zero bits are.

2) BZ2 transforms the data and then uses LZW. See 1)....

The correct way to "improve" almost random data is to process it with  
a hash like function with compression.

Jim


---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com