Relation between number theory and cryptography
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
According to 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.
Well, you may have placed an upper-limit on the amount of information in an encrypted message. I will try to place a lower limit. Consider the case where there is less information in the ciphertext than in the plaintext. Clearly, in this case, there is no way to retrieve the entire plaintext from the ciphertext since we no longer have enough information. So we have to have at least as much information in the CT as we do in the PT. If I bought your original arguement, I'd have to say there is no net change in information content. Unfortunately, I don't buy your arguement. What if we were to add some noise in the process of crypting the PT? If we did it algorithmicly, we have added some kind of information to your CP, totally unrelated to the actuall message. But nontheless, it is information of SOME type; it may simply be 0xFE if the message was writen in the daytime or 0xAC if not. This is information in a very "uncompressed" form. Strictly speaking this is only 1 bit of information encoded into a byte, but the net result is a gain in information content in our CT. I don't know, is there a flaw in my reasoning? Laters. +-----------------------+-----------------------------+---------+ | J. Michael Diehl ;-) | I thought I was wrong once. | PGP KEY | | mdiehl@triton.unm.edu | But, I was mistaken. |available| | mike.diehl@fido.org | | Ask Me! | | (505) 299-2282 +-----------------------------+---------+ | | +------"I'm just looking for the opportunity to be -------------+ | Politically Incorrect!" <Me> | +-----If codes are outlawed, only criminals wil have codes.-----+ +----Is Big Brother in your phone? If you don't know, ask me---+
participants (2)
-
hfinney＠shell.portal.com -
J. Michael Diehl