Prev: Double encryption method
Next: File Handling in Ada -95.- Demonstartion.
From: Mok-Kong Shen on 15 Jun 2010 04:14

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
From: Maaartin on 15 Jun 2010 04:29
On Jun 15, 10:14 am, 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.

What's wrong with those listed? Now I can only give you some more:

x * (2*x + a) # a odd; more general the polynomials you wrote about
(x >>>a) ^ (x >>>b) ^ (x >>>c) # there must be three operands, not two
x ^ (x>>n) # n in 1..31 for 32-bit ints
x ^ (x>>m) ^ (x>>n) # m, n in 1..31
gfmul(n, x) # multiplication in GF(2**32) with n!=0
From: Mok-Kong Shen on 15 Jun 2010 05:17
Maaartin wrote:
> Mok-Kong Shen 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)

> What's wrong with those listed? Now I can only give you some more:

Nothing wrong. I just like to have more of them.

> x * (2*x + a) # a odd; more general the polynomials you wrote about

Right. (I omitted a mention of permutation polynomial mod 2^n in general
before posting, fearing that to be rated a bit complicated on
inversion.)

> (x>>>a) ^ (x>>>b) ^ (x>>>c) # there must be three operands, not two
> x ^ (x>>n) # n in 1..31 for 32-bit ints
> x ^ (x>>m) ^ (x>>n) # m, n in 1..31

Interesting. Could you please tell how to show the bijectivity of these?

> gfmul(n, x) # multiplication in GF(2**32) with n!=0

O.k., though I personally consider it a bit complicated.

M. K. Shen

From: Maaartin on 15 Jun 2010 05:37
On Jun 15, 11:17 am, Mok-Kong Shen <mok-kong.s...(a)t-online.de> wrote:
> Maaartin wrote:
> > What's wrong with those listed? Now I can only give you some more:
>
> Nothing wrong. I just like to have more of them.
>
> > x * (2*x + a) # a odd; more general the polynomials you wrote about
>
> Right. (I omitted a mention of permutation polynomial mod 2^n in general
> before posting, fearing that to be rated a bit complicated on
> inversion.)
>
> > (x>>>a) ^ (x>>>b) ^ (x>>>c) # there must be three operands, not two
> > x ^ (x>>n) # n in 1..31 for 32-bit ints
> > x ^ (x>>m) ^ (x>>n) # m, n in 1..31
>
> Interesting. Could you please tell how to show the bijectivity of these?

(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.

> > gfmul(n, x) # multiplication in GF(2**32) with n!=0
> O.k., though I personally consider it a bit complicated.

Sure, and not as fast as the others, but it allows to construct MDS
functions.
From: Mok-Kong Shen on 15 Jun 2010 05:48
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.

M. K. Shen

 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: Double encryption method
Next: File Handling in Ada -95.- Demonstartion.