Ben Laurie wrote:
Good ciphers aren't permutations, though, are they? Because if they were, they'd be groups, and that would be bad.
There are multiple misconceptions rolled together there. 1) All of the common block ciphers (good and otherwise) are permutations. To prove this, it suffices to require that ciphertext blocks be the same length as plaintext blocks, and that arbitrary text can be enciphered and (given the proper key) uniquely deciphered. It's an elementary pigeon-hole argument: each plaintext block must map to one and only one ciphertext block. 2) If you consider the set of all imaginable permutations, there will be ((2^B) factorial) elements, where B is the blocksize of the cipher. Call this set U. The set U is closed under composition, so in fact we necessarily have a group. This is neither a good thing nor a bad thing; it just is. 3) However, the group mentioned in item (2) is not what people mean when they talk about a cipher having "the group property". Let me illustrate using plain old DES. There are at most 2^56 keys. Therefore let us consider the set of all 2^56 /keyable/ permutations; call this set K. This is a verrry small subset of the ((2^64) factorial) imaginable permutations. 4) The interesting question is whether K is closed under composition. This is of particular interest if you are trying to cobble up an improved cipher with an N-times longer key, by layering N copies of the original cipher. This is guaranteed to be a waste of effort if K is closed under composition, i.e. if K is in fact a group, i.e. a subgroup of U. The converse does not hold; showing that K is not closed does not suffice to show that layering is a good idea. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
