Pertanyaan Bagaimana pseudorandom dan nomor acak yang benar-benar berbeda dan mengapa itu penting?


Saya tidak pernah benar-benar mendapatkan ini. Katakan saja Anda menulis program kecil dalam bahasa apa pun yang menghasilkan beberapa dadu (hanya menggunakan dadu sebagai contoh). Setelah 600.000 gulung, setiap angka akan digulirkan sekitar 100.000 kali, itulah yang saya harapkan.

Mengapa ada situs web yang didedikasikan untuk 'keacakan sejati'? Tentunya, berdasarkan pengamatan di atas, peluang untuk mendapatkan angka apa pun hampir sama persis dengan berapa banyak angka yang dapat dipilihnya.

Saya mencobanya Python: Inilah hasil dari 60 juta gulungan. Variasi tertinggi seperti 0,15. Bukankah itu acak seperti itu?

1 - 9997653 2347.0
2 - 9997789 2211.0
3 - 9996853 3147.0
4 - 10006533 -6533.0
5 - 10002774 -2774.0
6 - 9998398 1602.0

651


asal


Lihatlah artikel wikipedia di perangkat keras yang menghasilkan angka acak Juga lihat ini - stats.stackexchange.com/questions/32794/… - steadyfish
Apa yang Anda maksud dengan "melempar beberapa dadu"? Apakah ada lengan robot dan kamera terpasang? - starblue
sementara saya setuju dengan intisari nada Anda, bahwa kita sering khawatir tentang hal ini terlalu banyak, tetapi telah dieksploitasi dalam kehidupan nyata: en.wikipedia.org/wiki/Ronald_Dale_Harris - Grady Player
Lihat ini artikel tentang permainan poker online kehilangan keacakan sejati untuk mengapa itu penting. - Varaquilex
Jika Anda hanya menyimpan 0-5 counter dan melempar dadu sesuai, 666 kali gorila, Anda akan mendapatkan distribusi yang sama juga. - jcora


Jawaban:


Mari kita bermain poker komputer, hanya Anda, saya dan server yang kami berdua percayai. Server menggunakan generator nomor pseudo-random yang diinisialisasi dengan seed 32 bit tepat sebelum kami bermain. Jadi ada sekitar empat miliar deck yang mungkin.

Saya mendapatkan lima kartu di tangan saya - tampaknya kami tidak bermain Texas Hold 'Em. Misalkan kartu dibagikan satu kepada saya, satu untuk Anda, satu untuk saya, satu untuk Anda, dan seterusnya. Jadi saya memiliki kartu pertama, ketiga, kelima, ketujuh dan kesembilan di dek.

Sebelumnya saya menjalankan generator nomor pseudo-random empat miliar kali, sekali dengan masing-masing benih, dan menuliskan kartu pertama yang dihasilkan untuk masing-masing ke dalam database. Misalkan kartu pertama saya adalah ratu sekop. Itu hanya menunjukkan satu sebagai kartu pertama di satu dari setiap 52 dek yang mungkin, jadi kami telah memotong dek yang mungkin dari empat miliar menjadi sekitar 80 juta atau lebih.

Misalkan kartu kedua saya adalah tiga hati. Sekarang saya menjalankan RNG 80 juta lebih banyak kali menggunakan 80 juta biji yang menghasilkan ratu sekop sebagai nomor pertama. Ini membutuhkan waktu beberapa detik. Saya menuliskan semua deck yang menghasilkan tiga hati sebagai kartu ketiga - kartu kedua di tangan saya. Itu lagi hanya sekitar 2% dari dek, jadi sekarang kita turun ke 2 juta deck.

Misalkan kartu ketiga di tangan saya adalah 7 klub. Saya memiliki database 2 juta biji yang menjual dua kartu saya; Saya menjalankan RNG saya 2 juta kali lagi untuk menemukan 2% dari deck yang menghasilkan 7 klub sebagai kartu ketiga, dan kami hanya mencapai 40 ribu deck.

Anda lihat bagaimana ini berjalan. Saya menjalankan RNG 40000 lebih banyak kali untuk menemukan semua benih yang menghasilkan kartu keempat saya, dan itu membuat kami turun menjadi 800 deck, dan kemudian menjalankannya 800 kali lebih banyak untuk mendapatkan ~ 20 biji yang menghasilkan kartu kelima saya, dan sekarang saya hanya menghasilkan dua puluh dek kartu dan saya tahu bahwa Anda memiliki salah satu dari dua puluh kemungkinan tangan. Selain itu, saya memiliki gagasan yang sangat bagus tentang apa yang akan saya gambar berikutnya.

Sekarang apakah Anda melihat mengapa keacakan sejati itu penting? Cara Anda menggambarkannya, Anda berpikir demikian distribusi itu penting, tetapi distribusi bukanlah apa yang membuat suatu proses acak. Ketidakpastian adalah apa yang membuat suatu proses acak.

MEMPERBARUI

Berdasarkan komentar (sekarang dihapus karena sifatnya yang tidak konstruktif), setidaknya 0,3% orang yang pernah membaca ini bingung dengan poin saya. Ketika orang-orang berdebat melawan poin yang saya belum buat, atau lebih buruk, berdebat untuk menunjukkan bahwa saya melakukan buat di asumsi bahwa saya tidak membuatnya, maka saya tahu bahwa saya harus menjelaskan dengan lebih jelas dan hati-hati.

Sepertinya ada kebingungan tertentu di sekitar kata itu distribusi jadi saya ingin memanggil penggunaan dengan hati-hati.

Pertanyaan-pertanyaan di tangan adalah:

  • Bagaimana nomor pseudorandom dan angka acak yang sebenarnya berbeda?
  • Mengapa perbedaan itu penting?
  • Apakah perbedaan ada hubungannya dengan distribusi output PRNG?

