Blum Blum Shub

Теория

Blum Blum Shub — единственный ГПСЧ с доказуемой стойкостью. Рекурренция проста: \(x_{n+1} = x_n^2 \bmod M\), где \(M = p \cdot q\) — произведение двух больших простых, дающих остаток 3 при делении на 4 (простые Блюма), а зерно взаимно просто с \(M\). Выход — младший бит \(x_n\) (или несколько младших бит).

Доказано: угадать следующий бит не проще, чем разложить \(M\) на множители, — задача квадратичных вычетов. Это делает BBS эталоном «доказуемо безопасного», но платой становится скорость: каждый бит требует модульного возведения в квадрат, поэтому на практике BBS почти не используют, предпочитая быстрые CSPRNG вроде ChaCha20.

Важно: стойкость опирается на размер модуля: на практике \(M\) должен быть не меньше 1024 бит. Учебные пресеты калькулятора малы и только демонстрируют механику.

Пример с решением

1. Условие. \(p = 11\), \(q = 19\) (\(M = 209\)), зерно 4: первые два состояния и их биты.
2. Формула. \(x_{n+1} = x_n^2 \bmod M\).
3. Подстановка. \(x_1 = 4^2 \bmod 209\).
4. Вычисление. \(x_1 = 16\) (бит 0), \(x_2 = 16^2 \bmod 209 = 47\) (бит 1).
5. Ответ. Последовательность 16, 47, 119, … зацикливается за 12 шагов — учебный модуль слишком мал для реальной стойкости.

Главное

• Доказуемая стойкость — предсказание бита эквивалентно факторизации.
• Медленный — каждый бит стоит модульного квадрата.
• Простые Блюма: \(p \equiv q \equiv 3 \pmod 4\).