我有这个函数来生成感觉像是一个序列中的随机数:
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，请查看链接文章了解相关理论。它接受一个递增的序列，并生成感觉像是随机整数的从递增的序列中。也就是说，它将递增序列映射到看似随机的输出，但它遵循模式!从输出中很难看出这种模式，但这一切都在理论中。"random"对于序列长度(build8从0到255的8位整数序列为256个值)，输出从不重复。
考虑到这个，你怎么能得到这个函数的输出并得到原始输入呢?假设我们知道最初插入的j产生原始输出。已知j并有输出数，如何得到原始数?也就是说，如何逆转build8或build16函数?
我被困在开始，我不知道如何逆转这样的函数实现的理论。如果你知道这个理论并能解释它，也许这会帮助我自己尝试，但到目前为止，我会在黑暗中拍摄，并想知道如果你已经知道这个理论，它是否简单。
我们可以简化这个问题，说我们知道build8函数中的o是什么，这在正向和逆/反向版本中总是固定和已知的。所以我们可以去掉o只留下x
const build8b = (x) => fetch8((fetch8(x) + 123) % 256 ^ 101)
问题是，你如何找到x给出build8b的输出?
console.log(build8b(100)) // => 92
// then this is what we need to figure out how to implement:
console.log(reverse8b(92)) // => 100
如果不可能找到逆，那么这也是一个很好的答案(以及为什么)，然后我可以停止寻找解决方案。
大致来说，这里的平方是可逆的因为可以计算根号取素数的模。如果你得到的输入值x不是二次余数，那么p - x将是。
因此，除了上面的对折之外，大多数操作都可以反转。我在下面包含了一些不太好用的代码，它们演示了基本概念。
值得注意的是，这不是一个好的CSPRNG，因为我们假设攻击者知道我们用来生成它的算法。对于非加密目的，它可能足够好，但对于这些目的，通常ChaCha8既更快，又能产生更好的输出，因为ChaCha8目前被认为是加密安全的(但仅仅是这样)，而对于加密目的，ChaCha12或ChaCha20更好。如果你想要一个小对象集合的排列，使用其中一个带有Fisher-Yates洗牌的prng。
下面是代码。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);