如何修改id混淆混洗位算法中的掩码？

Question

在 this question 中，根据 D. Knuth 的作品提出了一种 Shuffle Bits 算法，以混淆 id。代码是：

// *** Shuffle bits (method used here is described in D.Knuth's vol.4a chapter 7.1.3)
const unsigned mask1 = 0x00550055; const unsigned d1 = 7;
const unsigned mask2 = 0x0000cccc; const unsigned d2 = 14;

// Obfuscate
unsigned t = (x ^ (x >> d1)) & mask1;
unsigned u = x ^ t ^ (t << d1);
t = (u ^ (u  >> d2)) & mask2;
y = u ^ t ^ (t << d2);

// Restore
t = (y ^ (y >> d2)) & mask2;
u = y ^ t ^ (t << d2);
t = (u ^ (u >> d1)) & mask1;
z = u ^ t ^ (t << d1);

该算法已经过测试，如果运行不做任何更改，它可以完美运行。

我想修改它打乱位的方式，并且我一直在对 mask1、mask2、d1 和 d2 进行更改，但如果我更改它们，算法将停止工作并且反向（恢复）失败。我一直在尝试异或掩码、素数、逆和相关掩码，但总是失败。

我一直在尝试通过阅读 计算机编程艺术 vol.4a 中的章节来确定算法的见解，也是 Vol.4a。 2，第 4.3.2 章，但它们非常密集并且笼统地谈论，他们没有关注这个例子的变体，也没有特别详细解释这个算法的其他选项。

问题是：

为什么选择这些值而不选择其他值？（掩码 1、掩码 2、d1、d2）。

选择 mask1、mask2、d1、d2 的值以改变随机播放同时保持算法正常运行的规则是什么？ （通过工作意味着 x=z 在 obfuscation/restoration 过程结束时总是，对于任何自然值）。

Answer 1

混淆码实际为obfuscate1; obfuscate2;，恢复码实际为restore2; restore1;。可以任意嵌套这些步骤。

我们只看第一步。

// Obfuscate
unsigned t = (x ^ (x >> d1)) & mask1;
unsigned u = x ^ t ^ (t << d1);
// Restore
t = (u ^ (u >> d1)) & mask1;
z = u ^ t ^ (t << d1);

其实是同一个步骤，先应用到x，再应用到u。关键是 t 两次都相同，因为恒等式 a ^ b ^ b == a 连同 ^ 的结合律和交换律暗示了以下内容。（我将假定 == 的合理运算符优先级；如果将这些方程式转换为 C 语言，您将需要更多括号。）

z == u ^ t ^ (t << d1)
  == x ^ t ^ (t << d1) ^ t ^ (t << d1)
  == x ^ t ^ t ^ (t << d1) ^ (t << d1)
  == x ^ (t << d1) ^ (t << d1)
  == x

我声称如果 (mask1 << d1) >> d1 == mask1（即 mask1 的高 d1 位为零）和 (mask1 & (mask1 << d1)) == 0 就足够了。这是一些代数，我将 ^ 操作推到 u 的表达式树的根部，代价是破坏表达式。

t == (x ^ (x >> d1)) & mask1
  == (x & mask1) ^ ((x >> d1) & mask1)
t << d1 == ((x & mask1) ^ ((x >> d1) & mask1)) << d1
        == ((x & mask1) << d1) ^ (((x >> d1) & mask1) << d1)
u == x ^
     (x & mask1) ^
     ((x >> d1) & mask1) ^
     ((x & mask1) << d1) ^
     (((x >> d1) & mask1) << d1)

让我们对 t 的第二个表达式执行相同的操作（但中间步骤更稀疏），我将其称为 t'，因为尚未证明它等于 t还。

t' == (u ^ (u >> d1)) & mask1
   == (x & mask1) ^                                  // 0.
      ((x & mask1) & mask1) ^                        // 1.
      (((x >> d1) & mask1) & mask1) ^                // 2.
      (((x & mask1) << d1) & mask1) ^                // 3.
      ((((x >> d1) & mask1) << d1) & mask1) ^        // 4.
      (((x >> d1) & mask1) & mask1) ^                // 5.
      (((x & mask1) >> d1) & mask1) ^                // 6.
      ((((x >> d1) & mask1) >> d1) & mask1) ^        // 7.
      ((((x & mask1) << d1) >> d1) & mask1) ^        // 8.
      (((((x >> d1) & mask1) << d1) >> d1) & mask1)  // 9.

第二次屏蔽没有效果。

t' == (x & mask1) ^                                  // 0.
      (x & mask1) ^                                  // 1a.
      ((x >> d1) & mask1) ^                          // 2a.
      (((x & mask1) << d1) & mask1) ^                // 3.
      ((((x >> d1) & mask1) << d1) & mask1) ^        // 4.
      ((x >> d1) & mask1) ^                          // 5a.
      (((x & mask1) >> d1) & mask1) ^                // 6.
      ((((x >> d1) & mask1) >> d1) & mask1) ^        // 7.
      ((((x & mask1) << d1) >> d1) & mask1) ^        // 8.
      (((((x >> d1) & mask1) << d1) >> d1) & mask1)  // 9.

消除0和1a，以及2a和5a，它们相互抵消。

t' == (((x & mask1) << d1) & mask1) ^                // 3.
      ((((x >> d1) & mask1) << d1) & mask1) ^        // 4.
      (((x & mask1) >> d1) & mask1) ^                // 6.
      ((((x >> d1) & mask1) >> d1) & mask1) ^        // 7.
      ((((x & mask1) << d1) >> d1) & mask1) ^        // 8.
      (((((x >> d1) & mask1) << d1) >> d1) & mask1)  // 9.

自 (mask1 << d1) >> d1 == mask1 以来，屏蔽后左右移动是多余的。

t' == (((x & mask1) << d1) & mask1) ^          // 3.
      ((((x >> d1) & mask1) << d1) & mask1) ^  // 4.
      (((x & mask1) >> d1) & mask1) ^          // 6.
      ((((x >> d1) & mask1) >> d1) & mask1) ^  // 7.
      (x & mask1) ^                            // 8b.
      ((x >> d1) & mask1)                      // 9b.

恒等式 (mask1 & (mask1 << d1)) == 0 可以右移表示 (mask1 & (mask1 >> d1)) == 0。这意味着（乏味地）6、7、8b 和 9b 都是零，留下以下内容。

t' == (x & mask1) ^                            // 8b.
      ((x >> d1) & mask1)                      // 9b.
   == t

tl;博士

(mask1 << d1) >> d1 == mask1（即 mask1 的高 d1 位为零）和 (mask1 & (mask1 << d1)) == 0。但说真的，只是 AES encrypt/decrypt 而不是。

如何修改id混淆混洗位算法中的掩码？

How to modify masks in id obfuscation shuffle bits algorithm?

algorithm

encryption

binary

bit-manipulation

tl;博士