Acak (adj): a: kurang rencana, tujuan, atau pola yang pasti. b: dibuat, dilakukan, atau dipilih secara acak c: berkaitan dengan, memiliki, atau menjadi elemen atau peristiwa dengan kemungkinan terjadinya yang pasti. d: menjadi atau berkaitan dengan himpunan atau unsur himpunan yang masing-masing unsurnya memiliki probabilitas kejadian yang sama. [Kamus Inggris Oxford]

Sebelum memulai diskusi mendalam tentang seni “keacakan yang sebenarnya”, pertama-tama harus dijelaskan bahwa keacakan yang sebenarnya secara teoritis tidak mungkin dilakukan oleh prinsip-prinsip yang menentukan alam semesta kita. Definisi di atas dengan jelas mendefinisikan paradoks yang mengelilingi konsep keacakan ketika tunduk pada probabilitas. Intinya kita akan mengklaim bahwa “benar-benar acak” adalah keadaan di mana untuk himpunan A tertentu, untuk setiap i, elemen di A, i jika dipilih secara acak, memiliki probabilitas [1 / | A |] (di mana | x | menunjukkan kardinalitas himpunan) kejadian. Ini adalah bagaimana kita menilai “keacakan” dari Random Number Generator (RNG (s)), dengan kemampuannya untuk mengeksploitasi probabilitas; diberikan himpunan A, RNG sempurna tidak akan mengulangi elemen sebelum himpunan habis; digambarkan sebagai periode generator, titik pengulangannya.

Harus dicatat bahwa mendefinisikan pilihan sebagai acak adalah klasifikasi yang bergantung pada ketidaktahuan murni tentang penyebab dan peristiwa yang menghasilkan pilihan akhir. Dengan mengesampingkan itu, diskusi filosofis tentang “keacakan yang sebenarnya” akan ditinggalkan. Sisa diskusi akan menilai “keacakan yang sebenarnya” seperti yang dinyatakan di atas; distribusi probabilistik sempurna di atas medan berhingga tertentu. Meskipun distribusi seperti itu tidak pernah mungkin dilakukan dengan berbagai algoritme yang didiskusikan, (artinya distribusi seperti itu tidak dapat sempurna pada setiap kemunculan algoritme tertentu) distribusi yang relatif baik sudah cukup.

I.i Berbagai Penggunaan Generator Angka Acak:

Bilangan acak memiliki banyak aplikasi. Yang menarik untuk penelitian ini dan penelitian selanjutnya yang dimaksudkan oleh penulis adalah Kriptografi. Banyak protokol kriptografi menggunakan RNG, terutama, kriptografi kunci publik (RSA) dan beberapa implementasi cipher simetris (DES, Serpent). Selain fungsi kriptografi, RNG digunakan dalam Simulasi, untuk rekreasi realistis kejadian “alam”; dalam hal ini, game komputer memenuhi syarat sebagai simulasi, di mana RNG banyak digunakan dalam hubungannya dengan bobot probabilitas (Gaussian). Mereka juga digunakan untuk pengujian integritas pada berbagai aplikasi komputer selama pengembangan, bahkan pengujian perangkat keras, seperti GPU ke pipeline memori pada kartu grafis berbasis AGP. Di antara yang disebutkan adalah banyak kegunaan dan tujuan lain untuk pengembangan dan “kesempurnaan” membuat pilihan yang benar-benar acak.

I.ii Pengantar Algoritma Singkat:

Algoritme penghasil angka acak datang dalam berbagai bentuk; ini dapat dipisahkan menjadi dua kelompok utama, generator bilangan linier (LNG (s)) dan pembangkit bilangan non-linier (NLNG (s)). Setiap grup berisi beberapa jenis RNG dan masing-masing memiliki tujuan dan kegunaannya masing-masing. Penting untuk diketahui bahwa meskipun tidak semua generator dibuat sama, generator yang baik memiliki tujuan yang tidak cocok untuk generator lain yang baik.

I.ii.a Generator Nomor Linear:

