КЛАССИФИКАЦИЯ ГЕНЕРАТОРОВ ПСЕВДОСЛУЧАЙНЫХ ЧИСЕЛ

В основе почти каждого генератора псевдослучайных последовательностей лежит нелинейное преобразование, которое используется как режим обратной связи (OFB), или как режим выхода (CNT). Перечислим несколько основных на сегодняшний день способов построения таких преобразований.

1) Использование многократного повторения одной и той же раундовой операции, в состав которой входят преобразования замены и перестановки. Идея этого способа - обеспечить свойства рассеивания и перемешивания информации, которые, согласно К. Шеннону, необходимы любому непредсказуемому генератору псевдослучайных последовательностей. Данный способ используется для создания блочных генераторов. Этот принцип используют все существующие государственные стандарты. У генераторов такого класса есть несколько недостатков, одним из которых является невысокое быстродействие, также это высокая цена, которую приходится платить, чтобы обеспечить непредсказуемость формируемых последовательностей. Несмотря на это наличие у генератора этого свойства основывается на недоказуемом предположении о том, что у противника не хватит ресурсов (вычислительных, временных или материальных) чтобы инвертировать используемую нелинейную функцию обратной связи или выхода.

2) Использование односторонних функций. Понятие односторонней функции введено Диффи и Хеллманом в 1978 году, однако до сих пор ни одной односторонней функции не найдено. Существуют и реально используются лишь функции-кандидаты на звание односторонних, иначе говоря, функции, которые вероятно являются односторонними. Задача инвертирования этих функций эквивалентна решению трудной математической задачи, например, задачи факторизации больших чисел, на основе которой построен генератор RSA, долгое время являвшийся де-факто неофициальным мировым стандартом для генераторов псевдослучайных последовательностей этого класса. Недостатки генераторов этого класса те же, что и в предыдущем случае, причем их быстродействие во много раз ниже, чем у блочных генераторов, которые сами считаются медленными.

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

Наиболее удобным методом анализа архитектуры любого объекта является рассмотрение его с точки зрения системного подхода. Здесь должны быть получены ответы на следующие вопросы:

• установление состава, структуры и организации элементов и частей системы, обнаружение ведущих взаимодействий между ними;
• выявление внешних связей системы, выделение главных;
• определение функций системы и ее роли среди других систем;
• анализ диалектики структуры и функций системы;
• обнаружение на этой основе закономерностей и тенденций развития системы.

Попытаемся найти ответы на перечисленные вопросы относительно программно-аппаратного комплекса для моделирования и исследования стохастических процессов.

Классификация генераторов псевдослучайных последовательностей показана на рисунке 1. В качестве параметров выбраны:

• тип используемого нелинейного преобразования;
• структура генератора;
• наличие или отсутствие внешних источников случайности.

Рисунок 1. Классификация генераторов псевдослучайных последовательностей

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

Достоинство некриптографических генераторов – эффективная программная и аппаратная реализация. Недостаток – предсказуемость. Разновидность конгруэнтных генераторов – аддитивные генераторы Галуа и Фибоначчи, генераторы, функционирующие в конечных полях, генераторы на регистрах сдвига с нелинейными обратными связями можно использовать лишь в качестве строительных блоков при разработке качественных генераторов псевдослучайных последовательностей.

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

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

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

• использование в качестве строительных блоков генераторов, функционирующих в конечных полях (генераторы SOBER, PANAMA, SNOW и др.);
• использование при построении нелинейных функций блоков пространственного сжатия (space compression) информации для необратимости результирующего преобразования;
• использование таблиц замен или стохастического преобразования, непрерывно изменяющихся в процессе работы (RC4, SQ1-R и др.).

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

Анализ криптографических генераторов позволяет сделать два основных вывода:

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

Наличие или отсутствие внешних источников случайности. В тех приложениях, где требуется неоднократно формировать одну и ту же последовательность (например, при генерации гаммы), генераторы псевдослучайных последовательностей не имеют внешних источников случайности, во всех же других случаях их использование необходимо. При этом при программной реализации в качестве источников случайности обычно используются системный таймер, клавиатура, мышь, дисковая подсистема персонального компьютера (ПК). Классическим примером такого генератора псевдослучайных последовательностей может служить проект Yarrow фирмы Counterpane Б. Шнайера. При аппаратной реализации в качестве источников случайности могут использоваться физические датчики случайных чисел.

Список литературы:

1. Слеповичев И.И. Введение в теориюгенераторов псевдослучайных чисел / Слеповичев И.И. - Самара: LAP LAMBERT Academic Publishing, 2016 – 128 с.
2. Слеповичев И.И. Генераторы псевдослучайных чисел / Слеповичев И.И. - Самара: LAP LAMBERT Academic Publishing, 2017 – 113 с.
3. Асосков А.В., Иванов М.А., Мирский А.А., Рузин А.В., Сланин А.В., Тютвин А.Н. Поточные шифры. – М.: КУДИЦ-ОБРАЗ, 2013. С.8-30.