Created
October 12, 2025 17:03
-
-
Save JorianWoltjer/233e4f4e9ca72be98f4b4314b338184b to your computer and use it in GitHub Desktop.
Math.random() truncated samples solver/predictor for n bits (without z3)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| import numpy as np | |
| CHUNK_SIZE = 64 | |
| MASK64 = (1 << 64) - 1 | |
| def xorshift128_step(s0, s1): | |
| s0 = np.uint64(s0) | |
| s1 = np.uint64(s1) | |
| s1_copy = s0 | |
| s0_copy = s1 | |
| s1_copy ^= (s1_copy << np.uint64(23)) | |
| s1_copy ^= (s1_copy >> np.uint64(17)) | |
| s1_copy ^= s0_copy | |
| s1_copy ^= (s0_copy >> np.uint64(26)) | |
| return int(s0_copy), int(s1_copy) | |
| def to_double(state0): | |
| """V8 ToDouble equivalence: (state0 >> 12) / 2**52 (a double in [0,1)).""" | |
| mantissa = state0 >> 12 | |
| return mantissa / float(1 << 52) | |
| def build_basis_columns(m, bits_per_sample=9): | |
| """Build columns for linear system: | |
| For each basis vector of the 128-bit state, simulate m steps and | |
| record bits_per_sample bits per step starting from bit_offset.""" | |
| cols = [] | |
| bit_offset = 64 - bits_per_sample | |
| for bitpos in range(128): | |
| if bitpos < 64: | |
| s0 = 1 << bitpos | |
| s1 = 0 | |
| else: | |
| s0 = 0 | |
| s1 = 1 << (bitpos - 64) | |
| colbits = 0 | |
| cur_s0, cur_s1 = s0, s1 | |
| r = 0 | |
| for _ in range(m): | |
| new_s0, new_s1 = xorshift128_step(cur_s0, cur_s1) | |
| cur_s0, cur_s1 = new_s0, new_s1 | |
| for b in range(bits_per_sample): | |
| bit = (new_s0 >> (bit_offset + b)) & 1 | |
| if bit: | |
| colbits |= (1 << r) | |
| r += 1 | |
| cols.append(colbits) | |
| return cols | |
| def gf2_solve_from_columns(cols, y_bits, nvars, eq_count): | |
| """Solve A x = y over GF(2) where cols[j] is column j as an eq_count-bit integer.""" | |
| rows = [0] * eq_count | |
| rhs = [0] * eq_count | |
| for r in range(eq_count): | |
| row = 0 | |
| for j in range(nvars): | |
| if (cols[j] >> r) & 1: | |
| row |= (1 << j) | |
| rows[r] = row | |
| rhs[r] = (y_bits >> r) & 1 | |
| row = 0 | |
| where = [-1] * nvars | |
| for col in range(nvars): | |
| sel = -1 | |
| for r2 in range(row, eq_count): | |
| if (rows[r2] >> col) & 1: | |
| sel = r2 | |
| break | |
| if sel == -1: | |
| continue | |
| rows[row], rows[sel] = rows[sel], rows[row] | |
| rhs[row], rhs[sel] = rhs[sel], rhs[row] | |
| where[col] = row | |
| for r2 in range(eq_count): | |
| if r2 != row and ((rows[r2] >> col) & 1): | |
| rows[r2] ^= rows[row] | |
| rhs[r2] ^= rhs[row] | |
| row += 1 | |
| if row == eq_count: | |
| break | |
| for r2 in range(row, eq_count): | |
| if rows[r2] == 0 and rhs[r2]: | |
| raise ValueError("No solution (inconsistent system)") | |
| x = 0 | |
| for i in range(nvars): | |
| if where[i] != -1 and rhs[where[i]]: | |
| x |= (1 << i) | |
| return x | |
| def solve(samples, bits_per_sample=9): | |
| """Recover the 128-bit xorshift128+ internal state from observed samples.""" | |
| m = len(samples) | |
| eq_count = m * bits_per_sample | |
| if eq_count < 128: | |
| raise ValueError( | |
| f"Not enough data: {eq_count} bits available, but need 128. " | |
| f"Try at least {(-(-128 // bits_per_sample))} samples." | |
| ) | |
| cols = build_basis_columns(m, bits_per_sample=bits_per_sample) | |
| y_bits = 0 | |
| r = 0 | |
| for t in range(m): | |
| sample = samples[t] | |
| for b in range(bits_per_sample): | |
| if (sample >> b) & 1: | |
| y_bits |= (1 << r) | |
| r += 1 | |
| solution = gf2_solve_from_columns(cols, y_bits, 128, eq_count) | |
| rec_s0 = solution & MASK64 | |
| rec_s1 = (solution >> 64) & MASK64 | |
| return rec_s0, rec_s1 | |
| def xorshift128_reverse_step(state0, state1): | |
| """Reverse one xorshift128 step.""" | |
| def reverse23(val): | |
| bot46 = (val ^ (val << 23)) & 0x3fffffffffff | |
| original = (val ^ (bot46 << 23)) & 0xFFFFFFFFFFFFFFFF | |
| return original | |
| def reverse17(val): | |
| top34 = (val ^ (val >> 17)) & 0xFFFFFFFFC0000000 | |
| top51 = (val ^ (top34 >> 17)) & 0xFFFFFFFFFFFFE000 | |
| original = (val ^ (top51 >> 17)) | |
| return original | |
| prev_state1 = state0 | |
| prev_state0 = state1 ^ (state0 >> 26) | |
| prev_state0 ^= state0 | |
| prev_state0 = reverse17(prev_state0) | |
| prev_state0 = reverse23(prev_state0) | |
| return prev_state0, prev_state1 | |
| def solve_and_predict(samples, bits_per_sample=9, offset=0): | |
| """Predict future Math.random() outputs from observed low bits.""" | |
| s0, s1 = solve(samples[::-1], bits_per_sample) | |
| print(f"Recovered s0, s1 (hex): {hex(s0)}, {hex(s1)}") | |
| yield to_double(s0) | |
| for _ in range(CHUNK_SIZE - (len(samples) % CHUNK_SIZE) - offset - 1): | |
| s0, s1 = xorshift128_reverse_step(s0, s1) | |
| yield to_double(s0) | |
| for _ in range(CHUNK_SIZE - 1): | |
| s0, s1 = xorshift128_step(s0, s1) | |
| while True: | |
| chunk = [] | |
| for _ in range(CHUNK_SIZE): | |
| s0, s1 = xorshift128_step(s0, s1) | |
| chunk.append(to_double(s0)) | |
| yield from chunk[::-1] | |
| if __name__ == "__main__": | |
| samples = [251, 212, 237, 242, 12, 48, 246, 3, 91, | |
| 223, 45, 225, 46, 155, 157, 9, 111, 186, 204, 77] | |
| print(f"Using {len(samples)} samples of 8 bits each") | |
| queue = solve_and_predict(samples, bits_per_sample=8, offset=3) | |
| print("\nPredicted next Math.random() values:") | |
| for i in range(200): | |
| print(i, next(queue)) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment