这个反向工程算法是如何工作的？

Question

实际算法函数为：

output[i] = ( (129 * input[i]) XOR input[i-1]) % 256 //input[-1] = 0

有几种解决方案。通常采用的方案是：

var output = [0, 129, 3, 129, 7, 129, 3, 129, 15, 129, 3, 129, 7, 129, 3, 129];
var outputToInputArray = function(array) {
  var input = [];
  var outputToInput = function(dig, lastInput) {
    var current = dig;

    while(true) {
      if (!((current ^ lastInput) % 129)) {
        return (current ^ lastInput)/129;
      }
      current += 256;
    }
  }

  for(var i = 0; i < output.length; i++) {
    input.push(outputToInput(output[i], i>0 ? input[i-1] : 0));
  }

  return input;
}

console.log(outputToInputArray(output));

然而，我刚刚遇到了以下问题：

output = [0, 129, 3, 129, 7, 129, 3, 129, 15, 129, 3, 129, 7, 129, 3, 129]
var input = [];
for(var i =0; i < output.length; i++) {
    lastInput = input.length < 1 ? 0 : input[i-1];
    input.push(((output[i] ^ lastInput) * 129) % 256);
}
console.log(input);

当被要求反转一个函数时，遵循的思路是代数上反转该函数。然而，第二个解决方案似乎以一种在数学上不合法的方式简化了反转后的函数！但它起作用了！请帮忙！

注：期望输出为[0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15]

- googamanga

---

你不能反向哈希。它们是单向函数。在适当的哈希中执行的特定计算无法被反转以获取生成哈希的原始值。例如，1+2 => 3 是可以的，但是 3 -> ??? 就不行了。有着无限多的可能性：sqrt(9)，4-1等等。 - Marc B

@MarcB 大多数哈希函数都是单向的（或接近单向；真正单向函数的存在在计算机科学中仍是一个未解之谜）。可以制作一个哈希函数，对于给定的输入域，它是可逆的。 - qxz

尽管这个“哈希函数”的输出似乎不仅仅是一个固定位数的单一值，但它看起来与输入大小相同。因此，它实际上并不是一个哈希函数。 - qxz

好的，这不是一个哈希表...我移除了 'hash' 标签，改变了语言和变量名。 - googamanga

请查看此页面，其中提到了费斯妥密码。我不太理解它的工作原理，但这应该会给你正确的方向。这里还有一个类似的例子在这里，可能会有所帮助。 - user172818

Answer 1

首先，你的“哈希函数”并不是传统意义上的哈希函数。哈希函数通常接受一个输入（可以是可变大小的数据，例如字符串），并将其转换为固定位数的单个值。这种函数实际上无法被逆转，因为在转换过程中会丢失许多数据位，从4位无法重构100位。

你的函数将一组字节转换为另一组等长的字节。它似乎将当前输入通过函数 (x*129)%256>运行，然后与前一个输入进行异或运算。

函数f(x) = (x*129) % 256是有趣的部分。如果输入是偶数，则输出是相同的数字。如果输入是奇数，则输出是具有反转第7位（第127位）的位的输入。（尝试自己插入几个值）。因此，f(x)是自己的反转；f(f(x)) == x。

因此，整个“哈希函数”可以像这样反转：

1. 将当前哈希值与前一个输入值进行异或运算，如果是第一个则为0 2. 将结果通过f(x)函数运行以反转f(x)计算时的值 3. 对每个值进行重复操作

这就是你最后那段代码所做的事情。我不确定第一个代码块。

- qxz

---

x*129 = x<<7 + x，当考虑到模溢出时，等同于 x<<7 ^ x。 - samgak

我的函数不是 x => (x*129)%256，而是 x=> ((129 * x) XOR x[i-1]) % 256。据我所知，模数不能在 (129 * x) 和 x[i-1] 之间分配，因为 XOR 没有分配律。因此，你不能单独提出 (x*129) % 256。 - googamanga

@samgak 255*129= (255<<7)+255 = 32895 != (255<<7)^255 which is 32639 - googamanga

@googamanga 如果你将 % 256 重写为 & 255，它就可以了：((129 * x) ^ x[i-1]) & 255 => ((129 * x) & 255) ^ (x[i-1] & 255)。 - samgak

32895＆255 = 32639＆255 = 127 - samgak

Answer 2

注意：在写完这个答案后，我重新阅读了qxz的答案，并意识到这里涵盖的所有内容也都涵盖在qxz的答案中。但我还是决定发布这个答案，因为稍微不同的格式可能对一些人有所帮助。

要理解为什么这有效，你只需要计算一下即可。

y = (129 * x) % 256;  

对于0到255之间的每个x，从偶数开始

for ( x = 0; x < 256; x += 2 ) {
    y = (129 * x) % 256; 
    console.log(y);
}

输出结果为：

  0   0
  2   2
  4   4
  6   6
  8   8
 10  10
 12  12
 14  14
... ...

换句话说，当你用 129 模 256 相乘时，偶数不会改变。

奇数的输出为：

  1 129
  3 131
  5 133
  7 135
  9 137
 11 139
... ...
125 253
127 255
129   1
131   3
133   5
... ...

换句话说，将一个数乘以129然后对256取模等价于在该数对256取模的基础上加上128。因此，重复两次操作可以得到原始数值：(x + 128 + 128) % 256 = x 公式的其余部分实际上不会影响上述结论。对256取模使高于第七位的位被丢弃，只保留低8位。异或运算不会影响第7位以上的位，它仅反转了一些低8位。因此异或和模运算之间没有交互作用。异或仅影响低8位，而模运算则仅影响高位。

这意味着，在反向计算时，您可以先进行异或操作以获取低8位。然后，将结果乘以129并对256取模要么无效（如果结果为偶数），要么加上128对256取模（如果结果为奇数）。无论哪种方式，您都可以得到原始数值。

- user3386109