[35462] in cryptography@c2.net mail archive
Re: compressing randomly-generated numbers
daemon@ATHENA.MIT.EDU (james hughes)
Fri Aug 11 18:16:08 2006
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
In-Reply-To: <d4f1333a0608092044g3dece4c1g19678fd549d71fc0@mail.gmail.com>
Cc: james hughes <hughejp@mac.com>,
Cryptography <cryptography@metzdowd.com>
From: james hughes <hughejp@mac.com>
Date: Thu, 10 Aug 2006 17:06:54 -0700
To: "Travis H." <solinym@gmail.com>
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@metzdowd.com
