Cara Menghasilkan Angka Benar-benar Acak (dan Jenis Mana yang Anda Butuhkan)

Jawaban singkatnya

Pilih generator berdasarkan apa yang Anda tanggung kalau ada orang menebak angka Anda. Kalau tebakan itu berharga, misalnya akun, kunci, atau undian yang harus adil, pakai generator aman kriptografis milik platform Anda: crypto.getRandomValues di peramban, modul secrets di Python, atau sumber entropi sistem operasi yang keduanya bertumpu. Kalau tebakan tidak merugikan apa pun, misalnya lemparan dadu dalam game atau simulasi Monte Carlo, generator pseudorandom biasa dengan seed lebih cepat dan hasilnya bisa diulang, dan itulah yang Anda inginkan di sana.

Dua aturan menangkap hampir semua kesalahan nyata. Jangan pernah memakai Math.random() atau rand() bahasa C untuk membuat rahasia. Dan jangan pernah mempersempit nilai acak yang lebih lebar ke rentang Anda dengan operator sisa lalu menganggapnya selesai, karena itu memunculkan bias modulo, yaitu alasan mengapa alat tertaut itu menggambar ulang nilai alih-alih mempercayai satu operasi sisa.

• Rahasia, token, kunci, atau undian yang bisa digugat orang: selalu CSPRNG platform.
• Simulasi, sampling, atau apa pun yang ingin Anda jalankan dua kali dengan hasil yang sama: generator dengan seed.
• Keacakan fisik sejati: perangkat keras atau layanan entropi, tidak bisa dicapai dari sebuah halaman web.
• Alat tertaut ini adalah kasus peramban: bilangan bulat seragam pada rentang inklusif, dari CSPRNG sistem operasi, dengan rejection sampling, sampai 500 angka sekali jalan.

Tiga hal berbeda yang sama-sama disebut acak

Satu kata menutupi tiga mekanisme dengan tiga jaminan yang berbeda. Bacanya sebagai tangga: makin ke atas, makin sulit ditebak.

Keacakan sejati datang dari fisika

Generator angka acak sejati mengambil sampel proses fisik yang hasilnya tidak ditentukan oleh apa pun yang bisa Anda ukur: derau termal pada resistor, waktu peluruhan radioaktif, derau atmosfer yang ditangkap penerima radio, jitter osilator. Perangkat kerasnya ada, produsen cip mengeksposekannya sebagai instruksi atau periferal, dan layanan publik mengalirkan derau atmosfer yang sudah disampling untuk siapa pun yang meminta. Hasilnya tidak bisa ditebak secara prinsip, sebab seberapa besar pun komputasi tidak akan memulihkannya. Tapi sumber mentah tidak seragam: elektroniknya menyisakan sedikit lebih banyak satu simbol daripada simbol lain, jadi generator perangkat keras mengkondisikan sampel lewat pengekstrak keacakan sebelum ada yang menyebut keluarannya acak.

Pseudorandom yang aman secara kriptografis

CSPRNG adalah algoritme deterministik yang memegang keadaan internal rahasia, diberi seed sekali dari entropi nyata, lalu dijalankan maju dengan komputasi. Sistem operasi mengambil seed itu dari sumber-sumber yang bisa ia amati, seperti waktu interupsi, jeda kedatangan keyboard dan mouse, serta derau perangkat keras kalau ada driver yang mengeksposekannya, di dalam pool yang dilindungi kernel. Setiap panggilan ke crypto.getRandomValues mengambil dari pool itu, atau dari generator yang sistem operasi beri seed darinya.

Jaminannya praktis, bukan filosofis: penyerang yang mengamati keluaran sepanjang apa pun tetap tidak bisa menemukan keadaannya, jadi ia tidak bisa menebak nilai berikutnya atau merekonstruksi nilai-nilai sebelumnya. Itu properti yang dibutuhkan kunci dan token, dan itu pula alasan bahwa tingkat inilah, bukan tingkat fisika, yang dipakai perangkat lunak sehari-hari.

Pseudorandom biasa

