Mengapa kita tidak menggabungkan generator bilangan acak?

Ada banyak aplikasi di mana generator angka acak pseudo digunakan. Jadi orang menerapkan satu yang mereka anggap hebat hanya untuk menemukan kemudian bahwa itu cacat. Sesuatu seperti ini terjadi dengan generator nomor acak Javascript baru-baru ini. RandU jauh lebih awal juga. Ada juga masalah penyemaian awal yang tidak tepat untuk sesuatu seperti Twister.

Saya tidak dapat menemukan contoh siapa pun yang menggabungkan dua atau lebih keluarga generator dengan operator xor biasa. Jika ada kekuatan komputer yang cukup untuk menjalankan hal-hal seperti implementasi java.SecureRandom atau Twister, mengapa orang tidak menggabungkannya? ISAAC xor XORShift xor RandU harus menjadi contoh yang cukup baik, dan di mana Anda dapat melihat kelemahan satu generator sedang dikurangi oleh yang lain. Ini juga harus membantu dengan distribusi angka ke dimensi yang lebih tinggi karena algoritma intrinsik sangat berbeda. Apakah ada prinsip dasar yang tidak boleh digabungkan?

Jika Anda membangun generator angka acak yang benar, orang mungkin akan menyarankan Anda menggabungkan dua atau lebih sumber entropi. Apakah contoh saya berbeda?

Saya tidak termasuk contoh umum dari beberapa register shift umpan balik linier yang bekerja bersama karena mereka berasal dari keluarga yang sama.

IIRC (dan ini dari memori), buku terlaris Rand 1955, A Million Random Digit melakukan sesuatu seperti ini. Sebelum komputer murah, orang-orang memilih nomor acak dari buku ini.

Para penulis menghasilkan bit acak dengan noise elektronik, tetapi itu ternyata biassed (sulit untuk membuat flipflop menghabiskan waktu yang persis sama pada flip dan flop). Namun, menggabungkan bit membuat distribusinya jauh lebih seragam.

Tentu, Anda dapat menggabungkan PRNG seperti ini, jika mau, dengan asumsi mereka diunggulkan secara independen. Namun, itu akan lebih lambat dan mungkin tidak akan menyelesaikan masalah paling mendesak yang orang miliki.

Dalam praktiknya, jika Anda memiliki persyaratan untuk PRNG yang sangat berkualitas tinggi, Anda menggunakan PRNG kekuatan kriptografi yang teruji dengan baik dan Anda menyemainya dengan entropi sejati. Jika Anda melakukan ini, mode kegagalan Anda kemungkinan besar tidak masalah dengan algoritma PRNG itu sendiri; mode kegagalan yang paling mungkin adalah kurangnya entropi yang memadai (atau mungkin kesalahan implementasi). Xor-ing beberapa PRNG tidak membantu dengan mode kegagalan ini. Jadi, jika Anda menginginkan PRNG yang sangat berkualitas tinggi, mungkin ada gunanya mengatasinya.

Atau, jika Anda menginginkan PRNG statistik yang cukup baik untuk tujuan simulasi, biasanya masalah # 1 adalah kecepatan (menghasilkan angka pseudorandom sangat cepat) atau kesederhanaan (tidak ingin menghabiskan banyak waktu pengembangan untuk meneliti atau mengimplementasikannya). Xor-ing memperlambat PRNG dan membuatnya lebih kompleks, sehingga tidak memenuhi kebutuhan primer dalam konteks itu.

Selama Anda menunjukkan perhatian dan kompetensi yang wajar, PRNG standar lebih dari cukup baik, sehingga benar-benar tidak ada alasan mengapa kita membutuhkan sesuatu yang lebih mewah (tidak perlu untuk dilakukan). Jika Anda bahkan tidak memiliki tingkat perawatan atau kompetensi minimal, Anda mungkin tidak akan memilih sesuatu yang kompleks seperti xor-ing, dan cara terbaik untuk meningkatkan hal-hal adalah dengan fokus pada lebih banyak perhatian dan kompetensi dalam pemilihan PRNG bukan pada xor-ing.

Intinya : Pada dasarnya, xor trick tidak menyelesaikan masalah yang biasanya dialami orang ketika menggunakan PRNG.

