Интернет магазин китайских планшетных компьютеров

Компьютеры - Криптографически стойкий генератор псевдослучайных чисел - Требования

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

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

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

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