Bagaimana bisa dideteksi bahwa generator angka tidak benar-benar acak?

20

Saya mendengar bahwa pembuatan bilangan acak di komputer tidak benar-benar acak, tetapi tidak ada algoritma yang efisien untuk mendeteksinya. Bagaimana bisa dideteksi sama sekali?

randomness random-number-generator URL87
sumber
1
Posting ini dapat membantu Anda.
Anton
6
Dengan risiko terdengar gila-gilaan, itu tidak benar-benar mungkin untuk mengatakan dengan pasti bahwa sumber yang diberikan tidak acak, jika semua yang Anda lakukan adalah memeriksa hasilnya. Anda dapat flip adil koin kali berturut-turut dan mendapatkan kepala setiap kali, dan kesempatan Anda untuk mendapatkan ekor pada 10 100 + 1 st melemparkan masih 50%. Dengan memeriksa sumbernya, kita biasanya dapat mengidentifikasi hal-hal non-acak (misalnya, generator nomor pseudorandom ... kita dapat memprediksi urutan dari seed dan algoritma). Banyak sumber acak yang mungkin tidak cukup dipahami untuk memprediksi dengan andal. Tapi ini filosofis. 1010010100+1
Patrick87
@ Patrick87 Jika dengan "kepastian" yang Anda maksud secara matematis, itu benar. Namun, ada uji statistik yang dapat memberi Anda signifikansi sewenang-wenang (asalkan datanya "baik").
Raphael
@ Patrick87 Dengan risiko terdengar biasa-biasa saja ... Anda mengatakan "Anda dapat membalik koin yang adil kali berturut-turut dan mendapatkan kepala setiap kali" ... tidak, saya tidak bisa. Model apa pun yang memungkinkan saya untuk melihat bahkan 10 3 kepala berturut-turut dan masih percaya itu adalah koin yang adil tidak menangkap kenyataan dengan sangat baik. Ini memang filosofis. ;-)10100103
Don Hatch

Jawaban:

15

Komputer Menjadi Sangat Acak:

Keacakan yang sebenarnya tidak mungkin untuk Mesin Turing dalam arti teoretis, dan sebagian besar komputer tidak dapat menghasilkan output yang benar-benar acak. Oleh karena itu, beberapa komputer modern menyertakan perangkat keras yang memungkinkan komputer untuk mengakses sumber luar yang diharapkan akan mencakup beberapa keacakan. Salah satu contoh bagaimana hal ini dapat dilakukan adalah untuk melacak fluktuasi kecil dalam suhu di dalam komputer. Keacakan dapat diperoleh dari sumber luar juga. Tetapi dari nada tulisan Anda, saya tidak berpikir bahwa sumber keacakan dari luar adalah yang Anda minati.

Biji:

Tanpa tambahan dari luar, semua yang dilakukan komputer adalah deterministik. Ini mengarah ke masalah besar: jika Anda memanggil program pembuatan angka acak, itu akan memberi Anda hasil yang sama setiap kali jika Anda memberikan input yang sama. Jelas, kita membutuhkan program yang mengeluarkan angka acak untuk mengubah perilakunya setiap kali dijalankan (jika tidak kita akan tetap mendapatkan nomor "acak" yang sama, yang tidak terlalu membantu). Satu ide adalah memberi program beberapa input, yang berubah setiap kali program dijalankan, sehingga angka yang berbeda akan dihasilkan. Kami menyebut input ini sebagai "seed." Generator angka acak perlu mengambil sebuah seed, melakukan beberapa operasi, dan memberi kami nomor acak.

Waktu sistem saat ini adalah contoh klasik dari sebuah seed. Ini memberikan string panjang dengan entropi tinggi, dan jika waktu terus dilacak dengan cara yang cukup granular (yaitu jika jam sistem Anda menggunakan jam maka "waktu" adalah benih yang sangat buruk), Anda tidak mungkin memberi makan nomor pseudorandom generator nomor yang sama dua kali.

Algoritma yang Cukup Acak:

