T-functions Testbed

2007 October 23
by Ilya

During last year I’ve seen few submission papers that are based on my note about singe cycle functions. The latest such paper puzzled me. The authors have reconstructed theory quite well but at some point have jumped surprisingly to a premature and wrong conclusion. To make things simpler, I’ve sketched a small online tool to test functions. Write a function as a JavaScript subroutine, click on Evaluate button and if all mapping values are ‘1’ then the function is a single cycle and invertible. As simple as that.

Since I’m already on the subject here, I’d like to explain a bit more about the function x → (a(~x)) <<< b . Probably I was too harsh in dissemblance :) Overflow bits from multiplication do matter. It is easier to see when rotation replaced with
((x << b)|(x >> (2n-b))). If x = ((a(~x)) % 2n) then period is 2n-1 and the function is not invertible indeed. It is invertible without such mod.

upd: Here are couple more functions as a bonus :)

  • x → ax + (~x),  where a is a term of {a0 = 2, ai = ai-1 + 4}
  • x → (~x) + ax + bx,  where |a-b| ≡ 4t, t = 0,1,2,3…
Reddit this / Add to del.icio.us / Digg this!

from → crypto, paper, source code

14 Comments leave one →
2007 October 26
helin permalink

Both neg(x) and rot(x,k) are invertible functions modular 2^n, but a*x modular 2^n is invertible only when a is an odd integer, if for an even integer a such that a*(neg(x1)-neg(x2))mod2^n is invertible , it only needs that (neg(x1)-neg(x2))mod2^{n-1}. This is my opinion.

2007 October 26
helin permalink

what i want to say is ” it only needs that (neg(x1)-neg(x2))mod2^{n-1}=0. “

2007 October 26
Ilya permalink

Helin, you are right when it is about a*x mod 2^n. But it is not.

Just test these samples and check the results:
1. x=6*neg(x); x=(x< <7)|(x>>1);
2. x=6*neg(x) % 256; x=(x< <7)|(x>>1);

2007 October 26
helin permalink

What was said in the original paper “On Single Cycle Functions” is “In [1], Klimov and Shamir described the nonlinear invertible function with a single cycle which
requires only three primitive operations x® x + (x2 Ú C), where C = *..*1*12. Here we introduce
a few more functions of same properties. All functions are mod 2^n.”

this is contradict with what you said above.

2007 October 26
Ilya permalink

All referenced functions are single cycle and invertible. There is no any contradiction. And your claim about a(~x)<<<b is invertible iif an odd a is regardlessly wrong.

2007 October 26
helin permalink

we are both right under the assumption of ourown.

i am misleaded by “All functions are mod 2^n” in the original paper, and the explanation above is “without mod operation”. this leads to our discussion.

maybe i misunderstood you :)

2007 October 26
Ilya permalink

Yep, a misunderstanding :)

But note the results of
x=6*neg(x); x=(x<<7)|(x>>1); x %= 256;
:)

A function in the testbed is mod 28 by default.

2007 October 26
helin permalink

thanks for your explanation.

what you mean is y = [a*(~x)<<b]|[a*(~x)>>(2n-b)]

Ilya wrote: Yes indeed

2007 October 26
helin permalink

when we say rotation (x

2007 October 28
helin permalink

another question:

the rotation operation “

2007 November 5
helin permalink

rotation “

2007 November 5
Ilya permalink

Helin, your questions are broken because of html tags sanitation. I cannot see them to reply. Please do not use plain > and < as is while posting.

2007 November 7
helin permalink

thanks!

usually,right rotation(left rotation.etc) is linear transform.

but it seems not from your explanation?

2007 November 11
Ilya permalink

Rotation on its own is always a linear transformation. The abovementioned overflow bits involvement just makes it a rotation plus an extra operation.

Leave A Comment

Note: You can use basic XHTML in your comments. Your email address will never be published.

Subscribe to this comment feed via RSS