- Rumor has it… » »
- « « Cipher DAGs
T-functions Testbed
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), whereais a term of {a0 = 2, ai = ai-1 + 4}x → (~x) + ax + bx, where|a-b| ≡ 4t, t = 0,1,2,3…
Subscribe to RSS feed
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.
October 26, 2007 @ 7:17 am
what i want to say is ” it only needs that (neg(x1)-neg(x2))mod2^{n-1}=0. “
October 26, 2007 @ 7:41 am
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);October 26, 2007 @ 8:12 am
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.
October 26, 2007 @ 2:43 pm
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.
October 26, 2007 @ 3:40 pm
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 :)
October 26, 2007 @ 4:19 pm
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.
October 26, 2007 @ 4:53 pm
thanks for your explanation.
what you mean is y = [a*(~x)<<b]|[a*(~x)>>(2n-b)]
Ilya wrote: Yes indeed
October 26, 2007 @ 5:50 pm
when we say rotation (x
October 26, 2007 @ 5:54 pm
another question:
the rotation operation “
October 28, 2007 @ 5:19 am
rotation “
November 5, 2007 @ 2:12 pm
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.
November 5, 2007 @ 3:10 pm
thanks!
usually,right rotation(left rotation.etc) is linear transform.
but it seems not from your explanation?
November 7, 2007 @ 5:54 pm
Rotation on its own is always a linear transformation. The abovementioned overflow bits involvement just makes it a rotation plus an extra operation.
November 11, 2007 @ 6:16 am