3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Welcome to Cryptography, here, on Math related SE sites, CS related site, etc, there is $LaTeX/MathJax$ available. $\endgroup$ – kelalaka Feb 8 '20 at 19:27
  • $\begingroup$ Could you provide the origin of the question? $\endgroup$ – kelalaka Feb 8 '20 at 19:28
  • 1
    $\begingroup$ 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. $\endgroup$ – kelalaka Feb 8 '20 at 19:34
5
$\begingroup$

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)

$\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.