Pendahuluan: “Keadaan Berdosa” von Neumann dan Paradoks Keacakan Deterministik

Pada tahun 1951, John von Neumann mengucapkan kalimat legendaris dalam sejarah ilmu komputer: “Siapa pun yang mempertimbangkan metode aritmetika untuk menghasilkan digit acak, tentu saja berada dalam keadaan berdosa (in a state of sin)." Komputer digital adalah mesin keadaan hingga (finite-state machine) yang sepenuhnya deterministik: dengan status awal dan instruksi yang sama, setiap bit berikutnya 100% telah ditentukan. Namun, mulai dari simulasi Monte Carlo dalam fisika nuklir dan pembuatan dunia game prosedural hingga kunci TLS, SSH, dan tanda tangan ECDSA, peradaban modern mengonsumsi triliunan angka acak setiap detik.

Bagaimana algoritma yang pasti dapat menciptakan ketidakpastian? Dan mengapa generator yang secara statistik luar biasa seperti Mersenne Twister (MT19937) menjadi sangat tidak aman saat digunakan untuk membuat token reset kata sandi, memungkinkan penyerang yang mengamati 624 output berturut-turut untuk memprediksi 100% dari seluruh output masa depan dan masa lalunya?

Bab 1: Anatomi Matematika PRNG ── Benih (Seed), Ruang Keadaan Hingga, dan Prinsip Sarang Merpati

Secara formal, Pseudorandom Number Generator (PRNG) adalah automata deterministik $(\mathcal{S}, \mathcal{O}, f, g, s_0)$ dengan ruang keadaan internal hingga $\mathcal{S}$ berukuran $|\mathcal{S}| = 2^b$, benih awal (Seed) $s_0 \in \mathcal{S}$, fungsi transisi $f: \mathcal{S} \to \mathcal{S}$, dan fungsi output $g: \mathcal{S} \to \mathcal{O}$:

Begitu benih $s_0$ ditetapkan, seluruh barisan $r_0, r_1, r_2, \dots$ sepenuhnya ditentukan. Reprodusibilitas ini sangat berharga untuk debugging simulasi ilmiah. Namun menurut Prinsip Sarang Merpati (Pigeonhole Principle), automata pasti akan mengunjungi kembali keadaan sebelumnya $s_{k+P} = s_k$ dalam paling banyak $2^b$ langkah, terjebak dalam siklus periodik dengan periode $P \le 2^b$.

  flowchart LR
    S0["Benih awal s0"] --> S1["Keadaan s1 = f(s0)"]
    S1 --> S2["Keadaan s2 = f(s1)"]
    S2 -. "Pra-periode (Tail)" .-> Sk["Masuk siklus sk"]
    Sk --> Sk1["Keadaan s(k+1)"]
    Sk1 -. "Siklus periodik P <= 2^b" .-> Skm1["Keadaan s(k+P-1)"]
    Skm1 -- "f(s(k+P-1)) = sk" --> Sk

Metode Kuadrat Tengah (Middle-Square Method, 1949) milik von Neumann (mengkuadratkan bilangan $2k$ digit dan mengambil $2k$ digit tengah) cepat runtuh menuju 0000 atau siklus pendek sepanjang 4 karena tidak memiliki struktur aljabar.

Bab 2: Linear Congruential Generator (LCG) dan Teorema Marsaglia ── Tragedi 15 Bidang IBM RANDU

Pada tahun 1949, D. H. Lehmer memperkenalkan Linear Congruential Generator (LCG): $X_{n+1} = (a X_n + c) \bmod m$. Berdasarkan Teorema Hull-Dobell (1962), LCG mencapai periode penuh $P = m$ jika dan hanya jika: (1) $\gcd(c, m) = 1$, (2) setiap faktor prima $p$ dari $m$ membagi $a-1$, dan (3) jika $4 \mid m$, maka $4 \mid (a-1)$.

Pada tahun 1968, ahli statistik George Marsaglia menerbitkan makalah terkenal “Random numbers fall mainly in the planes”, membuktikan bahwa titik-titik $d$-dimensi $(X_n, \dots, X_{n+d-1})$ dari LCG mana pun jatuh pada paling banyak $(d! \cdot m)^{1/d}$ bidang hiper sejajar yang membentuk kisi kristal!

