Re: commutative property of algorithms

On Mar 16, 9:51 am, "Scott Fluhrer" <sfluh...@xxxxxxxxxxxxx> wrote:
"Maaartin" <grajc...@xxxxxxxxx> wrote in message

news:0e2af2b5-5650-4733-86ec-ce6cc23ce97f@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 s-box
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 N-1 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.
.

Relevant Pages

  • Re: commutative property of algorithms
    ... I am still grappling with how a permutation with an odd ... transpositions of 1 byte elements, the effect a single sbox on the entire ... of transpositions/swaps that a permutation can be decomposed into. ... a grand loop permutation (or single cycle permutation) on N elements ...
    (sci.crypt)
  • Re: Group Homomorphisms
    ... odd permutation to 1 is a homomorphism. ... then f is not a homomorphism. ... if both p and q are odd, then pq is XXXX, and .... ... This is nonsense as written; ...
    (sci.math)
  • Re: Finite groups exercise
    ... Hint: This is a very easy problem:) ... Are you asking for a hint or wondering whether we can do it or what? ... Again then, assume that some homothety x\mapsto xy is an odd permutation, ...
    (sci.math)
  • Re: even and odd permutations - popular presentation?
    ... For a given permutation, form it by exchanginging two objects at a time, and ... keep track of how many such transpositions were needed. ... > Can somebody suggest a presentation of even and odd ...
    (sci.math)
  • Re: Review of Mueckenheims book.
    ... There are *no* transpositions in that box at all. ... This requires an infinite sequence of transpositions. ... But Cantor recognized this as an infinite ... welche durch Permutation der Elemente entstehen." ...
    (sci.math)