Compression and Security


1. Introduction to compression before encryption

It has long been appreciated that there are advantages to eliminating regularities in the plaintext before encrypting.

The primary advantages to doing this are:

  • The opponents get less cyphertext to analyse;
  • What they do get has a corresponding plaintext with fewer redundancies and regularities.

The advantage of the first point should be obvious enough: the less data the enemy has to analyse, the fewer clues the have about the internal state of your cypher, and thus its key.

The advantage of the second point is that it hinders cryptanalytic attacks.

"Fewer redundancies and regularities" may be translated into more formal terms as "greater entropy per bit".

The more closely the statistical properties of the file approach that of a random data stream, the fewer regularities the cryptanalyst has to go on.

All this should be uncontroversial.

That compression aids encryption was realized by those who first employed "code-words" in their cyphers. By replacing frequently-used words like "the" and "and" with otherwise little-used symbols before encrypting they succeeded in reducing the volume of the text based on known regularities in the English language. This type of cypher was employed, for example, by Mary Queen of Scots.

That eliminating patterns in the frequency of the occurrence of particular symbols in the text before encyphering is desirable was clearly realized by the time homophones were employed in conjunction with mono alphabetic-substitution cyphers.

Index | Main Index | Links |