Generator biasa adalah konstruksi yang sama dengan syarat keamanannya dicabut: relasi rekurens deterministik di atas keadaan tetap, yang dipilih karena cepat dan berkualitas secara statistik. Modul random milik Python mengimplementasikan Mersenne Twister, yang distribusinya sangat indah tapi bisa ditebak sepenuhnya begitu pengamat mengumpulkan cukup banyak keluaran berurutan untuk menyelesaikan keadaannya.

Inilah alat yang tepat untuk simulasi: cepat, bisa diuji dengan baterai uji statistik, dan bisa diatur, karena seed yang sama memberi arus yang sama. Itu keunggulan di eksperimen Monte Carlo dan bencana di token sesi, dan itu perbedaan yang paling sering dibalik oleh orang.

Yang bisa diberikan peramban dengan jujur

Terang-terangan dulu: halaman web tidak bisa memanen entropi fisik. JavaScript tidak bisa mengambil sampel sumber derau, tidak punya instruksi untuk membaca keacakan perangkat keras, dan tidak bisa mengukur waktu elektron. Apa pun yang diberikan peramban datang dari algoritme yang keadaannya diberi seed oleh sistem operasi.

Yang bisa diberikan peramban adalah CSPRNG sistem operasi, dibungkus sebagai crypto.getRandomValues, yang mengisi array bertipe dengan byte atau kata 32 bit dari pool kernel. Web Crypto mengekspose persis satu primitif dan primitif itu adalah yang kriptografis, jadi tidak ada panggilan yang lebih lemah untuk ditabrak, dan halaman alat tertaut menyebutnya sebagai primitif yang sama yang dipakai untuk kata sandi dan kunci enkripsi.

Untuk semua keperluan pembaca halaman ini, jawaban berbasis CSPRNG adalah jawaban yang benar. Undian, pengenal sesi, kata sandi yang dibuat di laptop Anda: tidak ada yang butuh peluruhan radioaktif, dan semuanya dilayani oleh generator yang tidak bisa ditebak penyerang. Halaman yang mengiklankan “keacakan sejati” dari sebuah tab sedang ceroboh atau tidak jujur; klaim yang benar adalah “tidak bisa ditebak oleh siapa pun yang belum menguasai sistem operasi Anda”, dan itu sudah cukup.

Kenapa Math.random() bukan untuk rahasia

Keberatannya mekanis. Math.random() adalah fungsi deterministik dari keadaan internal: mesinnya memegang sekumpulan angka, menerapkan relasi rekurens tetap untuk memajukannya, mengembalikan hasil yang sudah diformat, dan tidak menengok apa pun dari luar di antaranya. Urutannya sudah tersirat dari keadaan, jadi satu-satunya pertanyaan adalah apakah pengamat bisa menemukan keadaan itu.

Untuk waktu yang lama jawabannya dengan nyaman iya. Generator yang dipakai peramban adalah rancangan statistik berkeadaan kecil yang keluarannya membocorkan struktur: beberapa nilai berurutan sudah cukup untuk menyusun persamaan yang solusinya adalah keadaan itu. Kalau Anda punya keadaannya, jalankan rekurens ke depan untuk menebak semua ambilan setelahnya dan ke belakang untuk memulihkan semua yang sebelumnya; itulah mode kegagalan terdokumentasi yang membuat peramban meninggalkan rancangan tersebut.

Ada lapisan kedua. Anda tidak pernah melihat keadaannya, jadi Anda tidak bisa memeriksa bahwa keadaan itu pernah benar-benar tak terduga, dan generator yang diberi seed secara malas dari jam kasar punya ruang pencarian yang bisa didaftarkan penyerang.

crypto.getRandomValues dibangun dengan arah sebaliknya: mengamati keluaran tidak membantu Anda merekonstruksi keadaan, jadi menebak angka Anda butuh kerja sebanding dengan besarnya rentang, bukan sebanding dengan beberapa sampel.

Bias modulo, dengan angka yang bisa Anda cek

Bagian yang sering disalahkan atau dilewati artikel adalah aritmetika yang bisa Anda periksa dengan tangan. Anggap sumber Anda mengeluarkan satu byte seragam, yaitu salah satu dari 256 nilai, 0 sampai 255, masing-masing dengan peluang 1 dari 256, dan Anda ingin satu digit seragam dari 0 sampai 9. Satu baris yang menggoda adalah sisa pembagian dengan 10.