Linear Congruential Generators (LCG (s)) layak disebut pertama kali semata-mata atas dasar keberadaan di mana-mana. LCG dan berbagai pemunculan serta modifikasinya digunakan dalam berbagai aplikasi. LNG dalam bentuk paling murni hampir dapat diprediksi seperti Urutan Fibonacci. Ini adalah generator unggulan yang membuat “pilihan” mereka – jika itu dapat dikatakan – secara linier di bidang terbatas yang diberikan, berdasarkan benihnya. Hadir dalam lebih banyak rasa daripada kebanyakan jenis generator lainnya, tidak diragukan lagi, karena kesederhanaan memodifikasi algoritme untuk tujuan tertentu.

I.ii.b Generator Nomor Non-Linear:

The Inversive Congruential Generator (ICG (s)) dan Explicit Inversive Congruential Generator (EICG (s)) adalah dua fokus utama dalam kategori ini. Generator ini non-linier (seperti yang tersirat), dan oleh karena itu tidak dapat diprediksi seperti halnya LNG. Juga disebutkan dalam grup non-linier adalah generator Register Geser Umpan Balik Linear (LFSR (s)). Generator ini walaupun linier, seperti yang tersirat dari namanya, mengusung prinsip-prinsip Non Linear Generator dalam implementasinya; sedemikian rupa, sehingga LFSR sangat mirip dengan counter part non-linearnya, generator Register Geser Umpan Balik Non-Linear. Rincian sejarah Register Geser Umpan Balik sedikit di luar cakupan makalah ini namun pengantar singkat untuk prinsip-prinsip fungsi umpan balik dan register geser diberikan secara paralel dengan diskusi LFSR.

II Generator Kongruensial Linear:LNG akhirnya menghasilkan urutan bilangan bulat antara 0 dan modulus tertentu, untuk persamaan Ij + 1 = aIj + c (mod m). Dalam persamaan ini, m digunakan sebagai modulus, a adalah pengali, dan c adalah selisih. Urutan tersebut akan berulang dalam periode m, di mana m biasanya adalah bilangan prima.

Keuntungan dari LNG segera terlihat dari persamaan di atas; cepat, membutuhkan satu perkalian, satu penambahan, dan satu modulus. Ini segera cocok untuk menjelaskan kegunaannya yang luas. Jenis generator ini digunakan dalam banyak aplikasi yang sifat dari urutan acak tidak menjadi masalah, hanya saja urutannya berbeda dari eksekusi hingga eksekusi; Simulasi Monte Carlo misalnya. Kecepatan dan kesederhanaan algoritme juga mengarah pada jumlah rasa yang dikembangkan untuk berbagai aplikasi. Misalnya, persamaan di atas adalah persamaan yang sama dengan yang telah di-dubbing oleh komite ANSI C / C ++ untuk digunakan dengan bahasa-bahasa ini, dengan nilai yang sesuai untuk a, c, dan m. Selain persamaan linier, ada juga:

LCG kuadrat:

Xn = (aXn-12 + bXn-1 + c) mod m

LCG kubik:

Xn = (aXn-13 + bXn-12 + cXn-1 + d) mod m

Genset Pekanbaru -Ada juga LCG polinomial, LCG terpotong, dll; masing-masing bekerja dengan prinsip yang sama dan umumnya dapat diprediksi dan dipecahkan. Misalnya, LCG standar pertama kali dipatahkan oleh Jim Reeds, dan Generator Kuadrat dan Kubik dipatahkan oleh Joan Boyar.

Perlu dicatat bahwa sebagian besar modifikasi pada LCG hanya menghasilkan generator yang paling buruk. Karena generator linier hanya dapat dinilai berdasarkan perkembangannya melalui bidang linier, dan bukan pada survei probabilistik dari himpunan tertentu, periode LCG adalah yang terpenting, lebih dari generator Kongruensial lainnya, bahkan di bidang non-linier . Ada beberapa metode untuk memperpanjang periode generator tertentu, bagaimanapun banyak upaya, tidak dapat diprediksi menghasilkan periode yang lebih pendek. Riwayat komputasi, baik perangkat keras maupun perangkat lunak, dipenuhi dengan upaya “gagal” untuk meningkatkan LCG. Khususnya, mainframe IBM awal dengan rutin RANDU, menggunakan a = 65539, dan m = 231 menghasilkan plot n-dimensi hanya dalam 11 dimensi bidang. Ada juga masalah penyemaian generator; setiap urutan hanya seunik benihnya. Keamanan browser Netscape adalah satu poin yang dikompromikan karena prediktabilitas benih yang dipilih di dalamnya LCG yang darinya kunci kripto dibuat.

