如何逆向实现16位线性变换加密算法并解释解密移位逻辑？

加密逻辑实现 #

加密端的16位线性变换规则为：将输入值与自身左循环移位6位、左循环移位10位的结果做按位异或，得到加密输出。
对应的Verilog实现代码：

module linear_transform_enc (
input   wire    [15:0] m,
output      [15:0] L);

wire [15:0] m6, m10;

assign m6 [15:0] = {m[9:0],m[15:10]};
assign m10[15:0] = {m[5:0],m[15:6]};

assign L = m ^ m6 ^ m10;

endmodule  

待解释的解密逻辑 #

已找到的解密模块实现逻辑为：将密文输入与自身左循环移位2位、4位、12位、14位的结果做异或得到明文，对应Verilog代码：

module linear_transform_dec(
input   wire    [15:0] L,
output      [15:0] m);

wire [15:0] L2, L4, L12, L14;

assign L2 [15:0] = {L[13:0],L[15:14]};
assign L4 [15:0] = {L[11:0],L[15:12]};
assign L12 [15:0] = {L[3:0],L[15:4]};
assign L14 [15:0] = {L[1:0],L[15:2]};

assign m = L ^ L2 ^ L4 ^ L12 ^ L14;

endmodule

解密逻辑的数学原理 #

该变换是*GF(2)域（二元域，仅包含0、1两个元素，加法对应按位异或，乘法对应按位与）*上的线性变换，可以通过算子运算直接推导逆变换：

• 记rotl_n(x)为将16位值x左循环移位n位的操作，循环移位满足结合律：rotl_a(rotl_b(x)) = rotl_((a+b) mod 16)(x)，且异或满足线性性质：rotl_n(x^y) = rotl_n(x) ^ rotl_n(y)
• 加密运算可以简写为算子形式：L = (I + rotl_6 + rotl_10)(m)，其中I是恒等算子（不对输入做任何变换），加法为按位异或
  我们需要找到对应的逆算子D，满足D(L) = m，也就是两个算子叠加后等于恒等算子：D ∘ (I + rotl_6 + rotl_10) = I。
  给出的解密逻辑对应的算子为D = I + rotl_2 + rotl_4 + rotl_12 + rotl_14，将其与加密算子做运算展开验证：

1. 按照分配律展开两个算子的乘积（算子相乘表示连续执行两个变换），得到所有移位项：
   • 恒等算子乘加密算子：m, rotl_6(m), rotl_10(m)
   • rotl_2乘加密算子：rotl_2(m), rotl_8(m), rotl_12(m)
   • rotl_4乘加密算子：rotl_4(m), rotl_10(m), rotl_14(m)
   • rotl_12乘加密算子：rotl_12(m), rotl_2(m), rotl_6(m)
   • rotl_14乘加密算子：rotl_14(m), rotl_4(m), rotl_8(m)
2. 由于GF(2)域中任意值异或自身结果为0，统计每个移位项的出现次数：
   • 原项m仅出现1次，保留
   • 移位2、4、6、8、10、12、14位的项均出现2次，全部抵消为0
     最终运算结果仅剩下原项m，完全符合逆变换的要求。
     本质上这类循环移位加异或的线性变换，都可以转化为二元多项式环上的乘法运算：左循环移位n位对应多项式乘以x^n，模x^16 + 1（因为16位循环移位，x^16等价于x0）。加密对应的多项式是1 + x^6 + x^10，计算该多项式在环上的乘法逆元，得到的结果恰好是1 + x^2 + x^4 + x^12 + x^14，对应到硬件实现就是代码中的移位异或逻辑。

内容的提问来源于stack exchange，提问作者john98