The study of chaotic pseudo-random sequence generator on the basis of the ODE solvers

Butusov Denis Nikolaevich PhD in Technical Science Associate Professor, Department of CAD, Ulyanov (Lenin) St. Petersburg State Electrotechnical University "LETI" 197376, Russia, g. Saint Petersburg, ul. Professora Popova, 5 dnbutusov@etu.ru Other publications by this author     Tutueva Aleksandra Vadimovna Assistant, Department of CAD, Ulyanov (Lenin) St. Petersburg State Electrotechnical University "LETI" 197376, Russia, Saint Petersburg, ul. Professora Popova, 5 avtutueva@etu.ru Other publications by this author     Pesterev Dmitrii Olegovich technician, Ulyanov (Lenin) St. Petersburg State Electrotechnical University "LETI" 197376, Russia, Saint Petersburg, ul. Professora Popova, 5 dopesterev@etu.ru

Ostrovskii Valerii Yur'evich Graduate Student, Ulyanov (Lenin) St. Petersburg State Electrotechnical University "LETI" 197376, Russia, Saint Petersburg, ul. Professora Popova, 5 vyostrovskii@etu.ru Other publications by this author

Примеры динамических систем с хаотическим поведением встречаются в механике, физике, медицине, биологии, химии, экономике и многих других областях науки и техники ^[1]. Одним из активно развивающихся приложений теории хаоса является использование хаотических систем для генерации псевдослучайных последовательностей (ПСП) в задачах криптографии. Последовательности, получаемые с помощью хаотических генераторов, обладают многими статистическими свойствами, присущими случайным последовательностям ^[2]. Наиболее известный подход к построению генераторов на основе хаотических систем заключается в сравнении двух траекторий, порождаемых дискретными хаотическими отображениями. Чаще всего используется логистическое ^[3] или кусочно-линейное ^[4] отображение. Хотя подобные генераторы просты в реализации, они позволяют получать всего один бит последовательности за одну итерацию. Кроме того, не исключена ситуация, когда траектории двух хаотических отображений, построенные с разными значениями начальных зерен, через некоторое время совпадут. В таком случае выходная последовательность генератора с момента наступления равенства значений отображений будет состоять из набора одинаковых бит ^[5]. Для увеличения мощности множества получаемых генератором ПСП применяют хаотические системы более высокого порядка с большим числом управляющих параметров [6–8]. Как правило, математическая модель таких систем представлена обыкновенными дифференциальными уравнения (ОДУ). Практическая реализация генераторов в данном случае влечет за собой необходимость выбора численного метода и шага интегрирования. На настоящий момент эта задача решается исследователем самостоятельно, и влияние эффектов дискретизации и типа дискретного оператора на статистические свойства генерируемых ПСП практически не учитывается. В большинстве случаев используются встроенные решатели ОДУ программных сред разработки, основывающиеся на одношаговых явных и неявных алгоритмах. Поскольку явные алгоритмы не всегда обладают нужной численной устойчивостью, а неявные методы характеризуются высокой вычислительной сложностью, оба этих класса методов не являются оптимальными при синтезе конечно-разностных схем генераторов ПСП. В качестве альтернативного математического аппарата в работах [9–14] были предложены полунеявные численные методы решения ОДУ, применение которых позволяет повысить адекватность конечно-разностной модели хаотической системы. При этом вопрос пригодности полуявных алгоритмов численного решения хаотических ОДУ в качестве основы для генератора ПСП не рассматривался.

