Relation between number theory and cryptography

[hfinney@shell.portal.com]

Clark Reynard, <clark@metal.psu.edu>, asks about information and cryptography.

As I see it, a cyphertext has at most the same information as the sum of
the original message, the key, and the encryption algorithm.  Without
knowing the key a cyphertext may appear random, but actually it is not.
If it is the encryption of a lower-information plaintext (such as English
text) then it still basically possesses that low level of information, it's
just not obvious how to compress it.

It's not unusual for different compression algorithms to achieve very different
levels of compression.  In a sense, these different algorithms disagree
about the amount of information in the original data.  We discussed digitized
speech here some time back.  Ordinary compression algorithms such as Lempel-
Ziv or Huffman encoding don't compress digitized speech much at all.  Special
algorithms such as linear predictive coding can achieve great compression.

In the same way, there is no contradiction between the fact that an encrypted
file looks random and incompressible, and the fact that knowing the key it
becomes clear that the file actually can be compressed.  Any calculation of
the information content of a file can only be considered an upper bound.
A more clever algorithm may always exist which will reveal the data to have
much less information than was originally thought.  This is basically the
situation you have when faced with an encrypted file for which you don't
have the key.

Hal Finney
hfinney@shell.portal.com