Kasus paling terkenal dalam sejarah adalah RANDU milik IBM ($m = 2^{31}, c = 0, a = 65539 = 2^{16} + 3$) pada mainframe System/360:

Akibat identitas $X_{n+2} \equiv 6 X_{n+1} - 9 X_n \pmod{2^{31}}$, semua titik 3D yang dihasilkan RANDU dalam kubus satuan terjebak hanya pada 15 bidang sejajar dengan ruang kosong yang luas di antaranya, merusak ribuan simulasi Monte Carlo selama puluhan tahun!

Bab 3: Mersenne Twister (MT19937) dan PRNG Statistik Modern (PCG64, Xoshiro256++)

Pada tahun 1997, matematikawan Jepang Makoto Matsumoto dan Takuji Nishimura menciptakan Mersenne Twister (MT19937) di atas medan hingga $\mathbb{F}_2 = \{0, 1\}$ (standar di Python random, R, MATLAB, C++ std::mt19937):

1. Periode Raksasa & Ekuidistribusi 623 Dimensi: Array keadaan $624$ kata 32-bit ($19.937$ bit aktif) menghasilkan periode bilangan prima Mersenne $P = 2^{19937} - 1 \approx 4,315 \times 10^{6001}$ dan ekuidistribusi sempurna hingga 623 dimensi!
2. Transformasi Tempering: Setiap kata keadaan $x$ dikalikan dengan matriks bit $32\times 32$ yang dapat dibalik di atas $\mathbb{F}_2$:

Untuk mengatasi ukuran memori MT19937 ($2,5\text{ KB}$) dan kegagalannya pada dua uji linearitas $\mathbb{F}_2$ dalam TestU01 (BigCrush), lahirlah PCG64 (Melissa O’Neill 2014: LCG 128-bit dengan rotasi bit acak bergantung data; standar di NumPy) dan Xoshiro256++ (Blackman & Vigna 2018: keadaan 256-bit dengan pengacak non-linear; digunakan di Rust dan Java), yang lulus 100% uji BigCrush dalam waktu kurang dari satu nanodetik.

Bab 4: Mengapa Kesempurnaan Statistik $\neq$ Keamanan Kriptografi ── Mengkloning MT19937 dan CSPRNG

4.1 Membalikkan Tempering: Mengkloning MT19937 dari 624 Output

Menggunakan MT19937 untuk token sesi atau kata sandi adalah kesalahan fatal: setiap tahap Tempering adalah bijeksi linear yang dapat dibalik dalam waktu $O(1)$:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def untemper(z: int) -> int:
    # Invert MT19937 32-bit output z back to internal state word x in O(1)
    y3 = z ^ (z >> 18)
    y2 = y3 ^ ((y3 << 15) & 0xEFC60000)
    y1 = y2
    for _ in range(4):
        y1 = y2 ^ ((y1 << 7) & 0x9D2C5680)
    x = y1
    for _ in range(2):
        x = y1 ^ (x >> 11)
    return x & 0xFFFFFFFF

Penyerang yang mengamati hanya 624 output 32-bit berturut-turut ($2.496\text{ byte}$) dari server yang menggunakan MT19937 cukup menerapkan untemper(z) pada masing-masing output untuk mengkloning 100% dari 624 kata keadaan internal server! Sejak saat itu, penyerang dapat memprediksi 100% angka di masa depan dan merekonstruksi semua angka di masa lalu.

4.2 Teorema Andrew Yao (1982) dan CSPRNG

Kriptografi mewajibkan CSPRNG (Cryptographically Secure PRNG) dengan tiga aksioma:

1. Ketidakpastian Bit Berikutnya $\iff$ Ketidakbedakan Komputasional (Teorema Yao, 1982 / Blum-Micali): Tidak ada algoritma waktu polinomial $\mathcal{A}$ yang mengetahui $k$ bit pertama yang dapat menebak bit $r_{k+1}$ secara signifikan lebih baik daripada lemparan koin ($1/2$):

