1. 随机数的数学概念

随机数是数学中一个重要的概念，它在计算机科学、统计学、密码学、模拟实验等领域有着广泛的应用。随机数通常指的是一个序列，其中每个数的取值在一定范围内，且每个数出现的概率相同，并且无法预测下一个数是什么。

真随机数和伪随机数

在物理世界中很多数据的产生都是随机的，如电子噪声、放射性衰变等，这些现象本质上是不可预测的。这一类自然现象产生的随机数叫做真随机数。

要在计算机中生成真随机数是非常困难的，可能需要借助特殊的硬件才能做到。大多数计算机生成的随机数是伪随机数。这些数字是通过算法生成的，看起来像是随机的，但实际上是可重复的和可预测的。

生成伪随机数的算法叫做伪随机数生成器（Pseudo-Random Number Generator，PRNG），伪随机数生成器通常会根据一个初始值（称为种子）通过特定算法产生一系列数值。给定相同的种子，伪随机数生成器（PRNG）将产生相同的数列。

也就是说，如果我通过某种方法知道了你的随机数算法和种子，我就能预测你生成的随机数！

2. Math.random

这是我们今天要讨论的主角。

Math.random() 是 JavaScript 中的一个函数，用于生成一个0到1之间的伪随机数，这个数是一个浮点数，取值范围从0（包括）到1（不包括）。简单来说，每次调用 Math.random() 时，都会返回一个0到小于1的随机数。

JavaScript引擎使用一个内部的伪随机数生成器（PRNG），并可能使用当前时间或其他不可预测的值作为种子来确保每次页面加载或脚本运行时生成的随机数序列不同。

它很方便，前端经常会用到它。然而，它并不安全。在MDN上甚至还有专门提醒：

为什么它不安全

人人都知道Math.random不安全，但是具体是为什么呢？

在JavaScript的世界中，Google的V8引擎以其优异的性能和开源的优势，占据了绝对的主导地位，各种chromium内核浏览器还有nodeJs都是用的V8引擎。

Math.random 需要通过JavaScript引擎实现，而实现它的V8 引擎是开源的，问题就在这里。

前面我们说到，要破解一个伪随机数生成器，我们必须需要知道它的算法和种子。通过V8引擎的开源代码，任何人都能够查到Math.random 的实现算法：

static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
    uint64_t s1 = *state0;
    uint64_t s0 = *state1;
    *state0 = s0;
    s1 ^= s1 << 23;
    s1 ^= s1 >> 17;
    s1 ^= s0;
    s1 ^= s0 >> 26;
    *state1 = s1;
  }

看起来并不复杂，只是一些异或操作和移位的操作，state0 和 state1 代表PRNG的两个内部状态，如果能倒推出这两个状态，就等同于知道了种子。

那么，元神，启动！

3. 破解Math.random

为了倒推Math.random PRNG的初始状态，我们需要借助一个工具：Z3求解器 The Z3 Theorem Prover

z3是由微软公司开发的smt求解器，我们可以将问题作为方程式列出，然后指定约束，z3就可以自动的解决这个问题

比如下面这个方程式组

x + 2y = 10
x > 0
y > 0

我们可以使用z3来帮助我们计算x和y的值。这里使用的是Z3的js版本z3-solver

  import { init } from 'z3-solver';

  // 创建求解器实例
  const { Context } = await init();
  const ctx = Context('main');
  const solver = new ctx.Solver();

  // 定义变量
  const x = ctx.Int.const('x');
  const y = ctx.Int.const('y');

  // 添加约束条件
  solver.add(
    x.gt(0),
    y.gt(0),
    x.add(y.mul(2)).eq(10)
  );

  // 求解约束
  if (await solver.check() === 'sat') {
      console.log(solver.model().get(x).toString(), solver.model().get(y).toString());
  } else {
      console.log("No solution found.");
  }

这样就得到了一组 x,y 的解

了解了Z3之后，我们就可以来破解Math.random了。只需要将函数逐行录入Z3，然后通过Math.random得到一组随机数作为约束条件，就可以倒推出初始状态。

Math.random源代码：

static inline void XorShift128(uint64_t* state0, uint64_t* state1) {
    uint64_t s1 = *state0;
    uint64_t s0 = *state1;
    *state0 = s0;
    s1 ^= s1 << 23;
    s1 ^= s1 >> 17;
    s1 ^= s0;
    s1 ^= s0 >> 26;
    *state1 = s1;
}

