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

Задачей генерации псевдослучайных чисел (ГПСЧ) есть создание на основе некоторого блока данных короткой длины, большую длину которые невозможно отличить от действительно случайных. Термин невозможно отличить характеризуется следующим образом, что не существует схемы с полиномиальной скоростью работы, который на основе большой выборки не смог узнать, генератор псевдослучайный или случайный. Случайный блок который создает псевдослучайную последовательность называют начальным. Его размер N в битах, имеет сильное значение для ГПСЧ.

Ясно что вне зависимости от объема потока псевдослучайных битов его емкость равна N бит. Так как ГПСЧ есть конечным элементом, то через 2^N созданных бит, он обязательно зациклится, плохие генераторы имеют еще меньшие длины циклов. Основные принципы ГПСЧ, которые применяются применяются:

Простые рекуррентные арифметические формулы (умножение, сложение) с откидыванием пару последних и первых битов результата.
Те же простые формулы, но в добавок еще взятые по модулю простых чисел.
разложение в любую дробь иррациональных чисел.

Разрядность начального вектора в таких схемах используют 16 или 32 бита — что есть 4 млрд уникальных значений, которых достаточно для множества прикладных задач. Были разработаны простые статистические тесты, которые поверхностно проверяли ГПСЧ. Они не гарантировали идеальную псевдослучайность, но в автоматическом режиме выявляли многие ошибки или сбои в работе ГПСЧ. Один из таких тестов FIPS 140-1. Пройденный тест щитается тогда, когда последовательность из 20000 бит подходит под следующие требования.

Количество единиц X в тестовой последовательности должны лежать в границах 9654 < X < 10346.
Последовательность разбивается на 5000 частей по 4 бита. Делается подщет частоты q[0], … q[15] появление блоков от 0000 до 1111. Также вычисляется сумма квадратов частот Q = q[0]² + q[15]². И делается критерий X₂ = ((Q × 2⁴/5000) — 5000), он владеет статистическим распределением с 2⁴ — 1 степенями свободы, и должен лежать в диапазоне 1,03 < X₂ < 57,4.
Количество непрерывных последовательностей единиц и нулей R₁ и R₀ длины К должны лежать в диапазонах, которые показано на рис.1.
В тестовой последовательности не должно быть непрерывных последовательностей единиц или нулей длиннее 33 бит.

Рисунок — 1

Генератор псевдослучайных чисел может быть криптостойким (КГПСЧ), если по любому объему последовательности не возможно предугадать следующий бит с любой вероятностью, в отличии от 0,5. Для таких требований начальный вектор должен быть 128 бит или больше. При этом начальный вектор не должен быть опубликован, так как с помощью него можно воссоздать цепочку генерации. В современной криптографии реализованы КГПСЧ на основе хэш-функций и блочных шифров. Также известны схемы КГПСЧ FIPS 186, Х9.17 и ГОСТ 28147-89.

Последний использует начальный вектор длиной 320 бит, который состоит из 256 битного ключа К и дополнительного элемента V в 64 бита. Этот элемент используется в алгоритме монолитно.
Алгоритм:

V = Encrypt(V, K);
цикл по i от 0 до нужного количества
начало_i
V[0] = (V[0] + 01010101₁₆)mod 2³²;
V[1] = (V[1] + 01010104₁₆)mod 2³²-1;
RND[i] = EnCrypt(V,K);
конец_i;

На каждом шаге алгоритм генерирует 64 псевдослучайных бита, период повторения последовательности которого 2³² × (2³² — 1). Стойкость к полному перебору начального вектора — 2³²⁰. Последовательность можно использовать для симметричного шифрования, или для поточных скремблеров.

Также смотрите: