Acak Angka Generator

Tentang generator ini

Komputer adalah mesin deterministik, yang membuat "acak" menjadi hal aneh untuk diproduksi. Sejarah generator angka pseudoacak (PRNG) di komputer dimulai dengan middle-square method John von Neumann pada 1946: kuadratkan angka sebelumnya, ambil digit tengah sebagai nilai baru, ulangi. Von Neumann sendiri menyebutnya "keadaan berdosa untuk menggunakan generator angka acak jenis apa pun" jika Anda tidak sepenuhnya memahaminya, karena middle-square memiliki mode kegagalan yang jelas (kembali ke nol, periode pendek). Linear congruential generator Lehmer (LCG, 1951): x_(n+1) = (a × x_n + c) mod m: adalah keluarga PRNG pertama dengan properti statistik yang masuk akal; rand() pustaka standar C masih biasanya menggunakan varian LCG. Mersenne Twister (Matsumoto & Nishimura, 1997-1998) memberi kita generator dengan periode 2¹⁹⁹³⁷−1 (ya, angka 6.000-digit) dan properti statistik yang sangat baik; itu menjadi default di Python, R, MATLAB, PHP, dan banyak bahasa lainnya. Keluarga xorshift Marsaglia (2003) jauh lebih cepat dan cukup kecil untuk muat dalam register hardware; V8 modern (mesin JavaScript Chrome) menggunakan varian xorshift128+ untuk Math.random(). PCG (Permuted Congruential Generator) oleh Melissa O'Neill (2014) adalah keadaan-seni statistik saat ini untuk PRNG non-kriptografis, menggabungkan kemajuan status gaya-LCG dengan permutasi output untuk properti statistik yang sangat baik dengan biaya rendah.

PRNG yang aman secara kriptografis (CSPRNG) adalah binatang yang berbeda. Properti yang menentukan: bahkan jika penyerang mengetahui setiap output yang telah dihasilkan generator, mereka tidak dapat memprediksi output berikutnya dengan keuntungan yang lebih baik dari yang dapat diabaikan. Syscall getrandom() Linux (ditambahkan di kernel 3.17, Oktober 2014) dan /dev/urandom yang mendasarinya menggunakan generator berbasis-ChaCha20 yang diseed oleh sumber entropi hardware (RDRAND, timing interrupt, audio noise). Windows BCryptGenRandom menggunakan konstruksi AES-CTR-DRBG (NIST SP 800-90A) yang diseed dari beberapa sumber entropi. macOS / iOS menggunakan CSPRNG turunan-Fortuna. Perbedaan antara PRNG dan CSPRNG sangat penting: PRNG baik-baik saja untuk keacakan game, bucketing A/B test atau simulasi; untuk apa pun yang mungkin coba diprediksi penyerang (token sesi, pembuatan kata sandi, ID keamanan), hanya CSPRNG yang aman.

Dua API Acak JavaScript

Math.random() adalah API yang lebih lama dan lebih sederhana: mengembalikan angka floating-point yang didistribusikan secara seragam di [0, 1). Spesifikasi ECMAScript sengaja meninggalkan algoritma yang mendasarinya tidak ditentukan ("distribusi seragam antara 0 dan 1, eksklusif"), dan mesin telah mengubah apa yang mereka gunakan selama bertahun-tahun. V8 (Chrome) menggunakan LCG Park-Miller hingga 2015, kemudian beralih ke xorshift128+ untuk properti statistik yang lebih baik. SpiderMonkey (Firefox) dan JavaScriptCore (Safari) menggunakan generator non-kriptografis cepat yang serupa. Math.random() cepat dan cukup seragam untuk mekanika game, simulasi, dan aplikasi apa pun di mana ketidakdapatdiprediksian bukan persyaratan keamanan. Itu tidak aman secara kriptografis: periodenya ditentukan oleh implementasi, status dapat dipulihkan dari sejumlah kecil output, dan urutannya tidak aman untuk pembuatan kata sandi atau kasus penggunaan sensitif keamanan. crypto.getRandomValues() adalah CSPRNG Web Crypto API. Ia mengisi typed array dengan byte acak yang aman secara kriptografis yang ditarik dari CSPRNG sistem operasi (sumber yang sama yang digunakan TLS untuk kunci sesi). Tersedia di semua browser modern sejak sekitar 2014; ukuran buffer maksimum dalam satu panggilan adalah 65.536 byte. Pilihan yang tepat untuk angka acak apa pun yang penting: pembuatan token, ID keamanan, pembuatan kata sandi, apa pun yang mungkin coba diprediksi penyerang.

