On Fri, Feb 21, 2003 at 06:31:20AM -0800, Ed Gerck wrote: > Shannon proved that if > "n" (bits, bytes, letters, etc.) is the unicity distance of a ciphersystem, > then ANY message that is larger than "n" bits CAN be uniquely deciphered > from an analysis of its ciphertext [...] > Conversely, Shannon also proved that if the intercepted message has less > than "n" (bits, bytes, letters, etc.) of plaintext then the message CANNOT > be uniquely deciphered from an analysis of its ciphertext -- even by trying > all keys and using unbounded resources.
No, the unicity distance is the amount of ciphertext where the expected number of spurious keys is zero. >From Shannon's "Communication Theory of Secrecy Systems" (http://www.cs.ucla.edu/~jkong/research/security/shannon.html) It will be seen from Fig. 7 that the equivocation curves approach zero rather sharply. Thus we may, with little ambiguity, speak of a point at which the solution becomes unique. This number of letters will be called the unicity distance. For the random cipher it is approximately H(K)/D. D (the redundancy in bits/letter) depends on how good the attackers model of the language is, which is difficult to control for whoever does the encryption. It should be possible to find two messages of the same size, one of which has no spurious keys while the other one has at least one. It is thus not possible to give an exact size for a given cipher system such that no ciphertexts have spurious keys but there exist spurious keys for all smaller ciphertexts. > The following is always true, for any possible plaintext bit pattern: > > "For each AES-128 plaintext/ciphertext (c,p) pair with length > equal to or larger than the unicity distance, there exists exactly > one key k such that c=AES-128-Encrypt(p, k)." No, if it was true I could take any plantext message and 2^128 + 1 random ciphertexts and find a key for each of the ciphertexts that encrypts the plaintext into it, unless you mean that the ciphertexts must be chosen so that there is a key which encrypts p into c. In the latter case it may be true if the source language is e.g. English, but not for an arbitraty language. It also does not hold for any arbitrary cipher; a trivial counter-example would be a cipher where not all key bits are used. Anyway, I believe that the original question was whether there is exactly one key for every possible pair of *blocks* c, p so that c=AES-128-Encrypt(p, k). I believe this since the original poster wrote: "Of course we can look at the generalized case of Rijndael with block size == key size and ask the same question." For that question I agree with what others have already said. /Andreas --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]