Псевдослучайный генератор

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

История

Потребность в генерации случайных чисел возникла задолго до появления электронных вычислительных машин. В древности использовались механические методы — бросание костей, вращение колеса, подбрасывание монеты. С развитием статистики и теории вероятностей в XIX веке (работы Пьера-Симона Лапласа, Карла Пирсона) возникла необходимость в больших выборках случайных чисел для проверки гипотез. Однако ручная генерация была трудоёмкой и ненадёжной.

Первые алгоритмические ПСГ появились в середине XX века вместе с первыми компьютерами. В 1946 году Джон фон Нейман предложил метод «средних квадратов»: взять число, возвести его в квадрат, извлечь средние цифры результата и использовать их как следующее число. Метод оказался неудовлетворительным из-за коротких периодов и вырождения в ноль. В 1951 году Деррик Лемер разработал линейный конгруэнтный генератор (LCG), который стал основой для многих последующих алгоритмов. В 1960-х годах появились более сложные конструкции, такие как регистры сдвига с линейной обратной связью (LFSR), используемые в аппаратуре.

Современный этап развития ПСГ связан с криптографией. В 1970-х годах были разработаны первые криптостойкие генераторы, например, на основе блочных шифров (DES в режиме счётчика). В 1990-х годах появились алгоритмы, устойчивые к статистическим атакам: Mersenne Twister (1997, Макото Мацумото и Такудзи Нисимура), который долгое время оставался стандартом для не криптографических приложений. В XXI веке акцент сместился в сторону устойчивости к атакам по побочным каналам и квантовым вычислениям. В 2015 году NIST (Национальный институт стандартов и технологий США) опубликовал стандарт SP 800-90A Rev.1, описывающий детерминированные генераторы случайных битов (DRBG) на основе блочных шифров (CTR_DRBG), хеш-функций (Hash_DRBG) и эллиптических кривых (HMAC_DRBG).

Принцип работы

Большинство ПСГ основаны на рекуррентной формуле: \( x_{n+1} = f(x_n) \), где \( x_n \) — текущее состояние, \( f \) — детерминированная функция, а \( x_{n+1} \) — следующее состояние. Начальное состояние \( x_0 \) (зерно) задаётся пользователем или извлекается из источника энтропии. Выходная последовательность обычно получается путём преобразования состояния (например, взятия младших битов или применения хеш-функции).

Ключевые характеристики ПСГ:

• Период — длина последовательности до её повторения. Для хороших ПСГ период должен быть максимально большим (например, \( 2^{19937} - 1 \) для Mersenne Twister).
• Равномерность распределения — статистическая неотличимость от истинно случайной последовательности. Проверяется тестами (например, набор тестов Diehard, NIST SP 800-22).
• Скорость генерации — количество бит в секунду, которое может выдать алгоритм.
• Криптостойкость — невозможность предсказать последующие биты, зная предыдущие (для криптографических ПСГ).

Классификация

По назначению

1. Не криптографические ПСГ (общего назначения). Используются в симуляциях, моделировании, компьютерных играх, научных расчётах. Не требуют стойкости к атакам, но должны быть быстрыми и иметь большой период. Примеры: Mersenne Twister, PCG (Permuted Congruential Generator), XorShift.
2. Криптографически стойкие ПСГ (CSPRNG). Обязаны быть непредсказуемыми: даже зная полную историю выходных битов, злоумышленник не должен иметь возможности вычислить следующий бит с вероятностью, отличной от 1/2. Примеры: CTR_DRBG, Hash_DRBG, ChaCha20 (в режиме генератора), алгоритм Блюма — Блюма — Шуба (BBS).
3. Специализированные ПСГ для аппаратной реализации. Например, регистры сдвига с линейной обратной связью (LFSR), которые легко реализуются на вентилях и используются в телекоммуникациях (коды, шифры).

По типу алгоритма

• Линейные конгруэнтные генераторы (LCG): \( x_{n+1} = (a \cdot x_n + c) \mod m \). Просты, но имеют короткий период и корреляции между последовательными числами.
• Регистры сдвига (LFSR, NLFSR): используют битовые сдвиги и XOR. Быстры, но не криптостойки без дополнительных преобразований.
• Генераторы на основе клеточных автоматов (например, Rule 30).
• Генераторы на основе хеш-функций и блочных шифров: используют криптографические примитивы для обеспечения непредсказуемости.
• Генераторы на основе эллиптических кривых (например, Dual_EC_DRBG, который был скомпрометирован из-за возможности закладки).

Криптографически стойкие ПСГ

Криптографические ПСГ (CSPRNG) являются критически важным компонентом современных систем безопасности. Они используются для генерации ключей шифрования, сессионных токенов, одноразовых паролей (OTP), значений nonce в протоколах, а также в криптовалютах (например, для генерации приватных ключей).

Основные требования к CSPRNG:

