Введение
Блум Блум Шуб (B. B. S.) — генератор псевдослучайных чисел, предложенный в 1986 году Ленор Блюм, Мануэлем Блюмом и Майклом Шубом, основанный на односторонней функции Майкла О. Рабина. TOC Blum Blum Shub имеет вид , где M = pq является произведением двух больших простых чисел p и q. На каждом шаге алгоритма из xn+1 извлекается некоторое выходное значение; обычно это либо битовая чётность xn+1, либо один или несколько младших значащих битов xn+1. Начальное значение x0 должно быть целым числом, взаимно простым с M (то есть p и q не являются делителями x0) и отличным от 1 или 0. Два простых числа p и q должны быть сравнимы с 3 по модулю 4 (это гарантирует, что каждый квадратный остаток имеет один квадратный корень, который также является квадратным остатком), и должны быть безопасными простыми числами с небольшим НОД((p-3)/2, (q-3)/2) (это обеспечивает большую длину цикла). Интересной особенностью генератора Blum Blum Shub является возможность прямого вычисления любого значения xi (с помощью теоремы Эйлера): , где — функция Кармихаэля. (В данном случае ).
Blum Blum Shub takes the form
,
where M = pq is the product of two large primes p and q. At each step of the algorithm, some output is derived from xn+1; the output is commonly either the bit parity of xn+1 or one or more of the least significant bits of xn+1. The seed x0 should be an integer that is co prime to M (i. e. p and q are not factors of x0) and not 1 or 0. The two primes, p and q, should both be congruent to 3 (mod 4) (this guarantees that each quadratic residue has one square root which is also a quadratic residue), and should be safe primes with a small gcd((p 3)/2, (q 3)/2) (this makes the cycle length large). An interesting characteristic of the Blum Blum Shub generator is the possibility to calculate any xi value directly (via Euler's theorem):
,
where is the Carmichael function. (Here we have ).
Безопасность
Есть доказательство, сводящее его безопасность к вычислительной сложности факторизации. Если простые числа выбраны должным образом и выводится O(log log M) младших битов каждого xn, то при стремлении M к бесконечности, отличить выходные биты от случайных должно быть не менее сложно, чем решить задачу об остатках квадратов по модулю M.
Производительность генератора случайных чисел BBS зависит от размера модуля M и количества бит на итерацию j. Уменьшение M или увеличение j ускоряет алгоритм, но также снижает его безопасность. В статье 2005 года приведено конкретное, а не асимптотическое, доказательство безопасности BBS для заданных M и j. Этот результат также можно использовать для выбора двух чисел, балансируя между ожидаемой безопасностью и вычислительными затратами.