Re: commutative property of algorithms
 From: "J.D." <degolyer181@xxxxxxxxx>
 Date: Tue, 16 Mar 2010 07:33:49 0700 (PDT)
On Mar 16, 9:51 am, "Scott Fluhrer" <sfluh...@xxxxxxxxxxxxx> wrote:
"Maaartin" <grajc...@xxxxxxxxx> wrote in message
news:0e2af2b55650473386ecce6cc23ce97f@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Mar 16, 1:58 am, "J.D." <degolyer...@xxxxxxxxx> wrote:
Permutation cycles, as I discovered today, are one of the many gaps in
my knowledge. I am still grappling with how a permutation with an odd
number of disjoint orbits can be "even" (for instance, the AES sbox
has 5 disjoint orbits).
Right. But the sbox works on 1 byte and leaves 15 bytes alone. Taken
as a function of the whole state it has 5 * 2**(15*8) orbits, right?
Yes, however more to the point, if a single sbox can be implemented in N
transpositions of 1 byte elements, the effect a single sbox on the entire
128 bit element can be performed in N * 2**120 tranpositions (as Martin has
pointed out). This is even, hence the effect of a single sbox on the entire
cipher is even, whether or not N is even.
Actually, all the sboxes (may) work in parallel, but thinking about
them as being applied in row makes it clearer here.
Either in a row or serially.
I take it that this has to do with the number
of transpositions/swaps that a permutation can be decomposed into.
But it would seem to raise the possibility that AES under a particular
key might well constitute a permutation with an odd number of disjoint
orbits (for example "one grand loop") despite being decomposable into
an _even_ number of transpositions. So evidently I am missing
something...
Yes, but it's simple, too: A permutation decomposable into an even
number of transpositions is by definition an even permutation. Is a
"grand loop" an even permutation? Only in case of a set having an odd
number of elements. Is 2**128 odd?
For the "grand loop" just make an example, consider the set {0,1,2,3},
wlog. let x > (x+1) mod 4 be the permutation, you can decompose it
into 3 swaps:
0 <> 1
1 <> 2
2 <> 3
Well, a grand loop permutation (or single cycle permutation) on N elements
can be implemented in N1 transpositions (as, in your case, you created a
single cycle permutation on 4 elements with 3 transpositions). Hence, a
single cycle permutation on an even number of elements is odd, while a
single cycle permutation on an odd number of elements is even.
In the case of AES, we have 2**128 elements, this is even, and hence a
single cycle permutation would be odd.

poncho
Thanks (to both of you). It all makes sense now.
.
 FollowUps:
 Re: commutative property of algorithms
 From: WTShaw
 Re: commutative property of algorithms
 References:
 Re: commutative property of algorithms
 From: unruh
 Re: commutative property of algorithms
 From: WTShaw
 Re: commutative property of algorithms
 From: Scott Fluhrer
 Re: commutative property of algorithms
 From: J.D.
 Re: commutative property of algorithms
 From: Scott Fluhrer
 Re: commutative property of algorithms
 From: J.D.
 Re: commutative property of algorithms
 From: Scott Fluhrer
 Re: commutative property of algorithms
 From: J.D.
 Re: commutative property of algorithms
 From: Maaartin
 Re: commutative property of algorithms
 From: J.D.
 Re: commutative property of algorithms
 From: Scott Fluhrer
 Re: commutative property of algorithms
 From: Maaartin
 Re: commutative property of algorithms
 From: Scott Fluhrer
 Re: commutative property of algorithms
 Prev by Date: Re: commutative property of algorithms
 Next by Date: On ngram substitutions
 Previous by thread: Re: commutative property of algorithms
 Next by thread: Re: commutative property of algorithms
 Index(es):
Relevant Pages