Bahkan, sesuatu terobosan baru saja diumumkan dengan melakukan ini dengan tepat.

Profesor ilmu komputer Universitas Texas, David Zuckerman dan mahasiswa PhD Eshan Chattopadhyay menemukan bahwa angka acak "berkualitas tinggi" dapat dihasilkan dengan menggabungkan dua sumber acak "berkualitas rendah".

Inilah makalah mereka: Ekstraktor Dua Sumber Eksplisit dan Fungsi Tangguh

Misalkan adalah urutan biner pseudorandom. Yaitu, setiap adalah variabel acak yang didukung pada , dan variabel belum tentu independen. Kita dapat memikirkan urutan ini yang dihasilkan dengan cara berikut: pertama kita sampel kunci acak acak , dan kemudian menggunakan beberapa fungsi untuk menghasilkan urutan pseudorandom.$X_1,\ldots,X_n$$X_i$$\{0,1\}$$X_1,\ldots,X_n$$K$$f(K)$

Bagaimana kita mengukur seberapa baik urutan pseudorandom ? Meskipun dimungkinkan untuk mengukur seberapa baik realisasi tertentu (katakanlah menggunakan kompleksitas Kolmogorov), di sini saya akan berkonsentrasi pada langkah-langkah yang bergantung pada seluruh distribusi variabel acak . Salah satu contohnya adalah entropi, tetapi kita hanya akan memerlukan dua properti ukuran : ( lebih besar berarti urutan yang lebih acak)$X_1,\ldots,X_n$$(X_1,\ldots,X_n)$$L$$L(\cdot)$

• Jika adalah urutan deterministik (yaitu, urutan tetap) maka . L ( X 1 ⊕ y 1 , ... , X n ⊕ y n ) = L ( X 1 , ... , X n$y_1,\ldots,y_n$$L(X_1 \oplus y_1, \ldots, X_n \oplus y_n) = L(X_1,\ldots,X_n)$

• Jika adalah dua urutan pseudorandom yang independen, adalah bit acak independen, dan , lalu .$\vec{X^0},\vec{X^1}$$T \in \{0,1\}$$\vec{Z} = \vec{X^T}$$L(\vec{Z}) \geq \min(\vec{X^0},\vec{X^1})$

Properti pertama berarti bahwa ukurannya tidak berubah di bawah membalik bit ke- . Properti kedua berarti bahwa jika kita mencampur dua distribusi , maka hasilnya setidaknya sama baiknya dengan yang lebih buruk.$i$$\vec{X},\vec{Y}$

Setiap tindakan pengacakan yang masuk akal akan memuaskan properti pertama. Properti kedua dipenuhi oleh langkah-langkah paling populer seperti entropi dan min-entropi .$H$$H_\infty$

Kita sekarang dapat menyatakan dan membuktikan teorema yang menunjukkan bahwa XORing dua urutan pseudorandom selalu merupakan ide yang baik.

Dalil. Biarkan menjadi dua urutan pseudorandom independen dengan panjang yang sama, dan biarkan menjadi ukuran keacakan yang dapat diterima (satu memenuhi dua kondisi di atas). Kemudian$\vec{X},\vec{Y}$$L$

Bukti. Misalkan . Kemudian adalah campuran dari distribusi , dicampur sesuai dengan distribusi . Karena dan campuran setidaknya sama baiknya dengan distribusi terburuk yang dicampur, kami memperoleh . $L(X) \geq L(Y)$$X \oplus Y$$X \oplus y$$Y$$L(X \oplus y) = L(X)$$L(X \oplus Y) \geq L(X)$$~\square$

Maksud teorema ini adalah bahwa jika Anda XOR dua urutan pseudorandom yang dihasilkan menggunakan dua kunci independen , hasilnya selalu setidaknya sebagus urutan yang lebih baik yang XOR, sehubungan dengan setiap ukuran keacakan yang diizinkan.

Dalam praktiknya, untuk menggunakan dua kunci independen, kami mungkin memperluas satu kunci menjadi dua kunci secara pseudorandom. Kedua kunci tersebut kemudian tidak independen. Namun, jika kita menggunakan cara "mahal" untuk memperluas satu kunci menjadi dua kunci, kita mengharapkan dua kunci yang dihasilkan untuk "terlihat" independen, dan teorema itu memegang "secara moral". Dalam kriptografi teoretis ada cara untuk membuat pernyataan ini tepat.

Haruskah kita, kemudian, XOR dua generator nomor pseudorandom? Jika kita tidak dibatasi oleh kecepatan, maka itu ide yang bagus. Namun dalam praktiknya kami memiliki batas kecepatan. Kami kemudian dapat mengajukan pertanyaan berikut. Misalkan kita diberi dua PRNG, masing-masing dengan parameter yang mengontrol waktu berjalan (dan juga kekuatan) generator. Sebagai contoh, bisa menjadi panjang LFSR, atau jumlah putaran. Misalkan kita menggunakan satu PRNG dengan parameter , yang lain dengan parameter , dan XOR hasilnya. Kita dapat mengasumsikan bahwa , sehingga total waktu berjalan konstan. Apa pilihan terbaik dari$T$$T$$T_1$$T_2$$T_1 + T_2 = t$$T_1,T_2$? Di sini ada tradeoff yang sulit dijawab secara umum. Mungkin saja pengaturannya jauh lebih buruk daripada atau .$(t/2,t/2)$$(t,0)$$(0,t)$

Saran terbaik di sini adalah tetap berpegang pada PRNG populer yang dianggap kuat. Jika Anda dapat meluangkan lebih banyak waktu untuk membuat urutan Anda, XOR beberapa salinan, menggunakan kunci independen (atau kunci yang dihasilkan dengan memperluas satu kunci menggunakan PRNG mahal).

Saya akan mencoba ini, karena saya cukup terganggu dengan saran yang diberikan dalam beberapa jawaban lain.

Biarkan menjadi urutan bit tak terbatas yang dihasilkan oleh dua RNG (tidak harus PRNG yang bersifat deterministik begitu keadaan awal diketahui), dan kami sedang mempertimbangkan kemungkinan menggunakan urutan dengan harapan meningkatkan perilaku dalam beberapa hal. Ada banyak cara berbeda di mana dapat dianggap lebih baik atau lebih buruk dibandingkan dengan masing-masing dari dan ; di sini ada segelintir kecil yang saya yakin bermakna, bermanfaat, dan konsisten dengan penggunaan normal kata "lebih baik" dan "lebih buruk":$\vec{X},\vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X}$$\vec{Y}$