Mari kita mulai dengan mempertimbangkan sempurna cara untuk menghasilkan setumpuk kartu acak yang digunakan untuk bermain poker. Kemudian kita akan melihat bagaimana teknik lain untuk menghasilkan deck berbeda, dan jika mungkin untuk mengambil keuntungan dari perbedaan itu.

Mari kita mulai dengan mengandaikan bahwa kita memiliki kotak ajaib berlabel TRNG. Sebagai inputnya, kami memberikannya sebuah integer n lebih besar atau sama dengan satu, dan sebagai outputnya memberikan kita angka acak antara satu dan n, inklusif. Output dari kotak tersebut sepenuhnya tak terduga (bila diberi nomor selain dari satu) dan nomor apa pun antara satu dan n sama dengan yang lain; yaitu mengatakan bahwa distribusi aku s seragam. (Ada pemeriksaan statistik lebih lanjut lainnya tentang keacakan yang bisa kami lakukan; Saya mengabaikan poin ini karena tidak berhubungan dengan argumen saya. TRNG secara statistik acak dengan asumsi.)

Kami mulai dengan setumpuk kartu yang tidak tergoyahkan. Kami meminta kotak untuk nomor antara satu dan 52 - yaitu, TRNG(52). Berapa pun jumlah yang dikembalikan, kami menghitung banyak kartu dari dek yang kami sortir dan menghapus kartu itu. Ini menjadi kartu pertama di dek yang dikocok. Lalu kami meminta TRNG(51) dan lakukan hal yang sama untuk memilih kartu kedua, dan seterusnya.

Cara lain untuk melihatnya adalah: ada 52! = 52 x 51 x 50 ... x 2 x 1 kemungkinan dek, yang kira-kira 2226. Kami telah memilih salah satu dari mereka secara acak.

Sekarang kita berurusan dengan kartu. Ketika saya melihat kartu saya, saya punya tidak tahu sama sekali kartu apa yang kamu miliki. (Selain dari fakta yang jelas bahwa Anda tidak memiliki kartu yang saya miliki.) Mereka bisa menjadi kartu apa saja, dengan probabilitas yang sama.

Jadi biarkan saya memastikan bahwa saya menjelaskan ini dengan jelas. Kita punya distribusi seragam dari setiap output individu TRNG(n); masing-masing mengambil angka antara 1 dan n dengan probabilitas 1 / n. Juga, hasil dari proses ini adalah bahwa kami telah memilih salah satu dari 52! kemungkinan deck dengan probabilitas 1/52 !, jadi distribusi atas set deck yang mungkin aku s juga seragam.

Baiklah.

Sekarang anggaplah kita memiliki kotak ajaib yang kurang berlabel PRNG. Sebelum Anda bisa menggunakannya, itu pasti diunggulkan dengan nomor unsigned 32 bit.

KE SAMPING: Mengapa 32? Tidak bisakah itu diunggulkan dengan 64 atau 256 atau 10.000 bit number? Yakin. Tetapi (1) dalam praktiknya, PRNG yang paling terbuka adalah benih dengan nomor 32 bit, dan (2) jika Anda memiliki 10.000 bit keacakan untuk membuat benih, lalu mengapa Anda menggunakan PRNG sama sekali? Anda sudah memiliki sumber 10000 bit keacakan!

Lagi pula, kembali ke cara kerja PRNG: setelah diunggulkan, Anda dapat menggunakannya dengan cara yang sama seperti yang Anda gunakan TRNG. Artinya, Anda memberikannya angka n dan memberi Anda kembali angka antara 1 dan n inklusif. Bahkan, distribusi output yang kurang lebih seragam. Yaitu, ketika kami bertanya PRNG untuk angka antara 1 dan 6, kita mendapatkan 1, 2, 3, 4, 5 atau 6 setiap kira-kira seperenam waktu, tidak peduli apa pun biji itu.

Saya ingin menekankan hal ini beberapa kali karena tampaknya menjadi salah satu yang membingungkan komentator tertentu. Distribusi PRNG seragam setidaknya dalam dua cara. Pertama, anggaplah kita memilih benih tertentu. Kita harapkan urutannya PRNG(6), PRNG(6), PRNG(6)... satu juta kali akan menghasilkan distribusi angka yang seragam antara 1 dan 6. Dan kedua, jika kita memilih sejuta benih yang berbeda dan dipanggil PRNG(6)  sekali untuk setiap benih, sekali lagi kami mengharapkan distribusi angka yang seragam dari 1 hingga 6. Keseragaman PRNG di salah satu operasi ini tidak relevan dengan serangan yang saya gambarkan.

Proses ini dikatakan pseudo-random karena perilaku kotak sebenarnya sepenuhnya deterministik; itu memilih dari salah satu dari 232 kemungkinan perilaku berdasarkan benih. Yaitu, setelah itu diunggulkan, PRNG(6), PRNG(6), PRNG(6), ...  menghasilkan a urutan angka dengan distribusi seragam, tetapi urutan itu sepenuhnya ditentukan oleh benih. Untuk urutan panggilan tertentu, katakanlah, PRNG (52), PRNG (51) ... dan seterusnya, hanya ada 232 kemungkinan urutan. Benih itu pada dasarnya memilih yang mana yang kita dapatkan.

Untuk menghasilkan dek server sekarang menghasilkan benih. (Bagaimana? Kita akan kembali ke titik itu.) Lalu mereka menelepon PRNG(52), PRNG(51) dan seterusnya untuk menghasilkan dek, mirip dengan sebelumnya.

Sistem ini rentan terhadap serangan yang saya gambarkan. Untuk menyerang server, kami terlebih dahulu membanjiri salinan kotak kami sendiri dengan 0 dan meminta PRNG(52) dan tuliskan itu. Lalu kita kembali berbiji dengan 1, minta PRNG(52), dan tuliskan itu, semua jalan hingga 232-1.

