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).