В настоящей работе рассматривается методика выбора параметров решателя ОДУ в составе хаотического генератора на основе анализа шаговых диаграмм (h-диаграмм). Данный инструмент представляет собой бифуркационную диаграмму дискретной модели с шагом интегрирования в роли изменяемого параметра. Применение предлагаемого подхода теоретически позволит ускорить процесс проектирования генераторов ПСП за счет более высокой скорости построения h-диаграмм по сравнению с традиционными статистическими тестами. В статье приводятся алгоритм генерации ПСП и методика выбора конечно-разностной схемы генератора, включая выбор оптимальных параметров конечно-разностной схемы путем анализа h-диаграмм. Для оценки качества решения порождаемые генераторами последовательности тестируются с помощью батареи статистических тестов NIST, реализованных в среде проектирования виртуальных приборов NI LabVIEW. Показано, что генераторы ПСП на основе полуявных алгоритмов численного решения ОДУ не уступают по качеству неявным конечно-разностным схемам, обладая при этом существенно меньшей вычислительной сложностью.

Алгоритм генерации двоичных ПСП на основе численного решения хаотической системы дифференциальных уравнений ^[15] состоит из следующих этапов:

1. Численное решение системы ОДУ.

1.1. Задание требуемой длины выходной последовательности генератора n.

1.2. Выбор хаотической системы, задание значений параметров нелинейности. Выбор численного метода и шага интегрирования h.

1.3. Расчет количества точек, в которых будет получено численное решение выбранной системы, по формуле m = n / 32h. Коэффициент в знаменателе задает получение 32 бит выходной последовательности генератора для каждого значения переменной состояния.

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

1. Извлечение двоичной последовательности из найденного решения.

2.1. Расчет коэффициента нормализации kкак максимального значения разности между двумя соседними точками решения:

`k=max{|x_(i)-x_(i-1)|}, i in <sup>[1;m]</sup>`

где x – выбранная переменная состояния.

2.2.Нормализация последовательности с применением коэффициента k:

`x_(NORM)=(x)/(k)-floor((x)/(k)).`

2.3.Приведение нормализованной последовательности x_NORM к беззнаковому целочисленному типу данных с длиной машинного слова 32 бит по формуле:

`x_(FINAL)=floor(x_(NORM)(2^(32)-1))`

2.4.Получение итоговой последовательности длины n путем конкатенации двоичных представлений чисел п. 2.3

В качестве тестовой хаотической системы была выбрана система Рёсслера, нормальная форма Коши которой имеет вид

`dotx=-y-z;`

`doty=x+ay;`

`dotz=b+z(x-c),`

где a = 0.2, b = 0.2, c = 5.7. При данных параметрах система демонстрирует хаотическое поведение ^[16].

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

Выбор параметров конечно-разностной схемы хаотического генератора осуществляется путем анализа шаговых диаграмм. С помощью алгоритма, предложенного в работе ^[17], для всех исследуемых конечно-разностных схем выполняется построение одномерной бифуркационной диаграммы. При этом параметром нелинейности выступает шаг интегрирования. Применяя к полученным данным алгоритм ядерной оценки плотности распределения (KDE) ^[17] можно определить диапазоны шагов дискретизации, при которых система демонстрирует хаотическое поведение. Ожидается, что при генерации ПСП в выбранных диапазонах шага порождаемые последовательности будут лучше проходить тесты на случайность.

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

1. Генерируется массив вещественных чисел, инициализирующих внутреннее состояние хаотического генератора (начальные условия задачи Коши), размерностью M × N, где M – количество переменных состояния хаотической системы, N – число последовательностей, которое планируется получить каждым рассматриваемым генератором.
2. По алгоритму KDE определяются два массива H₁ и H₂: значения шага интегрирования, при которых система демонстрирует хаотическое поведение, записываются в H₁, остальные – в H₂.
3. Рассматриваются два состояния генератора, соответствующие определенным в п. 2 массивам. В каждом из них для всех шагов интегрирования генерируется N последовательностей, которые тестируются батареей статистических тестов NIST.
4. По результатам тестирования по 15 статистическим тестам вычисляются частные пропорции p_ijпоследовательностей из N, которые можно считать псевдослучайными, где i – номер теста NIST, j – индекс шага интегрирования в массиве H₁ или H₂.
5. По полученным в п. 4 частным пропорциям вычисляется общая доля последовательностей p_Hi, успешно прошедших статистическое тестирование NIST для двух состояний генератора. Расчет p_Hiвыполняется по формуле