Sekarang, server poker yang menggunakan PRNG untuk menghasilkan deck harus menghasilkan benih. Tidak masalah bagaimana mereka melakukannya. Mereka bisa menelepon TRNG(2^32) untuk mendapatkan benih yang benar-benar acak. Atau mereka bisa mengambil waktu saat ini sebagai benih, yang hampir tidak acak sama sekali; Aku tahu jam berapa sebanyak yang kamu lakukan. Intinya serangan saya adalah itu tidak masalah, karena saya punya database saya. Ketika saya melihat kartu pertama saya, saya dapat menghilangkan 98% dari biji yang mungkin. Ketika saya melihat kartu kedua saya, saya dapat menghilangkan 98% lebih banyak, dan seterusnya, sampai akhirnya saya bisa mendapatkan segenggam biji yang mungkin, dan tahu dengan kemungkinan besar apa yang ada di tangan Anda.

Sekarang, sekali lagi, saya ingin menekankan bahwa asumsi di sini adalah itu jika kami menelepon PRNG(6) satu juta kali kita akan mendapatkan setiap angka kira-kira seperenam waktu. Distribusi itu (kurang lebih) seragam, dan jika keseragaman distribusi itu adalah semua yang Anda pedulikan, tidak apa-apa. Inti pertanyaannya adalah apakah ada hal-hal lain yang distribusi PRNG(6) yang kita pedulikan? dan jawabannya adalah iya nih. Kami peduli tidak dapat diprediksi demikian juga.

Cara lain untuk melihat masalah adalah bahwa meskipun distribusi satu juta panggilan ke PRNG(6) mungkin baik-baik saja, karena PRNG hanya memilih dari 232 kemungkinan perilaku, tidak dapat menghasilkan setiap dek yang mungkin.  Itu hanya bisa menghasilkan 232 dari 2226 deck yang mungkin; sebagian kecil. Jadi distribusinya di atas set semua deck sangat buruk. Tetapi sekali lagi, serangan mendasar di sini didasarkan pada kemampuan kita untuk berhasil meramalkan perilaku masa lalu dan masa depan PRNG dari sampel kecil outputnya.

Biarkan saya mengatakan ini ketiga atau empat kali untuk memastikan ini tenggelam. Ada tiga distribusi di sini. Pertama, distribusi proses yang menghasilkan benih 32 bit acak. Itu bisa sangat acak, tak terduga dan seragam dan serangan itu akan tetap bekerja. Kedua, distribusi satu juta panggilan ke PRNG(6). Itu bisa sangat seragam dan serangan itu akan tetap berfungsi. Ketiga, distribusi deck yang dipilih oleh proses pseudo-random yang telah saya uraikan. Distribusi itu sangat buruk; hanya sebagian kecil dari dek yang mungkin IRL mungkin dapat dipilih. Serangan itu tergantung pada prediktabilitas perilaku PRNG berdasarkan pengetahuan parsial dari outputnya.

ASIDE: Serangan ini mengharuskan penyerang mengetahui atau dapat menebak apa algoritma tepat yang digunakan oleh PRNG. Apakah itu realistis atau tidak adalah pertanyaan terbuka. Namun, saat merancang sistem keamanan, Anda harus merancangnya agar aman terhadap serangan bahkan jika penyerang mengetahui semua algoritme dalam program. Dengan kata lain: bagian dari sistem keamanan yang harus tetap dirahasiakan agar sistem aman disebut "kunci". Jika sistem Anda bergantung pada keamanannya pada algoritme yang Anda gunakan sebagai rahasia kemudian kunci Anda mengandung algoritme tersebut. Itu adalah sebuah sangat posisi lemah berada di dalam!

Bergerak.

Sekarang misalkan kita memiliki kotak ajaib ketiga yang diberi label CPRNG. Ini adalah versi kripto-kekuatan PRNG. Dibutuhkan 256 bit benih daripada benih 32 bit. Itu berbagi dengan PRNG properti yang dipilih oleh benih dari salah satu dari 2256 perilaku yang mungkin. Dan seperti mesin kami yang lain, ia memiliki properti yang banyak dihubungi CPRNG(n) menghasilkan distribusi seragam hasil antara 1 dan n: masing-masing terjadi 1 / n dari waktu. Bisakah kita melakukan serangan terhadapnya?

Serangan asli kami mengharuskan kami untuk menyimpan 232 pemetaan dari biji ke PRNG(52). Tapi 2256 adalah angka yang jauh lebih besar; itu benar-benar tidak layak untuk dijalankan CPRNG(52)yang banyak waktu dan menyimpan hasilnya.

Tetapi misalkan ada beberapa lain cara untuk mengambil nilai CPRNG(52) dan dari itu menyimpulkan fakta tentang benih? Kami sudah cukup bodoh sejauh ini, hanya brute-memaksa semua kemungkinan kombinasi. Bisakah kita melihat ke dalam kotak ajaib, mencari tahu cara kerjanya, dan menyimpulkan fakta tentang benih berdasarkan output?

Tidak. Rinciannya terlalu rumit untuk dijelaskan, tetapi CPRNG dirancang secara cerdik sehingga tidak layak untuk menyimpulkan apa saja fakta yang berguna tentang benih dari output pertama CPRNG(52) atau dari apa saja subset dari output, tidak peduli seberapa besar.

Oke, jadi sekarang anggaplah server sedang menggunakan CPRNG untuk menghasilkan dek. Dibutuhkan benih 256 bit. Bagaimana cara memilih benih itu? Jika ia memilih nilai apa pun yang dapat diprediksi oleh penyerang kemudian tiba-tiba serangan itu menjadi layak lagi. Jika kita dapat menentukan itu dari 2256 mungkin benih, hanya empat miliar dari mereka kemungkinan akan dipilih oleh server, lalu kami kembali berbisnis. Kita dapat melakukan serangan ini lagi, hanya memperhatikan jumlah kecil benih yang mungkin dapat dihasilkan.

