Алгоритм Блум - Блум - Шуба

Алгоритм Блум - Блум - Шуба (Шаблон:Lang-en) - генератор псевдовипадкових чисел, запропонований в 1986 році Ленором Блумом, Мануелем Блумом і Майклом Шубом.

BBS має такий вигляд:

$x_{n+1}=x_n^{2}modM,$

де $M=pq$ є добуток двох великих простих чисел $p$ і $q$. На кожному кроці алгоритму вихідні дані обчислюють з $x_n$ шляхом взяття або біта парності, або одного чи більше найменш значущих бітів $x_n$.

Два простих числа, $p$ і $q$, повинні бути конгруентні з 3 по $mod$ $4$ (це гарантує, що кожен квадратний залишок має один квадратний корінь, який також є квадратним залишком) і найбільший спільний дільник НСД $(p-1,q-1)$ має бути маленьким (це збільшує довжину циклу).

Цікавою особливістю цього алгоритму є те, що для отримання $x_n$ необов'язково обчислювати всі $n-1$ попередні числа, якщо відомо початковий стан генератора $x_0$ і числа $p$ і $q$. $n$ - е значення може бути обчислено безпосередньо використовуючи формулу:

$x_n=x_0^{2^{n}mod\lambda (M)}modM$,

де $\lambda$ - функція Кармайкла: в даному випадку $\lambda (M)=\lambda (pq)=lcm(p-1,q-1)$ - найменше спільне кратне чисел ($p-1$) і ($q-1$).

Надійність

Цей генератор підходить для криптографії, але не для моделювання, тому що він недостатньо швидкий. Однак, він має високу стійкість, яка забезпечується якістю генератора виходячи з обчислювальної складності завдання факторизації чисел. Коли прості числа обрані правильно, і $O(\log \log M)$ біт кожного $x_n$ є вихідними даними, тоді межа, при швидкозростаючому $M$, відрізнити вихідні біти від випадкових буде настільки ж складно, як і факторизація $M$.

Приклад

Нехай $p=11$, $q=19$ та $s=3$. Ми можемо розраховувати отримати велику довжину циклу для таких малих чисел, тому що $\mathrm{g}\mathrm{c}\mathrm{d}(\phi (p-1),\phi (q-1))=2$. Генератор починає рахувати $x_0$ за допомогою $x_{-1}=s$ і створює послідовність $x_0$, $x_1$, $x_2$, $\dots$ $x_5$ = 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Шаблон:Недоступне посилання, a GPL'ed GMP-based implementation of Blum Blum Shub in C by daffodil-11
• BlumBlumShubШаблон:Недоступне посилання, a GPL'ed implementation of Blum Blum Shub in Java by daffodil-11
• An implementation in Java Шаблон:Webarchive
• Randomness tests Шаблон:Webarchive

Література

• 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 PDF.
• Pascal Junod, «Cryptographic Secure Pseudo-Random Bits Generation: The Blum-Blum-Shub Generator», August 1999. 21 page PDF file Шаблон:Webarchive
• Martin Geisler, Mikkel Krøigård, and Andreas Danielsen. «About Random Bits», December 2004. Available as PDF and Gzipped Postscript.
• Randomness Recommendations for Security — RFC 1750 Шаблон:Webarchive.