Need some simple bijective mappings
in [Cryptography]
|
From: Maaartin on 15 Jun 2010 20:24 On Jun 16, 1:18 am, Tran Ngoc Duong <tranngocdu...(a)gmail.com> wrote: > I can offer an example more: > > The operation x.y = (1<<m)*k*x*y + x + y (k odd) is bijective on x and > on y. Agreed. > Actually, it is an (abelian) group operation for any word length n. I don't think it's a group. With K = (1<<m)*k != 0 you get (x.y).z = (K*x*y + x + y) . z = K*(K*x*y + x + y) * z + K*x*y + x + y + z = K*K*x*y*z + K*(x+y+x*y) + x + y + z which surely differs from x.(y.z) due to the asymmetry. So it's not associative. The function (x, y) -> K * x*y + K' * x + K'' * y with K even and both K' and K'' odd is a slight generalization of the above. You can even substitute xor for add (I think).
From: Tran Ngoc Duong on 15 Jun 2010 23:05 On Jun 16, 7:24 am, Maaartin <grajc...(a)seznam.cz> wrote: > On Jun 16, 1:18 am, Tran Ngoc Duong <tranngocdu...(a)gmail.com> wrote: > > > I can offer an example more: > > > The operation x.y = (1<<m)*k*x*y + x + y (k odd) is bijective on x and > > on y. > > Agreed. > > > Actually, it is an (abelian) group operation for any word length n. > > I don't think it's a group. With K = (1<<m)*k != 0 you get > (x.y).z = (K*x*y + x + y) . z = K*(K*x*y + x + y) * z + K*x*y + x + y > + z > = K*K*x*y*z + K*(x+y+x*y) + x + y + z You miscalculated the second term. Actually it is K*( x*y + x*z + y*z)... > which surely differs from x.(y.z) due to the asymmetry. So it's not > associative. .... so symmetry is there and associative it is. To be precise, I had to write that 1 <= m < n and the right-hand side of the definition of x.y is to be taken mod (1<<n). For the simplest case x.y = 2*x*y + x + y [mod (1<<n)], the group is isomorphic to the multiplicative group of odd integers mod (1<<(n+1)). The isomorphism is x |---> 2*x + 1 [mod (1<<(n+1))]. > > The function > (x, y) -> K * x*y + K' * x + K'' * y > with K even and both K' and K'' odd is a slight generalization of the > above. You can even substitute xor for add (I think). Yes. But they are quasi-groups only. Groups are nicer since the same formulae may be used for both encoding and decoding.
From: Mok-Kong Shen on 16 Jun 2010 02:47 Maaartin wrote: > Mok-Kong Shen wrote: >> BTW, I like to mention at this opportunity the (trivial) fact that, >> if the three simple ones I mentioned above are designated by A, B, C >> and their application in the sequence ABC with pseudo-random values >> constitutes a 'round', then the result of applying a few rounds on a >> sequence of plaintext words apparently could be quite hard for the >> analyst to deal with practically. > > There are many algorithms using only fixed distance rotations, > additions and xors, e.g., Cubehash, Salsa20, Threefish. This is quite > common in modern designs, since these operations can be computed fast > on nearly all architectures. Some even avoid additions (and use and/or > instead) in order to make the hardware implementation more efficient. I suppose you misunderstood me. Why "fixed" rotations? Fixed rotations are unfavourable for me. I wanted in the above context to process the sequence of plaintext words with "stream" ciphering technique. (I personally prefer to term processing with units up to the size of a computer word as stream processing and processing with units above that size as block processing, but this definition issue is nonrelevant here.) So, given x, the common processing with xor is x^d, where d is pseudo-random. Doing a superencipherment one has (x^d)>>>c. Another superencipherment gives a*((x^d)>>>c)+b. This is what I meant with designation like ABC. Each plaintext word is processed by a different set of pseudo-random values {a,b,c,d} than the others. If one uses more than one round, each word will be processed by several of such distinct sets of values from pseudo-random generation dependent one a certain message key. > You need no bijective operations if you use e.g., Feistel scheme. > Something like > (x, y) -> (x ^ f(y), y) > is bijective for any function f. Arbitrary function can be computed > quickly when stored in table. You can use > x -> x ^ t[x& 255] > with table t containing 256 ints and designed so that you get a > permutation when looking only on the lowest byte, i.e., t[x]& 255 = x > ^ p(x) for a permutation p and 0<=x<256. > > Additional I have no comment to this, considering that I have in the above cleared up a misunderstanding. M. K. Shen
From: Mok-Kong Shen on 16 Jun 2010 03:44 Tran Ngoc Duong wrote: > To be precise, I had to write that 1<= m< n and the right-hand > side of the definition of x.y is to be taken mod (1<<n). > > For the simplest case x.y = 2*x*y + x + y [mod (1<<n)], the group is > isomorphic to the multiplicative group of odd integers mod (1<<(n+1)). > The isomorphism is x |---> 2*x + 1 [mod (1<<(n+1))]. Would you please write the general form of the mapping once again for my clear understanding? Thanks. M. K. Shen
From: Tran Ngoc Duong on 16 Jun 2010 05:08
On Jun 16, 2:44 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Tran Ngoc Duong wrote: > > To be precise, I had to write that 1<= m< n and the right-hand > > side of the definition of x.y is to be taken mod (1<<n). > > > For the simplest case x.y = 2*x*y + x + y [mod (1<<n)], the group is > > isomorphic to the multiplicative group of odd integers mod (1<<(n+1)). > > The isomorphism is x |---> 2*x + 1 [mod (1<<(n+1))]. > > Would you please write the general form of the mapping once again > for my clear understanding? > > Thanks. > > M. K. Shen Sure. The bijective mapping is x |---> x.y with constant y (or y | --> x.y with constant x), where x.y = (1<<m)*k*x*y + x + y [mod (1<<n)] where 1 <= m < n, and k is odd. The formulae is exactly the same as stated in my first post. Just that the right hand-side is taken mod (1<<n). By 1<<n, I mean "n-th power of 2". |