# Reversing decryption function involving XORs and bit rotations?

I am trying to reverse this equation to find the encrypted number given to it. Here is the equation:

$$y = x \oplus n \oplus (x \ggg 3) \oplus (x \lll 7)$$

$\oplus$ is the bitwise exclusive or function
$a \lll b$ is $a$ bit rotated left by $b$ bits
$a \ggg b$ is $a$ bit rotated right by $b$ bits

$y$ is a known 32 bit integer
$n$ is a known 32 bit integer but unique for every $x$ and $y$
$x$ is the encrypted message and what I want to solve for, and it is an unknown 32 bit integer

• You can trivially eliminate $n$. After that you have 32 linear equations modulo 2 and 32 unknowns. Apply standard techniques for solving a system of linear equations, or if you're lazy brute-force it (should only take a couple of seconds). Jul 1, 2017 at 12:31
• Jul 1, 2017 at 12:32
• "$n$ is a known 32 bit integer but unique for every $x$ and $y$"; is $n$ a function of $x$, $y$, or both? If the latter, the system is under determined afaict. Jul 1, 2017 at 17:14
• I took it to mean n is a nonce. Jul 1, 2017 at 17:28
• Ok, then my answer should be alright. Give me a ping (or file an edit) if I misdid my indices... Jul 1, 2017 at 18:08

I'll demonstrate a "brute" way of doing it; should work for any XOR-rot system. Please note that indices are $\bmod 32$.

You basically write your equation in 32-vector and matrix notation:

$$\bar{y} = M\bar{x} \oplus \bar{n},$$ or in Einstein notation (which, in my opinion, can make stuff more readable) $$y_i=M_{ij}x^j \oplus n_i,$$ where the sum goes from $i=1\dots32$.

Now, the magic part (to solve the rotation) lies in finding the $32\times32$ matrix $M_{ij}$:

$$M_{ij}=\delta_{ij}\oplus\delta_{(i+3),j}\oplus\delta_{(i-7),j},$$ where $\delta_{ij}$ is the Kronecker delta symbol (the unit matrix):

$$\delta_{ij} = \begin{cases} 1, & \text{if } i=j,\\ 0, & \text{if } i\neq j. \end{cases}$$ Now your problem is reduced to inverting $M_{ij}$ (which is a one-time static thing), and calculating

$$\bar{x}=M^{-1}(\bar{y}+\bar{n})$$

• I added a link about the Einstein summation convention as well as an inline definition of the Kronecker delta. Hope you don't mind! Also, \bmod is better with the spacing when you type \mod 32.
– user47922
Jul 1, 2017 at 22:18