System of Boolean Equations

So we have six 32-digit sequences we want to determine, for a total of 192 unknown hexadecimal digits. We can focus on just the first digits of each to illustrate how we could try to solve for the others.

Let's call the first digits of S1, S2 and S3 a, b and c, respectively. Let's also call the first digits of C1, C2 and C3 x, y and z, respectively. Then we have the following equations, where * stands for XOR:

a * x = E     b * x = A     c * x = 7
a * y = 2     b * y = 6     c * y = B
a * z = 1     b * z = 5     c * z = 8

Let us note some properties of XOR. First, it is associative. That is, A XOR (B XOR C) is always equal to (A XOR B) XOR C. Second, it is commutative. That is, A XOR B is always equal to B XOR A. Also, A XOR A is always the "false" vector (0) for any A. A XOR FALSE is always A where FALSE stands for the "false" vector (0). These facts let us do algebra to solve for variables and substitute to solve. We can solve for c first, substitute in and simplify to get:

a * x = E     b * x = A     z * x = F
a * y = 2     b * y = 6     z * y = 3
a * z = 1     b * z = 5     c = 8 * z

We can do z next:

a * x = E     b * x = A     y * x = C
a * y = 2     b * y = 6     z = 3 * y
a * y = 2     b * y = 6     c = 8 * z

We found a couple of our equations are redundant. We expected that if the system were not inconsistent since we had nine equations in six unknowns. Let's continue with y:

a * x = E     b * x = A     y = C * x
a * x = E     b * x = A     z = 3 * y
a * x = E     b * x = A     c = 8 * z

We find now that we have even more unhelpful equations. Now we are in trouble, though: we only have five distinct equalities and six unknowns. This means that our system is underspecified and we will have multiple solutions. We can pick one or list them all. Let us continue with x:

a * b = 4     x = b * A     y = C * x
a * b = 4     x = b * A     z = 3 * y
a * b = 4     x = b * A     c = 8 * z

What this means we have one solution for every solution to the equation a * b = 4. How many solutions are there? Well, there must be 16, one for every value of a. Here is a table:

a: 0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
b: 4  5  6  7  0  1  2  3  C  D  E  F  8  9  A  B

We can fill in the rest of the table using the other equations we determined. Each row will then be a solution.

You can continue this process for each of the 32 places in the hexadecimal sequences. For each position, you will find:

1. there are multiple solutions, as we found for the first position
2. there is a unique solution, if you end up with six useful equations
3. there are no solutions, if you find one of the equations becomes a contradiction upon substitution (e.g., A = 3).

If you find a position that has no solutions, then the whole system has no solutions. Otherwise, you'll have a number of solutions that is the product of the nonzero numbers of solutions for each of the 32 positions.