4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ 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). $\endgroup$ – CodesInChaos Jul 1 '17 at 12:31
  • 1
    $\begingroup$ Related: How to break an arbitrary XOR and Rotation based encryption? $\endgroup$ – CodesInChaos Jul 1 '17 at 12:32
  • $\begingroup$ "$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. $\endgroup$ – Ruben De Smet Jul 1 '17 at 17:14
  • $\begingroup$ I took it to mean n is a nonce. $\endgroup$ – Thomas M. DuBuisson Jul 1 '17 at 17:28
  • $\begingroup$ Ok, then my answer should be alright. Give me a ping (or file an edit) if I misdid my indices... $\endgroup$ – Ruben De Smet Jul 1 '17 at 18:08
5
$\begingroup$

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}) $$

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – user47922 Jul 1 '17 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.