Perangkap Bias Modulo

Menghasilkan integer seragam dalam rentang tertentu dari CSPRNG lebih sulit daripada yang terlihat. Pendekatan naif: crypto.getRandomValues(new Uint8Array(1))[0] % 6 untuk lemparan dadu: menghasilkan distribusi yang bias karena 256 tidak terbagi rata oleh 6. Nilai 0-3 masing-masing terjadi 43 kali dalam rentang 0-255; nilai 4-5 terjadi 42 kali. Bias kecil untuk rentang kecil tetapi nyata, dan dapat dideteksi dalam jangka panjang. Perbaikan standarnya adalah rejection sampling: hasilkan byte acak, uji apakah jatuh dalam kelipatan terbesar dari rentang Anda yang sesuai (di sini, 252 = 42 × 6), gunakan jika ya, buang dan coba lagi jika tidak. Tingkat pembuangan dibatasi oleh (rentang / pangkat-2-berikutnya), jadi untuk "1-6" Anda membuang sekitar 1,5% byte; untuk "1-1000000" terhadap int acak 32-bit Anda membuang sekitar 0,02%. Setiap pustaka acak yang serius mengimplementasikan rejection sampling; Math.floor(Math.random() * (max - min + 1)) + min berbasis-Math.random() menghindari bias karena presisi Math.random() cukup tinggi (53 bit mantissa) sehingga bias berada di bawah level yang dapat dideteksi manusia untuk rentang yang masuk akal. Generator ini menggunakan output CSPRNG dengan rejection sampling: output seragam di seluruh rentang integer apa pun yang Anda minta.

Kasus Penggunaan: dan Tingkat Keacakan yang Dibutuhkan Masing-masing

• Pengundian lotere dan undian. Untuk pengundian non-moneter (pertukaran kantor, penugasan tim hackathon, tempat duduk kelas), Math.random() baik-baik saja. Untuk pengundian moneter atau apa pun yang diatur, gunakan CSPRNG dan idealnya publikasikan seed untuk dapat diverifikasi.
• Mekanika game. Lemparan dadu, pengocokan kartu, drop loot, generasi prosedural. Math.random() adalah pilihan standar: cepat, cukup seragam, cukup tidak dapat diprediksi sehingga pemain tidak akan melihat pola. CSPRNG dicadangkan untuk game kartu online di mana sisi server perlu mencegah kecurangan.
• Penugasan bucket A/B test. Hash ID pengguna dengan rahasia stabil untuk menempatkan setiap pengguna secara deterministik ke dalam bucket: menggunakan Math.random() akan berarti pengguna mendarat di bucket yang berbeda di seluruh pemuatan halaman, yang akan mengalahkan eksperimen. Penugasan berbasis-hash adalah pola yang tepat; keacakan hanya digunakan untuk memilih seed eksperimen, sekali.
• Pengambilan sampel acak untuk survei. Menggambar subset representatif dari populasi. Math.random() baik-baik saja; pertanyaan statistiknya adalah apakah sampel Anda cukup besar, bukan apakah sumber acak adalah kriptografis.
• Pembuatan data uji. Faker, data mockup, fixture database sintetis. Math.random() dengan seed tetap (untuk reproduksibilitas) adalah pilihan yang tepat.
• Kunci kriptografis, token sesi, pembuatan kata sandi. Hanya CSPRNG: crypto.getRandomValues() di browser, modul secrets di Python, crypto/rand di Go, jangan pernah random default bahasa. Bug di lapisan ini mengkompromikan semua yang bergantung padanya; konsekuensinya berkisar dari "sesi semua orang dapat dibajak" hingga "kunci enkripsi dapat dipulihkan."