Sekarang kami memiliki algoritma yang setidaknya memiliki beberapa cara untuk menjadi berbeda setiap kali dijalankan. Kami memberikannya seed, dan sementara algoritma memberikan angka yang sama ketika diminta dengan seed yang sama, kami ingin angka yang dihasilkannya menjadi acak jika tidak. Ini bertindak seperti di atas - Anda mengambil beberapa input, dan menghasilkan beberapa (mudah-mudahan cukup berbeda dari input menjadi "acak") output.

Sekarang katakanlah Anda datang dengan algoritma Anda sendiri untuk melakukan ini, dan Anda mengklaim bahwa angka-angka yang Anda buat cukup dekat secara acak ketika Anda memberikannya sejumlah benih yang berbeda. Bagaimana kita menguji seberapa bagusnya itu?

Sekarang kami ingin beberapa algoritma yang akan mengambil seed, melakukan beberapa operasi, dan menghasilkan angka acak. Paling sederhana, algoritma hanya bisa menampilkan benih - itu tidak memberi kita jumlah yang sama setiap kali, dan benih acak memberi kita hasil acak. Tapi jelas itu bukan yang kita inginkan. Di sisi lain, suatu algoritma bisa sangat rumit, seperti banyak generator pseudorandom yang sebenarnya. Bagaimana kita bisa mengetahui algoritma mana yang memberi kita angka "acak" dari benih kita yang belum tentu? Jika kita tidak bisa mendapatkannya dengan tepat, bagaimana kita bisa tahu mana yang terbaik?

1n

Cukup Acak untuk Menipu Penyerang:

Sekarang yang Anda maksudkan adalah Pseudorandom Generator Cryptographially Secure. Saya pikir cara terbaik untuk menjelaskan ini adalah dalam konteks di atas - di sini, kami menggunakan keacakan kami untuk kriptografi, jadi ketika kami merancang tes apa yang benar-benar kami pedulikan adalah bahwa seseorang tidak akan dapat memecahkan keamanan kami dengan memprediksi nomor acak apa yang kami ambil. Saya tidak tahu tingkat keakraban Anda dengan kriptografi, tetapi bayangkan kami sedang melakukan penggantian cypher sederhana --- setiap huruf diganti dengan beberapa huruf lainnya. Kami ingin memilih pengganti ini secara acak, sehingga sulit ditebak oleh penyerang. Tetapi jika dia bisa mencari tahu bagaimana generator nomor acak saya bekerja, dia akan bisa menyelesaikan cipher keseluruhan! Oleh karena itu, algoritma kriptografi memerlukan generator angka acak yang sulit ditebak.

Untuk alasan ini, CSPRG didefinisikan dalam hal seberapa baik algoritma lain menyelesaikannya (yang akhirnya kami tanyakan pada pertanyaan Anda). Secara khusus, katakanlah saya memiliki CSPRG yang saya sebut R. R adalah CSPRG jika dan hanya jika TIDAK ada algoritma yang layak yang dapat menebak bit mana yang akan dihasilkan selanjutnya. Ini benar bahkan jika Anda tahu semua bit yang dihasilkan sebelumnya!

Jadi misalkan lima bit pertama CSPRG saya memiliki output adalah 10100. Anda tidak tahu input yang saya gunakan untuk program, tetapi Anda memiliki akses ke kode yang saya gunakan untuk menulis CSPRG saya. Maka klaimnya adalah bahwa tidak mungkin bagi Anda untuk menulis sebuah program untuk memutuskan apakah output bit berikutnya adalah 101000 atau 101001.

Jadi untuk alasan kriptografi, kadang-kadang seberapa baik generator nomor pseudorandom tidak didefinisikan dalam hal seberapa dapat diprediksi untuk program lain. Perhatikan bahwa ini masih memberikan banyak intuisi "keacakan," seperti (katakanlah) jika Anda tahu semua output acak akan aneh itu tidak aman secara kriptografi dan tidak lulus uji keacakan akal sehat.