`p_(Hi)=(sum_(j=1)^s p_(ij))/(s)`

где s – размерность массива H₁ или H₂

Если значения p_Hi, соответствующие массиву H₁, подтверждают прохождение тестов NIST сгенерированными последовательностями, то отобранные значения шага можно использовать в хаотическом генераторе ПСП на основе данного метода. По h-диаграммам конечно-разностных схем также возможно определить максимальный шаг дискретизации, при котором сохраняются свойства хаотической системы-прототипа.

Рассматриваемые хаотические генераторы и инструменты их исследования были реализованы в среде проектирования виртуальных приборов NI LabVIEW. Численное решение ОДУ рассчитывалось с постоянным шагом интегрирования методами первого и второго порядка точности в диапазонах шага ^{[0,0005; 0,05]} и ^{[0,001; 0,15]}, соответственно. С помощью каждого генератора было получено 100 последовательностей длиной 10⁶ бит.

На рис. 1–4 представлены результаты экспериментального исследования генераторов ПСП на основе различных конечно-разностных схем первого порядка. Можно отметить сильную корреляцию графиков KDE и результатов статистического тестирования последовательностей. Анализ полученных h-диаграмм показывает, что наибольшим диапазоном шагов, в котором наблюдается хаотическое поведение системы, обладает генератор, основанный на полунеявном методе. При малых шагах интегрирования также возможно получение последовательностей, успешно проходящих тесты на случайность, в генераторах на основе неявного метода Эйлера и полуявного алгоритма Эйлера-Кромера. Таким образом, из всех исследованных методов первого порядка, наилучшим с точки зрения проектирования генераторов псевдослучайных последовательностей оказывается Д-метод.

Рисунок 1 – Шаговая диаграмма, оценка KDE и результаты NIST - тестирования хаотического генератора на основе явного метода Эйлера

Рисунок 2 – Шаговая диаграмма, оценка KDE и результаты NIST - тестирования хаотического генератора на основе неявного метода Эйлера

Рисунок 3 – Шаговая диаграмма, оценка KDE и результаты NIST - тестирования хаотического генератора на основе полуявного метода Эйлера-Кромера

Рисунок 4 – Шаговая диаграмма, оценка KDE и результаты NIST - тестирования хаотического генератора на основе полунеявного Д-метода

Рисунок 5 – Результаты статистического тестирования генераторов ПСП в (а) хаотическом и (б) гармоническом режимах колебаний дискретной модели системы Рёсслера

Приняв пороговое значение, при котором значение шага интегрирования будет отнесено к массиву H₁, равным 70, вычислим общие пропорции последовательностей p_Hi для двух исследуемых состояний генераторов (рис. 5). Можно отметить, что в нехаотическом режиме колебаний все рассматриваемые генераторы производят последовательности, 50–80% которых не проходят спектральный тест NIST (№ 6), что свидетельствует об их периодичности. Также в сгенерированных последовательностях обнаруживается неравномерность распределения нулей и единиц (тесты №1 и №13). В хаотическом режиме наиболее предпочтительными выглядят генераторы на основе явной и полунеявной конечно-разностной схем, так как вычисленные для них значения p_Hi превышают 0,775.

Бифуркационный анализ хаотических генераторов на основе конечно-разностных схем второго порядка (рис. 6–8) показывает, что диапазон шага дискретизации для метода неявной средней точки и полунеявного алгоритма КД шире, нежели для метода явной средней точки. Для всех генераторов характерно наличие двух-трех узких интервалов, где происходит смена режимов колебаний системы, однако в целом данные интервалы меньше, чем у решателей первого порядка. Учитывая существенную вычислительную сложность конечно-разностной схемы неявной средней точки даже в линейно-неявном варианте, при аппаратной реализации генератора предпочтительнее использовать симметричный полунеявный численный метод КД. С точки зрения настоящего исследования, также важно отметить сохраняющуюся корреляцию между шаговой диаграммой, ее оценкой по алгоритму KDE и успешностью прохождения тестов NIST порождаемыми псевдослучайными последовательностями. Это подтверждает теоретические предположения работы о пригодности предлагаемого аппарата анализа для оценки свойств хаотических генераторов ПСП.