RANDOM.ORG dan Perbedaan Keacakan Sejati

RANDOM.ORG diluncurkan pada 1998 oleh Mads Haahr di Trinity College Dublin dan tetap menjadi standar emas untuk "keacakan sejati" online. Di mana setiap CSPRNG akhirnya menurunkan bitnya dari transformasi algoritmik dari status yang diseed-hardware (proses deterministik, bahkan jika tidak dapat diprediksi penyerang), RANDOM.ORG mengukur noise atmosfer dari penerima radio dan mengonversi noise analog langsung ke bit. Ini menjadikannya True Random Number Generator (TRNG) daripada Pseudo-Random Number Generator: bitnya berasal dari proses fisik yang benar-benar non-deterministik, bukan dari algoritma deterministik. RANDOM.ORG digunakan oleh operator lotere, peneliti akademis yang menjalankan studi double-blind, dan game di mana keacakan yang dapat diverifikasi penting. Trade-off-nya: round-trip jaringan per permintaan, kuota harian untuk tier gratis, dan pertanyaan filosofis apakah Anda mempercayai sumber entropi yang diklaim RANDOM.ORG atas CSPRNG lokal Anda. Untuk sebagian besar kasus penggunaan, CSPRNG lokal sudah cukup; untuk kasus di mana pihak ketiga perlu memverifikasi keacakan secara independen, RANDOM.ORG menyediakan sertifikat keacakan yang ditandatangani sebagai layanan berbayar.

Pengambilan Sampel Tanpa-Penggantian: Fisher-Yates Shuffle

Ketika Anda membutuhkan N angka unik dari rentang: menggambar 6 angka dari 1-49 untuk lotere, memilih 10 pemenang dari 1000 peserta: pendekatan naif "hasilkan dan tolak jika duplikat" bekerja untuk N kecil tetapi memburuk tajam saat N mendekati ukuran rentang (peluang menggambar angka segar turun saat pool menyusut). Algoritma standarnya adalah Fisher-Yates shuffle, berasal dari tabel statistik Fisher dan Yates 1938 dan diberi bentuk informatika modernnya oleh Donald Knuth pada 1969 (kadang-kadang disebut Knuth shuffle). Algoritmanya sangat sederhana: tulis angka 1 hingga N ke array; untuk i dari N-1 ke bawah ke 1, tukar elemen i dengan elemen acak antara 0 dan i (inklusif); array sekarang dikocok secara seragam. Ambil K elemen pertama untuk K angka acak unik. Detail penting: indeks acak harus dalam [0, i], inklusif: menggunakan [0, i-1] memperkenalkan bias halus yang membutuhkan bertahun-tahun bagi komunitas kriptografis untuk dikarakterisasi (varian Sattolo, kadang-kadang salah digunakan menggantikan Fisher-Yates yang sebenarnya). Untuk rentang yang sangat besar di mana mengalokasikan array dari semua N nilai tidak praktis (misalnya memilih 100 nilai unik dari 1-10⁹), reservoir sampling (Vitter, 1985) menangani input streaming atau tak terbatas dalam sekali jalan dengan memori terbatas.

Konvensi Lemparan Dadu

