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

Криптографическая безопасность в основе своей зависит от непредсказуемости. Если злоумышленник может предсказать ваш ключ, IV или одноразовое число — даже частично, — вся криптографическая система может разрушиться. Слабая случайность уже приводила к катастрофическим взломам в реальном мире.

TRNG собирают физическую энтропию: тепловой шум в резисторах, дробовой шум в диодах со смещением в обратном направлении, радиоактивный распад, движения мыши, интервалы между нажатиями клавиш и задержки перемещения головки диска. Это действительно непредсказуемые физические явления.

OS поддерживает пул энтропии — набор образцов физического шума, объединённых с помощью XOR и хеширования. Linux: /dev/random и /dev/urandom получают данные из этого пула. По мере работы системы пул непрерывно пополняется.

PRNG (также называемый детерминированным RNG или DRNG) расширяет короткое начальное значение в длинный поток псевдослучайных байтов с помощью детерминированного алгоритма. При одном и том же начальном значении он выдаёт один и тот же результат. Он непригоден для криптографии, если не инициализирован истинной энтропией.

PRNG может иметь обнаружимое статистическое смещение или быть предсказуемым по наблюдаемым результатам. Криптографически стойкий PRNG (CSPRNG) добавляет: (1) прямую защищённость — прошлый результат нельзя предсказать по текущему состоянию, и (2) устойчивость к обратному отслеживанию — будущий результат нельзя предсказать по прошлому.

PRNG считается криптографически стойким, если ни один алгоритм с полиномиальным временем не может отличить его результат от истинно случайной последовательности с вероятностью, существенно превышающей 1/2. Это критерий непредсказуемости следующего бита.

Linux: /dev/urandom (не блокирует выполнение после первоначальной инициализации), системный вызов getrandom(). Windows: CryptGenRandom(), BCryptGenRandom(). macOS/iOS: SecRandomCopyBytes(). Браузер: window.crypto.getRandomValues(). Все они подают данные в пул энтропии OS.

NIST SP 800-22 содержит 15 статистических проверок случайности: частотная проверка, частотная проверка блоков, проверка серий, универсальная проверка Маурера, линейная сложность и другие. Прохождение статистических проверок не доказывает криптографическую безопасность, а лишь свидетельствует об отсутствии очевидного смещения.

CSPRNG, инициализированный слабой энтропией, например текущим временем в секундах, предсказуем. Злоумышленник, знающий начальное значение, может восстановить весь результат. Всегда используйте энтропию OS: os.urandom(32) в Python, а не time.time() или random.random().

Intel RDRAND (инструкция x86) возвращает аппаратно сгенерированные случайные байты от встроенного TRNG. Эквивалентное оборудование существует у AMD и ARM. Linux смешивает RDRAND с данными /dev/urandom. Его используют как дополнительный источник энтропии, а не как единственный источник из-за проблем с доверием.

QRNG используют явления квантовой механики (время прибытия фотонов и флуктуации вакуума) для получения доказуемо случайного результата. Коммерческие QRNG (ID Quantique, Quantis) применяются в приложениях с высокими требованиями к безопасности. Для общего применения их стоимость слишком высока.

TRNG собирают физическую энтропию; PRNG детерминированно расширяют начальное значение; CSPRNG неотличимы от истинной случайности. Пулы энтропии OS объединяют оба источника. Далее: конкретные конструкции CSPRNG, используемые на практике.