• (0) Probabilitas keacakan benar urutan meningkat atau menurun
• (1) Probabilitas kenaikan atau penurunan yang tidak acak yang dapat diamati (berkenaan dengan beberapa pengamat yang menerapkan sejumlah pengawasan tertentu, mungkin)
• (2) Tingkat keparahan / kejelasan non-keacakan yang diamati meningkat atau menurun.

Pertama mari kita pikirkan (0), yang merupakan satu-satunya dari ketiganya yang memiliki harapan untuk dibuat tepat. Perhatikan bahwa jika, pada kenyataannya, salah satu dari dua input RNG benar-benar acak, tidak memihak, dan independen dari yang lain, maka hasil XOR akan benar-benar acak dan tidak bias juga. Dengan mengingat hal itu, pertimbangkan kasus ketika Anda meyakini sebagai stream bit terisolasi terisolasi yang benar-benar acak, tetapi Anda tidak sepenuhnya yakin. Jika adalah masing-masing probabilitas yang Anda salah tentang masing-masing, maka probabilitas bahwa tidak-benar-acak adalah , sebenarnya jauh lebih sedikit sejak$\vec{X},\vec{Y}$$\varepsilon_X,\varepsilon_Y$$\vec{X} \oplus \vec{Y}$$\leq \varepsilon_X \varepsilon_Y \lt min\{\varepsilon_X,\varepsilon_Y\}$$\varepsilon_X,\varepsilon_Y$ dianggap sangat mendekati 0 ("Anda yakin mereka benar-benar acak"). Dan faktanya bahkan lebih baik dari itu, ketika kita juga memperhitungkan kemungkinan menjadi benar-benar independen bahkan ketika keduanya tidak benar-benar acak: Karena itu kita dapat menyimpulkan bahwa dalam arti (0), XOR tidak bisa sakit, dan berpotensi banyak membantu.$\vec{X},\vec{Y}$

