permutations +- groups

[John Denker]

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 majordomo at metzdowd.com