Pseudo-random Number Generator

Bilangan acak (random) adalah bilangan yang tidak dapat diprediksi dan terdistribusi secara uniform pada rentang tertentu. Secara umum pembangkitan bilangan acak terdiri dari dua metode, yaitu:
1. Metode fisik: dadu, roulette wheel, lotre, dll
2. Metode numerik/aritmetik.

Pembangkit bilangan acak secara matematis menggunakan fungsi matematis yang sekuensial, tiap bilangan baru merupakan fungsi deterministik dari bilangan-bilangan sebelumnya (rekuren). Basis dari fungsi rekursif tersebut disebut umpan (seed), yaitu satu atau lebih bilangan awal. Tidak ada fungsi matematis yang dapat menghasilkan deret bilangan acak yang sempurna/natural. Oleh karena itu pembangkit semacam itu disebut pseudo-random number generator (PRNG).


Linear Congruential Generator (LCG)

Merupakan PRNG yang paling sederhana dan lebih mudah & cepat dikomputasi. Fungsinya adalah sebagai berikut: X_n = (aX_{n – 1} + b) mod m
dimana:
X_n = bilangan acak ke-n dari deretnya
a, b = koefisien parameter
m = modulus
Basis dari fungsi ini adalah X₀ yang disebut seed. Berikut contohnya.

Spoiler:

LCG memiliki kelemahan, yaitu mempunyai periode tertentu yang selalu lebih kecil dari m. Pada contoh di atas, deret bilangan berulang dengan periode 16. Dengan menemukan perulangan, deret bilangan menjadi lebih mudah ditebak. Kita mungkin dapat memperkuatnya dengan menggunakan nilai m yang lebih besar dan nilai a & b tertentu yang mengakibatkan periode penuh (m-1).

Dengan demikian, LCG tidak aman untuk menghindari pembobolan, terutama untuk keperluan kriptografi. Secara praktis, LCG berguna untuk aplikasi non-kriptografi seperti game dan simulasi, karena LCG efisien dan memperlihatkan sifat statistik yang bagus dan sangat tepat untuk uji-uji empirik.


Cryptographically Secure Pseudorandom Generator (CSPRNG)

Pembangkit bilangan acak yang digunakan dalam kriptografi memiliki syarat yang penting, yaitu lolos uji keacakan statistik dan tahan terhadap serangan yang bertujuan untuk memprediksi bilangan acak yang dihasilkan. Pembangkit semacam ini disebut cryptographically secure pseudorandom generator (CSPRNG).


Blum Blum Shub (BBS)

BBS merupakan CSPRNG yang paling sederhana dan efisien dalam komputasi. BBS dibuat pada tahun 1986 oleh Lenore Blum, Manuel Blum, dan Michael Shub. Berikut algoritmanya.
1. Pilih dua buah bilangan prima rahasia, p dan q, yang masing-masing kongruen dengan 3 modulo 4.
2. Kalikan keduanya menjadi n = pq. Bilangan m ini disebut bilangan bulat Blum
3. Pilih bilangan bulat acak lain, s, sebagai umpan sedemikian sehingga:
(i) 2 <= s < n
(ii) s dan n relatif prima
kemudian hitung x0 = s2 mod n
4. Barisan bit acak dihasilkan dengan melakukan iterasi berikut sepanjang yang diinginkan:
(i) Hitung xi = xi – 1 2 mod n
(ii) zi = bit LSB (Least Significant Bit) dari xi
Barisan bit acak adalah z1, z2, z3, …

Keamanan BBS terletak pada sulitnya memfaktorkan n. Nilai n tidak perlu rahasia dan dapat visible secara publik.

BBS tidak dapat diprediksi dari arah kiri dan tidak dapat diprediksi dari arah kanan pula, artinya jika diberikan barisan bit yang dihasilkan oleh BBS, kriptanalis tidak dapat memprediksi barisan bit sebelumnya dan barisan bit sesudahnya.


Fungsi Chaos

Fungsi chaos adalah fungsi yang bersifat sangat peka terhadap nilai awal. Sensitifitas fungsi tersebut memperlihatkan keacakan bilangan yang dihasilkannya. Berikut contoh fungsi chaos.

a. Persamaan Logistik
x_i+1 = r x_i (1 – x_i)
dimana:
r = laju pertumbuhan ( 0 <= r <= 4 )
x = nilai-nilai chaos (0 <= x <= 1)

b. Henon map
x_n = 1 + b(x_n–2 – x_n–3) + cx²_n–2

