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

Алгоритм Блюма — Блюма — Шуба (англ. Blum Blum Shub, BBS) — это генератор псевдослучайных чисел, построенный на основе теоретико-числовых операций, в частности возведения в квадрат по модулю. Алгоритм был предложен в 1986 году американскими криптографами Ленор Блюм, Мануэлем Блюмом и Майклом Шубом. Относится к классу криптографически стойких генераторов, то есть его выходную последовательность невозможно отличить от истинно случайной при наличии вычислительных ограничений, если задача факторизации больших целых чисел является трудноразрешимой.

История и предпосылки

В середине 1980-х годов активно развивалась теория криптографических генераторов, основанных на сложных математических задачах. Одной из ключевых проблем было создание генератора, чья стойкость могла бы быть строго доказана. Алгоритм Блюма — Блюма — Шуба стал первым практическим генератором, для которого была доказана эквивалентность стойкости задаче факторизации целых чисел. Работа была опубликована в 1986 году в журнале «SIAM Journal on Computing» под названием «A Simple Unpredictable Pseudo-Random Number Generator».

Математическое описание

Параметры

Для работы алгоритма выбираются два больших простых числа \( p \) и \( q \), которые удовлетворяют условию:

\[ p \equiv q \equiv 3 \pmod{4} \]

Такие числа называются простыми числами Блюма. Затем вычисляется модуль:

\[ n = p \cdot q \]

Число \( n \) является произведением двух простых чисел Блюма и называется числом Блюма.

Инициализация

Выбирается начальное значение (зерно) \( s_0 \), которое является целым числом, взаимно простым с \( n \). На практике часто используют \( s_0 = x^2 \bmod n \), где \( x \) — случайное число, взаимно простое с \( n \).

Генерация последовательности

Последовательность псевдослучайных чисел \( x_i \) вычисляется по рекуррентной формуле:

\[ x_{i+1} = x_i^2 \bmod n \]

На каждом шаге из \( x_i \) извлекается один бит (обычно младший значащий бит) или несколько бит (например, бит чётности). В классическом варианте алгоритма выходной бит \( b_i \) определяется как:

\[ b_i = x_i \bmod 2 \]

Таким образом, выходная последовательность \( b_0, b_1, b_2, \dots \) представляет собой поток битов, который считается криптографически стойким.

Криптографическая стойкость

Основное преимущество алгоритма Блюма — Блюма — Шуба заключается в том, что его стойкость строго доказывается в предположении, что задача факторизации целых чисел является вычислительно сложной. Это означает, что если противник может предсказать следующий бит последовательности с вероятностью, существенно превышающей 1/2, то он может эффективно разложить \( n \) на множители. Поскольку факторизация больших чисел (например, 1024 или 2048 бит) считается практически невыполнимой для современных классических компьютеров, генератор считается безопасным.

Доказательство

Доказательство стойкости основано на сведении: любой алгоритм, способный отличить выходную последовательность BBS от истинно случайной, может быть преобразован в алгоритм факторизации \( n \). Это свойство называется «доказуемой стойкостью» (provable security). В отличие от многих других генераторов, где стойкость лишь предполагается, для BBS она математически обоснована.

Применение

Алгоритм Блюма — Блюма — Шуба используется в криптографических приложениях, где требуется высокая степень случайности и доказуемая безопасность:

• Генерация ключей: для создания симметричных ключей, сеансовых ключей и инициализационных векторов.
• Криптографические протоколы: в системах шифрования, электронной подписи и аутентификации.
• Потоковое шифрование: может использоваться как основа для поточного шифра, хотя на практике из-за низкой скорости чаще применяются более быстрые алгоритмы.
• Научные исследования: в качестве эталонного генератора для тестирования других генераторов и криптоаналитических методов.

Производительность и ограничения

Основным недостатком алгоритма является его низкая скорость по сравнению с другими генераторами, такими как RC4 или алгоритмы на основе регистров сдвига с линейной обратной связью (LFSR). Каждый выходной бит требует операции возведения в квадрат по модулю большого числа \( n \), что является вычислительно затратным. Для повышения скорости можно извлекать несколько бит из каждого \( x_i \) (например, младший байт), но это снижает доказуемую стойкость.

Рекомендации по выбору параметров

Для обеспечения безопасности рекомендуется использовать модуль \( n \) длиной не менее 1024 бит (в современных системах — 2048 или 4096 бит). Простые числа \( p \) и \( q \) должны быть примерно одинаковой длины и случайными. Зерно \( s_0 \) должно быть непредсказуемым и обновляться для каждого сеанса.

Пример работы

Пусть выбраны простые числа \( p = 7 \) и \( q = 11 \) (оба удовлетворяют условию \( p \equiv q \equiv 3 \pmod{4} \)). Тогда \( n = 77 \). Выберем зерно \( s_0 = 2 \). Последовательность:

• \( x_0 = 2 \)
• \( x_1 = 2^2 \bmod 77 = 4 \), бит: 0
• \( x_2 = 4^2 \bmod 77 = 16 \), бит: 0
• \( x_3 = 16^2 \bmod 77 = 256 \bmod 77 = 25 \), бит: 1
• \( x_4 = 25^2 \bmod 77 = 625 \bmod 77 = 9 \), бит: 1
• \( x_5 = 9^2 \bmod 77 = 81 \bmod 77 = 4 \), бит: 0

Выходная последовательность битов: 0, 0, 1, 1, 0, ... (начиная с \( x_1 \)). Для реального использования модуль должен быть намного больше.

Сравнение с другими генераторами

BBS уступает в скорости, но превосходит по доказуемой безопасности.

Интересные факты

• Алгоритм назван в честь Ленор Блюм (жены Мануэля Блюма), Мануэля Блюма и Майкла Шуба.
• В 1990-х годах BBS был включён в некоторые стандарты криптографических библиотек, но из-за низкой производительности редко использовался на практике.
• Для повышения скорости иногда применяют извлечение не одного бита, а нескольких (например, \( \log_2 \log_2 n \) бит), что не нарушает доказуемую стойкость при определённых условиях.
• Задача факторизации, на которой основана стойкость BBS, считается устойчивой к квантовым атакам только при использовании больших модулей (например, 4096 бит), так как квантовый алгоритм Шора позволяет эффективно факторизовать числа.

Источники

• Blum, L., Blum, M., & Shub, M. (1986). A Simple Unpredictable Pseudo-Random Number Generator. SIAM Journal on Computing, 15(2), 364–383.
• Menezes, A. J., van Oorschot, P. C., & Vanstone, S. A. (1996). Handbook of Applied Cryptography. CRC Press.
• Goldreich, O. (2001). Foundations of Cryptography: Volume 1, Basic Tools. Cambridge University Press.