Oleh karena itu server harus bekerja untuk memastikan bahwa nomor 256 bit adalah terdistribusi secara merata - Yaitu, setiap kemungkinan benih dipilih dengan probabilitas 1/2256. Pada dasarnya server harus memanggil TRNG(2^256)-1 untuk menghasilkan benih CPRNG.

Bagaimana jika saya dapat meretas server dan mengintip ke dalamnya untuk melihat benih apa yang dipilih? Dalam hal ini, penyerang mengetahui masa lalu dan masa depan CPRNG yang lengkap. Penulis server harus waspada terhadap serangan ini! (Tentu saja jika saya dapat berhasil me-mount serangan ini maka saya mungkin juga dapat mentransfer uang ke rekening bank saya secara langsung, jadi mungkin itu tidak menarik. Poinnya adalah: benih harus menjadi rahasia yang sulit ditebak, dan nomor 256 bit benar-benar acak sangat sulit ditebak.)

Kembali ke poin saya sebelumnya tentang pertahanan-mendalam: benih 256 bit adalah kunci ke sistem keamanan ini. Gagasan CPRNG adalah bahwa sistemnya aman selama kuncinya aman; bahkan jika setiap fakta lain tentang algoritma ini diketahui, selama Anda dapat menyimpan rahasia kunci, kartu lawan tidak dapat diprediksi.

OK, jadi benih harus dirahasiakan dan didistribusikan secara merata karena jika tidak, kita dapat melancarkan serangan. Kami telah dengan asumsi bahwa distribusi output dari CPRNG(n) seragam. Bagaimana dengan distribusi di atas set semua dek yang mungkin?

Anda mungkin berkata: ada 2256 kemungkinan urutan output oleh CPRNG, tetapi hanya ada 2226 deck yang mungkin. Oleh karena itu ada kemungkinan lebih banyak urutan daripada dek, jadi kami baik-baik saja; setiap dek IRL mungkin sekarang (dengan probabilitas tinggi) mungkin dalam sistem ini. Dan itu argumen yang bagus kecuali ...

2226 hanya sebuah perkiraan52! Bagilah. 2256/ 52! tidak mungkin menjadi bilangan bulat karena untuk satu hal, 52! habis dibagi 3 tapi tidak ada kekuatan dua! Karena ini bukan angka bulat, sekarang kita memiliki situasi di mana semua deck berada mungkin, tapi beberapa deck lebih mungkin daripada yang lain.

Jika itu tidak jelas, pertimbangkan situasinya dengan angka yang lebih kecil. Misalkan kita memiliki tiga kartu, A, B dan C. Misalkan kita menggunakan PRNG dengan biji 8 bit, jadi ada 256 kemungkinan benih. Ada 256 kemungkinan output PRNG(3) tergantung pada benih; tidak ada cara untuk memiliki sepertiga dari mereka menjadi A, sepertiga dari mereka adalah B dan sepertiga dari mereka adalah C karena 256 tidak terbagi oleh 3. Harus ada bias kecil terhadap salah satu dari mereka.

Demikian pula, 52 tidak membagi secara merata menjadi 2256, jadi pasti ada beberapa bias terhadap beberapa kartu saat kartu pertama dipilih dan bias menjauh dari yang lain.

Dalam sistem asli kami dengan benih 32 bit ada bias besar-besaran dan sebagian besar dek mungkin tidak pernah diproduksi. Dalam sistem ini semua deck dapat diproduksi, tetapi distribusi deck masih cacat. Beberapa deck sangat sedikit lebih mungkin daripada yang lain.

Sekarang pertanyaannya adalah: apakah kita punya serangan berdasarkan cacat ini? dan jawabannya adalah dalam prakteknya, mungkin tidak. CPRNG dirancang sedemikian rupa jika bijinya benar-benar acak kemudian itu adalah komputasi tidak layak untuk membedakan antara CPRNG dan TRNG.

Oke, jadi mari kita ringkas.

Bagaimana nomor pseudorandom dan angka acak yang sebenarnya berbeda?

Mereka berbeda dalam tingkat prediktabilitas yang mereka tunjukkan.

  • Angka-angka yang benar-benar acak tidak dapat diprediksi.
  • Semua angka pseudo-random dapat diprediksi jika benih dapat ditentukan atau ditebak.

Mengapa perbedaan itu penting?

Karena ada aplikasi di mana keamanan sistem bergantung tidak dapat diprediksi.

  • Jika TRNG digunakan untuk memilih setiap kartu maka sistem tidak dapat diganggu gugat.
  • Jika CPRNG digunakan untuk memilih setiap kartu maka sistem aman jika benih tidak dapat diprediksi dan tidak diketahui.
  • Jika PRNG biasa dengan ruang benih kecil digunakan maka sistem tidak aman terlepas apakah benih tidak dapat diprediksi atau tidak diketahui; ruang benih yang cukup kecil rentan terhadap serangan brute force dari jenis yang telah saya jelaskan.

Apakah perbedaan ada hubungannya dengan distribusi output PRNG?

Keseragaman distribusi atau ketiadaannya panggilan individual untuk RNG(n) tidak relevan dengan serangan yang telah saya jelaskan.

Seperti yang telah kita lihat, keduanya a PRNG dan CPRNG menghasilkan distibusi miskin dari probabilitas memilih setiap dek individu dari semua deck yang mungkin. Itu PRNG jauh lebih buruk, tetapi keduanya memiliki masalah.

Satu pertanyaan lagi:

Jika TRNG jauh lebih baik daripada CPRNG, yang pada gilirannya jauh lebih baik daripada PRNG, mengapa ada yang menggunakan CPRNG atau PRNG?

Ada dua alasan.

Pertama: biaya. TRNG adalah mahal. Menghasilkan angka yang benar-benar acak itu sulit. CPRNG memberikan hasil yang bagus untuk banyak panggilan dengan sembarang saja satu panggilan ke TRNG untuk benih. Sisi bawahnya tentu saja itu Anda harus merahasiakan benih itu.

