So, far my understanding was Modular addition is non linear function which is mainly used in ARX based ciphers.

While I was glancing through RC5 paper (https://link.springer.com/content/pdf/10.1007/3-540-60590-8_7.pdf) the author has mentioned that the only non-linear operation is "data dependent left-rotation", even though it has modulo 2^n addition.

In the given paper, the author, has not mentioned about finite field details, so it is assumed that the addition operation is happening on n-bit register.

I am attaching the image for the reference and also note the last 3 lines.

enter image description here


1 Answer 1


Consider $f: x\mapsto f(x)=\underbrace{x+x\ldots x}_{a\text{ times}}+b\bmod 2^{32}$ in the the ring $(\mathbb Z_{2^{32}},+,\times)$, where $a$ and $b$ are constants.

Per one meaning, $f$ is linear, that is of the form $x\mapsto a\times x+b$, for constants $a$ and $b$. Per another meaning, $f$ is not (in general) a linear boolean function. $f$ is also not linear in the field $(\mathbb F_{2^{32}},\oplus,\otimes)$, where $\otimes$ is polynomial multiplication modulo an irreducible polynomial of degree $32$.

To make «the rotations are the only non-linear operator in RC5» true, we can craft a meaning of «linear» that allows any of the above definitions.

Without rotations, RC5 would be trivially breakable no matter the number of rounds, for lack of propagation from high-order to low-order bits of the four 32-bit sub-blocks.

It's harder to prove the (true) assertion that with only fixed rotations, and baring much more rounds, RC5 would be breakable. That's because it would be too linear, in some sense that I fail to exactly define.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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