Find the numbers by XoR

84 Views Asked by At

I have 6 numbers M1, M2 and M3 and E1, E2 and E3 such that

M1 xor M2 = E1 xor E2

M2 xor M3 = E2 xor E3

M3 xor M1 = E3 xor E1

If M1, M2 and M3 are not equal to E1, E2 and E3 respectively, then given M1, M2 and M3 is it possible to find E1 E2 and E3?

1

There are 1 best solutions below

0
On

Imagine, as example, that $M_1=1$, $M_2=2$ and $M_3=4$.

$$\begin{aligned} 1 \oplus 2 &= 3 = 011_2 = E_1 \oplus E_2\\ 2 \oplus 4 &= 6 = 110_2 = E_2 \oplus E_3\\ 4 \oplus 1 &= 5 = 101_2 = E_3 \oplus E_1 \end{aligned}$$

Now, we guess a value for $E_1$ and select $E_2$ such that their two least significant bits are different and the remaining bits are equal.

$$\begin{aligned} E_1 &= E_2 \oplus 3 = 27 = 11011_2 \\ E_2 &= E_1 \oplus 3 = 24 = 11000_2 \end{aligned}$$

We can now derive $E_3$ in two ways:

$$\begin{aligned} E_2 &= E_1 \oplus 5 = 11011_2 \oplus 00101_2 = 11110_2 = 30 \\ E_3 &= E_2 \oplus 6 = 11000_2 \oplus 00110_2 = 11110_2 = 30 \\ \end{aligned}$$

Let's try a second guess.

$$\begin{aligned} E_1 &= E_2 \oplus 3 = 17 = 10001_2 \\ E_2 &= E_1 \oplus 3 = 18 = 10010_2 \end{aligned}$$

Again, we can now derive $E_3$ in two ways:

$$\begin{aligned} E_2 &= E_1 \oplus 5 = 10001_2 \oplus 00101_2 = 10100_2 = 20 \\ E_3 &= E_2 \oplus 6 = 10010_2 \oplus 00110_2 = 10100_2 = 20 \\ \end{aligned}$$

The examples demonstrate that there is no unique solution. One of the three variables can be freely selected. The other two variables are determined by the choice for the first variable.


Looking at it in gernal terms, we can calculate $E_2$ from $E_1$:

$$E_2 = E_1 \oplus M_1 \oplus M_2$$

We also calculate $E_3$ from $E_2$

$$E_3 = E_2 \oplus M_2 \oplus M_3$$

We insert the last equation to calculate $E_3 \oplus E_1$:

$$E_3 \oplus E_1 = E_2 \oplus M_2 \oplus M_3 \oplus E_1$$

Inserting for $E_2$ leads us to:

$$E_3 \oplus E_1 = E_1 \oplus M_1 \oplus M_2 \oplus M_2 \oplus M_3 \oplus E_1$$

Making use of the fact that $X \oplus X = 0$ we get:

$$E_3 \oplus E_1 = M_1 \oplus M_3$$

This is the third of the original equations. It shows that we can select an arbitrary value for $E_1$ and calculate the other two variables $E_2$ and $E_3$ from it.