LCG dapat dipaksakan secara probabilistik dengan menciptakan deviasi yang seragam. Masalah dengan fokus pada deviasi LCG adalah LCG yang terdistorsi dengan baik akan memiliki periode yang diperpanjang, tetapi kompleksitasnya meningkat, karena deviasi, terkadang di luar jangkauan LCG yang berguna. Dimungkinkan juga untuk menggunakan deviasi yang dinormalisasi dalam interval tertentu, seperti deviasi Gaussian, di mana periode diperpanjang sedemikian rupa sehingga setiap bilangan bulat dalam bidang tertentu dipilih.

III Generator Kongruensial Inversif dan Register Geser Umpan Balik Linear:

Didefinisikan sebagai generator non-linier kami, ICG dan EICG, yang dikembangkan oleh Eichenauer dan Lehn (1986, 1993) ditentukan oleh kesesuaian berikut:

yn + 1 = ayn + b (mod m)

Dimana, untuk kepraktisan, m juga dipilih sebagai bilangan prima yang sejajar dengan LCG. Kedua generator ini paling terkenal karena kompromi kecepatan dan efisiensi periode. Mereka menghasilkan periode yang relatif lama, dalam (5 – 10x rata-rata) lebih banyak waktu, daripada LCG.

III.i Register Geser Umpan Balik Linear:

Generator LFSR lebih relevan di sini, sebagai alternatif yang sesuai untuk LCG untuk aplikasi kriptografi. Register geser bekerja pada konsep menghasilkan pada tingkat bit, bukan dalam bidang terbatas basis 10. Mereka mengatasi masalah pembuatan distribusi seragam bit acak tunggal, dengan 0 dan 1 kemungkinan yang sama.

Generator LFSR terdiri dari dua bagian, register geser dan fungsi umpan balik. Register geser adalah urutan bit, di mana ukuran register geser ditentukan oleh panjang bit-bitnya. Ketika bit dibutuhkan, register digeser 1 bit ke kanan, dan bit kiri dihitung berdasarkan bit yang tersisa di register. Metode paling sederhana untuk merepresentasikan fungsi umpan balik LFSR adalah XOR dari bit register kunci. Metode yang digunakan oleh fungsi umpan balik disebut urutan tap.

Jelas, bahwa LFSR n-bit dapat berada dalam status 2n -1; mencatat bahwa ukuran register menunjukkan panjangnya. Oleh karena itu, register 4 bit (1111 akan disebut register 4 bit, berdasarkan kardinalitas register, daripada nilai bit orde tinggi, basis 10) akan menghasilkan 24-1, atau 15 status unik. Dengan urutan keluaran dari bit yang paling tidak signifikan setelah pergeseran, ukuran register menentukan periode atau 2n – 1 bit sebelum pengulangan, sehingga menghasilkan nilai basis 10 dari 22 ** n -1 sebagai nilai maksimum, dan periode. Untuk mencapai periode maksimum ini, polinomial primitif harus dibentuk oleh deret tap, di mana derajat polinomial tersebut menghasilkan panjang register geser.

III.i.a Polinomial Primitif dalam Register Geser Umpan Balik Linear

Polinomial primitif didefinisikan sebagai polinomial P yang tidak dapat direduksi dengan derajat d dalam [Z / p [x]] (menunjukkan bidang berhingga dari p [x] di Z) adalah primitif jika P membagi xd – 1 tetapi tidak membagi xi – 1 untuk sembarang bilangan bulat i dengan 0 xn = 1 mod P.

tapi,
xi! = 1 mod P untuk 0

Tidak perlu memeriksa semua nilai eksponensial yang lebih kecil dari d, tetapi hanya nilai yang mungkin dari pembagi derajat d.

Tidak ada metode yang mudah untuk menghasilkan polinomial primitif modulo 2 untuk derajat tertentu. Oleh karena itu, memilih polinomial acak dan menguji apakah primitifnya adalah metode yang paling banyak digunakan.

III.i.b Memaksimalkan dan Mencapai Periode LFSR

