Псевдослучайные последовательности

Псевдослучайные последовательности

Самое лучшее, на что способен компьютер, — это сгенерировать псевдослучайную последовательность, которая хотя и выглядит случайной, но, на самом деле, таковой не является. Период псевдослучайной последовательности должен быть достаточно большим, чтобы ее подпоследовательность требуемой длины была апериодичной, т. е. имела период, совпадающий с ее длиной. Например, если нужна строка из миллиона случайных бит, то для ее порождения не стоит использовать генератор последовательностей, которые повторяются через каждые 65536 бит.

Псевдослучайная битовая последовательность должна, по возможности, не отличаться от по-настоящему случайной. Необходимо, чтобы в ней число единиц примерно совпадало с числом нулей, а половина всех “полосок” (подряд идущих идентичных компонентов последовательности) имела длину 1, одна четвертая — длину 2, одна восьмая — длину 4 и т. д. Кроме только что перечисленных, существует еще ряд общепринятых тестов, которые позволяют проверить, действительно ли данная последовательность является псевдослучайной.

Созданию хороших генераторов псевдослучайных последовательностей уделяется достаточно большое внимание в математике. В настоящее время удается порождать последовательности с периодом порядка 2000—3000 бит. Проблема в том, что все генераторы псевдослучайных последовательностей при определенных условиях дают предсказуемые результаты и корреляционные зависимости. А это как раз то, чего ждут от псевдослучайных последовательностей криптоаналитики, чтобы предпринять эффективную атаку на криптосистемы, где эти последовательности используются.