Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Is the uncompressibility of encrypted data a necessary property for a good cryptographic algorithm?

To make a crude experiment, I encrypted an 8K file with all 'A' and then compressed both the encrypted and the unencrypted file.

The compressed unencrypted file went down to less than 200 bytes while the conpressed encrypted file became larger than the encrypted file.

I think that while this result says nothing about the goodness of the encryption, the opposite result (i.e. if the encrypted file would shrink after compression) would have revelead a weakness of the encrypting algorithm.

Am I correct or am I missing something about the relation between encryption and compression?

share|improve this question
add comment

1 Answer

Yes, a ciphertext of a bulk encryption algorithm normally should not be compressible to less than the plaintext size¹ (at least, if the compression function does not know the encryption key), other than in some corner cases which will occur only with negligible probability (like you hitting the one plaintext which will encrypt to the all-zero-string).

¹Of course, if the encryption algorithm applies some encoding after encrypting which makes the ciphertext larger, like PGP's ASCII-armor, Base64 or Hexadecimal encoding, you can compress this resulting encoded ciphertext, but not to less than the original plaintext size. Similar things could occur with some asymmetrical encryption algorithms, which have slightly biased output, when (mis)used for bulk encryption - don't do this.

If the compressor knows the algorithm and key, it can simply decrypt the ciphertext and then compress the plaintext, of course.

With bad modes of operation, such as ECB mode, some repetitions in the plain text will also show through in the cipher text (see this famous example in Wikipeda), which then might show by compressibility of the ciphertext (the ECB image is bigger than the plain"text" one, but still smaller than the CBC one).

On the other hand, non-compressibility of ciphertext with generic compression algorithms is given by every not totally trivial encryption algorithm, even if they have to be categorized as broken by every aspect.

share|improve this answer
    
@fgrieu: Thanks for this comment. I tried to find a wording and edited it in. –  Paŭlo Ebermann Jun 3 '12 at 11:03
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.