[19356] in cryptography@c2.net mail archive
Re: permutations +- groups
daemon@ATHENA.MIT.EDU (John Denker)
Thu Dec 22 11:27:39 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 21 Dec 2005 14:15:47 -0500
From: John Denker <jsd@av8n.com>
To: Ben Laurie <ben@algroup.co.uk>
Cc: cryptography@metzdowd.com
In-Reply-To: <43A8F1E1.80903@algroup.co.uk>
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@metzdowd.com
