Need some simple bijective mappings
in [Cryptography]
|
From: Maaartin on 16 Jun 2010 08:59 On Jun 16, 5:05 am, Tran Ngoc Duong <tranngocdu...(a)gmail.com> wrote: > On Jun 16, 7:24 am, Maaartin <grajc...(a)seznam.cz> wrote: > > (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)... You're right. > > which surely differs from x.(y.z) due to the asymmetry. So it's not > > associative. > ... so symmetry is there and associative it is. Right. Could you give me a reference in the literature? > > 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. Right, but a non-associative function is nice e.g. as a compression function for a non-cryptographic hash.
From: Mok-Kong Shen on 16 Jun 2010 09:27 Tran Ngoc Duong wrote: > 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". I have yet difficulties to understand. One obtains: x |---> x*y = 2^m*k*x*y + x + y = (2^m*k*y+1)*x + y mod 2^n For constant y = c, letting a = 2^m*k*c+1, this becomes x |---> a*x + c mod 2^n where a is odd. But this latter bijective mapping is well-known and is listed in my original post. What has one gained with the more complicated form of expression in my case (where a bijective mapping of x in [0, 2^n-1] is sought)? Thanks, M. K. Shen
From: Tran Ngoc Duong on 16 Jun 2010 23:00 On Jun 16, 8:27 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Tran Ngoc Duong wrote: > > 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". > > I have yet difficulties to understand. > > One obtains: > > x |---> x*y = 2^m*k*x*y + x + y = (2^m*k*y+1)*x + y mod 2^n > > For constant y = c, letting a = 2^m*k*c+1, this becomes > > x |---> a*x + c mod 2^n > > where a is odd. > > But this latter bijective mapping is well-known and is listed in my > original post. > Yes, when y is constant, it is. Even "my" bivariate mapping is not new, too. > What has one gained with the more complicated form of > expression in my case (where a bijective mapping of x in [0, 2^n-1] > is sought)? > Nothing if one need only a single mapping. Nevertheless with n-bit words one may need a set (or sets) of exactly 2^n bijective mappings, in which case group operators may be of interest and I tried to show a family of these, in addition to the usual "+", "^" and multiplication (in various representations) in GF(2^n).
From: Tran Ngoc Duong on 16 Jun 2010 23:45 On Jun 16, 7:59 pm, Maaartin <grajc...(a)seznam.cz> wrote: > On Jun 16, 5:05 am, Tran Ngoc Duong <tranngocdu...(a)gmail.com> wrote: > > > On Jun 16, 7:24 am, Maaartin <grajc...(a)seznam.cz> wrote: > > > (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)... > > You're right. > > > > which surely differs from x.(y.z) due to the asymmetry. So it's not > > > associative. > > ... so symmetry is there and associative it is. > > Right. Could you give me a reference in the literature? > I'm afraid I can't. Personally, I observed the group property myself some time around 1994, when I was impressed by the "no S-boxes" concept of the IDEA block cipher, and tried to "design" something like it for 32-bit machines. The group property of 2*x*y + y + z came to me first. When I found the isomorphism to the multiplicative group of odd integers, generalization to (1<<m)*k*x*y + x + y followed easily. As an undergraduate student without formal math-phys trainings, within my (very limited) knowledge, I was not aware of such references in literature. I'm not aware of that even now, too. > > > 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. > > Right, but a non-associative function is nice e.g. as a compression > function for a non-cryptographic hash. You're right. Also in the context of cryptography, I forgot that e.g. the composition of every consecutive two rounds of the Skipjack's function G (and maybe of GOST, I think) is also a non-associative quasigroup.
From: Maaartin on 17 Jun 2010 01:21
On Jun 16, 8:47 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > I suppose you misunderstood me. Why "fixed" rotations? No, I didn't, I just forgot to read your mind. Fixed rotations are better w.r.t. some criteria. You can combine them with other operations and get what you want, too. > 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.) There's a problem with what you're doing: You get something in between, but get disadvantages of both: - You need some padding since not every plaintext length is multiple of 4. - You can use it for no other purposes blockciphers are good for. Moreover, by processing x you give the attacker more handles to fiddle with. > 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. If the attacker can generate a plaintext such that x==d, then the result is b. This means, that there may be an attack such that the security of you cipher depends on the security of b and d only. Using x ^ (a*(x>>>c)+b) instead leads to a stream cipher which doesn't exhibit this problem. On Jun 17, 5:45 am, Tran Ngoc Duong <tranngocdu...(a)gmail.com> wrote: > On Jun 16, 7:59 pm, Maaartin <grajc...(a)seznam.cz> wrote: > > Right. Could you give me a reference in the literature? > > I'm afraid I can't. Personally, I observed the group property myself > some time around 1994, when I was impressed by the "no S-boxes" > concept of the IDEA block cipher, and tried to "design" something like > it for 32-bit machines. The group property of 2*x*y + y + z came to me > first. When I found the isomorphism to the multiplicative group of odd > integers, generalization to (1<<m)*k*x*y + x + y followed easily. As > an undergraduate student without formal math-phys trainings, within my > (very limited) knowledge, I was not aware of such references in > literature. I'm not aware of that even now, too. I ask only because I thought, there can be more information there. I was impressed by IDEA, too, and I still wonder why it uses its pseudomultiplication instead of something like 2*x*y+x+y, which can be written as x + (2*x+1) * y, and executed using only 3 instructions on x86 architectures using LEA. I saw it could be inverted by working from the LSb to the MSb, which lead me immediatelly to generalizations like A*x*y op B*x op C*x, where A is even, B and C are odd, and op is + or ^. One day I'll evaluate on a dictionary how good it performs as a hash. |