Namun, (0) tidak menarik untuk PRNG, karena dalam kasus PRNG tidak ada urutan yang dipertanyakan yang memiliki peluang untuk menjadi benar-benar acak.

Karena itu untuk pertanyaan ini, yang sebenarnya tentang PRNG, kita harus berbicara tentang sesuatu seperti (1) atau (2). Karena itu adalah dalam hal sifat dan jumlah seperti "dapat diamati", "parah", "jelas", "jelas", kita sekarang berbicara tentang kompleksitas Kolmogorov, dan saya tidak akan mencoba untuk membuat yang tepat. Tetapi saya akan melangkah lebih jauh dengan membuat pernyataan yang diharapkan tidak kontroversial bahwa, dengan ukuran seperti itu, "01100110 ..." (periode = 4) lebih buruk daripada "01010101 ..." (periode = 2) yang lebih buruk daripada " 00000000 ... "(konstan).

Sekarang, orang mungkin menebak bahwa (1) dan (2) akan mengikuti tren yang sama dengan (0), dan oleh karena itu kesimpulan "XOR tidak dapat terluka" mungkin masih berlaku. Namun, catat kemungkinan signifikan bahwa baik maupun yang diamati non-acak, tetapi korelasi di antara mereka menyebabkan secara non-acak dapat diamati. Kasus yang paling parah dari ini, tentu saja, adalah ketika (atau ), dalam hal ini konstan, yang terburuk dari semua hasil yang mungkin; secara umum, mudah untuk melihat itu, terlepas dari seberapa bagus dan ,$\vec{X}$$\vec{Y}$$\vec{X} \oplus \vec{Y}$$\vec{X} = \vec{Y}$$\vec{X} = \mathrm{not}(\vec{Y})$$\vec{X} \oplus \vec{Y}$$\vec{X}$$\vec{Y}$$\vec{X}$dan harus "dekat" dengan independen agar xornya menjadi non-acak. Pada kenyataannya, menjadi tidak tergantung secara wajar dapat didefinisikan sebagai menjadi tidak dapat diobservasi-nonrandom.$\vec{Y}$$\vec{X} \oplus \vec{Y}$

Ketergantungan yang mengejutkan seperti itu ternyata menjadi masalah yang sangat besar.

Contoh dari apa yang salah

Pertanyaannya menyatakan "Saya tidak termasuk contoh umum dari beberapa register shift umpan balik linier yang bekerja bersama karena mereka berasal dari keluarga yang sama". Tetapi saya akan mengecualikan pengecualian itu untuk saat ini, untuk memberikan contoh nyata yang sangat sederhana tentang hal-hal yang bisa salah dengan XORing.

Contoh saya adalah implementasi rand () lama yang ada pada beberapa versi Unix sekitar tahun 1983. IIRC, implementasi fungsi rand () ini memiliki properti berikut:

• nilai setiap panggilan ke rand () adalah 15 bit pseudo-acak, yaitu bilangan bulat dalam kisaran [0, 32767).
• nilai pengembalian berurutan berganti genap-ganjil-genap; yaitu, bit paling tidak signifikan berganti 0-1-0-1 ...
• bit berikutnya-ke-paling tidak signifikan memiliki periode 4, berikutnya setelah itu memiliki periode 8, ... sehingga bit urutan tertinggi memiliki periode .$2^{15}$
• oleh karena itu urutan nilai pengembalian 15-bit rand () adalah periodik dengan periode .$2^{15}$

Saya tidak dapat menemukan kode sumber asli, tetapi saya menduga dari menyatukan beberapa posting dari di https://groups.google.com/forum/#!topic/comp.os.vms/9k4W6KrRV3A yang ia melakukan persis yang berikut (kode C), yang sesuai dengan ingatan saya tentang properti di atas:

#define RAND_MAX 32767
static unsigned int next = 1;
int rand(void)
{
    next = next * 1103515245 + 12345;
    return (next & RAND_MAX);
}
void srand(seed)
unsigned int seed;
{
    next = seed;
}

