ctf-writeups

Python random number generator

References:

• 2025 强网杯——Crypto 题解

Table of contents:

• Python random number generator
  • Known getrandbits(32)
  • Known getrandbits(1)
  • Known partial bits of getrandbits(16)

Known getrandbits(32)

Recover random number generator from 624 (623 is required for only two solutions) 32-bit numbers generated by random.getrandbits(32):

# pip3 install git+https://github.com/maple3142/gf2bv
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random

# assume we got some random numbers from the remote
all_nums = [random.getrandbits(32) for i in range(1000)]
# at least 623 numbers are required (but with 2 solutions)
# 624 numbers correspond to only one solution
known = all_nums[:624]

# create equations
ls = LinearSystem([32] * 624)
gen = ls.gens()
rng = MT19937(gen)
zeros = [gen[0] ^ int(0x80000000)]
for value in known:
    zeros.append(rng.getrandbits(32) ^ value)

# found solutions
for sol in ls.solve_all(zeros):
    print("Solved")

    # recreate random number generator
    RNG = MT19937(sol).to_python_random()
    for i in range(1000):
        assert RNG.getrandbits(32) == all_nums[i]

Known getrandbits(1)

Recover random number generator from 20258 (19937 is required for only one solution) 1-bit numbers generated by random.getrandbits(1):

# https://dexterjie.github.io/2025/10/20/2025%E5%BC%BA%E7%BD%91%E6%9D%AF/#Blurred%E2%80%94%E2%80%94%E5%A4%8D%E7%8E%B0
# pip3 install git+https://github.com/maple3142/gf2bv
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random

# assume we got some random numbers from the remote
known = [random.getrandbits(1) for i in range(20258)]
all_nums = [random.getrandbits(32) for i in range(1000)]

# create equations
ls = LinearSystem([32] * 624)
gen = ls.gens()
rng = MT19937(gen)
zeros = [gen[0] ^ int(0x80000000)]
for value in known:
    zeros.append(rng.getrandbits(1) ^ value)

# found solutions
for sol in ls.solve_all(zeros):
    print("Solved")

    # recreate random number generator
    RNG = MT19937(sol).to_python_random()
    for i in range(20258):
        assert RNG.getrandbits(1) == known[i]

    for i in range(1000):
        assert RNG.getrandbits(32) == all_nums[i]

Known partial bits of getrandbits(16)

Recover random number generator from 3108 (3115 is required for only one solution) 16-bit (only higher 8 bits are known) numbers generated by random.getrandbits(16):

# https://dexterjie.github.io/2025/10/20/2025%E5%BC%BA%E7%BD%91%E6%9D%AF/#ezran
# pip3 install git+https://github.com/maple3142/gf2bv
from gf2bv import LinearSystem
from gf2bv.crypto.mt import MT19937
import random

# assume we got some random numbers from the remote
known = []
for i in range(3108):
    r1 = random.getrandbits(8)
    r2 = random.getrandbits(16)
    x = (pow(r1, 2 * i, 257) & 0xFF) ^ r2
    known.append(x)
all_nums = [random.getrandbits(32) for i in range(1000)]

# create equations
ls = LinearSystem([32] * 624)
gen = ls.gens()
rng = MT19937(gen)
zeros = [gen[0] ^ int(0x80000000)]
for value in known:
    rng.getrandbits(8)
    # the higher 8 bits of x equals to the higher 8 bits of r2
    zeros.append((rng.getrandbits(16) >> 8) ^ (value >> 8))

# found solutions
for sol in ls.solve_all(zeros):
    # recreate random number generator
    RNG = MT19937(sol).to_python_random()
    good = True
    for i in range(3108):
        r1 = RNG.getrandbits(8)
        r2 = RNG.getrandbits(16)
        x = (pow(r1, 2 * i, 257) & 0xFF) ^ r2
        if x != known[i]:
            # some solutions are wrong
            good = False

    if good:
        print("Solved")
        for i in range(1000):
            assert RNG.getrandbits(32) == all_nums[i]