Алгоритм Блум - Блум - Шуба (англ. Algorithm Blum — Blum — Shub, BBS) - генератор псевдовипадкових чисел, запропонований в 1986 році , Мануелем Блумом і .
BBS має такий вигляд:
де є добуток двох великих простих чисел і . На кожному кроці алгоритму вихідні дані обчислюють з шляхом взяття або біта парності, або одного чи більше найменш значущих бітів .
Два простих числа, і , повинні бути конгруентні з 3 по (це гарантує, що кожен квадратний залишок має один квадратний корінь, який також є квадратним залишком) і найбільший спільний дільник НСД має бути маленьким (це збільшує довжину циклу).
Цікавою особливістю цього алгоритму є те, що для отримання необов'язково обчислювати всі попередні числа, якщо відомо початковий стан генератора і числа і . - е значення може бути обчислено безпосередньо використовуючи формулу:
- ,
де - функція Кармайкла: в даному випадку - найменше спільне кратне чисел () і ().
Надійність
Цей генератор підходить для криптографії, але не для моделювання, тому що він недостатньо швидкий. Однак, він має високу стійкість, яка забезпечується якістю генератора виходячи з обчислювальної складності завдання факторизації чисел. Коли прості числа обрані правильно, і біт кожного є вихідними даними, тоді межа, при швидкозростаючому , відрізнити вихідні біти від випадкових буде настільки ж складно, як і факторизація .
Приклад
Нехай , та . Ми можемо розраховувати отримати велику довжину циклу для таких малих чисел, тому що . Генератор починає рахувати за допомогою і створює послідовність , , , = 9, 81, 82, 36, 42, 92. У наступній таблиці показано вихідні дані (у бітах) для різних методів вибору бітів, що використовуються для визначення виходу.
Парний біт | Непарний біт | Найменш значущий біт |
---|---|---|
0 1 1 0 1 0 | 1 0 0 1 0 1 | 1 1 0 0 0 0 |
Посилання
- GMPBBS[недоступне посилання з серпня 2019], a GPL'ed -based implementation of Blum Blum Shub in C by daffodil-11
- BlumBlumShub[недоступне посилання з серпня 2019], a GPL'ed implementation of Blum Blum Shub in Java by daffodil-11
- An implementation in Java [ 15 січня 2016 у Wayback Machine.]
- Randomness tests [ 3 червня 2019 у Wayback Machine.]
Література
- Lenore Blum, Manuel Blum, and Michael Shub. «A Simple Unpredictable Pseudo-Random Number Generator», SIAM Journal on Computing, volume 15, pages 364—383, May 1986.
- Lenore Blum, Manuel Blum, and Michael Shub. «Comparison of two pseudo-random number generators», Advances in Cryptology: Proceedings of Crypto '82. Available as .
- Pascal Junod, «Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator», August 1999. 21 page PDF file [ 24 жовтня 2019 у Wayback Machine.]
- Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. «About Random Bits», December 2004. Available as and .
- Randomness Recommendations for Security — RFC 1750 [ 22 березня 2019 у Wayback Machine.].
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Blum Blum Shuba angl Algorithm Blum Blum Shub BBS generator psevdovipadkovih chisel zaproponovanij v 1986 roci Manuelem Blumom i BBS maye takij viglyad x n 1 x n 2 mod M displaystyle x n 1 x n 2 bmod M de M p q displaystyle M pq ye dobutok dvoh velikih prostih chisel p displaystyle p i q displaystyle q Na kozhnomu kroci algoritmu vihidni dani obchislyuyut z x n displaystyle x n shlyahom vzyattya abobita parnosti abo odnogo chi bilshe najmensh znachushih bitiv x n displaystyle x n Dva prostih chisla p displaystyle p i q displaystyle q povinni buti kongruentni z 3 po m o d displaystyle mod 4 displaystyle 4 ce garantuye sho kozhen kvadratnij zalishok maye odin kvadratnij korin yakij takozh ye kvadratnim zalishkom i najbilshij spilnij dilnik NSD p 1 q 1 displaystyle p 1 q 1 maye buti malenkim ce zbilshuye dovzhinu ciklu Cikavoyu osoblivistyu cogo algoritmu ye te sho dlya otrimannya x n displaystyle x n neobov yazkovo obchislyuvati vsi n 1 displaystyle n 1 poperedni chisla yaksho vidomo pochatkovij stan generatora x 0 displaystyle x 0 i chisla p displaystyle p i q displaystyle q n displaystyle n e znachennya mozhe buti obchisleno bezposeredno vikoristovuyuchi formulu x n x 0 2 n mod l M mod M displaystyle x n x 0 2 n bmod lambda M bmod M de l displaystyle lambda funkciya Karmajkla v danomu vipadku l M l p q l c m p 1 q 1 displaystyle lambda M lambda pq lcm p 1 q 1 najmenshe spilne kratne chisel p 1 displaystyle p 1 i q 1 displaystyle q 1 NadijnistCej generator pidhodit dlyakriptografiyi ale ne dlya modelyuvannya tomu sho vin nedostatno shvidkij Odnak vin maye visoku stijkist yaka zabezpechuyetsya yakistyu generatora vihodyachi z obchislyuvalnoyi skladnosti zavdannya faktorizaciyi chisel Koli prosti chisla obrani pravilno i O log log M displaystyle O log log M bit kozhnogo x n displaystyle x n ye vihidnimi danimi todi mezha pri shvidkozrostayuchomu M displaystyle M vidrizniti vihidni biti vid vipadkovih bude nastilki zh skladno yak i faktorizaciya M displaystyle M PrikladNehaj p 11 displaystyle p 11 q 19 displaystyle q 19 ta s 3 displaystyle s 3 Mi mozhemo rozrahovuvati otrimati veliku dovzhinu ciklu dlya takih malih chisel tomu sho g c d f p 1 f q 1 2 displaystyle rm gcd varphi p 1 varphi q 1 2 Generator pochinaye rahuvati x 0 displaystyle x 0 za dopomogoyu x 1 s displaystyle x 1 s i stvoryuye poslidovnist x 0 displaystyle x 0 x 1 displaystyle x 1 x 2 displaystyle x 2 displaystyle ldots x 5 displaystyle x 5 9 81 82 36 42 92 U nastupnij tablici pokazano vihidni dani u bitah dlya riznih metodiv viboru bitiv sho vikoristovuyutsya dlya viznachennya vihodu Parnij bit Neparnij bit Najmensh znachushij bit 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 0PosilannyaGMPBBS nedostupne posilannya z serpnya 2019 a GPL ed based implementation of Blum Blum Shub in C by daffodil 11 BlumBlumShub nedostupne posilannya z serpnya 2019 a GPL ed implementation of Blum Blum Shub in Java by daffodil 11 An implementation in Java 15 sichnya 2016 u Wayback Machine Randomness tests 3 chervnya 2019 u Wayback Machine LiteraturaLenore Blum Manuel Blum and Michael Shub A Simple Unpredictable Pseudo Random Number Generator SIAM Journal on Computing volume 15 pages 364 383 May 1986 Lenore Blum Manuel Blum and Michael Shub Comparison of two pseudo random number generators Advances in Cryptology Proceedings of Crypto 82 Available as Pascal Junod Cryptographic Secure Pseudo Random Bits Generation The Blum Blum Shub Generator August 1999 21 page PDF file 24 zhovtnya 2019 u Wayback Machine Martin Geisler Mikkel Kroigard and Andreas Danielsen About Random Bits December 2004 Available as and Randomness Recommendations for Security RFC 1750 22 bereznya 2019 u Wayback Machine