Псевдослучайная двоичная последовательность

Псевдослучайная двоичная последовательность (ПСП, также ПСДП) — это детерминированная последовательность битов (нулей и единиц), которая по своим статистическим свойствам (равномерность распределения, отсутствие корреляции, непредсказуемость) неотличима от истинно случайной последовательности. В отличие от случайных чисел, порождаемых физическими источниками энтропии (например, тепловым шумом), ПСП формируется с помощью строго заданного алгоритма и полностью воспроизводима при известном начальном состоянии (ключе, или seed). ПСП широко применяются в криптографии, системах связи, моделировании, тестировании и генерации шумоподобных сигналов.

Определение и основные свойства

Псевдослучайная двоичная последовательность — это последовательность битов, генерируемая детерминированным алгоритмом (генератором псевдослучайных чисел, ГПСЧ), которая должна удовлетворять ряду критериев, чтобы считаться качественной. Ключевые свойства:

• Равномерность распределения: доля единиц и нулей в последовательности стремится к 1/2.
• Отсутствие корреляции: между любыми двумя битами последовательности нет статистически значимой зависимости.
• Непредсказуемость: зная предыдущие биты, невозможно с вероятностью, существенно превышающей 1/2, угадать следующий бит (для криптостойких ПСП).
• Воспроизводимость: при одинаковом начальном состоянии генератор всегда выдаёт одну и ту же последовательность.
• Периодичность: из-за конечной памяти генератора любая ПСП рано или поздно входит в цикл. Длина цикла (период) — важнейшая характеристика; для практических применений период должен быть огромным (например, 2^19937 − 1 для вихря Мерсенна).

История

Первые работы по псевдослучайным последовательностям относятся к середине XX века. В 1946 году Джон фон Нейман предложил метод «средних квадратов» для генерации случайных чисел на компьютере ENIAC, однако он оказался неудовлетворительным. В 1949 году Деррик Лемер разработал линейный конгруэнтный генератор (ЛКГ), который стал одним из самых распространённых.

В 1960-х годах Роберт Маршалл и другие исследователи заложили основы теории псевдослучайных последовательностей, используемых в системах связи с расширением спектра. В 1970-е годы возникли криптографические генераторы, такие как генератор Блюма — Блюма — Шуба (BBS), основанный на сложности факторизации. В 1997 году Макото Мацумото и Такудзи Нисимура представили вихрь Мерсенна (Mersenne Twister, MT19937), который до сих пор остаётся стандартом в научных расчётах. В 2000-е годы, с развитием интернета и криптовалют, были разработаны аппаратные и программные генераторы, устойчивые к атакам.

Классификация генераторов ПСП

Генераторы псевдослучайных двоичных последовательностей делятся на несколько классов по принципу работы и области применения.

Линейные рекуррентные генераторы

Основаны на линейных рекуррентных соотношениях. Наиболее известные:

• Линейный конгруэнтный генератор (ЛКГ): X_{n+1} = (a * X_n + c) mod m. Прост, но имеет низкую криптостойкость.
• Регистр сдвига с линейной обратной связью (РСЛОС, LFSR): последовательность битов формируется как линейная функция от предыдущих состояний. Широко применяется в системах связи (например, в стандарте CDMA) и встроенных системах. Период LFSR максимален при использовании примитивных полиномов.
• Вихрь Мерсенна (Mersenne Twister): использует рекурсию в конечном поле GF(2) и имеет огромный период 2^19937 − 1. Является стандартом в языках программирования (Python, C++).

Криптографически стойкие генераторы

Спроектированы так, чтобы даже при известном алгоритме, но неизвестном ключе, злоумышленник не мог восстановить последовательность. Примеры:

• Генератор Блюма — Блюма — Шуба (BBS): основан на сложности задачи факторизации. Безопасен при правильном выборе параметров.
• Генераторы на основе блочных шифров (например, в режиме счётчика CTR): последовательность получается шифрованием счётчика.
• Генераторы на основе хеш-функций (например, HMAC_DRBG): используют криптографические хеши для получения битов.
• Генераторы на основе эллиптических кривых (EC_DRBG).

Аппаратные генераторы

Используют физические источники энтропии (шум диода, тепловой шум, радиоактивный распад) для получения истинно случайных чисел, которые затем могут быть смешаны с псевдослучайной последовательностью для повышения качества. В РФ такие генераторы применяются в сертифицированных средствах криптографической защиты информации (СКЗИ).

Применение

Криптография

ПСП являются основой для:

• Генерации ключей: сеансовые ключи, ключи шифрования, инициализационные векторы.
• Поточных шифров: шифрование XOR-сложением открытого текста с ПСП (например, RC4, ChaCha20).
• Протоколов аутентификации и цифровых подписей.

Системы связи

В телекоммуникациях ПСП используются для:

• Расширения спектра (CDMA, DSSS): сигнал модулируется псевдослучайной последовательностью, что позволяет нескольким пользователям работать в одной полосе частот.
• Синхронизации: специальные ПСП (например, последовательности Голда, Касами) применяются для поиска и синхронизации в системах GPS, ГЛОНАСС.
• Тестирования каналов: генерация тестовых сигналов с заданными свойствами.

Моделирование и численные методы

В научных расчётах ПСП необходимы для:

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

Тестирование и верификация

ПСП применяются в:

• Стресс-тестировании оборудования: подача псевдослучайных данных на вход.
• Тестировании программного обеспечения: генерация случайных входных данных для поиска ошибок (fuzzing).

Примеры популярных ПСП

Критика и ограничения

Основной недостаток любых ПСП — детерминированность. Если злоумышленник узнает начальное состояние (seed) или часть последовательности, он может восстановить всю последовательность. Для криптографических применений необходимы генераторы, устойчивые к атакам по известному открытому тексту и атакам по времени. Кроме того, многие популярные генераторы (например, rand() в C) имеют короткий период и статистические дефекты, что делает их непригодными для серьёзных задач. В РФ требования к генераторам ПСП для криптографии регламентируются ГОСТ Р 34.10-2012 и ГОСТ Р 34.11-2012, а также методическими документами ФСБ России.

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

• В 1999 году было обнаружено, что генератор случайных чисел в операционной системе Windows 95/98 имел период всего 2^24, что позволяло предсказывать результаты.
• Последовательности Голда, используемые в GPS, имеют взаимную корреляцию, близкую к нулю, что позволяет различать сигналы разных спутников.
• В 2018 году исследователи показали, что вихрь Мерсенна можно восстановить по 624 последовательным числам.

Источники

• Кнут Д. Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2007. — 832 с.
• Голдман С. Теория информации. — М.: Мир, 1970. — 480 с.
• Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC Press, 1996. — 816 p.
• Matsumoto M., Nishimura T. Mersenne Twister: A 623-dimensionally equidistributed uniform pseudo-random number generator // ACM Transactions on Modeling and Computer Simulation. — 1998. — Vol. 8, № 1. — P. 3–30.
• ГОСТ Р 34.10-2012. Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.
• ГОСТ Р 34.11-2012. Информационная технология. Криптографическая защита информации. Функция хэширования.