Solving bitwise XOR and ADD equation

1.5k views Asked by At

Naturally XOR can be used twice to get back the original value. What if the original value is part of the mask?

Encoding:

e[i] = c[i] ^ (c[i] + c[i-1])

Assuming: starting value c[-1] = 0, ^ means bitwise XOR

In imperative C form:

void encode(byte *p, int len)
{
    byte prev = 0;
    for (auto i = 0; i < len; i++)
    {
        auto byt = p[i];
        p[i] = byt ^ (prev + byt);
        prev = byt;
    }
}

How do I create a decode step that reverses this from e => c?

I've simplified/clarified (read: changed) the question given what I've learned from your answers! Using similar steps to DanL, starting with the original equation:

e[i] = c[i] ^ (c[i] + c[i-1])

e[i] ^ c[i] = c[i] ^ (c[i] + c[i-1]) ^ c[i]
e[i] ^ c[i] = c[i] + c[i-1]
c[i] = e[i] ^ c[i] - c[i-1]
c[i] ^ c[i] = (e[i] ^ c[i] - c[i-1]) ^ c[i]
0 = e[i] ^ c[i] ^ c[i] - c[i-1] ^ c[i]
0 = e[i] - c[i-1] ^ c[i]
c[i-1] ^ c[i] = e[i]
c[i-1] ^ c[i] ^ c[i-1] = e[i] ^ c[i-1]
c[i] = e[i] ^ c[i-1]

???

Now, looking at the original encode - the first byte will always be zero (= c[i] ^ (c[i] + 0)). So yes, there must be a loss of one byte over the set.

1

There are 1 answers

1
DanL On BEST ANSWER

In each iteration of the loop you are effectively calculating

c_i = e ^ ( p + c_(i-1) )

If you wish to reverse the loop then given a c_i you need to calculate c_(i-1)

However as you said xoring twice gets you back to the original value and xor is a commutative operation so if you xor the above equation by e we then get

c_i ^ e = e ^ ( p + c_(i-1) ) ^ e

which simplifies to

c_i ^ e = p + c_(i-1)

then take away p from both sides to give you

(c_i ^ e) - p = c_(i-1)

Therefore in your "reversal" loop

you want the code

c = (c ^ e) - p

Edit: After seeing the revised question with code in context I don't believe this is possible as I believe the mix function is effectively mapping a len byte array onto a len-1 byte array.

I believe this because of the following argument:

Let the unmixed array be called unmixed and the mixed array after applying the mix function be called mixed

mixed[0] = unmixed[0] ^ (0 + unmixed[0])  //Remember prev = 0 initially

therefore mixed[0] = unmixed[0] ^ unmixed[0] = 0

so the first byte of the mixed array will always be 0.

The mix function doesn't increase or decrease the size of the array so we end up with a len byte array with the first element being 0.

We have therefore effectively mapped the space of len byte arrays onto len-1 byte arrays.

If this was perfectly reversible, we would be able to compress a n byte array to a n-1 byte array and then compress that n-1 byte array to a n - 2 byte array and so on.

If we use a one byte array as an example then we see mix just produces an array with a single element of 0, how do you know which of the 256 possible unmixed arrays it was before hand?