Need some simple bijective mappings
in [Cryptography]
|
From: Maaartin on 15 Jun 2010 06:07 On Jun 15, 11:48 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > Maaartin wrote: > > (x>>>a) ^ (x>>>b) ^ (x>>>c) > > can be written using matrix notation (over GF(2)**32) as > > (A+B+C) * x > > When you repeat the step 32 times, you get > > (A+B+C)**32 * x = (A**32 + B**32 + B**32 + 2 * (some other terms)) * x > > = 3*x = x > > since A**32 is rotation by 32*a, i.e., identity, and 2=0 in GF(2). > > > x ^ (x>>n) > > could be shown to be identity using matrices, too, but observe > > instead, that all bits can be reconstructed when going from the MSb to > > LSb. > > > x ^ (x>>m) ^ (x>>n) > > is about the same. > > I surmise from the above that the inversion may not be very simple to > do. Not really, in all three cases you need to repeat it 31 more times (at most). x ^ (x>>16) is self-inverse. x ^ (x>>10) need to be repeated only 3 more times. I forgot to say that the shifts must be unsigned (some call them quite illogically "logical"), otherwise the MSb gets lost (expect for x ^ (x>>m) ^ (x>>n) where it's fine). > BTW, a multiplication by a n*n non-singluar bit matrix gives also a > bijective mapping, but I personally consider the operation a bit > complicated. In general yes. Actually all of the above operations are special cases. One more: x ^ ((x>>m) & a) ^ ((x>>n) & b)
From: unruh on 15 Jun 2010 13:27 On 2010-06-15, Mok-Kong Shen <mok-kong.shen(a)t-online.de> wrote: > Maaartin wrote: > >> (x>>>a) ^ (x>>>b) ^ (x>>>c) >> can be written using matrix notation (over GF(2)**32) as >> (A+B+C) * x >> When you repeat the step 32 times, you get >> (A+B+C)**32 * x = (A**32 + B**32 + B**32 + 2 * (some other terms)) * x >> = 3*x = x >> since A**32 is rotation by 32*a, i.e., identity, and 2=0 in GF(2). >> >> x ^ (x>>n) >> could be shown to be identity using matrices, too, but observe >> instead, that all bits can be reconstructed when going from the MSb to >> LSb. >> >> x ^ (x>>m) ^ (x>>n) >> is about the same. > > I surmise from the above that the inversion may not be very simple to > do. > > BTW, a multiplication by a n*n non-singluar bit matrix gives also a > bijective mapping, but I personally consider the operation a bit > complicated. Since noone can read your mind to see what you consider complicated and what not, your requirements are unknown. You ask here for something or another, noone knows what or what for, and you expect reasonable answers. A bijective map is a one to one, only. It is a permutation. The number of permutations is N!. The inverse is a permutation. It is no harder of simpler than the forward direction. Now if you mean you want to create that permutation via some specific restricted set of operations, please specify. > > M. K. Shen >
From: Mok-Kong Shen on 15 Jun 2010 16:57 unruh wrote: > Since noone can read your mind to see what you consider complicated and > what not, your requirements are unknown. You ask here for something or > another, noone knows what or what for, and you expect reasonable > answers. A bijective map is a one to one, only. It is a permutation. The > number of permutations is N!. The inverse is a permutation. It is no > harder of simpler than the forward direction. Now if you mean you want > to create that permutation via some specific restricted set of > operations, please specify. Indeed you have hit on an essential vagueness of mine (for simple/complicated is akin to easy/difficult etc. etc.). On the other hand, it would also be interesting to see by how much the boundary between simple and complicated in this issue differs for different people. The intended (sorry, unstated) context is crypto computations. For me personally I tend to consider something that is commonly done by one simple hardware instruction (x>>>c, x^d) to be definitely simple and stuffs much more involved than a*x+b to be complicated. Certainly I'll also respect other's opinions in e.g. considering the arithmetic operations in GF to be simple. 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. M. K. Shen
From: Maaartin on 15 Jun 2010 17:49 On Jun 15, 10:57 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > unruh wrote: > > Since noone can read your mind to see what you consider complicated and > > what not, your requirements are unknown. You ask here for something or > > another, noone knows what or what for, and you expect reasonable > > answers. A bijective map is a one to one, only. It is a permutation. The > > number of permutations is N!. The inverse is a permutation. It is no > > harder of simpler than the forward direction. Now if you mean you want > > to create that permutation via some specific restricted set of > > operations, please specify. > > Indeed you have hit on an essential vagueness of mine (for > simple/complicated is akin to easy/difficult etc. etc.). On the other > hand, it would also be interesting to see by how much the boundary > between simple and complicated in this issue differs for different > people. The intended (sorry, unstated) context is crypto computations. > For me personally I tend to consider something that is commonly done by > one simple hardware instruction (x>>>c, x^d) to be definitely simple > and stuffs much more involved than a*x+b to be complicated. Certainly > I'll also respect other's opinions in e.g. considering the arithmetic > operations in GF to be simple. > > 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. 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
From: Tran Ngoc Duong on 15 Jun 2010 19:18
On Jun 15, 3:14 pm, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote: > I like to learn some simple to code bijective mappings of an n-bit word > x akin to the following: > > a*x + b (a odd) > > x >>> c > > x ^ c > > x ^ (x >> 1) > > Thanks in advance. > > M. K. Shen 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. Actually, it is an (abelian) group operation for any word length n. Regards, N. D. Tran |