Криптографический генератор псевдослучайных чисел

Криптографический генератор псевдослучайных чисел (КГПСЧ, англ. Cryptographically Secure Pseudorandom Number Generator, CSPRNG) — это алгоритм, предназначенный для генерации последовательности чисел, которая по своим свойствам неотличима от истинно случайной последовательности и пригодна для использования в криптографических системах. В отличие от обычных генераторов псевдослучайных чисел (ГПСЧ), КГПСЧ должен быть устойчив к атакам, направленным на предсказание или восстановление внутреннего состояния генератора, и соответствовать строгим требованиям теории информации и вычислительной сложности.

Основные свойства

КГПСЧ должен обладать следующими фундаментальными свойствами:

• Статистическая неотличимость от случайной. Последовательность на выходе должна проходить все статистические тесты на случайность (например, набор тестов NIST SP 800-22 или Diehard). Любой полиномиальный алгоритм, анализирующий выходную последовательность, не должен иметь возможности отличить её от истинно случайной с вероятностью, существенно превышающей 1/2.
• Непредсказуемость вперёд. Зная все предыдущие выходные значения, злоумышленник не должен иметь возможности вычислить следующее значение с вероятностью, большей, чем угадывание случайного числа. Это свойство гарантируется стойкостью односторонних функций, лежащих в основе генератора.
• Непредсказуемость назад (стойкость к компрометации состояния). Если злоумышленнику становится известно внутреннее состояние генератора в некоторый момент времени, он не должен иметь возможности восстановить предыдущие выходные значения. Это достигается использованием необратимых преобразований (например, хеш-функций) при обновлении состояния.
• Устойчивость к атакам по сторонним каналам. Реализация КГПСЧ должна минимизировать утечку информации через время выполнения, энергопотребление, электромагнитное излучение или другие побочные каналы.

Отличие от обычных ГПСЧ

Обычные генераторы псевдослучайных чисел, такие как линейный конгруэнтный генератор (LCG) или вихрь Мерсенна, предназначены для симуляций, статистических расчётов и игр. Они обладают хорошими статистическими свойствами, но не гарантируют криптографической стойкости. Например, по нескольким последовательным значениям LCG можно восстановить его параметры и предсказать все последующие числа. Вихрь Мерсенна, хотя и имеет огромный период, также может быть предсказан после наблюдения 624 выходных значений. КГПСЧ, напротив, проектируются так, чтобы даже при знании полной истории выходных значений восстановление состояния было вычислительно неосуществимо.

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

КГПСЧ можно разделить на несколько типов в зависимости от используемых криптографических примитивов:

На основе блочных шифров

Генератор использует блочный шифр (например, AES) в одном из режимов счётчика (CTR) или обратной связи (OFB, CFB). В режиме CTR генератор шифрует последовательно увеличивающееся значение счётчика, получая на выходе псевдослучайные блоки. Стойкость такого генератора напрямую зависит от стойкости блочного шифра. Пример: AES-CTR DRBG (Deterministic Random Bit Generator) — один из стандартизированных в NIST SP 800-90A.

На основе хеш-функций

Генератор использует криптографическую хеш-функцию (например, SHA-256). Внутреннее состояние обновляется путём хеширования предыдущего состояния с добавлением счётчика или энтропии. Выходные значения получаются хешированием текущего состояния. Пример: Hash_DRBG из NIST SP 800-90A.

На основе потоковых шифров

Потоковый шифр (например, ChaCha20, Salsa20) сам по себе является генератором псевдослучайной последовательности, которая затем смешивается с открытым текстом (XOR). В контексте КГПСЧ потоковый шифр используется напрямую для генерации случайных чисел. Пример: ChaCha20 DRBG — стандартизирован в NIST SP 800-90A.

На основе асимметричной криптографии

Редкий тип, основанный на сложности дискретного логарифмирования или факторизации. Например, Blum Blum Shub (BBS) — генератор, основанный на задаче квадратичных вычетов по модулю произведения двух больших простых чисел. Его стойкость доказуемо сводится к сложности факторизации, но он крайне медлителен и практически не используется.

Стандартизация

Наиболее известные стандарты КГПСЧ разработаны Национальным институтом стандартов и технологий США (NIST):

