googamanga googamanga - 3 months ago 18
Javascript Question

How does this reverse-engineered algorithm work?

The actual algorithm function is:

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


There are several solutions to this. The one that is usually done is along the lines of:

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));


However, I just came accorss:

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);


The idea to follow when asked to reverse a function is to algebraically reverse the function. However, the second solution seems to simplify the reversed function in a way that should not be mathematically valid! But it works! Please help!

P.S. Expected output is [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Answer

Note: after writing up this answer, I re-read the answer by qxz, and realized that everything covered here is also covered in qxz's answer. But I've decided to post this anyways, since a slightly different format may be helpful to some.

To understand why this works, all you have to do is compute

y = (129 * x) % 256;  

for each x between 0 and 255. Start with the even numbers

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

The output is

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

In other words, even numbers aren't changed when you multiple by 129 modulo 256.

The output for the odd numbers is

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

In other words, multiplying by 129 modulo 256 is the same as adding 128 to the number modulo 256. So when you do it twice you get the original number back: (x + 128 + 128) % 256 = x

The rest of the formula really doesn't have any effect on this. Modulo 256 drops any bits above bit 7, keeping the lower 8 bits. The XOR has no effect on the bits above bit 7, it simply inverts some of the lower 8 bits. Thus there's no interaction between the XOR and the modulo 256. The XOR only affects the lower 8 bits, and the modulo only affects the upper bits.

Which means that when reversing the calculation, you can do the XOR first to get the lower 8 bits back. And then multiplying by 129 modulo 256 either does nothing (if the number is even) or it adds 128 modulo 256 (if the number is odd). Either way, you get the original number back.