# Solving a system of equations using both arithmetic and bitwise operations

At first I asked this question on Stackoverflow, where I was advised to ask here. So there is the question:

I have a system of pretty simple equations:

1. $$x + y = A$$
2. $$f(x,y) + y = B$$

$$A, B$$ are known. All of the variables are 64-bit positive integers, including $$f(x,y)$$.

But the problem is that $$f(x,y)$$ uses bitwise operations:

$$f(x,y) = x \oplus (x \ll 3) \oplus y \oplus (y \gg 14)$$

I tried to solve this by representing arithmetic addition with bitwise opperations and carry-bits. I also tried to represent each bit as a boolean value and then solve a system of boolean equations. I didn't succeed any much. So is there any method of doing this properly?

• Welcome to Cryptography, here, on Math related SE sites, CS related site, etc, there is $LaTeX/MathJax$ available. Feb 8, 2020 at 19:27
• Could you provide the origin of the question? Feb 8, 2020 at 19:28
• Hint: assume you know least significant half of $y$. Then, clearly, you know half of the $x$ by the first equation. You will get information about 14 more bits of $y$ by the second equation. Don't be sure about that it is solvable and uniquely solvable. Feb 8, 2020 at 19:34

So is there any method of doing this properly?

Here's the most obvious method:

• Iterate through the lower 14 bits of $$y$$, that is, you'll perform the below steps for each of the 16384 possible settings of the lower bits of $$y$$

• Compute what the lower 14 bits of $$x$$ are, using $$x = A - y$$ (because the subtraction is modulo $$2^{64}$$, we can ignore everything higher than bit 13)

• Compute what the next 14 bits of $$y$$ must be, using $$y >> 14 = (B - y) \oplus x \oplus (x << 3) \oplus y$$

• Compute what the next 14 bits of $$x$$ are, using $$x = A - y$$ (only this time, because we know 28 bits of $$y$$, we can reconstruct 28 bits of $$x$$)

• Compute what the next 28 bits of $$y$$ must be...

• Keep on doing this until we start predicting bits of $$y$$ above 63; because the right shift shifts in 0's, the prediction must be that they are all 0 (and if it predicts something else, we can reject the original guess of the lower 14 bits of $$y$$).

This involves iterating through 16384 different possibilities; a tad tedious by hand, but fairly trivial for a computer program...

I threw together a quick C routine to do the above search:

typedef unsigned long long num;
void solve_it(num a, num b) {
unsigned lower_14_y;

for (lower_14_y = 0; lower_14_y < (1<<14); lower_14_y++) {
num y, x, upper_y = 0;
int i;

for (i=1;; i++) {
y = (upper_y << 14) + lower_14_y;
/* Lower i*14 bits of y are accurate */
x = a - y;
/* Lower i*14 bits of x are accurate */

if (14*i >= 64) break;  /* Got all the bits */
upper_y = (b - y) ^ x ^ (x << 3) ^ y;
}

if (b != y + (x ^ (x << 3) ^ y ^ (y>>14))) {
continue;
}
printf( "Found solution %llx, %llx\n", x, y );
}
}


On my machine, it takes 80usec to run, and as kelalaka suspected, sometimes there aren't any solutions, and sometimes there are multiple (e.g. for a = 0x6c, b = 0xee, there are 7 solutions)