• NIST SP 800-90A (Rev. 1, 2015) — определяет три детерминированных генератора: Hash_DRBG, HMAC_DRBG и CTR_DRBG. Они используют хеш-функции (SHA-1, SHA-2, SHA-3), HMAC или блочные шифры (AES, Triple DES).
• NIST SP 800-90B — описывает требования к источникам энтропии, используемым для инициализации и перезарядки КГПСЧ.
• NIST SP 800-90C — определяет комбинированные генераторы, объединяющие детерминированный КГПСЧ с источником энтропии.

В России действует собственный стандарт — ГОСТ Р 34.10-2012 (в части генерации случайных чисел для электронной подписи) и ГОСТ Р 34.11-2012 (хеш-функция «Стрибог»), на основе которых могут строиться КГПСЧ. Также существует национальный стандарт ГОСТ Р 34.13-2015 (режимы работы блочных шифров), который может использоваться для построения генераторов.

Источники энтропии

Для обеспечения непредсказуемости КГПСЧ требует начального заполнения (seed) истинно случайными данными. Источниками энтропии могут служить:

• Физические шумы: тепловой шум резисторов, джиттер тактовых генераторов, дробовой шум диодов.
• Временны́е задержки: интервалы между нажатиями клавиш, движениями мыши, сетевыми пакетами.
• Аппаратные генераторы: специализированные чипы (например, Intel RDRAND, AMD Secure Processor), использующие квантовые эффекты.
• Системные энтропийные пулы: в Linux — /dev/random и /dev/urandom, в Windows — CryptGenRandom.

После инициализации КГПСЧ может работать детерминированно, но для повышения стойкости рекомендуется периодически «перезаряжать» его новой порцией энтропии (reseed).

Применение

КГПСЧ являются критическим компонентом практически всех современных криптографических систем:

• Генерация ключей: создание симметричных ключей (AES, ChaCha20), асимметричных пар (RSA, ECDSA, Ed25519).
• Протоколы аутентификации: генерация одноразовых паролей (OTP), nonce, соли для хеширования паролей.
• Шифрование: создание инициализирующих векторов (IV) для режимов CBC, GCM, CTR.
• Цифровые подписи: генерация эфемерных ключей (например, k в ECDSA).
• Блокчейн и криптовалюты: генерация адресов кошельков, создание случайных чисел для консенсусных механизмов (Proof-of-Stake).
• Азартные игры и лотереи: обеспечение непредсказуемости результатов.
• Научные симуляции: моделирование, требующее высокой степени случайности (например, в квантовой физике).

Критика и уязвимости

Несмотря на теоретическую стойкость, на практике КГПСЧ могут быть скомпрометированы:

• Недостаточная энтропия при инициализации. Если seed-значение предсказуемо (например, основано на времени системы с низким разрешением), злоумышленник может восстановить состояние. Классический пример — атака на генератор случайных чисел в Android (2013), когда из-за недостатка энтропии при загрузке системы можно было предсказать ключи Bitcoin-кошельков.
• Аппаратные закладки. Использование встроенных в процессор генераторов (например, Intel RDRAND) вызывает опасения из-за возможного наличия «чёрного хода». В 2013 году появились подозрения, что NSA могла внедрить уязвимость в алгоритм Dual_EC_DRBG (стандарт NIST SP 800-90A, основанный на эллиптических кривых), что привело к его отзыву из стандарта.
• Атаки по сторонним каналам. Время выполнения операций, энергопотребление или электромагнитное излучение могут раскрыть внутреннее состояние генератора. Например, атака на генератор OpenSSL (2011) использовала разницу во времени выполнения модульного возведения в степень.
• Ошибки реализации. Даже стойкий алгоритм может быть скомпрометирован из-за ошибок программирования: использование небезопасного источника энтропии, неправильное обновление состояния, утечка seed-значения через логи.

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

• /dev/urandom (Linux) — использует пул энтропии ядра и хеш-функцию SHA-1 (или ChaCha20 в новых версиях). Считается криптостойким.
• CryptGenRandom (Windows) — встроенный генератор Windows, использующий аппаратные источники и алгоритм AES-256.
• ChaCha20 DRBG — современный генератор, используемый в OpenBSD, Linux (с версии 4.8) и многих других системах.
• Fortuna — генератор, разработанный Брюсом Шнайером и Нильсом Фергюсоном, использует AES-256 и несколько энтропийных пулов.
• Yarrow — предшественник Fortuna, используется в macOS и iOS.