Hitung berapa nilai byte jatuh ke tiap digit. 256 dibagi 10 adalah 25 dengan sisa 6; persisnya, 256 = 25 × 10 + 6. Tiap digit mendapat 25 nilai dan 6 sisanya tertinggal di ujung atas rentang, dan sisa itu jatuh ke digit-digit terendah: hasil 0 sampai 5 mendapat 26 nilai pendukung masing-masing, hasil 6 sampai 9 mendapat 25. Totalnya cocok, karena 6 × 26 adalah 156, 4 × 25 adalah 100, dan 156 + 100 = 256.

Digit yang diuntungkan punya peluang 26/256, yaitu 0.1015625; digit yang dirugikan 25/256, yaitu 0.09765625; undian yang adil memberi 0.1 untuk tiap digit. Digit yang diuntungkan 26/25 kali lebih mungkin daripada yang lain, dan 26/25 adalah persis 1.04, artinya empat persen lebih mungkin.

Kapan bias berhenti jadi sekadar teori

Empat persen masih lembut. Bias jadi serius ketika rentang Anda merupakan bagian besar dari sumber, karena hanya ada beberapa lintasan penuh dan blok sisanya menjadi sangat besar secara proporsional. Generator tertaut mengambil kata 32 bit, jadi sumbernya punya 2^32 nilai, yaitu 4,294,967,296.

Kasus ramah: dadu enam sisi, min 1 dan max 6, ukuran rentang 6. Pembagian: 4,294,967,296 = 6 × 715,827,882 + 4. Sisa biasa menguntungkan empat sisi, yaitu sisi 1 sampai 4 berasal dari 715,827,883 masukan masing-masing, sementara sisi 5 dan 6 dari 715,827,882. Sekitar satu per miliar, itu sebabnya tidak ada permainan papan yang dicurangi dengan cara ini.

Kasus permusuhan: indeks lotere dari 0 sampai 2,147,483,646, yaitu rentang berisi 2^31 − 1 nilai. Dua kali rentang itu adalah 4,294,967,294, yang kurang 2 dari 4,294,967,296, jadi sisa memberi dua tiket pertama 3 peluang masing-masing dan semua tiket lainnya 2, yaitu keunggulan 50%, karena 3/2 persis 1.5.

Rejection sampling: solusinya

Buang ekor yang canggung alih-alih melipatnya. Pada kasus byte, 250 = 25 × 10 habis dibagi, jadi pertahankan hanya masukan 0 sampai 249 dan gambar ulang setiap kali Anda mendapatkan 250 ke atas. Tiap masukan yang diterima lalu memetakan ke sebuah digit lewat persis 25 nilai, dan 25/250 adalah persis 0.1. Biayanya adalah peluang gambar ulang sebesar 6/256 per percobaan, yang tidak berarti dan berhenti dengan pasti.

Generator tertaut melakukan hal yang sama di 32 bit. Ia menghitung limit = Math.floor(4294967296 / range) * range, yaitu kelipatan terbesar dari rentang Anda yang muat di sumber, mengambil satu kata, menggambar ulang selama nilainya sama dengan atau di atas batas itu, lalu mengembalikan min + (x % range). Untuk dadu, limit adalah 6 × 715,827,882, yaitu 4,294,967,292, jadi persis empat masukan tertinggi ditolak, dan peluang gambar ulang adalah 4 dari 4,294,967,296, atau 1 dari 1,073,741,824. Dengan syarat diterima, tiap sisi punya 715,827,882 masukan pendukung dan 6 × 715,827,882 = 4,294,967,292, jadi tiap sisi persis seperenam. Tulisan alat itu sendiri menyebutnya tanpa aljabar: nilai yang diambil di luar kelipatan terbesar dari rentang Anda yang muat di 32 bit dibuang dan digambar ulang, dan inilah yang menghapus bias modulo.

Seragam, dengan seed, bisa diulang: tiga ide yang terpisah

Istilah “angka acak” juga menyembunyikan pertanyaan tentang bentuk: distribusinya, seed-nya, dan apakah sekali jalan bisa diulang.

