jeudi 19 août 2021

How can you reverse this pseudo "PRNG" to get back the original number?

I have this function to generate what feels like a random number from a sequence:

const fetch = (x, o) => {
  if (x >= o) {
    return x
  } else {
    const v = (x * x) % o
    return (x <= o / 2) ? v : o - v
  }
}

const fetch16 = (x) => fetch(x, 65519)
const fetch8 = (x) => fetch(x, 251)

// the last number can be anything.
const build16 = (x, o) => fetch16((fetch16(x) + o) % 65536 ^ 42703)
const build8 = (x, o) => fetch8((fetch8(x) + o) % 256 ^ 101)

const j = 115; // If you don't want duplicates, either i or j should stay fixed
let i = 0
let invalid = [];
let valid = new Set;
while (i <= 255) { // <-- small fix here!
    let x = build8(i, j); // To test, you can swap i and j here, and run again.
    if (x > 255) {
        invalid.push([ i, j, x ]);
    } else {
        valid.add(x);
    }
    i++;
}

console.log("invalid:", JSON.stringify(invalid));
console.log("count of valid:", valid.size);

How can you then take the output of this function and get back the original input? Assume we know the j plugged in originally to generate the original output. Given you know j and have the output number, how do you get back the original number? That is, how do you reverse this build8 or build16 function?

I am stuck at the beginning, I don't know the theory for how to reverse a function implementation like this. If you know the theory and can explain that, maybe that would help me try it on my own, but as of now I would be shooting in the dark and wondering if it's simple if you already know the theory.




Aucun commentaire:

Enregistrer un commentaire