问题

在循环移位异或加密中，我们已知变换后的密文 y ，以及多个偏移的密钥 ks ，要求出原文 x

方法

首先给出定理：在长度为 2 的方幂的二进制串中，循环移位异或变换中，如果有奇数项，那么这个变换是可逆的，否则就是不可逆的

例如说，我们讨论有 3 项的情形

\[y = x \oplus (x \ggg p) \oplus (x \ggg q) \]

对于此式，我们分别相应移位 p 和 q 位

\[y \ggg p = (x \ggg p) \oplus (x \ggg 2p) \oplus (x \ggg (p + q))\\ y \ggg q = (x \ggg q) \oplus (x \ggg 2q) \oplus (x \ggg (p + q)) \]

此时我们可以利用 \(A \oplus A = 0\) 将三式相消

\[y \oplus (y \ggg p) \oplus (y \ggg q) = x \oplus (x \ggg 2p) \oplus (x \ggg 2q) \]

左式是可以求出的，记为 \(y^{(n)}\) ,而右式相当于将偏移位变为原来的两倍，从而进行多次操作

\[y^{(n)} = x \oplus (x \ggg p \times 2^n) \oplus (x \ggg q \times 2^n) \]

而对于长度为 2 的方幂的二进制串，有

\[x = x \ggg p \times 2^n\\x = x \ggg q \times 2^n \]

即

\[y^{(n)} = x \]

类似的，我们可以证明项数为奇数的任意式成立

以下给出针对此方法的破解代码

def move(n, k): 
  s = bin(n)[2:].zfill(64) 
  k &= 63 
  return int(s[k:] + s[:k], 2) 

def encrypt(x, ks): 
  return xor(x, reduce(xor, map(lambda k: move(x, k), ks))) 

def decrypt(y, ks): 
  for _ in range(6): 
    y = encrypt(y, ks) 
    ks = [k << 1 for k in ks] 
  return y

另一种方法

上面是一种直观的方法，但是不够严谨，下面介绍另一种方法：

对于 m 位二进制数 \(a = {a_{m - 1}, a_{m - 2}, ..., a_{0}}\)，对应多项式 \(a(x) = a_{m - 1}x^{m - 1} + a_{m - 2}x^{m - 2} + ... + a_{0}\)

我们定义方法 \(L(a) = (a \lll k_1) \oplus (a \lll k_2) \oplus ... \oplus (a \lll k_n)\)（右移位可以看作是左移位）

对 m 位二进制数下循环左移 k 位等价于多项式乘以 \(x^k\) 后对多项式 \(x^m + 1\) 取模，即有

\[\begin{aligned} L(a) & = x^{k_1}a(x) + x^{k_2}a(x) + ... +x^{k_n}a(x) & \bmod(x^m + 1)\\ & = (x^{k_1} + x^{k_2} + ... + x^{k_n})a(x) & \bmod(x^m + 1)\\ & = k(x)a(x) & \bmod(x^m + 1) \end{aligned} \]

对长度为 2 的方幂的二进制数，有 \(x^{2^k} + 1\) 可以完全分解为 \((x + 1)^{2^k}\) ，从而只含有 \((x + 1)\) 这一个因子，从而判断以 \(x^{2^k} + 1\) 为模的重模多项式环中元素存在逆元就变成了被判断的多项式是否有 \(x +1\) 这个因子，只需判断 \(k(1) = 0\) 与否

\[奇数项 \iff k(1) = 1 \iff 不含 x + 1 因子 \iff 有逆元\\ 偶数项 \iff k(1) = 0 \iff 含有 x + 1 因子 \iff 无逆元 \]

证毕！