1

I am trying to solve following formula:

$(A\ \mathrm{ror}\ 5)\ \mathrm{xor}\ A = X$

where $X$ is an unsigned 32-bit integer which is known, and $A$ is an unsigned 32-bit integer which needs to be calculated. $\mathrm{ror}$ is rotate right through carry.

When replacing $\mathrm{ror}$ with $\mathrm{shr}$ and $\mathrm{shl}$ (Shift right and left and filling with zero bits), I get

$((A\ \mathrm{shr}\ 5)\ \mathrm{or}\ (A\ \mathrm{shl}\ 27))\ \mathrm{xor}\ A = X$

But I can't find a solution for this. Is there some kind of numeric algebra which can be applied to the xor, or, shl, shr operators?

Daniel Marschall
  • 265
  • You can attempt to solve it bitwise: say $A=a_0\dots a_{31}$ and $a_0=0$, we get $a_{27}\mathop{xor} a_0=x_0$. – Berci Jun 27 '18 at 12:26

2 Answers2

2

Note that $$X\operatorname{ror} 5=(A\operatorname{ror} 5)\operatorname{xor} (A\operatorname{ror} 10) $$ so that $$(X\operatorname{ror}5)\operatorname{xor}X=(A\operatorname{ror} 10)\operatorname{xor} A$$ By repeating this, we obtain $(A\operatorname{ror} 15)\operatorname{xor} A$, $(A\operatorname{ror} 20)\operatorname{xor} A$ etc from $X$, finally $(A\operatorname{ror} 65)\operatorname{xor} A=(A\operatorname{ror} 1)\operatorname{xor} A=:Y$.

Now start with $Z=0$ and repeatedly assign $$Z\leftarrow (Z\operatorname{xor} Y)\operatorname {shl}1$$ (do this $31$ times). If the lower $k$ bits of $Z$ agree with $A$ before such a step, then $Z\operatorname{xor}Y$ has the correct lower $k$ bits of $A\operatorname{ror}1$, hence after shifting left (and resetting the lowest bit to $0$, which we assume correct), we have the correct lower $k+1$ bits of $A$.

Alternatively, start with $Z=1$ and repeatedly assign $$Z\leftarrow (Z\operatorname{xor} Y)\operatorname {shl}1\,+1$$ (do this $31$ times).

If neither of these attempts yields a solution, there is none.

Hagen von Eitzen
  • 374,180
  • Thank you for your answer! I have a few problems: (1) You write (A ror 1) xor A =: Y, and put Y into the formula (Z xor Y) shl 1. But A is the value I am searching for, so I cannot calculate Z repeatedly. (2) What is $k$ ? Am I looking for k=32 because I want all 32bits of A be correct? Would it be possible that you show a small sample calculation, e.g. to find A if X=123456789 ? – Daniel Marschall Jun 28 '18 at 08:03
0

I found a solution how to find valid values of $A$ for a given $X$.

I am not sure if it is actually the procedure described by Hagen von Eitzen.

First I split A into 32 bits $A_0$ to $A_{31}$. Then I set the first bit $A_0 = 0$ (or $1$).

Now I can calculate bit #5, then calculate bit #10, etc.: $A_{(i+5)\ \mathrm{mod}\ 32} = A_i\ \mathrm{xor}\ X_i$.

At the end, the "loop" closes at bit #27 and step #32. Then I need to look if the calculated bit 0 matches the initial value: $A_{27} \stackrel{?}{=} A_{0}\ \mathrm{xor}\ X_{27}$.

If not, then there are zero solutions (this happens in exactly 50% of all values of $X$).

Otherwise, there are always two solutions which are inverted (solution one XOR FFFFFFFF results in solution two, and vice versa). Setting the initial bit to 1 also gives the second solution.

Daniel Marschall
  • 265