Seperti yang mungkin dibayangkan, mencoba menggunakan rand ini () dengan berbagai cara menyebabkan bermacam-macam kekecewaan.

Misalnya, pada satu titik saya mencoba mensimulasikan urutan membalik koin acak dengan berulang kali mengambil:

rand() & 1

yaitu bit paling signifikan. Hasilnya adalah pergantian kepala-ekor-kepala-ekor yang sederhana. Itu sulit dipercaya pada awalnya (pasti ada bug di program saya!), Tetapi setelah saya meyakinkan diri sendiri itu benar, saya mencoba menggunakan bit berikutnya yang paling tidak signifikan. Itu tidak jauh lebih baik, seperti disebutkan sebelumnya - bit itu adalah periodik dengan periode 4. Terus mengeksplorasi bit-bit yang lebih tinggi secara berturut-turut mengungkapkan pola yang saya catat sebelumnya: yaitu, setiap bit orde tinggi berikutnya memiliki dua kali periode sebelumnya, jadi dalam hormat ini bit orde tertinggi adalah yang paling berguna dari semuanya. Namun perhatikan bahwa tidak ada ambang hitam-putih "bit berguna, bit tidak berguna" di sini; yang bisa kita katakan adalah posisi bit bernomor memiliki tingkat kegunaan / kegunaan yang berbeda-beda.$i$$i-1$

Saya juga mencoba hal-hal seperti mengacak hasil lebih lanjut, atau XORing bersama nilai yang dikembalikan dari beberapa panggilan ke rand (). XORing pasangan rand () nilai yang berurutan adalah bencana, tentu saja - itu menghasilkan semua angka ganjil! Untuk tujuan saya (yaitu menghasilkan urutan membalik koin yang tampaknya acak), hasil paritas konstan XOR bahkan lebih buruk daripada perilaku bolak-balik genap asli.

Variasi sedikit menempatkan ini ke dalam kerangka kerja asli: yaitu, mari menjadi urutan nilai 15-bit yang dikembalikan oleh rand () dengan seed diberikan , dan urutan dari seed yang berbeda . Sekali lagi, akan menjadi urutan angka all-even atau all-odd, yang lebih buruk daripada perilaku genap even / odd.$\vec{X}$$s_X$$\vec{Y}$$s_Y$$\vec{X} \oplus \vec{Y}$

Dengan kata lain, ini adalah contoh di mana XOR memperburuk keadaan dalam arti (1) dan (2), oleh interpretasi yang masuk akal. Lebih buruk dalam beberapa hal lain juga:

• (3) Bit-paling-signifikan XOR jelas-jelas bias, yaitu memiliki frekuensi yang tidak sama antara 0 dan 1, tidak seperti posisi bit bernomor dalam salah satu input yang semuanya tidak bias.
• (4) Faktanya, untuk setiap posisi bit, ada pasangan biji yang posisi bitnya bias dalam hasil XOR, dan untuk setiap pasangan biji, ada (setidaknya 5) posisi bit yang bias dalam XOR hasil.
• (5) Periode seluruh urutan nilai 15-bit dalam hasil XOR adalah 1 atau , dibandingkan dengan untuk aslinya. 2 $2^{14}$$2^{15}$

Tidak satu pun dari (3), (4), (5) yang jelas, tetapi semuanya mudah diverifikasi.

Akhirnya, mari pertimbangkan untuk memperkenalkan kembali larangan PRNG dari keluarga yang sama. Masalahnya di sini, saya pikir, adalah tidak pernah benar-benar jelas apakah dua PRNG adalah "dari keluarga yang sama", sampai / kecuali seseorang mulai menggunakan XOR dan pemberitahuan (atau pemberitahuan penyerang) hal-hal menjadi lebih buruk dalam arti (1) dan (2), yaitu sampai pola-pola non-acak dalam keluaran melewati ambang batas dari tidak diperhatikan menjadi diperhatikan / memalukan / berbahaya, dan pada saat itu sudah terlambat.