首先定义两个初始变量

    const state0 = ctx.BitVec.const('state0', 64);
    const state1 = ctx.BitVec.const('state1', 64);
    let se_state0 = state0, se_state1 = state1;

将原函数录入Z3

function random() {
    let se_s1 = se_state0;
    let se_s0 = se_state1;
    se_state0 = se_s0;
    se_s1 = se_s1.xor(se_s1.shl(23));
    se_s1 = se_s1.xor(se_s1.lshr(17));
    se_s1 = se_s1.xor(se_s0);
    se_s1 = se_s1.xor(se_s0.lshr(26));
    se_state1 = se_s1;
}

接下来我们到浏览器里面获取一组真实的(伪)随机数

Array.from(Array(5), Math.random)

将随机数结果录入Z3，这里需要做一些转换

sequence.forEach(num => {
    random();
    record(num);
});

function record(num) {
    // 分配缓冲区
    const buffer = Buffer.alloc(8);
    // 写入双精度浮点数，整数部分补1
    buffer.writeDoubleLE(num + 1);
    // 读取64位无符号整数
    const ulong64 = buffer.readBigUInt64LE();
    // 提取尾数部分
    const mantissa = ulong64 & ((1n << 52n) - 1n);

    solver.add(se_state0.lshr(12).eq(ctx.BitVec.val(Number(mantissa), 64)));
}

提取模型结果，同样需要做一些转换

function readResult(num: bigint) {
    // 右移，构造64位整数
    const ulong64 = (num >> 12n) | 0x3FF0000000000000n;
    // 分配缓冲区
    const buffer = Buffer.alloc(8);
    // 以小端字节序写入缓冲区
    buffer.writeBigUInt64LE(ulong64);
    // 读取双精度浮点数，并减去1
    const result = buffer.readDoubleLE() - 1;
    return result;
}

完整代码如下（node环境，ts代码需自行编译）

import { exit } from 'process';
import { Z3HighLevel, Z3LowLevel, init } from 'z3-solver';

const sequence = [0.7581919191801032, 0.6094776900063383, 0.9398641206874401, 0.9985947102532351, 0.3755325596355945].reverse();

init().then(main)

async function main({ Z3, Context }: Z3HighLevel & Z3LowLevel) {
  const ctx = Context('main');
  const solver = new ctx.Solver();
  const state0 = ctx.BitVec.const('state0', 64);
  const state1 = ctx.BitVec.const('state1', 64);

  let se_state0 = state0, se_state1 = state1;
  function random() {
    let se_s1 = se_state0;
    let se_s0 = se_state1;
    se_state0 = se_s0;
    se_s1 = se_s1.xor(se_s1.shl(23));
    se_s1 = se_s1.xor(se_s1.lshr(17));
    se_s1 = se_s1.xor(se_s0);
    se_s1 = se_s1.xor(se_s0.lshr(26));
    se_state1 = se_s1;
  }

  function record(num: number) {
    const buffer = Buffer.alloc(8);
    buffer.writeDoubleLE(num + 1);
    const ulong64 = buffer.readBigUInt64LE();
    const mantissa = ulong64 & ((1n << 52n) - 1n);

    solver.add(se_state0.lshr(12).eq(ctx.BitVec.val(Number(mantissa), 64)));
  }

  sequence.forEach(num => {
    random();
    record(num);
  });

  if (await solver.check() === 'sat') {
    const model = solver.model();
    const states = model.decls().map(decl => [decl.name(), model.get(decl)])
    const state0_val: bigint = (states.find((item) => item[0] === 'state0')![1] as any).value()
    const nextSequence = readResult(state0_val);
    console.log("Next sequence value:", nextSequence);
    exit(0);
  } else {
    console.log("No solution found.");
  }
}

function readResult(num: bigint) {
  const ulong64 = (num >> 12n) | 0x3FF0000000000000n;
  const buffer = Buffer.alloc(8);
  buffer.writeBigUInt64LE(ulong64);
  const result = buffer.readDoubleLE() - 1;
  return result;
}

运行这个脚本，即可预测sequence序列的下一个随机数

到浏览器验证一下 预测成功

参考

• developer.mozilla.org/zh-CN/docs/…
• blog.csdn.net/qq_45894840…