## All is not lost : right bitwise shifts

A friend forwarded me this blog post, it was inspiring:

https://krypt05.blogspot.in/2015/10/reversing-shift-xor-operation.html

It got me thinking about some strange properties that exist in binary arithmetic

This equation

where the shift amount **y** is known and the result **z** is also known. doesn’t have a unique solution, as the right-hand shift loses data.

However this equation:

where the shift amount **y** is known and the result **z** is also known.

Has a unique solution.

**Pseudo-reasoning**

let’s change our x to be an array of bits, as that’s what it really is.

what we can reason about this here is that \(x_{0..n} >> y\) when xor’d with \(x_{0..n}\) we’re actually solving **n** simple simultaneous equations of the form

but if the x subscript is less than zero, x is just zero. So we actually have **y** degrees of freedom in this simultaneous system, hence it is solvable via a chain substitution.

**A 4 bit unsigned example**

ok, so now to write this out in pseudo-binary-goofy-stupid-me-notation:

Simplifying to

now we can see that the following equations need to be satisfied

Checking the solution for b1010 aka 10 decimal

**Why is that important?**

From a security perspective, we must be careful to avoid mistakes like xoring a shift with itself, as it converts the desired surjection into a bijection, aka we lose our many-to-one.