2 ms·
In truth if you're using a decent algorithm, then breaking it is effectively impossible anyways. But that said, techniques for breaking encryption rely on iden
by btilly 16y ago
In truth if you're using a decent algorithm, then breaking it is effectively impossible anyways.
But that said, techniques for breaking encryption rely on identifying redundant information in a message. The less redundant information there is, the harder this is to do. Sure, the known header on a ZIP is useful redundancy. But the amount of introduced redundancy is much, much less than the redundancy you got rid of by moving from a document in English to binary gibberish.
Underlying this is a fundamental fact of information theory, which is that messages with a high information density look like white noise. A slight mistake in the message you have results in something that looks like another potentially valid message rather than something that is obviously wrong. This makes it much harder to verify that you're on an intermediate step towards properly decrypting the message.
Therefore increasing information density makes an attacker's life harder. Compression increases information density by a lot, and so makes the encryption harder to break.
- CWuestefeld 16y agoI think I'm understanding your argument, but I don't think it's correct. A well-encrypted message -- whether pre-compressed or not -- is indistinguishable from noise. If it was not pre-compressed, then its information density is lower, which means the S/N is lower. Information theory tells us that the worse the S/N, the harder it is to extract the information.
- btilly 16y agoWhether or not you agree with it, the argument is believable enough to have been presented in a graduate level course that I was in a number of years ago. (The course was on wavelets, but background review on information theory was presented at the beginning.) You are correct that a perfectly encrypted message is indistinguishable from noise. Decryption is the art of distinguishing imperfectly encrypted messages from noise. Anything that makes the message harder to distinguish, makes decryption harder. Which means that the more the message looks like noise, the harder it is to decrypt. Your attempted counter argument fails on the fact that a redundant message has very little noise, and therefore has a high S/N despite having not that much signal per bit. However that said, it is true that if you take a redundant message, remove some redundancy by adding some random noise to it, then encrypt it, the result will be harder to decrypt than if you just encrypted the original redundant message. Of course the fundamental reason behind that is that detecting redundant information is at the heart of decryption. In that light it is interesting to compare the two known perfect encryption mechanisms. The first is the one-time pad. In that case the transmitted message has absolutely no redundancy because the definition of the encryption method contains as much information as the transmitted message. The second is for the two end points to have a list of pre-agreed messages of equal likelyhood, which they will refer to in binary code. This offers perfect compression with absolutely no redundancy, and therefore the attacker again has absolutely no way to guess what the pre-encoded messages are. (This is much harder to do properly in practice than one time pads, which themselves are pretty tricky.)