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: 32/64 bit cc differences
    ... Ben Bacarisse wrote: ... some odd idioms, unnecessary casts, not using prototype declarations, ... Permutation will mess up all-or-nothing, as far as I can tell. ... It's xcryptstr with the xor/xnor's that ...
    (comp.lang.c)
  • 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)