algorithm - 如何在ID混淆混洗位算法中修改掩码？

在this question中，根据D.Knuth的工作，提出了一种混洗位算法，以模糊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，但是如果我修改它们，算法就会停止工作，反向（还原）也会失败。我一直在尝试XORed掩码、质数、逆掩码和相关掩码，但总是失败。
我一直试图通过阅读《计算机编程艺术》第4a卷第2卷第4.3.2章来确定算法的真知灼见，但是它们非常密集，而且通常都是对话式的，它们不关注这个例子的变体，也不详细解释这个算法的其他选项。
问题是：
为什么选择这些价值观而不是其他价值观？（mask1、mask2、d1、d2）。
选择mask1、mask2、d1、d2的值来改变洗牌，同时保持算法工作的规则是什么？（通过工作方式，对于任何自然值，模糊处理/恢复过程结束时的x=z）。

最佳答案

模糊代码实际上是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是相同的，因为同一性^和==的结合性和交换性意味着以下内容。（我假设(mask1 << d1) >> d1 == mask1的运算符优先；如果将这些方程转换为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

我认为如果d1（即mask1的高位为零）和(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（即d1的高位为零）和mask1。但说真的，只有AES加密/解密。

关于algorithm - 如何在ID混淆混洗位算法中修改掩码？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/32242156/