in reply to Re^5: Compressing and Encrypting files on Windows
in thread Compressing and Encrypting files on Windows

sigh. I read the link you originally posted, and with regard to this this discussion, it is irrelevant.

My point is that when encrypting data with a OTP, there is absolutely no requirement that the cypher text be uncompressible.

You seem be confusing the concepts of random and compression. And that if something is randomly generated, it can't be compressed.

To show that this isn't the case, lets do a small thought experiment. We'll use an unbiased coin as a generator of randomness and flip the coin a number of times to generate a series of events. If you flip the coin enough times you would expect the results overall to be statistically indistinguishable, but if you examine sections of the sequence then you might find sections which are repeats, and therefore can be compressed. For example, it's entirely possible to flip 100 heads in a row, which is possible to compress with run length encoding. In fact, the probability of this sequence is exactly the same as all other orderings of 100 flips.

As a concrete example, lets assume we want to send a message of 100 bits, we need a key length of 100 bits (equivalent to 100 coin flips) to apply to the data, as you pointed out. We'll assume that the message has all the bits set to 0, which could correspond to a particular flag. So lets look at the key. Given that over a small number of events, the key might be compressible, and given that the message is xor'd against the key, the result might be compressible.

Now you might say that a geiger counter would never produce this kind of data. But imagine that a sun in a distant systems goes supernova, or there's a large solar flame in our Sun, either of which creates a large number of exotic particles, which during the acquisition of the key maxes out our geiger counter. The key will be all the same bits. This would result in a cypher text with the same statistical properties as the plain text, which if it's english text, is compressible.

Indeed, the cypher text might appear to be english text, irrespective of what the key or the plain text is, and therefore compressible.

What are the chances of this, flipping small.

  • Comment on Re^6: Compressing and Encrypting files on Windows