Kedua: terkadang kita ingin prediktabilitas dan semua yang kita pedulikan adalah distribusi yang baik. Jika Anda menghasilkan data "acak" sebagai input program untuk rangkaian uji, dan ini akan menampilkan bug, maka akan lebih baik menjalankan rangkaian uji kembali menghasilkan bug lagi!

Saya harap itu sekarang jauh lebih jelas.

Akhirnya, jika Anda menikmati ini maka Anda mungkin menikmati beberapa bacaan lebih lanjut tentang masalah keacakan dan permutasi:


1371



Ok, anak laki-laki dan perempuan. Sudah cukup komentar untuk saat ini. Jika Anda ingin membahas ini lebih lanjut, pergi ambil sendiri ruang obrolan, kthnxbye! - Ivo Flipse♦
@Eric Tapi benihnya tidak diatur ulang sebelum setiap undian dek baru, bukan? Jadi sementara Anda benar bahwa hanya ada sedikit saja lintasan Kami mengambil sampel dari, Anda tidak tahu persis di mana di lintasan Anda saat ini dan lintasan berpotongan. - A.S.
Seseorang benar-benar melakukan sesuatu seperti ini - EJoshuaS
Perlakuan yang baik (tetapi padat) dari isu-isu terkait ada dalam TAFCP Knuth vol 2, bagian 3.5 “Apa itu Urutan Acak?” (Hal. 149), dimulai dengan definisi yang mengilumikan distribusi yang merata, k-terdistribusi, dan ∞-terdistribusi. Urutan pseudorandom didiskusikan dalam 3.5.F (p. 170). Lihat juga kriteria pseudorandomness dari teori kompleksitas dan BSI Jerman. - ShreevatsaR


Seperti Eric Lippert katakan, itu bukan hanya distribusi. Ada cara lain untuk mengukur keacakan.

Salah satu generator nomor acak awal memiliki urutan dalam bit paling tidak signifikan - bergantian 0 dan 1. Oleh karena itu LSB 100% dapat diprediksi. Tetapi Anda perlu khawatir tentang lebih dari itu. Setiap bit harus tidak dapat diprediksi.

Ini cara yang bagus untuk memikirkan masalah. Katakanlah Anda menghasilkan 64 bit keacakan. Untuk setiap hasil, ambil 32 bit pertama (A), dan 32 bit terakhir (B), dan buat indeks ke dalam array x [A, B]. Sekarang lakukan pengujian satu juta kali, dan untuk setiap hasil, tambahkan larik pada angka itu, yaitu X [A, B] ++;

Sekarang gambarlah diagram 2D, di mana semakin besar angkanya, semakin terang pixel di lokasi tersebut.

Jika benar-benar acak, warnanya harus berwarna abu-abu seragam. Tetapi Anda mungkin mendapatkan pola. Ambil contoh diagram ini dari "keacakan" dalam nomor urut TCP dari sistem Windows NT:

Windows NT 

atau bahkan yang ini dari Windows 98:

Windows 98 

Dan di sini adalah keacakan dari router Cisco (IOS) implementasi. Cisco ISO

Diagram ini adalah milik Makalah Michał Zalewski. Dalam kasus khusus ini, jika seseorang dapat memprediksi apa nomor urut TCP dari suatu sistem, seseorang dapat meniru sistem itu ketika membuat sambungan ke sistem lain - yang memungkinkan pembajakan koneksi, intersepsi komunikasi, dll. Dan bahkan jika kita tidak dapat memprediksi angka berikutnya 100% dari waktu, jika kita dapat menyebabkan koneksi baru dibuat di bawah kendali kami, kita dapat meningkatkan peluang sukses. Dan ketika komputer dapat menghasilkan 100.000 sambungan dalam beberapa detik, kemungkinan serangan yang sukses pergi dari astronomi ke kemungkinan atau bahkan mungkin.


155



Ini sangat brilian hingga membuat saya meneteskan air mata. Harus ada aplikasi yang membuat ini untuk setiap OS (mobile / desktop / server) dan platform (JVM / Javascript / dll). - HDave
Fungsi Windows rand () cukup bagus! Ini menghasilkan awan yang tidak memiliki pola yang jelas. Lihat penerapan saya untuk mencobanya (dan algoritme lain): github.com/Zalastax/visualize_random - Zalastax


Sementara nomor pseudorandom yang dihasilkan oleh komputer dapat diterima untuk sebagian besar kasus penggunaan yang dihadapi oleh pengguna komputer, ada skenario yang mengharuskan sama sekali nomor acak tak terduga.

Dalam aplikasi yang peka terhadap keamanan seperti enkripsi, pembuat nomor pseudorandom (PRNG) dapat menghasilkan nilai-nilai yang, meskipun secara acak, pada kenyataannya dapat diprediksi oleh penyerang. Seseorang yang mencoba memecahkan sistem enkripsi mungkin dapat menebak kunci enkripsi jika PRNG digunakan dan penyerang memiliki informasi tentang keadaan PRNG. Oleh karena itu, untuk aplikasi seperti itu, generator bilangan acak yang menghasilkan nilai-nilai yang benar-benar dapat diatur diperlukan. Perhatikan itu beberapa PRNG dirancang agar aman secara kriptografi dan dapat digunakan untuk aplikasi yang peka terhadap keamanan tersebut.

Informasi lebih lanjut tentang serangan RNG dapat ditemukan di artikel Wikipedia ini.


91