Keseragaman adalah properti distribusi

Ambilan seragam berarti setiap nilai di rentang Anda punya peluang yang sama, seperti dadu, undian, atau indeks acak. Ambilan tidak seragam membentuk peluang dengan sengaja: derau pengukuran normal, celah eksponensial antar kedatangan, atau sampling berbobot di mana item A tiga kali lebih mungkin daripada item B. Simulasi menghabiskan sebagian besar tenaganya pada kasus tidak seragam, dan teknik standarnya adalah mulai dari arus seragam lalu mengubahnya.

Alat tertaut ini hanya seragam pada rentang bilangan bulat: kurva lonceng, pilihan berbobot, atau angka desimal adalah pekerjaan yang berbeda.

Apa sebenarnya seed itu

Seed adalah keadaan awal sebuah generator deterministik. Generator yang sama, seed yang sama, urutan keluaran yang sama, selamanya. Menetapkan seed tidak menambah keacakan; ia menetapkan titik awal sebuah komputasi supaya prosesnya bisa diulang.

Itu sebabnya generator dengan seed sangat dicintai di simulasi: kolega mengulang eksperimen Anda dan memperoleh angka Anda, sebuah paper menerbitkan seed-nya untuk ditinjau. Bisa ditebak justru tujuannya, dan CSPRNG tanpa seed menghalangi karena Anda tidak bisa menunjukkan urutan di balik kesimpulan Anda.

Kenapa bisa diulang adalah tujuan yang salah untuk rahasia

Balikkan properti itu dan ia menjadi lubangnya: generator rahasia yang bisa diulang adalah generator yang bisa ditebak. Siapa pun yang mengetahui atau menebak seed akan membangkitkan ulang semua nilai yang Anda keluarkan, berurutan, dan rahasia yang bisa dibangkitkan ulang orang lain bukan rahasia.

Jadi alat-alat yang membangkitkan kunci dan token menolak mengekspose seed. Generator tertaut tidak punya masukan seed dan tidak ada cara memutar ulang sebuah proses; tiap ambilan datang segar dari pool sistem operasi, dan keadaannya hidup di kernel, bukan di halaman.

Di Python, C++, JavaScript, dan MATLAB

Setiap varian bahasa dari pencarian ini punya jawaban yang sama di bawah sintaksnya: pakai generator aman kriptografis milik platform, bukan yang mainan. Di dua di antara bahasa-bahasa ini, pustaka standar tidak menyediakannya sepenuhnya.

Python membagi pekerjaannya dengan sengaja. random adalah modul pseudorandom, berbasis Mersenne Twister, baik untuk game dan simulasi, dan didokumentasikan tidak layak untuk keamanan. Untuk rahasia pakai modul secrets: secrets.randbelow(n) mengembalikan nilai seragam dari 0 sampai n−1 dari sumber entropi sistem operasi, dan secrets.token_urlsafe mengurus token. Untuk simulasi yang bisa diulang, beri seed dengan random.seed(1234) dan tetap di random.

C++ tidak punya CSPRNG di pustaka standarnya, dan itulah jawaban jujur untuk autocomplete tersebut. std::random_device adalah pegangan yang diniatkan ke entropi non-deterministik dan hal yang tepat untuk memberi seed sebuah mesin, tapi perilahnya ditentukan implementasi: pada beberapa toolchain ia meneruskan langsung ke sumber sistem operasi, pada yang lain ia jatuh ke mesin pseudorandom dengan seed, ia bisa memblokir sementara pool kernel terisi di awal boot, dan keseragaman tiap hasil tidak dijamin. std::mt19937 secara eksplisit adalah generator statistik, dan rand() warisan bahasa C tidak seragam di bawah operasi sisa maupun tidak bisa ditebak. Kalau itu benar-benar penting, panggil API entropi milik platform atau pustaka kriptografi yang sudah diverifikasi.

JavaScript di peramban cukup satu panggilan: crypto.getRandomValues ke sebuah array bertipe, dan itulah yang dipakai alat tertaut ini; global yang sama juga ada di Node dan Deno. Untuk bilangan bulat tanpa bias, pasangkan dengan rejection sampling alih-alih mengalikan sebuah float.