Sebagaimana disebutkan di atas, periode setiap LFSR didasarkan pada ukuran register geser; ukuran register geser didasarkan pada derajat polinomial, oleh karena itu periode LFSR ditentukan oleh polinomial yang digunakan. Polinomial primitif diperlukan di sini karena jika polinomial yang digunakan tidak primitif, periode akan diperpendek, dan mungkin terdapat status buruk yang dapat memperpendek periode lebih lanjut. Oleh karena itu, memilih polinomial primitif adalah hal yang sangat penting bagi LFSR mana pun.

Mengingat polinomialnya, x8 + x4 + x3 + x2 + x yang merupakan modulo 2 primitif, periode maksimal dapat dihasilkan. Eksponen pertama adalah panjang register geser, dan semua eksponen kecuali 1 dan 0 digunakan untuk menentukan urutan tap dengan fungsi umpan balik, di mana istilah derajat rendah sesuai dengan bit register paling kiri. Oleh karena itu, dalam register geser 8-bit tertentu, bit baru dihasilkan dengan meng-XOR bit register ke-8, ke-4, ke-3, dan ke-2 secara bersamaan. LFSR yang dihasilkan dari polinomial ini akan memiliki periode yang tepat 28-1.

Register Geser Umpan Balik Linear ditemukan di banyak tempat, seperti dalam rutinitas Fast Prime Generation Ueli Maurer, tetapi paling umum di domain stream-cipher kriptografi. Oleh karena itu, perbanyakan polinomial primitif penting untuk keberhasilan sandi tersebut. Polinomial yang digunakan dalam LFSR sama pentingnya dengan seed yang digunakan dalam LCG. Sama seperti LCG dipecahkan oleh benih deterministik, LFSR juga dipecahkan oleh banyak organisasi, berdasarkan penggunaan dan penggunaan kembali polinomial primitif deterministik. Perlu juga dicatat bahwa algoritme itu sendiri sepenuhnya linier ketika bit sekuensial diperhitungkan, namun implementasinya dalam perangkat lunak membuatnya menjadi non-linier. Dengan menjalankan aplikasi LFSR secara simultan (32 untuk komputer dengan ukuran word 32) sekuens nonlinear dapat diproduksi; lebih tepatnya, tampaknya nonlinier, digambarkan sebagai kompleksitas linier yang besar.

IV Diskusi:

Generator Kongruensial Linear yang kami sajikan di sini untuk memudahkan konsep pembuatan bilangan acak, dan untuk mempelajari berbagai metode pembangkitan. Namun, dalam domain kriptografi, LCG semuanya tidak relevan. LFSR, dan Register Geser Umpan Balik Non-Linear “sepupu” mereka lebih relevan dengan minat penulis. Selain metode yang dijelaskan di atas, metode menarik lainnya untuk menghasilkan bilangan acak juga perlu disebutkan secara singkat.

Cipher blok simetris juga mampu menghasilkan keacakan. Dimulai dengan cipher produk blok seperti LUCIFER dan DES, penggunaan cipher blok untuk menghasilkan bit acak, meskipun berkali-kali lebih lambat dari LCG dan bahkan LFSR, menghasilkan urutan bit yang sangat acak. Penerus yang lebih baru untuk DES, AES (algoritma Rijndael) dan bahkan pesaing runner up untuk AES, Serpent, juga telah digunakan untuk pembuatan bit acak.

Pada dasarnya, debat filosofis tentang konsep keacakan menunjukkan kesulitan yang nyata dalam membangun algoritme yang benar-benar acak. Fakta bahwa kebanyakan algoritma generasi acak didasarkan pada urutan acak, baik itu urutan nomor atau urutan bit, melemahkan istilah acak dari baris pertama kode dan komentar yang membenarkan kelayakannya. Namun, urutan acak sering digunakan, dan banyak menggunakan faktor ketidaktahuan. Selama metode baru penyemaian dan polinomial primitif baru ditemukan, yang persediaannya tidak terbatas, generator bilangan di atas akan tetap digunakan. Kemungkinan keberadaan algoritma bilangan acak benar-benar dipertanyakan, tetapi dengan banyak algoritma dan urutan yang masih belum terputus dan tidak dipetakan, keberadaan itu tidak dapat disangkal.