PRNG kriptografi ada, dan banyak digunakan. Mereka dapat dari biji berukuran sedang menghasilkan aliran angka acak yang tak terbatas. Hal ini secara komputasi tidak layak untuk membedakan aliran seperti itu dari bilangan acak yang sebenarnya, sehingga tidak ada informasi tambahan yang dapat diperoleh dari setiap bagian dari aliran seperti itu, dan untuk tujuan praktis apa pun jumlahnya sama bagusnya dengan bilangan acak yang sebenarnya. - aaaaaaaaaaaa
Saya pikir cara termudah untuk menjelaskan ini adalah bahwa algoritma pembangkit nomor acak harus diprogram. Itu berarti ada seperangkat instruksi yang sedang diikuti. Jika ada satu set instruksi, itu tidak bisa acak. - Keltari
@Keltari Anda kehilangan elemen entropi ... Kebanyakan RNG (paling tidak yang bersifat kriptografi) mengumpulkan input dari sumber luar (mis. Gerakan mouse) dan menggunakannya sebagai bagian dari kondisi awal - dengan demikian, transformasi dari A untuk B diprogram tetapi keadaan awal A (seharusnya) tidak bisa ditebak. Linux /dev/random akan menjaga perkiraan berapa banyak entropi tersedia dan berhenti memberikan angka jika jatuh terlalu rendah. - Basic
Karena penasaran - mengapa lampu lava dianggap "benar-benar acak"? Saya mengerti itu menunjukkan perilaku yang agak tak terduga, tetapi seseorang dengan cukup kuat memahami dinamika fluida dan bagaimana cairan yang berinteraksi dalam lingkungan gravitasi Bumi pasti dapat menghasilkan hasil yang "dapat diprediksi", bukan? Tentu, lampu lava tidak dapat diprediksi, tetapi bagi saya, mereka tidak acak sama sekali, tetapi sangat mudah diprediksi. - theGreenCabbage
@ theGreenCabbage: Saya menduga lampu lava itu kacau. Dengan model komputer yang cukup baik, dan cukup banyak ketepatan, Anda dapat (secara prinsip) memprediksi perilaku untuk sementara waktu. Tapi, karena sistemnya kacau, dua lampu lava dengan perubahan terkecil dalam kondisi awal akan dengan cepat berubah dalam perilaku. (Dan komentar ini mengabaikan penarik yang kacau.) - dmm


Saya mencobanya dengan Python: Ini hasil dari 60 juta gulungan. Variasi tertinggi seperti 0,15. Bukankah itu acak seperti itu?

Sebenarnya itu jadi "baik" itu buruk... Semua jawaban yang ada fokus prediktabilitas diberikan urutan kecil dari nilai awal. Saya ingin mengangkat masalah lain:

anda distribusi memiliki deviasi standar yang jauh lebih kecil daripada gulungan acak seharusnya

Keacakan sejati tidak datang begitu saja bahwa dekat dengan rata-rata "hampir tepat 1 atas berapa banyak angka yang dapat dipilih" yang Anda gunakan sebagai indikasi kualitas.

Jika Anda melihat pertanyaan Stack Exchange ini tentang distribusi probabilitas untuk beberapa gulungan dadu, Anda akan melihat rumus untuk deviasi standar gulungan N dadu (dengan asumsi hasil yang benar-benar acak):

 sqrt(N * 35.0 / 12.0).

Menggunakan rumus itu, the standar deviasi untuk:

  • 1 juta gulungan adalah 1708
  • 60 juta gulungan adalah 13229

Jika kami melihat hasil Anda:

  • 1 juta gulungan: stddev (1000066, 999666, 1001523, 999452, 999294, 999999) adalah 804
  • 60 juta gulungan: stddev (9997653, 9997789, 9996853, 10006533, 10002774, 9998398) adalah 3827

Anda tidak dapat mengharapkan standar deviasi dari sampel terbatas untuk sama persis dengan rumus, tetapi seharusnya cukup dekat. Namun, pada 1 juta gulungan Anda memiliki kurang dari setengah stddev yang tepat, dan dengan 60 juta Anda berada di bawah sepertiga - itu semakin buruk, dan itu bukan kebetulan ...

Pseudo-RNG cenderung bergerak melalui urutan angka yang berbeda, dimulai dengan benih dan tidak meninjau kembali nomor asli untuk periode tertentu. Misalnya, implementasi perpustakaan C lama rand() fungsi umumnya memiliki periode 2 ^ 32, dan mereka akan mengunjungi setiap angka antara 0 dan 2 ^ 32-1 tepat satu kali sebelum mengulangi benih. Jadi, jika Anda simulasi 2 ^ 32 dadu gulung pre-modulus (%) hasil akan mencakup setiap angka dari 0 hingga 2 ^ 32, jumlah untuk setiap hasil 1-6 akan menjadi 715827883 atau 715827882 (2 ^ 32 bukan kelipatan dari 6), dan standar deviasi karena itu hanya sepele di atas 0. Menggunakan rumus di atas, standar deviasi yang benar untuk 2 ^ 32 gulungan adalah 111924. Lagi pula, karena jumlah gulungan pseudo-acak Anda meningkat, Anda bertemu ke arah 0 standar deviasi. Masalah ini dapat diharapkan menjadi signifikan ketika jumlah gulungan adalah bagian yang signifikan dari periode, tetapi beberapa pseudo-RNG dapat menunjukkan masalah yang lebih buruk - atau bahkan masalah dengan sampel yang lebih sedikit - daripada yang lain.

Jadi bahkan jika Anda tidak peduli tentang kerentanan kriptografi, dalam beberapa aplikasi Anda mungkin peduli tentang memiliki distribusi yang tidak terlalu berlebihan, bahkan hasil palsu. Beberapa jenis simulasi cukup khusus mencoba untuk mengetahui konsekuensi dari tidak merata hasil yang secara alami terjadi dengan sampel besar hasil individual acak, tetapi mereka kurang terwakili dalam beberapa hasil pRNG. Jika Anda mencoba untuk mensimulasikan bagaimana populasi besar bereaksi terhadap suatu peristiwa, masalah ini bisa terjadi secara radikal mengubah hasil Anda mengarah ke kesimpulan yang sangat tidak akurat.


