I can see many xor and rotation operations in cryptography. I just want to make some algorithms fast. So, I'm looking for a way to combine between xor rotation operations. I don't know if it is possible or not.

R3(A) xor R4(B) = A * B (R3,R4 means left rotate shift by 3 bits and 4 bits)

I'm looking for *. Is there any idea? If you have please, let me know. And if it is impossible, please show me why. Thanks.

  • 4
    $\begingroup$ It seems to be asked for variations of the $*$ operation (over words of some bit size $n$) defined by $$A*B=(A\lll3)\oplus(B\lll4)$$ where $\lll$ designates left rotation, and $\oplus$ designates eXclusive-OR. We can rewrite this as $$A*B=(A\oplus(B\lll1))\lll3$$ and a number of other ways, using that $$\begin{align*} \forall X, \forall Y, \forall u,&&(X\oplus Y)\lll u &= (X\lll u)\oplus(Y\lll u)\\ \forall X, \forall u, \forall v,&&(X\lll u)\lll v &= X\lll(u+v\bmod n) \end{align*}$$ Is that what the question is about? $\endgroup$ – fgrieu May 16 '14 at 13:37
  • $\begingroup$ Thank you, fgrieu. this is exactly what i was looking for. And I also thought about this. But I actually wanted to ask about opposite directions to rotate such as (A<<<3)⊕(B>>>4). To make it simple. And I have a few questions. If you know, let me know. Is it possible to make them simple? ((A>>>3)+(B<<<4))<<<4 (+:addition mod 2^32) and (A⊕B+C⊕D)⊕E. Thank you so much for your answer anyways $\endgroup$ – user140018 May 17 '14 at 8:07

The question asks for simple variations of the $*$ operations defined by formulas similar to $A*B=(A\lll3)\oplus(B\lll4)$ or $A*B=(A\lll3)\oplus(B\ggg4)$, where uppercase letters are words of $n=32$ bits, lowercase letters are integers, $\lll$ designates left rotation, $\ggg$ designates right rotation, $\oplus$ designates eXclusive-OR.

There are a number of properties we can use: $$\begin{align*} \forall X, \forall Y, &&X\oplus Y &=Y\oplus X\\ \forall X, \forall Y, \forall Z,&&(X\oplus Y)\oplus Z&=X\oplus(Y\oplus Z)\\ \forall X, \forall Y, \forall u,&&(X\oplus Y)\lll u &= (X\lll u)\oplus(Y\lll u)\\ \forall X, \forall u, \forall v,&&(X\lll u)\lll v &= X\lll((u+v)\bmod n)\\ \forall X, \forall u, &&X\ggg u &= X\lll((-u)\bmod n) \end{align*}$$ where $a\bmod n$ is defined to be the $r$ such that $0\le r<n$ and $n$ divides $a-r$.

It follows that $$\begin{align*} (A\lll3)\oplus(B\lll4)&=(A\oplus (B\lll1))\lll3\\ &=((B\lll1)\oplus A)\lll3\\ &=((A\ggg1)\oplus B)\lll4 \end{align*}$$ which can be considered a simplification (in particular, absent a smart compiler, some of these alternate forms will likely be faster on 8-bit CPUs, and 32-bit CPUs lacking a barrel shifter)

Similarly we can write $$\begin{align*} (A\lll3)\oplus(B\ggg4)&=((B\ggg7)\oplus A)\lll3\\ &=(A\oplus (B\ggg7))\lll3\\ &=((A\lll7)\oplus B)\ggg4\\ &=(((A\lll8)\ggg1)\oplus B)\ggg4 \end{align*}$$ with the last form geared for 8-bit CPUs, where rotation by multiples of 8 is relatively efficient.

There's no way to simplify $((A\ggg3)\boxplus(B\lll4))\lll4$, or $((A\oplus B)\boxplus(C\oplus D))\oplus E$, where $\boxplus$ is addition modulo $2^n$. Problem is, we have no simple exact properties of $\boxplus$ with respect to $\lll$, $\ggg$, and $\oplus$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.