SamM
sumber
7
Ini adalah jawaban yang baik (tetapi tidak lengkap) secara keseluruhan, tetapi beberapa poin salah. “Keacakan yang sebenarnya tidak mungkin untuk komputer, karena semua yang mereka lakukan adalah deterministik.” Itu tidak selalu benar, beberapa prosesor menyertakan RNG perangkat keras. Komputer juga dapat bereaksi terhadap input eksternal yang mungkin acak. “... untuk kriptografi, jadi kami tidak terlalu peduli seberapa" acak "mereka dalam hal distribusi": sebenarnya kadang-kadang distribusi seragam penting dalam kripto, misalnya IV untuk CBC dan parameter k dalam DSA.
Gilles 'SANGAT berhenti menjadi jahat'
Dia menulis "Tanpa tambahan luar, semua yang dilakukan komputer adalah deterministik". Penambahan luar adalah referensi ke perangkat seperti RNG seperti yang Anda sebutkan. Tanpa penambahan ini, kemampuan komputasi kami sama dengan TM yang tidak mungkin dilakukan pengacakan secara acak.
Kent Munthe Caspersen
Jika saya ingat dengan benar, saya menambahkannya setelah komentar Gilles.
SamM
4

Baru-baru ini saya menemukan posting yang bagus tentang keacakan dalam perhitungan di blog MIT CSAIL Theory of Computation Group blog: Dapatkah Anda tahu apakah sedikit itu acak?

Posting dimulai dengan beberapa ide yang diambil dari ceramah Avi Wigderson yang luar biasa tentang kekuatan dan keterbatasan keacakan dalam perhitungan, mensurvei area indah dari algoritma acak, dan hubungan mengejutkan antara pseudorandomness dan komputasi yang tidak dapat dipraktikkan .

Kemudian ia merangkum beberapa hasil terbaru tentang kriptografi kuantum; khususnya cara untuk menguji secara efisien apakah output dari perangkat jenis tertentu benar-benar acak (protokol ekspansi keacakan).

Sebagai contoh, lihat karya terbaru oleh Umesh Vazirani, Thomas Vidick, Quantum Dice yang Tersertifikasi (Atau, ekspansi keacakan eksponensial yang dapat diuji)

Abstrak: Kami memperkenalkan protokol di mana sepasang perangkat mekanis kuantum dapat digunakan untuk menghasilkan n bit keacakan benar dari benih bit O (log n) yang seragam. Bit yang dihasilkan secara acak hanya berdasarkan pada uji statistik sederhana yang dapat dilakukan oleh pengguna, dan dengan asumsi bahwa perangkat mematuhi prinsip no-pensinyalan. Tidak ada asumsi lain yang ditempatkan pada cara kerja perangkat ...

Vor
sumber
3

Dengan asumsi Anda berbicara tentang keacakan statistik - kriptografi memiliki kebutuhan lain! - ada banyak tes good-of-fit yang dapat mendeteksi apakah urutan angka sesuai dengan distribusi yang diberikan. Anda dapat menggunakan ini untuk menguji apakah generator nomor acak (semu) baik (hingga kualitas pengujian Anda dan signifikansi yang dipilih).

Suite tes Diehard menggabungkan metode yang berbeda.

Raphael
sumber
0

Ini adalah topik yang luas / kompleks dalam ilmu komputer yang dijawab oleh SamM oleh beberapa orang. Pertanyaan spesifik Anda tampaknya tentang apakah komputer memiliki apa yang disebut PRNGs , yaitu generator bilangan acak semu, bagaimana seseorang dapat mendeteksi itu?

Jawaban singkatnya adalah bahwa PRNG nontrivial dibangun sehingga algoritme mereka tidak dapat dideteksi (diturunkan). Secara umum, jika PRNG adalah apa yang disebut "aman", bahkan jika penyerang tahu algoritma yang digunakan untuk menghasilkan urutan pseudorandom, mereka tidak dapat menebak parameter tertentu yang digunakan untuk menghasilkan urutan. Dengan cara ini pseudorandomness memiliki banyak ikatan mendalam dengan kriptografi, dan orang dapat berbicara tentang "melanggar" PRNG dengan cara yang hampir sama dengan algoritma kriptografi yang dapat "rusak". Ada banyak makalah penelitian di bidang ini, ini merupakan area aktif di garis depan kriptografi.

Untuk PRNG "sepele", misalkan generator linear kongruensial , jika penyerang mengetahui algoritma yang digunakan untuk menghasilkannya dan tidak dihasilkan dengan "bignum" , ruang pencarian "relatif kecil" dan penyerang secara teoritis juga dapat menemukan parameter digunakan oleh PRNG tertentu pada dasarnya oleh kekuatan kasar dan mencoba semua kombinasi.

