WikiSort.ru - Не сортированное

Криптографически стойкий генератор псевдослучайных чисел (англ. Cryptographically secure pseudorandom number generator, CSPRNG) — это генератор псевдослучайных чисел с определёнными свойствами, позволяющими использовать его в криптографии.

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

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

Задача

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

Требования

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

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

  Пример

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

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

Реализации

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

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

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

Примечания

Ссылки

• Юрий Лифшиц. Лекция 9: Псевдослучайные генераторы // Современные задачи криптографии. — Курс лекций. (недоступная ссылка)
• Cryptographic Random Numbers (англ.)
• Theory and Practice of Random Number Generation (англ.)
• Zvi Gutterman, Benny Pinkas, Tzachy Reinman. Analysis of the Linux Random Number Generator (англ.)
• A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications (англ.) NIST SP 800-22