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

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]

Reply via email to