1
$\begingroup$

How do I solve equations like this $$(aX \oplus X+b) \bmod M = c$$

If a,b and c are known?
and if i have system of of equation with different b values, is it solvable? I am particularly interested in $M$ being a power of $2.$

$\endgroup$
2
  • $\begingroup$ It's easy if $M$ is a power of 2. I assume it's not... $\endgroup$
    – poncho
    Oct 4, 2023 at 19:06
  • $\begingroup$ lets say m = 2**128 $\endgroup$
    – Sora
    Oct 4, 2023 at 20:49

1 Answer 1

2
$\begingroup$

is it solvable?

If $M$ is a power of 2, say, $2^{128}$, then it is easily solvable.

We first recognize that, in this system, what happens to bits $0-k$ are not affected by any of the bits $k+1$ and above. That is, we can solve the system to the modulus $2^k$ and then extend that answer to higher order bits.

To be more concrete, here is what we can do:

  • Define the set of the solutions modulo $2^0$; this set consists of a single entry $X = 0$, because for any integers $x, y$, $x \equiv y \pmod 1$

  • For $k=1$ up to $128$ we consider the set of solutions modulo $2^{k-1}$

  • For each such solution, we extend $X$ by setting bit $k-1$ to 0, and see if that's a solution. If it is, we add that to the set of solutions modulo $2^k$.

  • Then, we extend $X$ by setting bit $k-1$ to 1, and see if that's a solution. If it is, we add that to the set of solutions modulo $2^k$

After we reached $k=128$, the final set will have all the solutions modulo $2^{128}$

And, yes, this process is fast

$\endgroup$
1
  • $\begingroup$ Yes. That tends to be applicable to solve for $X$ many equations $f(X)=0$ where $f$ has no right-diffusion (and $f$ does not collide too much, especially if we want all the solutions). Here, depending on how we read the question, $f(X)=((((aX)\oplus X)+b)\bmod2^b)\oplus c$, or $f(X)=(((aX)\oplus(X+b))\bmod2^b)\oplus c$ (with $b=128$). $\endgroup$
    – fgrieu
    Oct 5, 2023 at 5:48

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.