Saya khawatir dengan jawaban lain di sini yang memberikan saran yang tidak memenuhi syarat "XOR tidak ada salahnya" atas dasar langkah-langkah teoritis yang menurut saya melakukan pekerjaan yang buruk dalam pemodelan apa yang kebanyakan orang anggap sebagai "baik" dan "buruk" tentang PRNG dalam kehidupan nyata. Saran itu bertentangan dengan contoh-contoh yang jelas dan terang-terangan di mana XOR memperburuk keadaan, seperti contoh rand () yang diberikan di atas. Meskipun dapat dibayangkan bahwa PRNG yang relatif "kuat" dapat secara konsisten menampilkan perilaku yang berlawanan ketika XOR dibandingkan dengan mainan PRNG yang rand (), sehingga membuat XOR ide yang baik untuk mereka, saya belum melihat bukti ke arah itu, secara teori atau empiris, jadi sepertinya tidak masuk akal bagi saya untuk menganggap itu terjadi.

Secara pribadi, setelah digigit kejutan oleh XORing rand () di masa muda saya, dan oleh banyak korelasi kejutan beragam lainnya sepanjang hidup saya, saya memiliki sedikit alasan untuk berpikir hasilnya akan berbeda jika saya mencoba taktik yang sama lagi. Itulah sebabnya saya, secara pribadi, akan sangat enggan XOR bersama-sama beberapa PRNG kecuali jika analisis yang sangat luas dan pemeriksaan telah dilakukan untuk memberi saya kepercayaan diri bahwa mungkin aman untuk melakukannya untuk RNG tertentu yang dimaksud. Sebagai obat potensial ketika saya memiliki kepercayaan diri yang rendah pada satu atau lebih PRNG individu, XORing mereka tidak mungkin meningkatkan kepercayaan diri saya, jadi saya tidak mungkin menggunakannya untuk tujuan seperti itu. Saya membayangkan jawaban untuk pertanyaan Anda adalah bahwa ini adalah sentimen yang dipegang secara luas.

PENOLAKAN: Jawaban ini semata-mata tentang "Kita adalah kita tidak melakukannya" dan bukan "inilah bukti matematika mengapa itu bisa atau tidak bisa bekerja". Saya tidak mengklaim bahwa XOR memperkenalkan (atau tidak) kerentanan kriptografi. Maksud saya hanya pengalaman yang menunjukkan kepada kita bahwa skema paling sederhana pun hampir selalu menimbulkan konsekuensi yang tidak terduga - dan inilah mengapa kita menghindarinya.

"Keacakan" hanyalah puncak gunung es ketika berbicara tentang RNG dan PRNG. Ada kualitas lain yang penting, misalnya keseragaman.

Bayangkan sebuah dadu umum yang merupakan RNG yang cukup bagus. Tapi sekarang katakanlah Anda membutuhkan rentang 1-5 bukan 1-6. Hal pertama yang terlintas dalam pikiran adalah dengan hanya menghapus 6 wajah dan menggantinya dengan tambahan 1. "Keacakan" tetap (hasilnya masih benar-benar acak), namun keseragaman sangat menderita: sekarang 1 dua kali lebih mungkin sebagai hasil lainnya.

Menggabungkan hasil dari beberapa RNG adalah kemiringan yang sama licinnya. Misalnya. sederhana menambahkan 2 lemparan dadu sepenuhnya menghapus keseragaman, karena "7" sekarang 6 kali lebih mungkin daripada "2" atau "12". Saya setuju bahwa XOR terlihat lebih baik daripada penambahan pada pandangan pertama, tetapi dalam PRNG tidak ada yang berubah seperti yang terlihat pada pandangan pertama.

Inilah sebabnya mengapa kita cenderung berpegang pada implementasi yang dikenal - karena seseorang menghabiskan banyak waktu dan uang untuk meneliti mereka dan semua kekurangannya diketahui, dipahami dan dapat diatasi. Ketika Anda meluncurkannya sendiri, Anda berpotensi menciptakan kerentanan dan Anda harus melakukan upaya serupa untuk membuktikannya. Seperti yang ditunjukkan contoh tambahan dadu, menggabungkan bisa tidak jauh berbeda dengan membuat yang baru dari awal.

Keamanan adalah rantai, sekuat komponen terlemah. Aturan praktis dalam keamanan: setiap kali Anda menggabungkan 2 hal, Anda biasanya mendapatkan sejumlah kekurangan, bukan jumlah kekuatan.