6
$\begingroup$

I was recently introduced to XOR and other bitwise operators while reading up some articles on C++. The concept seems rather simple but can be confusing because it involves visualizing numbers in binary. I ran into an equation that involves XOR sometime while I was looking up some real-world examples people use for encryption.

I was baffled at the equation, and wanted to learn how to solve it.

Here is the equation:

$y = (x * (i+A)+B) \oplus (x*i+C)$

I am trying to solve for x in the equation, with all other variables being known at the time of the solve. Variables A, B, and C remain constant at all times, with y, x, and i changing. This can simplify the equation to:

$y = (x * (i+32757935)-29408451) \oplus (x*i-5512095)$

I would like to learn how to solve this equation for x, and many others similar to this in the future as well. As such, I want to have some pointers on how to solve it. I remember reading up that splitting the equation into a system of linear equations in modulo 2 is the way to go, but I do not know how to do that. I've read up about the rules about XOR and such, but I'm not sure how I should go about creating a system, and solving it.

Note:

  • All variables are unsigned 32-bit integers
  • $\oplus$ is the XOR operation
$\endgroup$
4
$\begingroup$

For reasons that @JohnWaylandBales pointed out, you're unlikely to find a closed form for $x$ in terms of your other variables. The recursion approach suggested in that answer is interesting, but it's also not clear why such an approach should work (and I suspect in many cases, it will not; for instance, probably for most values of $x_n$, the RHS will not be an integer).

We could still hope for a simple and efficient method/algorithm to solve for $x$ given the values of the other variables. This is slightly confounded by the issue that there might be multiple (or even infinitely many) values of $x$ which satisfy your equation. Even worse, even if we restrict looking at $x$ of a certain size (e.g. 32-bit $x$), there still may be exponentially many possible $x$ (a fun example to think about is the equation $x \oplus 2x = 3x$).

I don't know of any provably efficient method to find such an $x$, nor do I know any result that says it is hard (perhaps there is some way to embed an NP-complete problem into equations of this form). That said, here is a heuristic approach which will definitely find all $B$-bit solutions $x$ to your equation, and possibly spend much less time than the brute force solution.

The trick is to notice that both operators $+$ and $\oplus$ satisfy the following property for any positive integer $k$:

$$((a \bmod 2^{k}) + (b \bmod 2^{k})) \bmod 2^{k} = (a+b) \bmod 2^{k}$$

$$((a \bmod 2^{k}) \oplus (b \bmod 2^{k})) = (a\oplus b) \bmod 2^{k}$$

This lets us build up a solution to your equation, starting modulo 2, then progressing modulo 4, modulo 8, until finally we have solutions modulo $2^{B}$ (which correspond to $B$-bit solutions). For example, let's look at the equation

$$(2x+5)\oplus(3x+4) = 56 $$

We'll try to find all 6-bit solutions $x$ to this equation (i.e. all $x \in [0, 63]$ that satisfy this equation).

We begin by looking modulo 2. Modulo 2 $\oplus$ is just $+$, so our equation reduces to

$$(2x + 5) + (3x + 4) \equiv 62 \bmod 2$$

or equivalently

$$x + 1 \equiv 0 \bmod 2$$

It follows from this that any solution $x$ must be odd, i.e. $x \equiv 1 \bmod 2$. Proceeding modulo $4$, we have that $x$ must satisfy (modulo 4):

$$(2x + 1) \oplus 3x = 2$$

We know $x$ is odd, so there are two values to try mod 4, namely $1$ and $3$. We find that $1$ does not work ($3 \oplus 3 = 0$) but $3$ does ($7 \oplus 9 = 14 \equiv 2 \bmod 4$). So now we know that $x$ is $3$ mod $4$.

Trying both $x=3$ and $x=7$, we find that $x$ must be $3$ mod $8$. Continuing, we find that $x$ must be $11$ mod $16$, $11$ mod $32$, and $11$ mod $64$; so the only possible $x$ in our range that can work is $x=11$, and we can check that it does in fact work.

This procedure seems to work quite well in most cases; at each step you usually only have to check $2$ possible values modulo $2^k$. Of course, there are cases where both solutions mod $2^{k}$ will work, and this can lead to exponential branching. For example, $x \oplus x = 0$ inevitably leads to exponential branching, since every $x$ is a solution. More subtly, things like $(64x + 1) \oplus (192x + 2) = 3$ will also lead to a lot of branching even though the only solution is $x=0$, because this equation reduces to $1 \oplus 2 = 3$ modulo $2^k$ for $k$ up to $6$. I think it might be possible to prove some general characterization of when it does work, in terms of powers of $2$ dividing $i$, $A$, and $i+A$, but I haven't been able to work it out yet.

Hopefully this helps!

$\endgroup$
  • $\begingroup$ I don't follow the claim that $((a \bmod 2^{k}) \oplus (b \bmod 2^{k})) = (a+b) \bmod 2^{k}$. Let $a=23,\,b=17,\,k=3$. Then it is claimed that $(23\bmod 8)\oplus (17\bmod 8)=40\bmod 8$, that is, $7\oplus1=0$. But in fact $7\oplus1=6.$ If you replace $(a+b)\bmod8$ with $(a\oplus b)\bmod8$ it still does not work because $(23\oplus17)\bmod8=10\bmod8=2$. $\endgroup$ – John Wayland Bales Jul 9 '17 at 22:33
  • $\begingroup$ You're right that that's a typo; it is supposed to be $a\oplus b$ on the right. I believe with this correction the statement is correct. I think your counterexample is wrong; I have that $23 \oplus 17 = 6$. $\endgroup$ – jschnei Jul 10 '17 at 0:08
  • $\begingroup$ (It's also quite straightforward to prove that it is correct under the change, since modding by $2^k$ corresponds to just taking the last $k$ bits). $\endgroup$ – jschnei Jul 10 '17 at 0:11
  • $\begingroup$ You're correct, $23\oplus17=6$. My mistake. $\endgroup$ – John Wayland Bales Jul 10 '17 at 0:14
2
$\begingroup$

We know that

  1. $A\oplus B=B\oplus A$
  2. $A\oplus(B\oplus C)=(A\oplus B)\oplus C$
  3. $A\oplus A=0$
  4. $A\oplus 0=A$

However, what are lacking are rules for dealing with

  1. $A\oplus(B+C)$
  2. $A\oplus(B*C)$

We can manipulate the equation as follows:

\begin{eqnarray} y &=& (x * (i+A)+B) \oplus (x*i+C)\\ y\oplus (x*i+C) &=& x * (i+A)+B\\ y\oplus (x*i+C)-B &=& x * (i+A)\\ x&=&\frac{y\oplus (x*i+C)-B}{i+A} \end{eqnarray}

This opens the possibility of using a recursion which hopefully converges to a solution for $x$:

\begin{equation} x_{n+1}=\frac{y\oplus (x_n*i+C)-B}{i+A} \end{equation}

$\endgroup$

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.