Translate this page:
Please select your language to translate the article


You can just close the window to don't translate
Library
Your profile

Back to contents

Software systems and computational methods
Reference:

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
 

 

DOI:

10.7256/2454-0714.2017.4.24786

Received:

20-11-2017


Published:

11-01-2018


Abstract: An approach to the selection of a finite-difference scheme of a chaotic pseudo-random sequence generator based on the use of step diagrams (h-diagrams) is proposed. As a test problem, a generator is considered based on the random Rössler system discretized by explicit, implicit and semiquant numerical methods of the first and second order of algebraic accuracy. The sequences generated by different variants of the generator are randomly checked by a battery of NIST statistical tests. Advantages of the proposed approach in the design of chaotic signal generators are shown, consisting in an essential (by an order of magnitude) acceleration of the device design time due to a new method of selecting the discretization step and the discrete operator. The effectiveness of using semi-implicit finite difference schemes in the generation of pseudo-random sequences by the method of numerical solution of chaotic differential equations is confirmed. The obtained results can be used in cryptography applications, in the design of secure communication systems, in solving problems of numerical simulation of dynamical systems and mathematical statistics.


Keywords:

pseudo-random numbers, dynamical chaos, numerical integration method, step diagram, NIST tests, Rossler system, ODE solver, semi-implicit method, bifurcation, discrete operator


Введение

Примеры динамических систем с хаотическим поведением встречаются в механике, физике, медицине, биологии, химии, экономике и многих других областях науки и техники [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 [1;m]`

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

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

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

2.3.Приведение нормализованной последовательности xNORM к беззнаковому целочисленному типу данных с длиной машинного слова 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 определяются два массива H1 и H2: значения шага интегрирования, при которых система демонстрирует хаотическое поведение, записываются в H1, остальные – в H2.
  3. Рассматриваются два состояния генератора, соответствующие определенным в п. 2 массивам. В каждом из них для всех шагов интегрирования генерируется N последовательностей, которые тестируются батареей статистических тестов NIST.
  4. По результатам тестирования по 15 статистическим тестам вычисляются частные пропорции pijпоследовательностей из N, которые можно считать псевдослучайными, где i – номер теста NIST, j – индекс шага интегрирования в массиве H1 или H2.
  5. По полученным в п. 4 частным пропорциям вычисляется общая доля последовательностей pHi, успешно прошедших статистическое тестирование NIST для двух состояний генератора. Расчет pHiвыполняется по формуле

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

где s – размерность массива H1 или H2

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

Экспериментальные результаты

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

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

1_01

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

2

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

3

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

4

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

5

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

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

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

6

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

7

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

8

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

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

9

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

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

Заключение

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

References
1. Skiadas C. H., Skiadas C. Handbook of applications of chaos theory. – CRC Press, 2016.
2. Falcioni M., Palatella L., Pigolotti S., Vulpiani A. Properties making a chaotic system a good pseudo random number generator // Physical Review E. – 2005. – vol. 72. – №. 1. – p. 016220.
3. Patidar V., Sud K. K., Pareek N. K. A pseudo random bit generator based on chaotic logistic map and its statistical testing // Informatica. – 2009. – p. 33. – №. 4.
4. Wang X. Y., Xie Y. X. A design of pseudo-random bit generator based on single chaotic system // International Journal of Modern Physics C. – 2012. – vol. 23. – №. 03. – pp. 1250024.
5. François M., Defour D., Negre C. A fast chaos-based pseudo-random bit generator using binary64 floating-point arithmetic // Informatica. – 2014. – vol. 38. – №. 3.
6. Akhshani A., Akhavan A., Mobaraki A., Lim S. C., Hassan Z. Pseudo random number generator based on quantum chaotic map // Communications in Nonlinear Science and Numerical Simulation. – 2014. – vol. 19. – №. 1. – pp. 101-111.
7. Hu H. P., Liu L. F., Ding N. D. Pseudorandom sequence generator based on the Chen chaotic system // Computer Physics Communications. – 2013. – vol. 184. – №. 3. – pp. 765-768.
8. Stoyanov B., Szczypiorski K., Kordov K. Yet Another Pseudorandom Number Generator // International Journal of Electronics and Telecommunications. – 2017. – vol. 63. – №. 2. – pp. 195-199.
9. Butusov D. N., Karimov A. I., Andreev V. S. Computer simulation of chaotic systems with symmetric extrapolation methods //Soft Computing and Measurements (SCM), 2015 XVIII International Conference on. – IEEE, 2015. – S. 78-80.
10. Butusov D. N., Karimov A. I., Tutueva A. V. Symmetric extrapolation solvers for ordinary differential equations //NW Russia Young Researchers in Electrical and Electronic Engineering Conference (EIConRusNW), 2016 IEEE. – IEEE, 2016. – S. 162-167.
11. Butusov D. N., Tutueva A. V., Homitskaya E. S. Extrapolation Semi-implicit ODE solvers with adaptive timestep //Soft Computing and Measurements (SCM), 2016 XIX IEEE International Conference on. – IEEE, 2016. – S. 137-140.
12. Butusov D. N., Andreev V. S., Pesterev D. O. Composition semi-implicit methods for chaotic problems simulation //Soft Computing and Measurements (SCM), 2016 XIX IEEE International Conference on. – IEEE, 2016. – S. 107-110.
13. Butusov D. N., Ostrovskii V. Y., Pesterev D. O. Numerical analysis of memristor-based circuits with semi-implicit methods //Young Researchers in Electrical and Electronic Engineering (EIConRus), 2017 IEEE Conference of Russian. – IEEE, 2017. – S. 271-276.
14. Karimov A. I., Butusov D. N., Tutueva A. V. Adaptive explicit-implicit switching solver for stiff ODEs //Young Researchers in Electrical and Electronic Engineering (EIConRus), 2017 IEEE Conference of Russian. – IEEE, 2017. – S. 440-444.
15. Tutueva A. V. et al. Novel normalization technique for chaotic Pseudo-random number generators based on semi-implicit ODE solvers //" Quality Management, Transport and Information Security, Information Technologies"(IT&QM&IS), 2017 International Conference. – IEEE, 2017. – S. 292-295.
16. Peitgen H. O., Jürgens H., Saupe D. Chaos and fractals: new frontiers of science. – Springer Science & Business Media, 2006.
17. Butusov D. N. et al. Comparing the algorithms of multiparametric bifurcation analysis //Soft Computing and Measurements (SCM), 2017 XX IEEE International Conference on. – IEEE, 2017. – S. 194-198