Sabtu, 12 September 2009

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:

Xn = (aXn – 1 + b) mod m

Xn = bilangan acak ke-n dari deretnya

Xn – 1 = bilangan acak sebelumnya

a = faktor pengali

b = increment

m = modulus

Kunci pembangkit adalah X0 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, x0)
  • 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.


Tidak ada komentar:

Posting Komentar