Untuk memberikan contoh konkret: Katakanlah seorang matematikawan mengatakan kepada programmer mesin poker bahwa setelah 60 juta rol simulasi - digunakan untuk mengedipkan ratusan "lampu" kecil di sekitar layar, jika sudah ada 10.013.229 atau lebih berenam, yang diharapkan oleh matematikawan 1 stddev jauh dari rata-rata, harus ada pembayaran kecil. Per Aturan 68–95–99.7 (Wikipedia) ini harus terjadi 16% waktu (~ 68% jatuh dalam standar deviasi / hanya setengah luar di atas). Dengan generator nomor acak Anda, ini adalah dari sekitar 3,5 standar deviasi di atas rata-rata: Bawah 0,025% kesempatan - hampir tidak ada pelanggan yang mendapatkan manfaat ini. Lihat tabel Higher Deviations pada halaman yang baru saja disebutkan, khususnya:

| Range    | In range   | Outside range | Approx. freq. for daily event  |
| µ ± 1σ   | 0.68268... | 1 in 3        | Twice a week                   |
| µ ± 3.5σ | 0.99953... | 1 in 2149     | Every six years                |

75



Anda membandingkan apel dan jeruk di sini. Dua standar deviasi sama sekali tidak ada hubungannya dengan satu sama lain. - Jbeuh


Saya baru saja menulis nomor acak ini untuk menghasilkan gulungan dadu

def get_generator():
  next = 1
  def generator():
    next += 1
    if next > 6:
      next = 1
    return next
  return generator

Anda menggunakannya seperti ini

>> generator = get_generator()
>> generator()
1
>> generator()
2
>> generator()
3
>> generator()
4
>> generator()
5
>> generator()
6
>> generator()
1

dll. Apakah Anda akan senang menggunakan generator ini untuk program yang menjalankan permainan dadu? Ingat, distribusinya persis seperti yang Anda harapkan dari generator "benar-benar acak"!

Generator nomor pseudo-random melakukan hal yang sama - mereka menghasilkan angka yang dapat diprediksi dengan distribusi yang benar. Mereka buruk untuk alasan yang sama bahwa generator nomor acak sederhana di atas adalah buruk - mereka tidak cocok untuk situasi di mana Anda membutuhkan ketidakterdugaan yang sebenarnya, bukan hanya distribusi yang benar.


50



"Pseudo-random number generators ... menghasilkan angka yang dapat diprediksi dengan distribusi yang benar" - Hanya karena PRNG tidak menjamin bahwa ia memiliki distribusi sempurna (pada kenyataannya, yang komersial pada umumnya tidak, untuk persis alasan yang dijabarkan dalam jawaban ini). Meskipun mereka dapat diprediksi dengan memberikan informasi yang cukup (algo yang digunakan, benih awal, nilai output, w / e), mereka masih memiliki varians. - Brian S
Selain intinya, saya tahu, tapi get_generator = lambda: itertools.cycle(range(1,7)), generator = get_generator(), next(generator) # and so on terlalu elegan belum lagi :) - Janus Troelsen
@BrianS Sebenarnya, PRNG yang gagal dalam uji distribusi akan dapat diprediksi menurut definisi. Jadi di atas beberapa N besar, jika Anda mendapatkan sedikit jalan dari N / 2 kepala di N koin membalik, Anda dapat mulai bertaruh pada kepala, dan Anda dapat memenangkan lebih dari yang Anda kalah. Demikian pula, jika Anda mendapatkan distribusi sempurna dari kepala v. Ekor, tetapi kepala selalu datang berpasangan, maka Anda akan kembali memiliki resep untuk menang. Tes distribusi adalah bagaimana Anda tahu PRNG ada gunanya. - Jon Kiparsky
Anda lupa nonlocal next :-). - Kos
Bahkan contoh yang lebih baik: Pi diyakini normal, yang berarti bahwa setiap urutan digit dari setiap panjang yang diberikan dalam basis apa pun tidak lebih sering muncul daripada urutan lain dari panjang tersebut dalam basis tersebut. Algoritma yang, ketika diminta n bit acak, mengambil yang berikutnya n bit pi dan mengembalikan mereka ("benih" adalah bit yang Anda mulai), seharusnya dalam jangka panjang menghasilkan distribusi yang merata. Tetapi Anda masih tidak menginginkannya untuk generator Anda - seseorang yang mengetahui kumpulan bit terakhir yang Anda hasilkan dapat menemukan pertama kalinya urutan itu terjadi, menganggap benih Anda ada di sana, dan mungkin benar. - cpast


Pembangkitan angka acak yang dapat dilakukan komputer Anda sesuai untuk sebagian besar kebutuhan, dan Anda tidak akan menemukan waktu di mana Anda memerlukan nomor acak yang sesungguhnya.

Generasi angka acak yang benar memiliki tujuannya. Dalam keamanan komputer, perjudian, sampel statistik besar, dll.

Jika Anda tertarik pada aplikasi angka acak, periksa Artikel Wikipedia.


26



Masalah besar adalah ketika Anda membutuhkan angka acak yang tidak dapat diprediksi oleh penyerang karena alasan keamanan. - David Schwartz
Anda yakin sekali akan menemukan waktu di mana Anda memerlukan nomor yang benar-benar acak. Ini cukup untuk membuka halaman web yang dimulai dengan https://... - Jan Hudec
@JanHudec: Baik, dalam penggunaan sehari-hari, Anda akan memerlukan nomor acak yang aman saat Anda membuka program apa pun, jauh sebelum Anda mengetik ke bilah alamat: lihat pengacakan tata letak ruang alamat. S mengapa hal-hal seperti ini terjadi. - Reid
@JanHudec Saya secara khusus berbicara dalam arti bahwa Anda akan perlu menggunakan generator nomor acak online. Nomor acak benar sering digunakan, tetapi sangat sedikit orang yang benar-benar perlu membuatnya sendiri. - Alex McKenzie
Mesin slot juga menggunakan PRNG, bukan TRNG. Generator berjalan sepanjang waktu dan nomor diambil tepat pada saat tombol putar ditekan. Jumlah PRNG dan waktu tekan tombol yang benar-benar acak berjumlah TRNG. - Roger Dahl