PRNG dapat dipatahkan dalam praktik (sekali lagi tergantung pada "keamanan" mereka) dalam beberapa kasus dengan menjalankan serangkaian uji keacakan statistik terhadap mereka. misalnya ini adalah alasan dari program "Dieharder" (oleh Brown). Ada juga suite NIST .

Kesulitan intrinsik / kekerasan melanggar PRNG belum secara teoritis terbukti tetapi pada dasarnya terkait dengan apa yang disebut "pintu jebakan" atau "fungsi satu arah" yang dapat dihitung secara efisien dalam satu arah tetapi "sulit" untuk dibalik (terbalik) . Ada beberapa masalah terbuka dalam kriptografi tentang kekerasan acak. Pertanyaan-pertanyaan ini berkaitan erat dengan pemisahan kelas kompleksitas misalnya pertanyaan P =? NP yang terkenal.

Pertanyaan tentang melanggar PRNG juga terkait dengan kompleksitas Kolmogorov , bidang yang mempelajari Mesin Turing terkecil yang dapat menghasilkan urutan. melanggar PRNG juga berkaitan erat dengan menemukan program "terpendek" untuk menghitung urutan pseudorandom. Dan kompleksitas Kolmogorov tidak dapat ditentukan untuk dihitung secara umum.

Seperti yang ditunjukkan Gilles dalam komentar, ada RNG berbasis perangkat keras yang dibangun dari proses elektronik fisik seperti yang terkait dengan noise kuantum. ini jika direkayasa dengan benar tidak dapat dipecahkan.

vzn
sumber
"PRNG nontrivial dibangun sehingga algoritme mereka tidak dapat dideteksi (diturunkan)" - Saya rasa itu tidak benar. Faktanya, kalimat Anda berikutnya bertentangan dengannya. Apakah Anda ingin mengedit jawaban Anda untuk memperbaikinya?
DW
itu bisa disempurnakan lebih tepatnya tetapi tidak mengikuti, apa keberatan spesifik Anda? intinya adalah bahwa algoritma yang menghasilkan urutan tidak dapat ditentukan hanya dari urutan data saja, kecuali dengan kekuatan kasar, jika algoritma aman, dan kekuatan kasar tidak mungkin berhasil dalam kasus itu.
vzn
1
Keberatan khusus saya adalah bahwa kalimat itu terdengar salah bagi saya: sepertinya Anda mengatakan bahwa PRNG dirancang sehingga seseorang yang mengamati output mereka tidak dapat menyimpulkan apa algoritmanya, tetapi bukan itu yang terjadi dalam kehidupan nyata. Kebanyakan PRNG tidak dibangun untuk mencegah seseorang mempelajari algoritma; biasanya, algoritmanya bersifat publik. Mungkin maksud Anda bahwa PRNG dibuat sehingga outputnya tidak dapat dibedakan dari bit-bit yang benar-benar acak?
DW
1
"Algoritma yang menghasilkan urutan tidak dapat ditentukan hanya dari urutan data saja, kecuali dengan kekuatan kasar, jika algoritme aman" - Ini juga tidak benar. The algoritma biasanya publik. Hanya benih yang non-publik, dan hanya benih yang seharusnya sulit diperoleh dari hasil.
DW
-1

Sebenarnya segala sesuatu yang dilakukan komputer klasik adalah deterministik, dalam arti bahwa ketika Anda memberi mereka beberapa tugas, ia mengikuti mereka dengan cara deterministik. Oleh karena itu jika Anda ingin memiliki satu nomor acak, Anda dapat menghitungnya sesuai dengan waktu (berdasarkan waktu input pengguna), tetapi jika Anda ingin memiliki satu set angka acak, Anda tidak dapat menggunakan waktu untuk nomor berikutnya, karena angka tidak lagi independen.

Apa yang dilakukan orang adalah dengan menggunakan generator pseudo-acak yang memiliki seed, yaitu nomor yang digunakan untuk menghitung semua nomor generator nomor pseudo-acak (dalam beberapa kasus simulasi atau tugas lain yang lebih canggih, mungkin diperlukan lebih banyak benih , jika lebih dari satu set angka acak independen diperlukan). Benih biasanya 0 atau nomor tertentu jika Anda ingin hasil yang dapat direproduksi, atau waktu jika Anda dan hasil yang berbeda tidak dapat diproduksi.

