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

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

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

${\displaystyle x_{n+1}=x_{n}^{2}\;{\bmod {\;}}M,}$

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

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

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

${\displaystyle x_{n}=x_{0}^{2^{n}{\bmod {\lambda }}(M)}\;{\bmod {\;}}M}$,

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

Надійність

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

Приклад

Нехай ${\displaystyle p=11}$, ${\displaystyle q=19}$ та ${\displaystyle s=3}$. Ми можемо розраховувати отримати велику довжину циклу для таких малих чисел, тому що ${\displaystyle {\rm {gcd}}(\varphi (p-1),\varphi (q-1))=2}$. Генератор починає рахувати ${\displaystyle x_{0}}$ за допомогою ${\displaystyle x_{-1}=s}$ і створює послідовність ${\displaystyle x_{0}}$, ${\displaystyle x_{1}}$, ${\displaystyle x_{2}}$, ${\displaystyle \ldots }$ ${\displaystyle 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^[недоступне посилання з серпня 2019], a GPL'ed GMP-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 PDF.
• 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 PDF and Gzipped Postscript.
• Randomness Recommendations for Security — RFC 1750 [Архівовано 22 березня 2019 у Wayback Machine.].