Angka-angka acak yang dihasilkan oleh fungsi-fungsi khas di sebagian besar bahasa pemrograman bukan angka acak. Mereka adalah angka acak pseudo. Karena mereka bukan angka acak, mereka dapat ditebak dengan informasi yang cukup tentang angka yang dihasilkan sebelumnya. Jadi ini akan menjadi bencana untuk keamanan dalam kriptografi.

Untuk contoh fungsi generator nomor acak berikut yang digunakan dalam glibc tidak menghasilkan angka acak. Nomor acak pseudo yang dihasilkan oleh ini dapat ditebak. Ini adalah kesalahan untuk masalah keamanan. Ada sejarah ini menjadi bencana. Ini tidak boleh digunakan dalam kriptografi.

glibc random():
    r[i] ← ( r[i-3] + r[i-31] )  % (2^32)
    output  r[i] >> 1

Jenis pseudo random number generator ini seharusnya tidak pernah digunakan di tempat-tempat sensitif keamanan meskipun secara statistik jauh signifikan.

Salah satu serangan terkenal pada kunci acak pseudo adalah menyerang 802.11b WEP. WEP memiliki kunci jangka panjang 104-bit, disambung dengan 24-bit IV (penghitung) untuk membuat kunci 128 bit, yang pada gilirannya diterapkan pada Algoritma RC4 untuk menghasilkan kunci acak pseudo.

( RC4( IV + Key ) ) XOR (message)

Kunci-kunci itu terkait erat satu sama lain. Di sini, hanya IV yang meningkat sebesar 1 dalam setiap langkah dan yang lainnya tetap sama. Karena ini tidak murni acak, itu bencana dan mudah rusak. Kuncinya dapat dipulihkan dengan menganalisis sekitar 40000 frame, yang merupakan hitungan menit. Jika WEP menggunakan IV 24-bit murni acak, maka itu bisa aman sampai sekitar 2 ^ 24 (hampir 16,8 juta) frame.

Jadi orang harus pergi dengan generator nomor acak murni dalam isu-isu sensitif keamanan bila memungkinkan.


26



Saya akan menyalahkan hal-hal WEP pada protokol yang dirancang dengan buruk menggunakan sandi yang lemah. Dengan stream stream modern Anda dapat menggunakan counter sebagai IV. - CodesInChaos
Masalah utama dengan WEP adalah mengulang kunci dalam 2 ^ 24 (hampir 16 juta) frame. Itu bahkan lebih buruk dengan kunci terkait yang memungkinkan untuk memecahkan kode di sekitar 40000 frame. Poin utama di sini adalah bahwa kuncinya tidak acak. Ini terkait erat, sehingga mudah retak. - Prabhu
Pseudo-randomness buruk dalam kriptografi hanya ketika menghasilkan kunci kriptografi. Itu sangat baik di luar itu. Memang, RC4 sedikit lebih dari generator nomor pseudo-acak yang dibudidayakan dengan ekspansi 128-bit dari kunci XORed ke plaintext dari pesan. - Matt


Perbedaannya adalah nomor pseudorandom yang dihasilkan dapat diprediksi (berulang) setelah beberapa waktu di mana nomor acak yang benar tidak. Panjang yang diperlukan untuk mengulangi tergantung pada panjang benih yang digunakan untuk pembangkitannya.

Berikut ini video yang cukup bagus tentang topik itu: http://www.youtube.com/watch?v=itaMNuWLzJo 


12



Prediktabilitas! = Mengulang. Mersenne Twister adalah contoh bagusnya. Pada sebagian besar implementasi setelah 624 Int32 Anda dapat memprediksi semua nomor berikutnya, tetapi urutan Mersenne Twister jauh lebih lama dari itu (2 ^ 19937 - 1). - HoLyVieR
Saya tidak mengerti mengapa jawaban ini tidak mendorong tumpukan, karena ini tampaknya bagi saya bahwa ini adalah jawaban yang akurat dan ringkas untuk pertanyaan itu, setidaknya sebagian. Nomor acak pseudo dapat dengan mudah diprediksi setelah beberapa kali imbang, jumlah imbang yang bervariasi dengan "kualitas" algoritma pseudo random. Memilih algoritma "baik" adalah melihat ke aspek: 1. setiap nilai diambil dalam frekuensi yang sama (distribusi), 2. dibutuhkan "waktu yang lama" untuk memulai kembali urutan di awal dan mulai menggambar lagi angka yang sama di pesanan yang sama. - mins
"Angka acak yang sebenarnya tidak [diprediksi]". Untuk hari ini, ini benar. Sekarang jika kita percaya pada teori Big Bang, dan kita memiliki banyak kekuatan untuk menghitung keadaan alam semesta kapan saja setelah BB, berdasarkan fisika maka ... kita dapat memprediksi masa depan, termasuk fakta bahwa Saya menulis komentar yang sangat tepat ini. Kanan? - mins
Itu benar secara hipotetis, bagaimanapun, mengingat besarnya derajat entropi yang terlibat dalam tindakan nyata dari tubuh nyata, daya komputasi yang dibutuhkan akan sangat besar. Pikirkan benua yang tercakup dalam komputer. Plus, karena ketergantungan pada keadaan sebelumnya, keadaan setiap tubuh di alam semesta pada setiap titik waktu akan perlu disimpan, yang menurut definisi akan membutuhkan lebih banyak ruang daripada yang tersedia di alam semesta, yang sepenuhnya diisi dengan alat memori. - TheEnvironmentalist
@TheEnvironmentalist - Ah! "Benua yang tercakup dalam komputer" ... bukankah itu apa "The Hitchhiker's Guide to the Galaxy" semua tentang? ;-) - ysap