Fakta bahwa generator angka pseudo-acak cukup baik, terletak pada fakta bahwa mereka mengikuti "karakteristik dasar dari generasi nomor pseudo-acak", agar dapat dihitung secara efisien dan berperilaku seperti bilangan acak nyata:

  • angka-angka yang dihasilkan harus mengikuti distribusi yang seragam (dari distribusi ini Anda dapat mencapai distribusi lainnya);
  • angka-angka yang dihasilkan harus independen secara statistik;
  • urutannya dapat direproduksi (titik ini diberlakukan karena properti perangkat keras komputer klasik, dan itulah sebabnya mereka disebut "angka pseudo-acak");
  • periode urutannya harus cukup besar;
  • generasi angka harus cepat.

Dari setiap nomor urutan angka pseudo-acak nomor baru dihitung (biasanya kita bekerja dengan bilangan bulat). Namun ada periode, n, dalam urutan generator pseudo-acak nomor yang disiapkan untuk bekerja dalam basis tertentu dengan jumlah bit terbatas yang tersedia untuk mengekspresikan angka (mis. Biner). Jika n ini tidak akan cukup besar akan ada masalah serius, tetapi jangan khawatir, para ilmuwan komputer memilih benih dan parameter lain dari generator pseudo-acak dengan baik, untuk mendapatkan n yang baik.

Misalnya, generator nomor pseudo-acak yang mungkin, dengan metode linear kongruensial, yang merupakan salah satu algoritma generator nomor pseudo-acak tertua dan terbaik yang dapat didefinisikan sesuai dengan:

ia memiliki empat nilai:
- x_0 ≥ 0
- a ≥ 0
- c ≥ 0
- m> x_0, di mana:

x0 adalah nilai awal, a, c, dan m adalah konstanta di mana: m> a, m> c, dan menghasilkan urutan dengan fornula:

x_ {i + 1} = (a * x_i + c) MOD m

Nilai untuk konstanta ini harus dipilih dengan cermat. Satu kemungkinan adalah:

x_ {i + 1} = (1664525 * x_i + 1013904223) MOD 2 ^ 32, ref. [1-2]

Ada algoritma lain yang lebih canggih untuk menghasilkan angka acak, yang menghindari beberapa masalah dari algoritma sebelumnya, yang termasuk: [3]

  • periode yang lebih pendek dari yang diperkirakan untuk beberapa kondisi benih (kondisi benih tersebut dapat disebut 'lemah' dalam konteks ini);
  • kurangnya keseragaman distribusi untuk sejumlah besar jumlah yang dihasilkan;
  • korelasi nilai-nilai berturut-turut;
  • distribusi dimensi urutan output yang buruk;
  • jarak antara di mana nilai-nilai tertentu terjadi didistribusikan secara berbeda dari mereka yang berada dalam distribusi urutan acak.

Di masa depan, komputer klasik dapat disatukan dengan sistem kuantum yang dapat memberikan angka yang benar-benar acak, dan mengirimkannya. [4]

referensi:
[1] http://en.wikipedia.org/wiki/linear_congruential_generator
[2] William H., et al. (1992). "Resep numerik dalam fortran 77: Seni komputasi ilmiah" (2nd ed.). ISBN 0-521-43064-X.
[3] http://en.wikipedia.org/wiki/pseudorandom_number_generator
[4] http://www.technologyreview.com/view/418445/first-evidence-that-quantum-processes-generate-truly-random-number /

sissi_luaty
sumber
Ini tidak benar-benar menjawab pertanyaan. Anda menjelaskan cara membuat angka acak, bukan untuk mendeteksi apakah RNG yang diberikan adalah acak. Bahkan ketika penjelasan Anda agak kurang, kongruensi linier hampir tidak "salah satu yang terbaik". Perangkat keras RNG memang ada sekarang, tidak ada kebutuhan untuk komputasi kuantum; ada peluang bagus bahwa Anda memiliki satu di PC Anda, satu di telepon Anda dan bahkan satu di kartu kredit Anda.
Gilles 'SO- berhenti bersikap jahat'