Генерация случайных последовательностей

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

На практике в большинстве случаев применяются программные методы получения случайных чисел. На самом дел'е случайные последовательности, получаемые по некоторому алгоритму, являются псевдослучайными. Это происходит из-за того, что связь между значениями в последовательности, получаемой программным путем, обычно все-таки существует. Данное обстоятельство приводит к тому, что на каком-то этапе генерируемая последовательность чисел начинает повторяться — «входит в период».

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

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

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

За эталон генератора случайных чисел (ГСЧ) принят такой генератор, который порождает последовательность случайных чисел с равномерным законом распределения в интервале (0; 1). За одно обращение данный генератор возвращает одно случайное число. Если наблюдать такой ГСЧ достаточно длительное время, то окажется, что, например, в каждый из десяти интервалов (0; 0.1), (0.1; 0.2), (0.2; 0.3), …, (0.9; 1) попадет практически одинаковое количество случайных чисел — то есть они будут распределены равномерно по всему интервалу (0; 1). Если изобразить на графике k = 10 интервалов и частоты N_i попаданий в них, то получится экспериментальная кривая плотности распределения случайных чисел

Рис. 3.1.Частотная диаграмма выпадения случайных чисел, порождаемых реальным генератором.

Оценка качества последовательности производится по определенным критериям. В большинстве случаев для быстрой оценки качества работы генератора случайной последовательности достаточно использовать следующие критерии.

– Длина периода и длина апериодичности. Под длиной периода понимается длина максимальной, не содержащей самой себя, числовой цепочки в последовательности случайных чисел. Длина апериодичности — длина подинтервала последовательности случайных чисел, в пределах которого не встречаются одинаковые значения.

– Равномерность последовательности псевдослучайных чисел. Этот критерий означает вероятность попадания значений, генерируемых датчиком случайных чисел, в каждый из m подинтервалов, на которые можно разбить весь интервал значений, генерируемых данным датчиком случайных чисел.

– Стохастичность последовательности псевдослучайных чисел. Этот критерий означает определение вероятности появления единиц (нулей) в определенных п разрядах генерируемых датчиком случайных чисел.

– Независимость элементов псевдослучайной последовательности. Этот критерий определяет степень корреляции (зависимости) двух случайных величин в сгенерированной последовательности. При проведении оценки по этому критерию можно рассматривать любые, а не только рядом стоящие случайные величины последовательности.