Проблемы генерирования криптографически стойкой псевдослучайной последовательности (псп) чисел.

К генератору такой ПСП предъявляются следующие требования:

1. Период ПСП должен быть достаточно большим.

2. ПСП должна быть труднопредсказуемой по отдельному «куску».

3. Генерирование должно быть технически не очень сложным.

Известно довольно много простых алгоритмов генерации, обеспечивающих длину периода порядка 10⁷…10⁹неповторяющихся десятичных чисел с довольно хорошими статистическими свойствами.

Например, по Хоффману хорош линейный конгруентный генератор. i-е псевдослучайное числоq_iвычисляется из предыдущегоq_i-1по формуле:

q_i = (aq_i-1 + b) mod m , (1)

где m– максимальное значение целого псевдослучайного числа.

ПСП qимеет максимальную длину неповторяющихся равнуюm, если взятьm= 2^k,k– целое большее 2 (k>2),b– нечетное и аmod4 = 1.

Разработаны методики конгруентных генераторов, например, m– простое 2³¹–1,b– взаимно простое сmи а – нечетное, а также другие модификации параметров в формуле (1).

Алгоритм конгруентного генератора генератора национального бюро стандартов США имеет длину периода 2⁶⁴и обладает сравнительно хорошими статистическими свойствами.

Всякий генератор ПСП чисел следует сначала тестировать на статистические качества (см. описание лабораторной работы http://www.main.vsu.ru/library/met/на сайте физического ф-та ВГУ), а затем исследовать на криптостойкость.

Тесты статистических свойств ПСП чисел:

1. определение длины периода lи апериодаL;

2. определение одномерной, двух-, 3-х и 4-мерной равномерности разбиением чисел ПСП на числа с соответствующим количеством разрядов;

3. вычисление коэффициентов неравномерности;

4. определение корреляционных свойств ПСП чисел;

5. вычисление по известной статистической задаче, например, значения числа .