Рисунок 6 – Шаговая диаграмма, оценка KDE и результаты NIST-тестирования хаотического генератора на основе явного метода средней точки

Рисунок 7 – Шаговая диаграмма, оценка KDE и результаты NIST-тестирования хаотического генератора на основе линейно-неявного метода средней точки

Рисунок 8 – Шаговая диаграмма, оценка KDE и результаты NIST-тестирования хаотического генератора на основе полунеявного метода КД

Статистическое исследование хаотических генераторов, основанных на конечно-разностных схемах второго порядка, показывает, что ПСП, получаемые при шагах интегрирования, соответствующих нехаотическому режиму дискретной модели системы Рёсслера, не обладают свойствами случайных последовательностей (рис. 9, б). Тестирование NIST выявляет множественные статистические дефекты в 40% сгенерированных ПСП. Доля успешно прошедших статистические тесты последовательностей, получаемых в хаотическом режиме работы генератора, варьируется в диапазоне 0,63–0,98 в зависимости от используемого численного метода. Наиболее эффективной по результатам всех тестов NIST является полуявная конечно-разностная схема на основе метода КД, поскольку рассчитанные для нее доли p_H1 во всех случая превышают 0,85.

Рисунок 9 – Результаты статистического тестирования генераторов ПСП в (а) хаотическом и (б) гармоническом состояниях дискретной модели системы Рёсслера

Анализируя результаты вычислительных экспериментов, можно сделать вывод, что более целесообразным является применение конечно-разностных схем второго порядка, поскольку их использование позволяет генерировать ПСП на большем диапазоне шагов, а некоторое усложнение алгоритма генерации несущественно в контексте прогресса современных аппаратных платформ. Исходя из результатов статистического тестирования, полунеявные алгоритмы численного интегрирования не только обладают оптимальным соотношением вычислительных затрат к точности моделирования, как было показано в работах [9–14], но и могут быть рекомендованы для использования в хаотических генераторах ПСП. Проведенное тестирование сгенерированных последовательностей экспериментально подтверждает возможность применения шаговых диаграмм в качестве инструмента выбора шага дискретизации и дискретного оператора при синтезе архитектуры генератора ПСП. Учитывая существенные временные затраты на обработку генерируемых последовательностей пакетом тестов NIST, использование h-диаграмм в паре с графиками KDE для оценки качества конечно-разностной схемы генератора, может значительно ускорить процесс проектирования хаотических генераторов ПСП.

В работе предложен новый инструмент анализа хаотических генераторов ПСП на основе шаговых диаграмм. Экспериментально показана возможность определения по h-диаграммам диапазонов шага дискретизации, в которых могут быть получены последовательности, успешно проходящие статистические тесты на случайность. Применение рассматриваемого подхода может ускорить процесс проектирования хаотических генераторов ПСП, поскольку построение h-диаграмм является существенно (в несколько десятков раз) менее вычислительно затратной задачей, нежели статистическое тестирование генерируемых последовательностей. Полученные экспериментальные данные для генераторов на основе конечно-разностных моделей системы Рёсслера, синтезированных с помощью методов первого и второго порядка алгебраической точности, подтверждают преимущества полунеявных алгоритмов в сравнении с традиционно используемыми численными методами интегрирования. Дальнейшим направлением работы является исследование генераторов ПСП на основе других хаотических систем и разработка строгих критериев выбора шага интегрирования при помощи количественных оценок и мер хаоса. Работа выполнена при поддержке РФФИ, проект «Теория и средства проектирования цифровых генераторов хаотических сигналов» (Договор № 17-07-0086217 от 10.04.2017).