19.3. Генераторы псевдослучайных чисел.

Генераторы псевдослучайных чисел предназначены для получения числовых последовательностей, у которых распределения выборок элементов ведут себя как аналогичные выборки из совокупности с равновероятным и независимым распределением вероятностей.

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

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

В криптографии применяются т.н. криптографически стойкие датчики псевдослучайных чисел (КСД). Так называются генераторы ПСЧ, использующие секретные параметры. Для таких генераторов требуется свойство непредсказуемости: отрезок выходной последовательности относительно большой длины не может быть продолжен как вперед (вправо) так и назад (налево) без знания ключа. Иногда требуется лишь непредсказуемость влево.

Одним из примеров КСД является генератор, рекомендованный стандартом ANSI X9.17, используемый, в частности, при осуществлении платежных операций.

DES

T(i)

V(i+1)

DES c ключом К



DES

V(i)

DES



R(i)

Генератор ПСЧ ANSI X9.17 с использованием алгоритма DES.

На выходе генератора формируются два блока размеров в 64 бита: псевдослучайный блок R(i), являющийся элементом псевдослучайной последовательности, предназначенной для пользователя, и псевдослучайный блок V(i+1), используемый для работы в следующем цикле (изменение внутреннего состояния генератора).

Входными данными генератора, постоянными в течение сеанса генерации, являются К – ключ шифрования и блок V(0) - секретное начальное значение. Кроме того, в каждом цикле работы генератора используется блок T(i), связанный со значением даты-времени начала цикла i (временная отметка).

Очевидно, данную схему возможно приспособить для использования любого блочного шифра.

В Украинском стандарте на цифровую подпись ДСТУ 4145-2002 генератор случайных двоичных последовательностей построен по схеме ПСЧ ANSI X9.17 с использованием криптоалгоритма ГОСТ 28147-89.

Очередной бит b(i) такой последовательности является правым крайним разрядом соответствующего блока R(i).

19.4. Генератор bbs.

Непредсказуемость генератора BBS (аббревиатура связана с фамилиями авторов) основана на сложности задачи извлечения квадратного корня по составному двупростому модулю. Стойкость генератора не ниже сложности задачи факторизации больших двупростых чисел.

Параметром генератор является двупростое число n=pq, где сомножители - большие псевдослучайные простые числа одинакового размера, причем каждый сомножитель сравним с 3 по модулю 4.

Начальное значение формируется в виде , где число , , выбирается случайным образом.

Для построения m битов псевдослучайной последовательности , из i-го члена рекуррентной последовательности вида , , выбирается младший двоичный разряд.

Заметим, что если сомножители числа n известны, то можно легко вычислить произвольный бит псевдослучайной последовательности, порождаемой генератором, без вычисления всех предыдущих битов.

Действительно, , где . Поскольку функция Эйлера известна, то можно эффективно вычислить s при больших значениях i.