MATLAB pantas mendapat satu baris karena yang mencarinya meminta “angka real acak” dan “angka acak yang nyata”. Fungsi-fungsi serbagunanya, yaitu rand, randi, dan randn dengan rng yang mengatur seed, bersifat pseudorandom karena rancangannya: deterministik, bisa diberi seed, sangat baik secara statistik, dan ditujukan untuk kerja numerik yang bisa diulang. Sumber entropi sejati adalah hal berbeda, dan mendapatkannya berarti harus memakai fasilitas sistem operasi atau layanan eksternal.

Aturan yang menutupi keempatnya: CSPRNG platform ketika angka yang bisa ditebak merugikan Anda, generator statistik dengan seed ketika bisa ditebak justru menguntungkan. Tidak ada jalan tengah.

Untuk apa Anda butuh keacakan, dan apa yang rusak kalau keacakannya lemah

Kunci, kata sandi, dan apa pun yang diturunkan dari keduanya. Kelemahannya di sini adalah aritmetika: penyerang mendaftarkan ruang yang masuk akal, dan tiap ambilan seragam yang bebas dari m nilai menambah log2(m) bit; satu byte menambah 8 bit karena 2^8 = 256, sedangkan sepuluh nilai menambah sedikit lebih dari 3, karena log2(10) sekitar 3.32. Empat digit kurang dari 14 bit, yaitu sepuluh ribu terkaan yang bisa didaftar; tiga puluh dua byte adalah 256 bit, yang tidak akan didaftar siapa pun. Generator yang keadaannya bisa direkonstruksi, atau seed yang diambil dari jam, meruntuhkan angka itu sampai seukuran seed.

Token: pengenal sesi, tautan reset, kunci API. Ada dua cara kalah. Bisa ditebak membuat penyerang memalsukan token berikutnya alih-alih mencari token Anda. Tabrakan lebih halus: token datang dari pool yang terbatas, jadi mengeluarkan banyak token pendek akhirnya memberi dua pengguna string yang sama, dan sesi yang sudah terautentikasi milik satu orang jadi milik orang lain. Sesuaikan ukuran token dengan volume yang Anda keluarkan, dan mengambillah dari CSPRNG.

Undian dan lotere, seperti undian berhadiah, pemilihan siswa, atau sampling audit. Yang dibutuhkan adalah bisa dibela di depan orang, bukan dirahasiakan: setelahnya ada yang bertanya apakah prosesnya bisa menguntungkan satu peserta, dan Anda butuh jawaban. Bias modulo adalah cara klasik undian yang berniat baik menjadi tidak adil, dan bisa ditebak adalah cara undian diatur lebih dulu. Pakai generator kriptografis dengan rejection sampling, simpan daftar peserta dan hasilnya, dan jangan biarkan pemenangnya yang menulis skripnya.

Sampling dan simulasi: integrasi Monte Carlo, bootstrap, lalu lintas uji beban. Di sini Anda ingin kualitas statistik dan hasil yang bisa diulang, dan CSPRNG salah di dua arah: lebih lambat, dan tidak bisa memutar ulang sebuah proses. Pakai generator statistik dengan seed dan catat seed-nya. Untuk keacakan yang cuma hiasan, tidak ada yang rusak.

Mode kegagalan yang umum

Empat pola menjelaskan sebagian besar keacakan yang rusak di kode nyata, dan keempatnya tampak baik-baik saja saat uji cepat.

Mengarang pengocokan sendiri. Versi yang menggoda, yaitu untuk tiap posisi tukar dengan elemen yang dipilih dari mana saja di array, itu bias sehingga beberapa urutan lebih mungkin daripada yang lain. Langkah Fisher–Yates yang benar menukar tiap elemen dengan posisi yang diambil seragam pada atau setelah posisi itu, dan kalau urutan melindungi sesuatu, ambilan-ambilan itu butuh CSPRNG. Versi ceroboh tidak bisa disetel menjadi benar: memilih indeks untuk masing-masing dari n posisi menghasilkan n^n jalur yang sama mungkin, yang terbagi rata di antara n! urutan hanya kalau n! habis membagi n^n, dan untuk satu setumpak 52 kartu itu tidak terjadi, karena 52^52 hanya punya 2 dan 13 sebagai faktor prima sedangkan 52! mencakup 3.