• Непредсказуемость вперёд (forward secrecy): даже если злоумышленник узнаёт текущее состояние генератора, он не может восстановить предыдущие выходные биты.
• Непредсказуемость назад (backward secrecy): если злоумышленник узнаёт текущее состояние, он не может вычислить будущие выходные биты (если генератор использует энтропию из внешних источников).
• Устойчивость к атакам по побочным каналам (время, энергопотребление, излучение).

Стандарт NIST SP 800-90A описывает три основных механизма:

• CTR_DRBG — на основе блочного шифра AES в режиме счётчика. Шифрует последовательность счётчиков, увеличивающихся на каждом шаге.
• Hash_DRBG — на основе криптографической хеш-функции (SHA-256, SHA-512). Состояние обновляется через хеширование предыдущего состояния и счётчика.
• HMAC_DRBG — на основе HMAC (Hash-based Message Authentication Code). Использует HMAC для генерации и обновления состояния.

В операционных системах обычно используются гибридные подходы: аппаратный генератор (например, RDRAND на процессорах Intel) смешивается с программным CSPRNG (например, /dev/urandom в Linux, CryptGenRandom в Windows). В России для криптографических нужд рекомендуется использовать ГОСТ Р 34.10-2012 и ГОСТ Р 34.11-2012, на основе которых строятся ПСГ, соответствующие требованиям ФСБ России.

Применение

Научное моделирование

В методе Монте-Карло, молекулярной динамике, физике элементарных частиц, климатологии и других областях, где требуется моделирование случайных процессов, используются ПСГ с большим периодом и хорошими статистическими свойствами. Например, Mersenne Twister является стандартом для многих вычислительных пакетов (MATLAB, Python NumPy, R).

Компьютерные игры и графика

ПСГ применяются для генерации процедурного контента (ландшафты, уровни, текстуры), анимации частиц, искусственного интеллекта (случайное поведение NPC), а также для создания шумов (Perlin noise, Simplex noise).

Криптография и информационная безопасность

Генерация ключей, сессионных токенов, случайных чисел для протоколов аутентификации, защита от атак повторного воспроизведения (replay attack). В блокчейне и криптовалютах ПСГ используются для генерации приватных ключей, адресов кошельков, а также в алгоритмах консенсуса (например, Proof-of-Stake).

Тестирование программного обеспечения

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

Телекоммуникации

В системах связи (CDMA, Bluetooth, Wi-Fi) ПСГ применяются для скремблирования данных, формирования псевдослучайных последовательностей для расширения спектра, а также в алгоритмах коррекции ошибок.

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

Основной недостаток ПСГ — их детерминированность. Если злоумышленник узнаёт начальное состояние (зерно) или может наблюдать достаточно длинную последовательность, он может восстановить всё состояние генератора. Это привело к ряду известных атак:

• В 1995 году была взломана реализация ПСГ в библиотеке Netscape SSL (использовался слабый источник энтропии на основе времени).
• В 2008 году было показано, что встроенный ПСГ в PlayStation 3 (на основе алгоритма Mersenne Twister) позволял предсказывать приватные ключи ECDSA, что привело к возможности подделывать цифровые подписи.
• В 2013 году вскрылась закладка в генераторе Dual_EC_DRBG, предложенном NIST, который мог быть использован АНБ для компрометации криптографических систем.

Другая проблема — недостаточная энтропия начального состояния. Если зерно задаётся предсказуемым образом (например, на основе времени с точностью до миллисекунд), злоумышленник может перебрать возможные варианты. Поэтому в современных системах ПСГ обязательно смешиваются с аппаратными источниками энтропии (например, через системный вызов getrandom() в Linux).

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

• Самый длинный период среди известных ПСГ имеет Mersenne Twister: \( 2^{19937} - 1 \), что составляет примерно \( 4.3 \times 10^{6001} \) чисел.
• Алгоритм Блюма — Блюма — Шуба (BBS) является одним из немногих ПСГ, чья криптостойкость строго доказывается на основе сложности факторизации больших чисел.
• В 2018 году в процессорах Intel была обнаружена уязвимость CVE-2018-5407, позволяющая предсказывать значения, генерируемые инструкцией RDRAND, из-за недостаточной энтропии в некоторых режимах работы.
• В России для государственных информационных систем использование ПСГ регламентируется ГОСТ Р ИСО/МЭК 18031-2012, а также методическими документами ФСБ России.

Источники

• Кнут, Дональд Э. Искусство программирования. Том 2. Получисленные алгоритмы. — 3-е изд. — М.: Вильямс, 2000. — 832 с. — ISBN 5-8459-0081-6.
• Menezes, A., van Oorschot, P., Vanstone, S. Handbook of Applied Cryptography. — CRC Press, 1996. — 780 p. — ISBN 0-8493-8523-7.
• NIST Special Publication 800-90A Rev.1: Recommendation for Random Number Generation Using Deterministic Random Bit Generators. — National Institute of Standards and Technology, 2015.
• 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.
• ГОСТ Р ИСО/МЭК 18031-2012. Информационная технология. Методы защиты. Генерация случайных битов. — М.: Стандартинформ, 2013.