Blum Blum Shut (BBS)

• CSPRNG yang paling sederhana dan paling mangkus (secara kompleksitas teoritis).
• BBS dibuat pada tahun 1986 oleh Lenore Blum, Manuel Blum, dan Michael Shub.
• Berbasis teori bilangan

Algoritma:

• Pilih dua buah bilangan prima rahasia, p dan q, yang masing-masing kongruen dengan 3 modulo 4.
• Kalikan keduanya menjadi n = pq. Bilangan m ini disebut bilangan bulat Blum
• Pilih bilangan bulat acak lain, s, sebagai umpan sedemikian sehingga:

(i) 2 £ s < n

(ii) s dan n relatif prima

kemudian hitung x⁰ = s² mod n

• Barisan bit acak dihasilkan dengan melakukan iterasi berikut sepanjang yang diinginkan:
• (i) Hitung xⁱ = x^{i – 1 2} mod n
• (ii) zⁱ = bit LSB (Least Significant Bit) dari xⁱ

Barisan bit acak adalah z¹, z², z³, …

• Bilangan acak tidak harus 1 bit LSB tetapi bisa juga j buah bit (j adalah bilangan bulat positif yang tidak melebihi log²(log² n)) ).

• Perhatikan contoh berikut:

• Keamanan BBS terletak pada sulitnya memfaktorkan n. Nilai n tidak perlu rahasia dan dapat diumumkan kepada publik.

• BBS tidak dapat diprediksi dari arah kiri (unpredictable to the left) dan tidak dapat diprediksi dari arah kanan (unpredictable to the kanan),

• artinya jika diberikan barisan bit yang dihasilkan oleh BBS, kriptanalis tidak dapat memprediksi barisan bit sebelumnya dan barsian nit sesudahnya

CSPRNG Berbasis RSA

• Pilih dua buah bilangan prima rahasia, p dan q, dan bilangan bulat e yang relatif prima dengan (p – 1)(q – 1)
• Kalikan keduanya menjadi n = pq
• Pilih bilangan bulat acak lain, s, sebagai x⁰ yang dalam hal ini 2 £ s £ n
• Barisan bit acak dihasilkan dengan melakukan iterasi berikut sepanjang yang diinginkan:

a. Hitung xⁱ = x^{i – 1 e} mod n degan x⁰ = s.

b. zⁱ = bit LSB (Least Significant Bit) dari xⁱ

5. Barisan bit acak adalah z¹, z², z³, …