rand() % n, atau sisa apa pun di atas sumber yang tidak habis dibagi. Hasil-hasil rendah mengumpulkan sisa pembagiannya, kemiringannya tidak terlihat dalam pemakaian biasa, dan itu menentukan ketika rentangnya merupakan bagian besar dari sumber. Rejection sampling solusinya, bukan sumber yang lebih lebar, karena 10 juga tidak habis membagi 65,536.

Memberi seed dari jam. Seed berupa stempel waktu meninggalkan ruang pencarian yang bisa didaftar: penyerang yang tahu token Anda muncul pada satu menit tertentu mencoba sekitar 60 seed di menit itu lalu menjalankan tiap generator ke depan. Seed dari jam juga bertabrakan: dua proses yang dimulai bersamaan mendapat seed yang sama dan mengeluarkan arus yang identik.

Memakai seed berulang, atau satu arus untuk dua keperluan. Seed yang sama memberi urutan yang sama, jadi dua komponen yang seed-nya sama menghasilkan nilai yang cocok, dan memulihkan yang satu memulihkan yang lain. Mengambillah secara bebas, per keperluan, dari CSPRNG, dan kalau rancangan Anda butuh dua nilai berbeda, periksa bahwa keduanya berbeda alih-alih berharap ambilan yang bebas tidak saling bertemu.

Generator tertaut: apa yang ia lakukan dan di mana ia berhenti

Alat di balik tombol ini adalah kasus peramban, dibangun sesuai argumen bagian-bagian di atas. Anda menetapkan minimum dan maksimum inklusif serta banyaknya bilangan bulat; alat ini mengambil tiap nilai dengan crypto.getRandomValues ke sebuah Uint32Array dan menerapkan rejection sampling, yaitu limit = Math.floor(4294967296 / range) * range, lalu menggambar ulang selama kata itu sama dengan atau di atas batas tersebut, kemudian mengembalikan min + (x % range). Keluarannya tidak membuat nilai mana pun lebih mungkin karena posisinya di rentang Anda.

Kendaliannya memang kecil. Ujung-ujungnya inklusif, jadi 1 sampai 6 adalah dadu, dan max sama dengan min diperbolehkan. Nilai negatif juga boleh, dan masukan untuk kedua ujung adalah teks tanpa batas. Hasil dicetak satu per baris atau dipisahkan koma, dan tombol Copy menaruhnya di papan klip. Mode tanpa duplikat yang bersifat opsional menyimpan tiap nilai di sebuah set dan menggambar ulang sampai penuh, serta memberi galat ketika Anda meminta lebih banyak nilai daripada yang ada di rentang. Yang tidak dilakukannya adalah bagian jujurnya.

• Hanya bilangan bulat, tidak ada angka desimal atau float; bilangan real seragam dalam suatu interval adalah alat lain.
• Hanya seragam, tidak ada ambilan berbobot, normal, atau eksponensial.
• Sampai 500 angka sekali jalan; nasihat alat itu sendiri kalau Anda butuh lebih banyak adalah menjalankannya beberapa kali lalu menggabungkan hasilnya.
• Tidak ada kontrol seed dan tidak ada proses yang bisa diulang, dan itu disengaja: urutan yang bisa Anda ulangi adalah urutan yang bisa orang lain ulangi juga.
• Tidak ada daftar pengecualian; Anda tidak bisa mengambil 1 sampai 100 sambil melompati kelipatan 5.
• Rentang yang mencakup lebih dari 2^32 nilai tidak didukung, karena batas penolakan mengandaikan sumber 32 bit.
• Tidak ada yang disimpan, diekspor, atau diunduh: tutup tab dan angkanya hilang.
• Logika pembangkitannya sendiri tidak melakukan permintaan apa pun, hanya API kriptografi, DOM, dan papan klip, tapi situs ini memuat skrip pihak ketiga, jadi halaman ini tidak bebas jaringan dan tidak mengaku demikian.

Pertanyaan yang sering diajukan