Generator angka acak adalah dadu yang menyamar. D6 (dadu enam-sisi) adalah default game papan universal, rentang 1-6. D20 (dadu dua-puluh-sisi) adalah dadu ikonik Dungeons & Dragons yang digunakan untuk pemeriksaan kemampuan, lemparan serangan, dan lemparan penyelamatan: sistem modifier D&D berarti satu lemparan D20 plus bonus stat menentukan hasil sebagian besar tindakan. D100 (persentil, 1-100) digunakan untuk lemparan persentil di Call of Cthulhu, Warhammer Roleplay, dan banyak sistem peluang-kritikal. Notasi NdM berarti "lempar N dadu dengan M sisi masing-masing dan jumlahkan"; NdM+B menambahkan bonus. 3d6 melempar tiga dadu enam-sisi dan menjumlahkan (rentang 3-18, rentang skor-kemampuan klasik D&D, dengan distribusi triangular yang berpusat di 10-11). Untuk simulasi yang adil, menghasilkan integer seragam di [1, M] untuk setiap dadu dan menjumlahkan adalah persis setara dengan melempar dadu fisik: distribusi CSPRNG yang mendasarinya lebih seragam daripada dadu fisik mana pun yang dapat Anda beli. Kasino dan game yang diatur menggunakan RNG bersertifikat yang diuji terhadap baterai statistik (BigCrush TestU01, NIST SP 800-22) untuk membuktikan keseragaman kepada regulator game; standar yang sama berlaku untuk RNG lotere.

Seeding dan Reproduksibilitas

Properti halus tetapi penting dari PRNG: mereka deterministik diberi seed. Atur seed ke nilai yang diketahui, dan urutan angka "acak" tepat dapat direproduksi. Ini sangat berharga untuk pengujian (unit test yang menggunakan data acak harus mengatur seed tetap sehingga kegagalan dapat direproduksi) dan untuk undian yang dapat diverifikasi (publikasikan seed sebelum menggambar, kemudian siapa pun dapat memverifikasi hasilnya). Modul random Python memiliki random.seed(value) untuk ini; Random Java mengambil seed di konstruktor. Math.random() JavaScript sengaja tidak mengekspos API seeding: mesin memperlakukan seed sebagai status internal: tetapi beberapa pustaka pure-JS (seedrandom, pcg-random) menyediakan PRNG yang diseed. CSPRNG berbeda berdasarkan desain: mereka tidak mengekspos seeding karena seluruh poinnya adalah ketidakdapatdiprediksian. Jika Anda membutuhkan reproduksibilitas, gunakan PRNG dengan seeding eksplisit; jika Anda membutuhkan keamanan, gunakan CSPRNG dan terima bahwa Anda tidak dapat mereproduksi urutan nanti.

Privasi: Mengapa Hanya-Browser Bahkan untuk Angka Acak

Angka acak itu sendiri jarang berisi informasi sensitif, jadi mengapa arsitektur browser-only penting? Dua alasan. Pertama, ketika angka acak digunakan sebagai token sesi, kunci idempotensi, tantangan autentikasi, atau nilai mirip-rahasia lainnya, menghasilkannya di server pihak ketiga berarti server itu melihat nilai sebelum Anda menggunakannya: eksposur kecil tetapi nyata. Kedua, generator sisi-server yang menjanjikan "keacakan kriptografis" tidak dapat diverifikasi oleh pengguna; server yang buggy atau berbahaya dapat mengembalikan nilai non-acak atau bias yang terlihat acak, dan Anda tidak akan memiliki cara untuk mendeteksi bias tanpa pengambilan sampel masif. Generator browser-only menjalankan panggilan crypto.getRandomValues() yang sama yang akan dijalankan aplikasi Anda di sisi server; entropi berasal dari sumber sistem operasi yang sama (Linux getrandom(), Windows BCryptGenRandom, macOS); tidak ada pihak ketiga yang melihat output. Anda dapat memverifikasi dengan membuka tab Network DevTools saat Anda mengklik Generate: tidak ada permintaan keluar. Bawa halaman offline (mode pesawat) setelah dimuat dan generator masih berfungsi.

Pertanyaan yang Sering Diajukan