Pembangkitan Bilangan Acak PSEUDO-RANDOM GENERATION

Pembangkit Bilangan Acak Semu

• Bilangan acak: bilangan yang tidak dapat diprediksi
• Bilangan acak (random) banyak digunakan di dalam kriptografi
• Misalnya untuk pembangkitan parameter kunci pada algoritma kunci-publik, pembangkitan initialization vector (IV) pada algoritma kunci-simetri, dan sebagainya.
• Tidak ada komputasi yang benar-benar menghasilkan deret bilangan acak secara sempurna.
• Bilangan acak yang dihasilkan dengan rumus-rumus matematika adalah bilangan acak semu (pseudo), karena pembangkitan bilangannya dapat diulang kembali.
• Pembangkit deret bilangan acak semacam itu disebut pseudo-random number generator (PRNG)

Linear Congruential Generator (LCG)

• Pembangkit bilangan acak kongruen-lanjar (linear congruential generator atau LCG ) adalah PRNG yang berbentuk:

Xⁿ = (aX^{n – 1} + b) mod m

Xⁿ = bilangan acak ke-n dari deretnya

X^{n – 1} = bilangan acak sebelumnya

a = faktor pengali

b = increment

m = modulus

Kunci pembangkit adalah X⁰ yang disebut umpan (seed).

• LCG mempunyai periode tidak lebih besar dari m, dan pada kebanyakan kasus periodenya kurang dari itu.

• LCG mempunyai periode penuh (m – 1) jika memenuhi syarat berikut:
• b relatif prima terhadap m.
• a – 1 dapat dibagi dengan semua faktor prima dari m
• a – 1 adalah kelipatan 4 jika m adalah kelipatan 4
• m > maks(a, b, x⁰)
• a > 0, b > 0

• Keunggulan LCG terletak pada kecepatannya dan hanya membutuhkan sedikit operasi bit.

• Sayangnya, LCG tidak dapat digunakan untuk kriptografi karena bilangan acaknya dapat diprediksi urutan kemunculannya.

• Oleh karena itu LCG tidak aman digunakan untuk kriptografi. Namun demikian, LCG tetap berguna untuk aplikasi non-kriptografi seperti simulasi, sebab LCG mangkus dan memperlihatkan sifat statistik yang bagus dan sangat tepat untuk uji-uji empirik

Pembangkit Bilangan Acak yang Aman untuk Kriptografi

• Pembangkit bilangan acak yang cocok untuk kriptografi dinamakan cryptographically secure pseudorandom generator (CSPRNG).

• Persyaratan CSPRNG adalah:
• Secara statistik ia mempunyai sifat-sifat yang bagus (yaitu lolos uji keacakan statistik).
• Tahan terhadap serangan (attack) yang serius. Serangan ini bertujuan untuk memprediksi bilangan acak yang dihasilkan.