2. Forward Secrecy (Ketahanan Lacak Balik): Setelah setiap output, kunci internal segera ditimpa melalui fungsi satu arah (Fast-Key-Erasure), mencegah pemulihan kunci masa lalu meskipun keadaan saat ini bocor.
3. Backward Secrecy (Ketahanan Prediksi): Penyemaian ulang (Reseeding) berkala dengan entropi perangkat keras memulihkan keamanan setelah kebocoran.

  flowchart TD
    subgraph Insecure ["PRNG Statistik (LCG / MT19937 / Xoshiro)"]
        StateM["Keadaan internal s_i (624 kata)"] -- "Tempering F2 linear dapat dibalik" --> OutM["Output r_i"]
        OutM -- "untemper() mengkloning keadaan dari 624 output!" --> StateM
    end
    subgraph Secure ["CSPRNG Kriptografi (ChaCha20 / AES-CTR_DRBG)"]
        Entropy["Sumber Entropi Perangkat Keras<br/>(Derau Termal / RDSEED)"] -- "Reseeding Berkala (Backward Secrecy)" --> StateC["Kunci Rahasia 256-bit & Counter"]
        StateC -- "Primitif Satu Arah (ChaCha20 / AES)<br/>[Membalikkan butuh 2^256 operasi!]" --> OutC["Aliran Acak Kriptografi r_i"]
        StateC -- "Fast-Key-Erasure Key' = PRF(Key)<br/>[Forward Secrecy!]" --> StateC_Next["Keadaan Baru Key'"]
    end

CSPRNG modern menggunakan cipher seperti ChaCha20-RNG (kernel Linux, OpenBSD, Rust) dan AES-CTR_DRBG (NIST SP 800-90A), atau masalah pemfaktoran seperti Blum-Blum-Shub ($x_{n+1} = x_n^2 \bmod M$). Sebaliknya, generator kurva eliptik Dual_EC_DRBG yang distandarisasi NIST pada 2006 ternyata menyimpan backdoor kleptografi NSA (dikonfirmasi dokumen Snowden 2013: siapa pun yang mengetahui logaritma diskrit rahasia $d$ di mana $P = d \cdot Q$ dapat menghitung keadaan internal hanya dari 32 byte output dan mendekripsi lalu lintas TLS).

Bab 5: Generator Fisik (TRNG), Min-Entropi ($H_\infty$), dan Pool Entropi OS

Benih awal CSPRNG berasal dari Hardware Random Number Generator (TRNG / HRNG) yang menangkap kekacauan fisik: derau termal Johnson-Nyquist pada resistor, derau tembakan kuantum dari kerusakan longsoran dioda Zener, dan jitter fase osilator cincin (instruksi RDSEED/RDRAND pada CPU Intel/AMD). Dalam kriptografi (NIST SP 800-90B), ketidakpastian kasus terburuk diukur dengan Min-Entropi ($H_\infty$) alih-alih entropi rata-rata Shannon $H_1$:

Derau fisik mentah melewati proses pemutihan (Whitening) melalui algoritma von Neumann atau ekstraktor hash kriptografi (BLAKE2s di kernel Linux berdasarkan Leftover Hash Lemma) sebelum masuk ke CSPRNG.

Di Linux modern (5.6+), /dev/random dan /dev/urandom menggunakan CSPRNG kernel ChaCha20 yang sama persis; pengembang harus selalu memanggil getrandom(2) (atau Python secrets, JS crypto.getRandomValues(), Rust OsRng/ThreadRng, Go crypto/rand). Bencana Debian OpenSSL 2008 (CVE-2008-0166) — di mana mengomentari satu baris kode demi menghilangkan peringatan Valgrind menurunkan entropi semua kunci RSA/SSH menjadi hanya ID proses PID 15-bit ($32.768$ kemungkinan kunci) selama dua tahun — serta kegagalan nonce statis ECDSA pada Sony PlayStation 3 (2010) membuktikan hukum mutlak: kekuatan sistem kriptografi tidak pernah bisa melampaui entropi generator angka acaknya.