Re: commuting?/non-group cipher?

From: Peter Fairbrother (zenadsl6186_at_zen.co.uk)
Date: 10/28/04 

Date: Thu, 28 Oct 2004 19:00:05 +0100

Kristian Gjøsteen wrote:

> Peter Fairbrother <zenadsl6186@zen.co.uk> wrote:
>> Some ciphers have the property that a double encryption can always be
>> replaced by a single encryption, ie E(k3)[P] = E(k1)[E(k2)[P]]

>> Can anyone think of an example of a cipher with this property that is not a
>> group?
>
> I believe any cipher with this property must be a group.

So did I, but I'd missed the inheritance of associativity. Got closure,
inverses and identity (the hard way) though, so I wasn't doing too bad.

Thanks. 

-- 
Peter Fairbrother
left this for reference:
> First we note that the E(.)-functions must be permutations on some set
> for the composition to be possible. Therefore, the set X = { E(.) } is
> a subset of some finite permutation group G. Composition on X inherits
> the associative property from composition on G.
> 
> We need to show that the identity permutation is in X, and that every
> E(.) has an inverse in X.
> 
> So for any x in X, consider the subset X_x = { x^i | i=1,2,... } of
> G. Since G is finite, so must X_x be. In fact, X_x will be the cyclic
> subgroup of G generated by x. Since X is closed under composition,
> X_x is a subset of X. X_x contains the identity and the inverse of x.
> 
> Therefore X is a group.
 
> But X does not have to be commutative (which is what the adjective
> "commuting" suggests to me). An alternative name could perhaps be
> "group cipher" (as opposed to "non-group cipher")?
That's actually the name I used before I was challenged about it.

Relevant Pages

  • Re: commuting?/non-group cipher?
    ... I believe any cipher with this property must be a group. ... for the composition to be possible. ... We need to show that the identity permutation is in X, ... "commuting" suggests to me). ...
    (sci.crypt)
  • Re: Bit-swaps
    ... How many states the actual permutation can take on depend on the bit ... stream in two permutation tables than use bytewise swaps between the ... tables xor together for your pseudorandom stream. ... You might find something of interest in the ciphers of A.A. Moldovyan ...
    (sci.crypt)
  • Re: Passwords with evoluting key/expansion/setup that has flaws some bite leak could be a good thing
    ... and ciphers, so is it true? ... The t and x permutation allows 256! ... permutate invpassword at bitlevel ... and come to read about permutation based PRNG as base for ...
    (sci.crypt)
  • Re: Bit-swaps
    ... How many states the actual permutation can take on depend on the bit ... stream in two permutation tables than use bytewise swaps between the ... most of Moldovyan's ciphers are broken because the bit permutation function is not strong enough. ... int hello; ...
    (sci.crypt)
  • Re: commuting?/non-group cipher?
    ... the property that a double encryption under two keys is ... I can only think of three ciphers which have the property - Caesar, ... permutations ...
    (sci.math)