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

Многие прикладные задачи криптографии требуют случайных чисел, например:

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

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

Требования к обычному генератору псевдослучайных чисел выполняются и криптографически стойким ГПСЧ, обратное неверно. Требования к КСГПСЧ можно разделить на две группы: во-первых, они должны проходить статистические тесты на случайность; а во-вторых, они должны сохранять непредсказуемость, даже если часть их исходного или текущего состояния становится известна криптоаналитику. А именно:

• КСГПСЧ должен удовлетворять «тесту на следующий бит». Смысл теста в следующем: не должно существовать полиномиального алгоритма, который, зная первые k битов случайной последовательности, сможет предсказать (k+1)-ый бит с вероятностью более 50 %. Эндрю Яо доказал в 1982 году, что генератор, прошедший «тест на следующий бит», пройдёт и любые другие статистические тесты на случайность, выполнимые за полиномиальное время.
• КСГПСЧ должен оставаться надёжным даже в случае, когда часть или все его состояния стали известны (или были корректно вычислены). Это значит, что не должно быть возможности получить случайную последовательность, созданную генератором, предшествующую получению этого знания криптоаналитиком. Кроме того, если во время работы используется дополнительная энтропия, попытка использовать знание о входных данных должна быть вычислительно невозможна.
  Пример
  Пусть генератор основывается на выводе битов двоичного представления числа π, начиная с какой-то неизвестной точки. Такой генератор, возможно, и пройдёт «тест на следующий бит», так как π, видимо, является случайной последовательностью (это было бы гарантированно, если доказать, что π является нормальным числом). Однако этот подход не является криптографически надёжным — если криптоаналитик определит, какой бит числа π используется в данный момент, он сможет вычислить и все предшествующие биты.

Большинство генераторов псевдослучайных чисел не подходит для использования в качестве КСГПСЧ по обоим критериям. Во-первых, несмотря на то, что многие ГПСЧ выдают последовательность, случайную с точки зрения разнообразных статистических тестов, они не надёжны по отношению к обратной разработке. Могут быть обнаружены специализированные, особым образом настроенные тесты, которые покажут, что случайные числа, получаемые из ГПСЧ не являются по настоящему случайными. Во-вторых, для большинства ГПСЧ возможно вычислить всю псевдослучайную последовательность, если их состояние скомпрометировано, что позволит криптоаналитику получить доступ не только к будущим сообщениям, но и ко всем предыдущим. КСГПСЧ разрабатываются с учётом сопротивляемости к различным видам криптоанализа.

Рассмотрим три класса реализации КСГПСЧ:

1. На основе криптографических алгоритмов
2. На основе вычислительно сложных математических задач
3. Специальные реализации

В последних часто используются дополнительные источники энтропии, поэтому, строго говоря, они не являются «чистыми» генераторами, так как их выход не полностью определяется исходным состоянием. Это позволяет дополнительно защититься от атак, направленных на определение исходного состояния.

Реализации на основе криптографических алгоритмов

• Безопасный блочный шифр можно преобразовать в КСГПСЧ, запустив его в режиме счетчика. Таким образом, выбрав случайный ключ, можно получать следующий случайный блок, применяя алгоритм к последовательным натуральным числам. Счет можно начинать с произвольного натурального числа. Очевидно, что периодом будет не больше, чем 2ⁿ для n-битного блочного шифра. Также очевидно, что безопасность такой схемы полностью зависит от секретности ключа.

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

• Большинство потоковых шифров работает на основе генерации псевдослучайного потока бит, которые некоторым образом комбинируется (почти всегда с помощью операции XOR) с битами открытого текста. Запуск такого шифра на последовательности натуральных чисел даст новую псевдослучайную последовательность, возможно, даже с более длинным периодом. Такой метод безопасен только если в самом потоковом шифре используется надёжный КСГПСЧ (что не всегда так). Опять же, начальное состояние счётчика должно оставаться секретным.

Реализации на основе математических задач

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

Специальные реализации

Существует целый ряд практически используемых ГПСЧ которые разрабатывались с учетом криптографической стойкости, например

• Алгоритм Ярроу (англ. Yarrow algorithm) который пытается определить энтропию входных данных. Он используется в FreeBSD, OpenBSD и Mac OS X
• Алгоритм Fortuna (англ. Fortuna algorithm), наследник алгоритма Ярроу.
• Специальный файл ОС UNIX /dev/random, в частности, /dev/urandom, реализованный в Linux.
• Функция CryptGenRandom предоставленная в CryptoAPI компании Microsoft
• ISAAC базируется на варианте RC4.