你如何反转这个伪 "PRNG" 以取回原始数字？

Question

我有生成感觉来自序列的随机数：

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

这不是真正的 PRNG，请查看 linked post 了解理论。这需要一个递增序列，并从递增序列中生成 感觉像随机整数 的东西。也就是说，它将递增序列映射到看似随机的输出，但它遵循一种模式！从输出中很难看出这种模式，但这一切都在理论上。 “随机”输出从不重复序列的长度（对于 build8，从 0 到 255 的 8 位整数序列有 256 个值）。

鉴于此，您如何获取此函数的输出并取回原始输入？假设我们知道最初插入的 j 是为了生成原始输出。假设你知道 j 并且有输出数字，你如何取回原始数字？也就是这个build8或者build16函数怎么反转？

我一开始就卡住了，我不知道如何反转这样一个函数实现的理论。如果你知道这个理论并且可以解释它，也许这会帮助我自己尝试，但截至目前我会在黑暗中拍摄并想知道如果你已经知道这个理论是否简单。

我们可以通过说我们知道 o 在 build8 函数中的内容来简化问题，它总是会在前向和 inverse/reverse 版本。所以我们可以去掉 o 只留下 x.

const build8b = (x) => fetch8((fetch8(x) + 123) % 256 ^ 101)

问题是，如何从 build8b 的输出中找到 x 的内容？

console.log(build8b(100)) // => 92
// then this is what we need to figure out how to implement:
console.log(reverse8b(92)) // => 100

如果无法找到逆，那么这也是一个很好的答案（以及为什么），然后我可以停止寻找解决方案。

Answer 1

粗略地说，这里的平方是可逆的，因为 compute square roots modulo a prime 是可能的。如果你得到的输入值x不是二次留数，那么p - x就是。

因此，除了在顶部完成的对折操作之外，您可以反转大部分操作。我在下面包含了一些不太有效的代码，这些代码演示了基本概念。

请注意，这不是一个好的 CSPRNG，因为我们假设攻击者知道我们用来生成它的算法。对于非加密目的，它可能已经足够好了，但通常对于这些目的，ChaCha8 速度更快并产生更好的输出，因为 ChaCha8 目前被认为是密码安全的（但勉强如此），而对于密码目的，ChaCha12 或 ChaCha20 更好。如果您想要排列一小组对象，请将其中一个 PRNG 与 Fisher-Yates 随机播放一起使用。

这是代码。 test8 和 testinv8 显示了没有最终平方和折叠操作的操作，这说明了为什么它不是完全可逆的。

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

const powmod = (a, k, p) => {
    let t = a
    let x = 1
    while (k != 0) {
        if (k & 1) {
            x *= t
            x %= p
        }
        t = (t * t) % p
        k >>= 1
    }
    return x
}

const euler = (a, p) => powmod(a, (p - 1) / 2, p)

const sqrt = (z, p) => {
    if (z >= p) {
        return z
    }

    const e = euler(z, p)
    if (e != 1) {
        z = p - z
    }

    const k = (p - 3) / 4
    const v = powmod(z, k + 1, p)
    return (v <= p / 2) ? v : p - v
}

const sqrt8 = (x) => sqrt(x, 251)

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 test8 = (x, o) => ((fetch8(x) + o) % 256)
const testinv8 = (x, o) => sqrt8((256 + x - o) % 256)

const inv8 = (x, o) => sqrt8(((sqrt8(x) ^ 101) + (256 - o)) % 256)

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.
    let y = inv8(x, j)
    let z = test8(i, j)
    let a = testinv8(z, j)
    if (x > 255) {
        invalid.push([ i, j, x ]);
    } else {
        valid.add(x);
        console.log("item ", i, ", ", x, ", ", y, ", ", z, ", ", a)
    }
    i++;
}

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

你如何反转这个伪 "PRNG" 以取回原始数字？

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

javascript

random

math

cryptography