commutative property of algorithms
in [Cryptography]
|
Prev: Volume on Advanced Linear Cryptanalysis -- Contributions sollicited
Next: OAEP vs. PSS in PKCS#1
From: Scott Fluhrer on 15 Mar 2010 20:52 "Maaartin" <grajcar1(a)seznam.cz> wrote in message news:28c6fdaa-aeed-40cb-8fd8-d5e3cfbb7fee(a)d27g2000yqf.googlegroups.com... On Mar 16, 12:08 am, "J.D." <degolyer...(a)yahoo.com> wrote: >> On Mar 15, 6:46 pm, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote: >> Thanks. That certainly helps, though I am going to have to do a lot >> more reading before I can understand enough to fully follow your >> argument. > > I don't think so, it's easy, the 1st and 3rd parts follows directly > from the definition. The second can be clarified by an example: > Consider the set of 4-bit numbers (written in hex), habe a function > complementing the first bit. This function looks like follows: > 0 -> 1 > 1 -> 0 > 2 -> 3 > 3 -> 2 > ... > E -> F > F -> E > so it's composition of 8 swaps: > 0 <-> 1, 2 <-> 3, ..., E <-> F, > so it's even per definition. Obviously the same argument holds for > "any operation on a subset of bits (which happen independently of the > values of the bits not in the subset)". In fact, the number of swaps > is always a multiple of 2**n where n is the number of the bits not in > the subset. Thank you, that is an excellent way of putting it -- poncho
From: J.D. on 15 Mar 2010 20:58 @Maaartin > On Mar 16, 12:08 am, "J.D." <degolyer...(a)yahoo.com> wrote: > > > On Mar 15, 6:46 pm, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote: > > Thanks. That certainly helps, though I am going to have to do a lot > > more reading before I can understand enough to fully follow your > > argument. > > I don't think so, it's easy, 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). 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... I don't know; I'll figure it out, but I just need to do some more reading.
From: Scott Fluhrer on 15 Mar 2010 21:10 "J.D." <degolyer181(a)yahoo.com> wrote in message news:5f6ca934-40f1-4030-914e-8b6e7c379a5d(a)d27g2000yqf.googlegroups.com... > 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). Actually, the sbox itself might implement an odd permutation (I haven't checked it myself); we'vr been talking about the AES function itself, not the sbox. -- poncho
From: J.D. on 15 Mar 2010 21:18 On Mar 15, 9:10 pm, "Scott Fluhrer" <sfluh...(a)ix.netcom.com> wrote: > "J.D." <degolyer...(a)yahoo.com> wrote in message > > news:5f6ca934-40f1-4030-914e-8b6e7c379a5d(a)d27g2000yqf.googlegroups.com... > > > 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). > > Actually, the sbox itself might implement an odd permutation (I haven't > checked it myself); we'vr been talking about the AES function itself, not > the sbox. > > -- > poncho That was just an example of a permutation with an odd number of orbits, though perhaps not the best one since I am not sure myself what the parity of the s-box is. A better example of what is confusing me is on the Wikipedia "parity of a permutation" page: http://en.wikipedia.org/wiki/Parity_of_a_permutation#Example In that example the parity is odd, but the number of disjoint orbits is even.
From: Maaartin on 15 Mar 2010 21:37
On Mar 16, 1:58 am, "J.D." <degolyer...(a)yahoo.com> 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? Actually, all the sboxes (may) work in parallel, but thinking about them as being applied in row makes it clearer here. > 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 |