wah wah dahsyat

ini sih lebih keren dari trit gw

hmmmm ternyata ada fungsi chaos? tapi itu tetep tergolong pseudo kan?

nambah pengetahuan nih...

wah, gk ngerti

ini utk memperoleh nilai scara random kan? kyk fungsi random() pada GM.
dan kok kliatan ny ribet bnget?

atau mksd dri trit di atas itu kyk enkripsi nilai gitu, jdi contoh ny kyk gini:
ak mau meng-enkripsi nilai pada var uang (uang=1000), trus ak pke salah satu metode di atas, yaitu yg BBS. trus ak menentukan 2 nilai rahasia, yaitu p&q = 1 & 9

trus stelah di proses, jdi ny kyk gini "uang = 1000+NILAI_BBS"

dan misalkan kalo ak mau enkrip exp, maka ak akan merubah nilai p&q lgi, shingga ak mndapat nilai yg berbeda lgi dri nilai BBS tdi. bgitu kah konsep / fungsi dari tulisan" diatas?

@zebrakelabu
semua fungsi pembangkit bilangan acak bersifat deterministik (karena jelas ditentukan seed / nilai awalnya), maka termasuk pseudo-random juga~

@Kevin Blaze Coolerz
hmm, kira2 prosesnya seperti gini:
- pertama nilai seed ditentukan terlebih dahulu, bisa dilakukan secara otomatis dengan randomize() dimana nilai seed ditentukan dari clock CPU, atau secara manual dengan random_set_seed(seed)
- lalu nilai random berikutnya dihitung dengan fungsi random()
- jika kita langsung menggunakan fungsi random(), fungsi tsb sebetulnya memanggil fungsi randomize() terlebih dahulu

jadi, untuk keperluan kriptografi, pake fungsi random_set_seed(seed) terlebih dahulu

Note: nilai seed berada pada rentang 32-bit integer (-2147483648 ~ 2147483647)

@asuna:
ooh, I see thx atas penjelasan ny

gk di buat gmk ny nih?

^
tinggal coba contoh sederhana ini aja:

Code:

random_set_seed(12345678)
show_message(random(10))
show_message(random(10))
show_message(random(10))
show_message(random(10))
show_message(random(10))

^
hmm, stelah di coba, trnyata hasil nya random membingungkan, fungsi set_seed seakan" gk brguna

ak kira kalo seed = X, maka nilai random akan mendekati X

*setelah baca ulang koment kamu

semua fungsi pembangkit bilangan acak bersifat deterministik (karena jelas ditentukan seed / nilai awalnya)

seed = nilai awal, jdi GM itu sdh menentukan default utk seed ny ya?
knp kmu set seed ny jdi 12345678, dan padahal yg di pke di script cma random(10) ?

btw ak jdi bingung lgi

^
seems you don't understand what seed really means
coba run ulang, untuk nilai seed yang sama, deret bilangan randomnya mestinya sama juga

contohnya kev, mungkin kamu pernah main minecraft ato semacamnya (android ada yang pocket edition dan free)

waktu generate world, kita dikasi pilihan isian World Generator seed. Kalo kita biarkan kosong maka minecraft akan membuatkan dunia yang benar2 random. Kalo kita isikan sesuatu (misalnya nama kamu) maka isian ini akan diconvert menjadi seed bagi pembuatan dunia game. Dengan isian yang sama di hp lain maka dunianya bisa tetap sama bentuknya, walau digenerate secara random.

Asuna wrote:^
seems you don't understand what seed really means
coba run ulang, untuk nilai seed yang sama, deret bilangan randomnya mestinya sama juga

tdi emg blum ngerti, tpi pas baca komen om adit skrg jdi ngerti terima kasih tong feng

zebrakelabu wrote:contohnya kev, mungkin kamu pernah main minecraft ato semacamnya (android ada yang pocket edition dan free)

waktu generate world, kita dikasi pilihan isian World Generator seed. Kalo kita biarkan kosong maka minecraft akan membuatkan dunia yang benar2 random. Kalo kita isikan sesuatu (misalnya nama kamu) maka isian ini akan diconvert menjadi seed bagi pembuatan dunia game. Dengan isian yang sama di hp lain maka dunianya bisa tetap sama bentuknya, walau digenerate secara random.

blum prnh main
tpi ak ngerti kok mksd ny thx om atas penjelasan ny

Ou gitu toh.. makasih baru tahu.. ditunggu selanjutnya