🍙 🤛🏾 🦓 Generator Blum-Blum-Shub dan aplikasinya 👩🏿‍🤝‍👩🏻 👩🏿‍🎓 🚽

pengantar

Saat ini, bilangan acak digunakan di berbagai bidang ilmu pengetahuan. Misalnya, untuk mensimulasikan berbagai proses nyata, sering kali perlu mempertimbangkan tidak hanya perilaku kuantitas yang diselidiki, tetapi juga pengaruh berbagai fenomena yang tidak dapat diprediksi. Selain itu, beberapa metode untuk menganalisis data eksperimen juga menggunakan bilangan acak. Dalam teori permainan, peluang juga memainkan peran besar. Dan tentu saja dalam kriptografi. Banyak algoritma enkripsi atau tanda tangan elektronik menggunakan nomor acak.

Tetapi bagaimana Anda mendapatkan nomor acak? Di alam, ada banyak fenomena acak yang berbeda, yang menjadi dasar penemuan generator. Generator nomor acak perangkat keras dapat didasarkan pada proses acak makroskopik menggunakan item seperti koin, dadu, atau roda roulette. Tetapi generator seperti itu sangat lambat dan tidak cocok untuk memecahkan masalah. Untuk memperoleh bilangan acak lebih cepat, fenomena fisik yang bersifat kuantum, seperti derau pada rangkaian listrik, dapat digunakan. Tetapi kelemahan utama generator nomor acak perangkat keras adalah tidak dapat diandalkannya terkait dengan seringnya malfungsi. Untuk menghindari tidak dapat diandalkan, mereka mulai menggunakan tabel nomor acak yang telah diperoleh sebelumnya. Namun, mereka juga memiliki kelemahan besar - mereka memakan banyak memori.

Karena baik metode perangkat keras maupun tabel bilangan acak tidak memenuhi kebutuhan untuk memperoleh bilangan acak secara cepat dan andal, para ilmuwan mulai mencari metode algoritmik untuk memperoleh bilangan acak. Jelas bahwa urutan yang diperoleh sebagai hasil dari metode-metode tersebut tidak lagi acak, karena sepenuhnya ditentukan oleh rumus dan data awal tertentu. Tetapi jika nilai awal dirahasiakan, dan algoritme tahan (algoritme dianggap resisten, serangan yang berhasil yang mengharuskan penyerang memiliki sumber daya komputasi dalam jumlah yang tidak dapat dicapai), maka hasil yang dihasilkan generator tidak akan dapat diprediksi. Algoritme semacam itu untuk memperoleh urutan angka, yang propertinya mendekati urutan angka acak, disebut generator bilangan acak semu.

- BBS (Blum-Blum-Shub generator) - .

BBS :

- ,
– ,
– , ,
() - , n l(n), . ,

, « ». , , , , . , , .
x n n, y, $y ^ 2 \ equiv x \ mod \ n$ . x - n.
p , $p \ equiv 3 \ mod \ 4$ , .

2 :

, , , 1/2.
, , , r≤l(n)−1 s (r+1)- s 1/2.

BBS (Blum-Blum-Shub generator)

p q
$n: = p \ cdot q$
$s \ dalam Z_n ^ *$ ( n)
$x_0: = s ^ 2 \ mod \ n$
$x_i: = x_ {i-1} ^ 2 \ mod \ n$ $b_i: = x_i \ mod \ 2$
:

$n = p \ cdot q = 7 \ cdot 19 = 133$ s = 100 . $x_0 = 100 ^ 2 \ equiv 25 \ mod \ 133$ . : $x_1 = 25 ^ 2 \ equiv 93 \ mod \ 133$ $b_1 = 93 \ equiv 1 \ mod \ 2$ , $x_2 = 93 ^ 2 \ equiv 4 \ mod \ 133$ $b_2 = 4 \ equiv 0 \ mod \ 2$ , $x_3 = 4 ^ 2 = 16 \ mod \ 133$ $b_3 = 16 \ equiv 0 \ mod \ 2$ , $x_4 = 16 ^ 2 \ equiv 123 \ mod \ 133$ $b_4 = 123 \ equiv 1 \ mod \ 2$

1,0,0,1.

, BBS, , $\ lambda (\ lambda (x))$ , $\ lambda (n) = \ {\ min {m}: a ^ m \ equiv 1 \ mod n \}$ - .

BBS , n .

i- , x_0 , n, $\ lambda (n)$ .

BBS

, , .

BBS , :

, $x \ dalam Z_n ^ *$ .
- , , 1 , x 0 .

, BBS ( ) .

. BBS. , . BBS ,

, , , . : , RSA, ( ), , . , , . , . .

. — , . . , . , . , .

(Password-Based Key Derivation Function, PBKDF) — , - . , , -.

PBKDF . PRF. , , . , S - , , - MK_Length.

- MK , $MK = PBKDF _ {(PRF, C)} (P, S, MK \ _ Panjang)$

, , , , . - C. $2 ^ {Garam \ _ Panjang}$ , Salt_Length - .

Dummy _ Bits _ Number , BBS, -. , BBS, . - . a.

T U i : T_i , U_0 S i, Binary(). BBS T_i C. - . r .

, , , . , BBS , , .

Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (July 2012). "Recommendation for Key Management" (PDF). NIST Special Publication 800-57. NIST. Retrieved 19 August 2013.
Pascal Junod, «Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator», August 1999
..; ‘’ ’’, 2017
A. C. Yao. Theory and application of trapdoor functions. In Proc. 23rd IEEE Symp. on Foundations of Comp. Science, pages 80–91, Chicago, 1982. IEEE.
M. Blum and S. Micali. How to generate cryptographically strong se- quences of pseudo-random bits. SIAM J. Computing, 13(4):850–863, November 1984.
Lenore Blum, Manuel Blum, and Michael Shub. Comparison of two pseudo-random number generators. In R. L. Rivest, A. Sherman, and D. Chaum, editors, Proc. CRYPTO 82, pages 61–78, New York, 1983. Plenum Press.
A. J. (Alfred J.) Menezes, Paul C. Van Oorschot, and Scott A. Van- stone. Handbook of applied cryptography. The CRC Press series on discrete mathematics and its applications. CRC Press, 2000 N.W. Cor- porate Blvd., Boca Raton, FL 33431-9868, USA, 1997.
E. Kranakis. Primality and Cryptography. Wiley-Teubner Series in Computer Science, 1986.
S. Goldwasser dan S. Micali. Enkripsi probabilistik dan cara bermain poker mental menjaga rahasia semua informasi parsial. Dalam Proc. ACM Symp ke-14. tentang Theory of Computing, halaman 365-377, San Francisco, 1982. ACM.
Vybornova, Yu.D. Implementasi generator Blum-Blum-Shub dan mempelajari karakteristik utamanya / Yu.D. Vybornova // DI SITU.
Brassard, J. Kriptologi Modern / J. Brassard. - Moskow: Polimed, 1999. - 107 hal.
Yu.D. Vybornova, Pengembangan Fungsi Penghasil Kunci Berbasis Kata Sandi sebagai Aplikasi Generator Blum-Blum-Shub, Teknik Baru, 2017
Turan, M. Rekomendasi untuk derivasi kunci berbasis sandi / M. Turan, E. Barker, W. Burr, L. Chen - NIST, 2010. - 18 hal.

Generator Blum-Blum-Shub dan aplikasinya

pengantar

BBS (Blum-Blum-Shub generator)

BBS

More articles: