# Crack Random Module
:::info
Để khởi động, chúng ta sẽ có 1 video được minh họa một cách trực quan và sinh động nhằm giúp bạn tiếp cận dễ hơn với chủ đề này:

Link: [How To Predict Random Numbers Generated By Computers](https://www.youtube.com/watch?v=-h_rj2-HP2E)
:::

## 1. Python
Hàm random của Python sử dụng thuật toán [Mersenne Twister](https://en.wikipedia.org/wiki/Mersenne_Twister) - với 624 số nguyên 32 bit làm trạng thái, sau đó cứ mỗi lần xuất ra một số nguyên 32 bit, nó sẽ thay đổi trạng thái.
### Mersenne Twister
Ta sẽ phân tích thuật toán tạo số ngẫu nhiên trong khoảng `[0,0xffffffff]`: [Link](https://github.com/python/cpython/blob/23362f8c301f72bbf261b56e1af93e8c52f5b6cf/Modules/_randommodule.c)

/* Period parameters -- These are all magic.  Don't change. */
#define N 624
#define M 397
#define MATRIX_A 0x9908b0dfU    /* constant vector a */
#define UPPER_MASK 0x80000000U  /* most significant w-r bits */
#define LOWER_MASK 0x7fffffffU  /* least significant r bits */

static uint32_t
genrand_uint32(RandomObject *self)
{
    uint32_t y;
    static const uint32_t mag01[2] = {0x0U, MATRIX_A};
    /* mag01[x] = x * MATRIX_A  for x=0,1 */
    uint32_t *mt;

    mt = self->state;
    if (self->index >= N) { /* generate N words at one time */
        int kk;

        for (kk=0;kk<N-M;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+M] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        for (;kk<N-1;kk++) {
            y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
            mt[kk] = mt[kk+(M-N)] ^ (y >> 1) ^ mag01[y & 0x1U];
        }
        y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
        mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];

        self->index = 0;
    }

    y = mt[self->index++];
    y ^= (y >> 11);
    y ^= (y << 7) & 0x9d2c5680U;
    y ^= (y << 15) & 0xefc60000U;
    y ^= (y >> 18);
    return y;
}

Nếu `index >= N (= 624)`, nghĩa là đã dùng hết số trong mảng `mt[]` và do đó phải tạo lại 624 số tiếp theo. Mảng `mt[]` được thay đổi bằng quá trình sau:

y = (mt[kk] & UPPER_MASK) | (mt[(kk + 1) % N] & LOWER_MASK)
mt[kk] = mt[(kk + M) % N] ^ (y >> 1) ^ mag01[y & 0x1U]

y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
mt[N-1] = mt[M-1] ^ (y >> 1) ^ mag01[y & 0x1U];

Sau đó, số `y` ngẫu nhiên được tạo như sau:

y = mt[self->index++];
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680U;
y ^= (y << 15) & 0xefc60000U;
y ^= (y >> 18);
return y;

Do đó, nếu ta có thể đảo ngược được quá trình này thì ta có thể dự đoán giá trị tiếp theo khi biết được 624 đầu ra 32 bit.

### Khôi phục từ đầu ra đầy đủ 32-bit
Sau đây là các bước đảo ngược chi tiết:
:::spoiler y ^= (y >> 18)
Đây là dịch phải 18 bit, ảnh hưởng từ bit cao tới bit thấp và sau bước này thì bit cao không thay đổi cùng với việc $18*2 = 36 > 32$ nên ta chỉ cần 1 lần đảo là được.

# Step 1
y ^= (y >> 18)

:::

:::spoiler y ^= (y << 15) & 0xefc60000
Ở đây, mask 0xefc60000 có cấu trúc đặc biệt với làm phép biển đổi trở thành 1 hàm tự nghịch đảo, nghĩa là $f(f(x))=x$, với $f(x) = x \oplus ((x \ll 15) \ \&$ 0xefc60000$)$. Chứng minh:
- Đặt A = 0xefc60000. Khi đó:
$f(y)=f(f(x)) = f(x \oplus ((x \ll 15) \ \& \ A))$
$= (x \oplus ((x \ll 15) \ \& \ A)) \oplus (((x \oplus ((x \ll 15) \ \& \ A)) \ll 15)\ \& \ A)$
$= (x \oplus ((x \ll 15) \ \& \ A)) \oplus (((x \ll 15) \ \& \ A) \oplus((x \ll 30)\ \& \ (A \ll 15) \ \& \ A))$
$= x \oplus (((x \ll 15) \ \& \ A) \oplus ((x \ll 15) \ \& \ A)) \oplus((x \ll 30)\ \& \ (A \ll 15) \ \& \ A) = x$
(vì tính chất $P \oplus P = 0$ và $A$ có 17 bit thấp là 0 nên nếu dịch trái 15 bit thì 32 bit cuối của $A \ll 15$ sẽ điều là 0 nên $(A \ll 15) \ \& \ A = 0$)

Do đó, để đảo ngược thì ta chỉ cần 1 lần biến đổi hàm nữa:

# Step 2
y ^= (y << 15) & 0xefc60000

:::

:::spoiler y ^= (y << 7) & 0x9d2c5680
Ở bước này thì ta sẽ thiết lập một hàm dịch bit gần tương tự như bước trên:
- Đặt B = 0x9d2c5680.
Với $y = x \oplus ((x \ll 7) \ \& \ B$)$
, ta sẽ dùng hàm $f(x') = y \oplus ((x' \ll 7) \ \& \ B$)$
Khi đó:
$f_4(y) = f_4(x \oplus ((x \ll 7) \ \& \ B)) = f_3(y \oplus (((x \oplus ((x \ll 7) \ \& \ B)) \ll 7)\ \& \ B))$
$= f_3(x \oplus (((x \ll 7) \ \& \ B) \oplus ((x \ll 7) \ \& \ B)) \oplus((x \ll 7*2)\ \& \ (B \ll 7) \ \& \ B))$
$= f_3(x \oplus((x \ll 7*2)\ \& \ (B \ll 7) \ \& \ B))$
$= f_2(x \oplus((x \ll 7*3)\ \& \ (B \ll 7*2) \ \& \ (B \ll 7) \ \& \ B))$
$= f(x \oplus((x \ll 7*4)\ \& \ (B\ll 7*3) \ \& \ (B \ll 7*2) \ \& \ (B \ll 7) \ \& \ B))$
$= x \oplus((x \ll 7*5)\ \& \ (B\ll 7*4) \ \& \ (B\ll 7*3) \ \& \ (B \ll 7*2) \ \& \ (B \ll 7) \ \& \ B)$
$=x$
(vì $B$ có 7 bit thấp là 0 nên nếu dịch trái 28 bit thì 32 bit cuối của $B \ll 28$ sẽ đều là 0 nên đẳng thức trên xảy ra.)

Do đó, để đảo ngược thì ta chỉ cần 4 lần biến đổi hàm như sau:

# Step 3
res = y
for _ in range(4):
    res = y ^ (res << 7) & 0x9d2c5680
y = res

:::

:::spoiler y ^= (y >> 11)
Đây là dịch phải 11 bit, ảnh hưởng từ bit cao tới bit thấp và sau bước này thì bit cao không thay đổi cùng với việc $11*3 = 33 > 32$ nên ta chỉ cần 2 lần đảo để khôi phục từ bit cao đến bit thấp.

# Step 4
res = y
for _ in range(2):
    res = y ^ (res >> 11)

:::

Tổng hợp lại thì ta có hàm đảo (untemper):

def untemper(y):
    # 1. Rev: y ^= (y >> 18)
    y ^= (y >> 18)
    # 2. Rev: y ^= (y << 15) & 0xefc60000
    y ^= (y << 15) & 0xefc60000
    # 3. Rev: y ^= (y << 7) & 0x9d2c5680
    temp = y
    for _ in range(4):
        temp = y ^ (temp << 7) & 0x9d2c5680
    y = temp
    # 4. Rev: y ^= (y >> 11);
    temp = y
    for _ in range(2):
        temp = y ^ (temp >> 11)
    y = temp
    return y

Ví dụ cụ thể:

import random

state = random.getstate()

outputs = [random.getrandbits(32) for _ in range(1000)]
recovered_state = (3, tuple([untemper(v) for v in outputs[:624]] + [0]), None)
random.setstate(recovered_state)

for i in range(1000):
    assert outputs[i] == random.getrandbits(32)

- State được phục hồi có 3 phần tử:
1. Số nguyên 3, là chỉ số "vị trí trạng thái" được module random của Python sử dụng để chỉ ra vị trí của bộ tạo trong mảng trạng thái.
2. Bộ dữ liệu gồm 624 số nguyên, biểu diễn mảng trạng thái đã phục hồi.
3. None là "giá trị giữ chỗ" để đảm bảo tính tương thích với định dạng trạng thái mà module random của Python mong đợi.

Khi chạy đoạn kiểm thử trên thì dòng lệnh đối chiếu với `assert` không bị lỗi, chứng tỏ đã khôi phục thành công state ban đầu.

## 2. Javascript

Phương thức tĩnh `Math.random()` trả về một số dấu phẩy động, ngẫu nhiên lớn hơn hoặc bằng 0 và nhỏ hơn 1, với phân phối gần như đồng đều trong phạm vi đó — sau đó bạn có thể điều chỉnh theo phạm vi mong muốn. Việc triển khai sẽ chọn `seed` ban đầu cho thuật toán tạo số ngẫu nhiên; người dùng không thể chọn hoặc đặt lại `seed` này.

- XorShift128 trả về trạng thái 128-bit qua `state0, state1` và được triển khai như sau:

def xs128(state0, state1):
    mask = (1 << 64) - 1
    s1 = state0 & mask
    s0 = state1 & mask
    s1 ^= (s1 << 23) & mask
    s1 ^= (s1 >> 17) & mask
    s1 ^= s0
    s1 ^= (s0 >> 26) & mask
    return s0, s1

- Khi `cache` trống, 1 chuỗi 64 giá trị ngẫu nhiên mới sẽ được tạo thành qua xs128 và lưu trữ trong `cache` với chỉ số được đặt ở cuối.

def _refill(self):
    """
    Refill the Math.random cache using xs128.
    Can only be used when Math.random cache is empty.

    A new 64-long list of random values is stored in cache.
    The cache_idx is set to the last index of the cache (63).
    """
    assert self.cache_idx == -1
    self.cache = []
    for _ in range(64):
        self.state0, self.state1 = xs128(self.state0, self.state1)
        self.cache.append(self.state0)
    self.cache_idx = 63

- Lúc gọi `Math.random()` thì `next()` được gọi và đưa ra 1 giá trị thập phân từ 0.0 đến 1.0. Ở đây thì v8 chuyển đổi số từ xs128 sang double bằng cách bỏ 12 bit cuối, còn 52 bit thì đưa vào phần Mantissa của số double trong chuẩn IEEE754. Sau đó trừ đi 1 và có được giá trị thập phân từ 0.0 đến 1.0.

def v8_to_double(state0, debug):
    r = (state0 >> 12) | 0x3ff0000000000000
    if debug:
        return r
    else:
        return struct.unpack('d', struct.pack('<Q', r))[0] - 1
    
def next(self):
    if self.cache_idx < 0:
        self._refill()
    val = v8_to_double(self.cache[self.cache_idx], self.debug)
    self.cache_idx -= 1
    return val

### Khôi phục trạng thái từ một lượng giá trị ngẫu nhiên được cho
`Math.random()` của V8 sử dụng `xs128` gồm các biểu thức tuyến tính trong hệ GF(2). Do đó, ta có thể xây dựng một hệ các phương trình tuyến tính trên GF(2) với 1 lượng giá trị ngẫu nhiên cho trước vừa đủ và từ đó, ta được nghiệm của hệ này là hai trạng thái ban đầu (seed) của thuật toán và dự đoán được giá trị ngẫu nhiên tiếp theo.

Chúng ta sẽ xây dựng hệ như sau:

numbers = [
    0.20850633840727073,
    0.28382289045651743,
    0.4071416957057805,
    0.3101367279739642,
    0.6813711566813534,
    0.8365880507655776,
    0.2238039081275922,
    0.014754643967695324,
    0.44290438850282876,
    0.5473214381957232,
    0.40023560591139606,
    0.14837298522461473,
    0.12321774476187275,
    0.8501766788936596,
    0.9212308144118708,
    0.8099337802981195,
    0.06047989985671265,
    0.6552969701254443,
    0.5803218168252511,
    0.41915921494443964,
    0.9153038363744563,
    0.7403989120318095,
    0.6630141727527132,
    0.5230661117641415
]

- Đây là những giá trị ngẫu nhiên cho trước

from gf2bv import LinearSystem

lin = LinearSystem([64] * 2)
state0, state1 = lin.gens()

Random = MathRandom(state0, state1, True)
out = [Random.next() for _ in range(len(numbers))]

- `state0, state1` là hai `symbolic unknown` có 64-bit và nằm trong hệ tuyến tính. `Random` sẽ tạo những biểu thức tuyến tính chính là `out` với ẩn là `state0, state1` để xây dựng hệ.

zeros=[(v8_from_double(x) >> 12 | 0x3ff0000000000000) ^ y for x,y in zip(numbers, out)]

- Với mỗi cặp giá trị và phương trình ẩn, ta khôi phục 52 bit mantissa của đầu ra và đưa về chuẩn IEEE754 cho dạng double + 1.0 rồi XOR với biểu thức ẩn đã cho.
- Nếu biểu thức này trùng với giá trị đầu ra thì sau khi XOR sẽ bằng 0. Vậy là ta đã có hệ tuyến tính ẩn `state0, state1`, giải hệ này và ta nhận được trạng thái ban đầu.

sol = lin.solve_one(zeros)

## 3. C/C++
Bên ngôn ngữ C/C++, hàm rand() xây dựng dựa trên [GLIBC random number generator](https://www.mscs.dal.ca/~selinger/random/)

Hàm `random()` của thư viện GNU C cung cấp các số giả ngẫu nhiên thông qua phương pháp phản hồi cộng tuyến tính. Phản hồi này tuyến tính theo modulo $2^{32}$. Tính phi tuyến tính nhỏ duy nhất xuất hiện trong giai đoạn `seeding`, do phép này được thực hiện theo modulo $2^{31} - 1$ chứ không phải modulo $2^{31}$ hay $2^{32}$. Điều này có nghĩa là, mặc dù mỗi số ngẫu nhiên được tạo ra phụ thuộc tuyến tính vào các số trước đó trong chuỗi, nhưng toàn bộ các số ngẫu nhiên không phụ thuộc tuyến tính vào `seed`.

### Thuật toán
Như mô tả ở trên, ta có: $2147483647 = 2^{31} - 1$ và $4294967296 = 2^{32}$

Với mỗi `seed` cho trước, 1 `initialization vector` (iv) $r_0...r_{33}$ được tính như sau:
- $r_0$ = `seed`
- $r_i\equiv (16807 * r_{i-1}) \mod 2147483647 \ ( i \in [1,30])$
- $r_i=r_{i-31}\ (i\in [31, 33])$

Sau đó, 1 chuỗi các số ngẫu nhiên $r_{34}...$ được tạo bằng vòng lặp phản hồi tuyến tính:
- $r_i\equiv r_{i-3}+r_{i-31}\mod 4294967296 \ (i \ge 34)$

$r_0...r_{343}$ không được sử dụng mà đầu ra $o_i$ của hàm `rand()` là: $o_i =r_{i+344} \gg 1$

Code in C:

#include <stdio.h>

#define MAX 1000
#define seed 1

main() {
  int r[MAX];
  int i;

  r[0] = seed;
  for (i=1; i<31; i++) {
    r[i] = (16807LL * r[i-1]) % 2147483647;
    if (r[i] < 0) {
      r[i] += 2147483647;
    }
  }
  for (i=31; i<34; i++) {
    r[i] = r[i-31];
  }
  for (i=34; i<344; i++) {
    r[i] = r[i-31] + r[i-3];
  }
  for (i=344; i<MAX; i++) {
    r[i] = r[i-31] + r[i-3];
    printf("%d\n", ((unsigned int)r[i]) >> 1);
  }
}

### Khôi phục
Phân tích thuật toán trên thì ta thấy rằng:
- Từ $i\ge34$, $r_i\equiv r_{i-3}+r_{i-31}$ là tuyến tính và có nghĩa là khi ta biết được 2 trong 3 giá trị thì sẽ suy ra được giá trị còn lại.
- Với đầu ra $o_i =r_{i+344} \gg 1$, nghĩa là nó có 31 bit và mất bit bên phải ngoài cùng $r_{i+344}$
- Nghĩa là nếu ta có đủ đầu ra liên tiếp thì hoàn toàn có thể lan truyền để khôi phục lại mảng trạng thái ban đầu (iv).

Các bước để khôi phục iv như sau:
1. Đoán bit thấp bị bỏ rồi ghép thành một phần trạng thái:

def crack(outputs):
    states = []

    for i in range(len(outputs)):
        if (i >= 31 and 
            outputs[i]      != None and
            outputs[i - 31] != None and 
            outputs[i - 3]  != None and 
            outputs[i] != (outputs[i - 31] + outputs[i - 3]) & 0x7fffffff
        ):
            states[i - 31] = (outputs[i - 31] << 1) + 1
            states[i - 3]  = (outputs[i - 3]  << 1) + 1
            states.append((outputs[i] << 1) + 0)
        else:
            states.append(None)

    return states

:::info
Nếu ta có $o_i, o_{i-31},o_{i-3}$ và chúng không thỏa:

outputs[i] == (outputs[i - 31] + outputs[i - 3]) & 0x7fffffff

Đoán trạng thái của nỏ ở dạng:
$$
\begin{cases}
s_{i-31} = o_{i-31} \ll 1 + 1 \\
s_{i-3} = o_{i-3} \ll 1 + 1 \\
s_i = o_i \ll 1 + 0
\end{cases}
$$
:::
Nếu không, gắn $s_i =$ None vì chưa biết dạng chuẩn.

2. Khôi phục trạng thái:

Chạy ngược công thức cộng để khôi phục các giá trị (nếu có) trong 344 giá trị đầu

states = crack(outputs)
init = [None] * 344

for i in range(343, 2, -1):
    s31 = states[i + 31 - 344] if i + 31 >= 344 else init[i + 31]
    s28 = states[i + 28 - 344] if i + 28 >= 344 else init[i + 28]
    if s31 is not None and s28 is not None:
        init[i] = (s31 - s28) % 2**32

Nếu có 1 giá trị trong khoảng 31 giá trị đầu, ta có thể tính tất cả các giá trị còn lại vì tính chất tuyến tính bằng công thức:
$r_i\equiv (16807 * r_{i-1}) \mod 2147483647 \Leftrightarrow r_{i-1}\equiv (16807^{-1} * r_i) \mod 2147483647$

base_idx = next((i for i in range(31) if init[i] is not None), None)
    
if base_idx is not None:
    for i in range(31):
        if init[i] is None:
            init[i] = pow(16807, i - base_idx, 2147483647) * init[base_idx] % 2147483647

Vì tính chất tuyến tính $r_i \equiv r_{i-3}+r_{i-31}, \forall i \ge 34$ nên nếu ta biết 2 giá trị thì suy ra được giá trị còn lại. Do đó, ta viết hàm lặp đến khi không thể khôi phục giá trị nào nữa để điền tất cả các giá trị còn thiếu.

def self_recover(states):
    MOD = 2 ** 32
    length = len(states)

    while True:
        updated = False

        for i in range(34, length):
            s_i = states[i]
            s_31 = states[i - 31]
            s_3 = states[i - 3]

            if s_i is not None and s_3 is not None and s_31 is None:
                states[i - 31] = (s_i - s_3) % MOD
                updated = True

            elif s_i is not None and s_31 is not None and s_3 is None:
                states[i - 3] = (s_i - s_31) % MOD
                updated = True

            elif s_i is None and s_3 is not None and s_31 is not None:
                states[i] = (s_3 + s_31) % MOD
                updated = True

        if not updated:
            break
             
all_states = init + states
self_recover(all_states)

Điền 3 giá trị đầu bằng các sao chép từ thứ tự 31 và lấy được `seed` ban đầu:

for i in range(3):
    all_states[i] = all_states[i + 31]

Full code ở [đây](https://github.com/r1muru2006/Crack_random/blob/main/glibc_random/crack.py)...

## 4. Golang
PRNG của Golang xây dựng dựa trên Lagged Fibonacci Generator.
### Thuật toán
Hàm tạo `seed` cho rng: $x_{n+1} = 48271 * x_n \mod (2^{31} - 1)$

def seedrand(x):
    A = 48271
    Q = 44488
    R = 3399

    hi = x // Q
    lo = x % Q
    x = A * lo - R * hi
    if x < 0:
        x += INT32_MAX
    return x

Để tránh tràn số thì code dùng Schrage’s Method (hi = x // Q, lo = x % Q).

Tiếp theo, ta có class `RNGSource` là PRNG chính.

self.tap = 0
self.feed = RNG_LEN - RNG_TAP   # 607 - 273 = 334

Hai con trỏ là `tap` và `feed` chạy ngược nhau, thực hiện phép cộng sinh số ngẫu nhiên rồi sau đó lưu trữ trạng thái này vào mảng `vec`, tổng 607 phần tử 64-bit.

def seed(self, seed):
    self.tap = 0
    self.feed = RNG_LEN - RNG_TAP

    seed %= INT32_MAX
    if seed < 0:
        seed += INT32_MAX
    if seed == 0:
        seed = 89482311

    x = int(seed)
    for i in range(-20, RNG_LEN):
        x = seedrand(x)
        if i >= 0:
            u = (int(x) << 40) & 0xFFFFFFFFFFFFFFFF
            x = seedrand(x)
            u ^= (int(x) << 20) & 0xFFFFFFFFFFFFFFFF
            x = seedrand(x)
            u ^= int(x)
            u ^= rng_cooked[i]
            self.vec[i] = u

Hàm `seed()` sẽ nhận giá trị `seed` và tạo ra mảng trạng thái `vec` như sau:
1. x được gọi `seedrand()` 20 lần để tạo số ngẫu nhiên.
2. Ghép 3 giá trị 31-bit thành số 64-bit qua hàm `seedrand()` với $x \ll 40, x \ll 20, x$.
3. XOR với 1 giá trị trong bảng `rng_cooked[]`.

Tiếp theo, ta sẽ sinh số ngẫu nhiên 64-bit qua `vec` bằng hàm `uint64()`:

def uint64(self):
    self.tap -= 1
    if self.tap < 0:
        self.tap += RNG_LEN

    self.feed -= 1
    if self.feed < 0:
        self.feed += RNG_LEN

    x = (self.vec[self.feed] + self.vec[self.tap]) & 0xFFFFFFFFFFFFFFFF
    self.vec[self.feed] = x
    return x

- Hai con trỏ `tap` và `feed` đi lùi trong vòng có độ dài 607.
- Theo đó là công thức Additive Lagged-Fibonacci Generator:
$$
vec_{feed}=(vec_{feed} + vec_{tap}) \ \& \ 0xFFFFFFFFFFFFFFFF
$$

x = (self.vec[self.feed] + self.vec[self.tap]) & 0xFFFFFFFFFFFFFFFF
self.vec[self.feed] = x

### Khôi phục
Như ta thấy, trong golang thì từ sau giai đoạn sinh `seed`, giai đoạn sinh số ngẫu nhiên chỉ gồm phép cộng tuyến tính trên chuỗi `seed` lấy được. Nghĩa là nếu ta có chuỗi đầu ra đủ dài, ta có thể xây dựng hệ phương trình tuyến tính để tính chuỗi `seed` ban đầu.

Để xây dựng được hệ như vậy, mình nghĩ ngay tới z3-solver và sau đây là phần crack:

from rng import *
from z3 import *

s = Solver()
NUM_TEST = 700

vec = [BitVec(f'vec_{i}', 64) for i in range(RNG_LEN)]
rng_equation = RngSource(vec)
equations = [rng_equation.uint64() for _ in range(NUM_TEST)]

rng_value = RngSource()
rng_value.seed(int(input("Enter seed: ")))
vals = [rng_value.uint64() for _ in range(NUM_TEST)]

for i in range(NUM_TEST):
    s.add(equations[i] == vals[i])

print("99%...")

if s.check() == sat:
    model = s.model()
    array_values = [model.evaluate(vec[i]).as_long() for i in range(RNG_LEN)]
    rng = RngSource(array_values)

    for _ in range(NUM_TEST):
        res = rng.uint64()

    for _ in range(10):
        print(rng.uint64(), rng_value.uint64())

## 5. Bash
Bash dùng linear congruential generator (LCG) là biến thể của thuật toán Park–Miller “minimal standard” để tạo số ngẫu nhiên 31-bit.
### Thuật toán
Hàm `next_seed` sinh `seed` mới bằng cách áp dụng công thức Park-Miller LCG:
$$
X_{k+1}=(a\times X_k)\mod m
$$

với $a = 16807,\ m = 2^{31} - 1$

def next_seed(self) -> int:
    if self.seed == 0:
        self.seed = 123459876

    h = self.seed // 127773
    l = self.seed - (127773 * h)
    t = 16807 * l - 2836 * h
    self.seed = (t + 0x7fffffff) if t < 0 else t
    return self.seed

Giống Golang, nhằm tránh bị tràn số thì ta dùng Schrage’s Method để tách h và l.

Với `seed` đó, ta sinh giá trị ngẫu nhiên bằng hàm `next_16`:

def next_16(self) -> int:
    self.next_seed()

    if self.is_old:
        # Bash 5.0 and earlier
        result = self.seed & BASH_RAND_MAX
    else:
        # Bash 5.1 and later
        result = ((self.seed >> 16) ^ (self.seed & 0xffff)) & BASH_RAND_MAX

    # Skip if same as last
    if result == self.last:
        return self.next_16()
    self.last = result
    return result

Có 2 phiên bản khác nhau:
- Từ bản Bash 5.0 trở xuống, ta chỉ lấy 15 bit thấp.
- Bash 5.1 trở lên: XOR 2 giá trị 16 bit cao và 16 bit thấp của `seed` rồi trả về 15 bit cuối.

Bên cạnh đó, nếu số mới giống số cũ, ta bỏ qua và tính số mới.
### Khôi phục
Vì ở đây, ta không có được trực tiếp $X_n$ mà chỉ lấy được giá trị của nó sau hàm `next_16` nên không thể truy ngược được Park-Miller LCG. Do đó, kỹ thuật mình có thể sử dụng ở đây để crack là brute-force.

Mặt khác `output` chỉ cho 15 bit, trong khi `state` có 31 bit, thế nên chắc chắn có rất nhiều `state` cho ra cùng 1 giá trị `output`. Để lọc được `state` phù hợp, ta cần nhiều giá trị `output` liên tiếp để chắc chắn tìm được duy nhất 1 `state.` Nếu không có nhiều `output` như vậy, ta có thể tìm những `state` phù hợp để thử và tìm ra kết quả cuối cùng.

Do `seed` có 32 bit, ta nên sử dụng nhiều luồng nhằm chia các khoảng của nó và chạy các task song song để giảm thời gian thực hiện và tối ưu hóa bộ nhớ. Ở đây, mình sử dụng Pool của thư viện multiprocessing trong Python để chia luồng, rồi thực hiện các task duyệt, so sánh với đầu ra cho trước và trả về `seed` nếu khớp.
Full code ở [đây](https://github.com/R1MURUN0PR0/Crack_random/blob/main/bash_random/crack.py)...

# All code in Github
https://github.com/R1MURUN0PR0/Crack_random/tree/main
# Tài liệu
1. https://soon.haari.me/import-random/
2. https://rbtree.blog/posts/2021-05-18-breaking-python-random-module/
3. https://github.com/JorianWoltjer/BashRandomCracker?tab=readme-ov-file
4. https://en.wikipedia.org/wiki/Xorshift
5. https://github.com/maple3142/gf2bv
6. https://www.mscs.dal.ca/~selinger/random/
7. https://github.com/d0nutptr/v8_rand_buster