Sankt-Peterburg, St. Petersburg, Russian Federation
Sankt-Peterburg, St. Petersburg, Russian Federation
Sankt-Peterburg, St. Petersburg, Russian Federation
Sankt-Peterburg, St. Petersburg, Russian Federation
UDK 62 Инженерное дело. Техника в целом. Транспорт
GRNTI 55.13 Технология машиностроения
Information safety plays an important role in modern technologies. A stream encryption is one of the common means for information safety support. The sequences with pseudo-random characteristics are often required in the algorithms of stream enciphering. Random systems are recently used as a source of pseudo-random numbers with desired statistical properties. A small length of a sequence period is one of the known problems of the generators of pseudo-random numbers based on chaos realized with a small length of a digit grid. The disturbance of a path or a parameter of random system nonlinearity is one of possible solutions of a short period problem. In this paper there is considered a new approach to the increase of a period length through the change of a symmetry factor in the random model of a memristive circuit. The approach offered is based on switching two values of the symmetry factor in accordance with the output of a shear register with the linear feedback. To confirm the effectiveness of the disturbance circuit described the lengths of a period for the disturbed and original model of the memristive system are estimated. The properties of the output sequences caused by a generator on the basis of the model with controlled symmetry are confirmed by the results of the correlation analysis and NIST statistical testing. The results obtained can be used in cryptographic applications and also at the designing of safe communication systems.
random system, memristor, enciphering, controlled symmetry, semi-non-evident integration
Введение
Хаотическое шифрование - одна из перспективных областей современной криптографии. Эргодичность, топологическое смешивание и высокая чувствительность к начальным условиям и изменениям параметров хаотических систем схожи с традиционно рассматриваемыми процессами перемешивания и рассеивания в традиционных алгоритмах криптографии [1-3]. Использование хаотических систем для генерации псевдослучайных последовательностей (ПСП) в потоковых шифрах обеспечивает высокую скорость шифрования. Поэтому криптографические системы на основе детерминированного хаоса представляют интерес с точки зрения безопасной обработки и передачи мультимедийных данных [4].
Одной из ключевых проблем систем хаотического шифрования, реализуемых на ЭВМ с ограниченной точностью представления данных, является малая длина периода квазихаотической последовательности. В работе [5] К. Персон представил результаты моделирования логистического отображения с использованием арифметики с фиксированной запятой с четырьмя битами для описания дробной части. Автором было показано, что вне зависимости от выбора начальных условий значения начинают повторяться с периодом, равным трем, после всего двух итераций. Одним из перспективных методов увеличения периода квазихаотической последовательности является использование алгоритмов возмущения орбиты или параметра хаотической системы [6; 7]. В частности, в работе [6] было показано, что переключение между двумя значениями параметра логистического отображения значительно увеличивает период квазихаотической последовательности. Стоит отметить, что при возмущении параметра нелинейности системы необходимо отслеживать текущий режим колебаний, определяя его тип - гармонический или хаотический.
В настоящей работе мы предлагаем собственное решение обозначенной выше проблемы путем использования моделей хаотических систем с новым управляемым параметром, называемым коэффициентом симметрии. Изменение коэффициента симметрии осуществляет аффинное преобразование фазового пространства, поэтому его возмущение не влияет на нелинейные свойства системы. Помимо этого, коэффициент симметрии может являться частью ключа для потоковых шифров на основе хаоса. Таким образом, возможно потенциальное повышение криптографической стойкости схем шифрования на основе хаоса.
Модели хаотических систем с управляемой симметрией
Идея дискретных моделей хаотических систем с управляемой симметрией является развитием концепции симметричных хаотических отображений, описанных ранее в работах Д.Н. Бутусова и А.И. Каримова [8; 9]. Отображения Чирикова и Хенона, демонстрирующие симметрию в фазовом пространстве, были получены путем интегрирования гамильтоновых систем. Симметрия достигается за счет применения композиции двух сопряженных полунеявных методов Эйлера - Кромера на интервалах [tn; tn + 0.5h] и
[tn + 0.5h; tn + h] соответственно, где h - шаг интегрирования. При изменении момента интегрирования с 0.5 на коэффициент симметрии S (рис. 1) приобретается возможность управления поворотом в фазовом пространстве.
Рис. 1. Геометрическая интерпретация управления симметрией
Например, для хорошо изученного отображения Чирикова [10], устанавливающего взаимосвязь между импульсом p и координатой x как
симметричная версия, имеющая вид
может быть преобразована в модель с управляемой симметрией следующим образом:
(1)
Фазовые портреты отображения (1) при разных значениях коэффициента симметрии представлены на рис. 2.
Аналогично дискретным хаотическим отображениям с управляемой симметрией могут быть получены адаптивно-симметричные модели непрерывных систем. Рассмотрим систему обыкновенных дифференциальных уравнений (ОДУ), описывающих динамику цепи с мемристором - нелинейным элементом, изменяющим свое сопротивление в зависимости от протекающего через него заряда [11]:
(2)
Хаотический режим в системе (2) наблюдается при ,
,
,
. Применение мемристивных систем в потоковых шифрах представляет особый интерес, поскольку в отличие от многих других систем с хаотическим поведением такие системы подразумевают теоретическую возможность реализации генератора истинно случайных чисел [12] на перспективной элементной базе.
Рис. 2. Фазовые портреты отображения Чирикова с управляемой симметрией при разных S
От системы ОДУ (2) перейдем к конечно-разностной схеме, полученной путем применения полунеявного метода интегрирования [13]:
(3)
Чтобы получить модель с управляемой симметрией, заменим коэффициент 0.5 в (3) на S, как ранее в случае дискретного отображения Чирикова. Итоговая модель системы примет вид
(4)
Возмущение коэффициента симметрии не влияет на нелинейный характер процесса, однако позволяет эффективно избегать наступления периодического режима аналогично изменению параметра нелинейности.
Алгоритм возмущения коэффициента симметрии
Наиболее простая схема возмущения параметра нелинейности была описана Г. Спенгером в работе [6]. Предложенный им способ основан на переключении между двумя значениями параметра каждые N итераций. Хаотичность системы подразумевает, что малое изменение значения параметра приводит к значительному изменению поведения системы. Подход Спенгера показывает хорошие результаты при вычислениях с плавающей запятой. Однако при использовании типа данных с фиксированной запятой и малым количеством бит для представления дробной части хаотическая последовательность может стать периодичной еще до наступления N-й итерации. Поэтому в настоящей статье предлагается модифицировать этот подход и использовать его для возмущения коэффициента симметрии, которое можно производить гораздо чаще за счет минимального влияния симметрии на хаотичность решения.
Пусть S1 и S2 - два значения коэффициента симметрии. Тогда возмущение хаотической системы с управляемой симметрией выполняется путем переключения коэффициента между двумя значениями S1 и S2. Для определения момента переключения используется регистр сдвига с линейной обратной связью (РСЛОС). Значение S1 соответствует нулевому биту на выходе РСЛОС, а S2 - единичному. Предложенная схема возмущения коэффициента симметрии с РСЛОС, который задается примитивным многочленом y8 + y6 + y5 + y4 + 1, представлена на рис. 3.
Рис. 3. Схема возмущения коэффициента симметрии модели хаотической системы
Рассмотрим применение предложенного подхода к мемристивной системе (2). Для оценки длины периода получаемой последовательности используем 16-битный тип данных с фиксированной точкой, где по 8 бит отводится на описание дробной и целой частей. Период оценим при моделировании системы с использованием симметричной конечно-разностной схемы (3), а также схемы с управляемой симметрией (4) при начальных условиях y0 = 0, и
. Для каждой пары начальных условий выполнялось моделирование на временном интервале 500 с с разными значениями
.
Рис. 4. Оценки времени начала периодического режима хаотических последовательностей,
полученных для разных значений параметра нелинейности
Полученные результаты показаны на рис. 4. Белый цвет соответствует максимальному периоду, т.е. в этом случае каждое значение последовательности встречалось ровно один раз. Как можно увидеть, предложенный способ возмущения решения позволяет увеличить период хаотической последовательности.
Генерация псевдослучайных последовательностей на основе моделей с управляемой симметрией
Одним из распространенных способов потокового шифрования является гаммирование - метод, заключающийся в побитовом сложении по модулю 2 последовательности псевдослучайных чисел с открытым текстом. В 2014 г. М. Француа и др. описали генератор ПСП на основе хаотических систем [14]. В предложенной схеме генерации из каждого числа с плавающей запятой извлекаются младшие 32 бита мантиссы. Полученные биты конкатенирутся и образуют искомую последовательность. Рассмотрим генератор ПСП, реализующий такой способ получения бит и использующий разработанный нами способ возмущения коэффициента симметрии. Для оценки генератора проведем статистический анализ генерируемых последовательностей.
Традиционным способом анализа генераторов ПСП является тестирование последовательностей с использованием пакетов статистических тестов. В настоящем исследовании использовались 15 статистических тестов NIST, разработанные в 2001 г. [15]. Пакет NIST позволяет определить меру случайности двоичных последовательностей, полученных исследуемым генератором. Каждый тест вычисляет статистику, характеризующую одно из свойств набора сгенерированных последовательностей. Затем с использованием полученного значения статистики вычисляется вероятность pvalue. Результат сравнивается с уровнем статистической значимости . Если pvalue превышает
, то тест считается пройденным.
В настоящем исследовании расмматривался набор из 100 последовательностей длиной 106 бит каждая, которые были получены при x0 = z0 = 0.492188, y0 = 0, ,
,
,
. Для получения каждой последовательности начальная точка сдвигалась 100 раз на величину машинного эпсилон. Доверительный уровень в проведенных экспериментах был равен 0.01. Полученные результаты представлены в таблице. Можно увидеть, что исследуемый генератор порождает последовательности с характеристиками случайных.
Таблица
Результаты статистического тестирования NIST
|
Статистический тест NIST |
pvalue |
Последовательности, прошедшие тест |
|
Частотный побитовый тест |
0.000001 |
98/100 |
|
Частотный блочный тест |
0.071177 |
98/100 |
|
Тест на последовательность одинаковых битов |
0.000883 |
100/100 |
|
Тест на самую длинную последовательность единиц в блоке |
0.004629 |
100/100 |
|
Тест рангов бинарных матриц |
0.455937 |
100/100 |
|
Спектральный тест |
0.289667 |
99/100 |
|
Тест на совпадение неперекрывающихся шаблонов |
0.026948 |
100/100 |
|
Тест на совпадение перекрывающихся шаблонов |
0.383827 |
99/100 |
|
Универсальный статистический тест Маурера |
0.080519 |
100/100 |
|
Тест на линейную сложность |
0.350485 |
99/100 |
|
Тест на периодичность 1 |
0.006661 |
100/100 |
|
Тест на периодичность 2 |
0.001296 |
100/100 |
|
Тест приблизительной энтропии |
0.090936 |
100/100 |
|
Тест кумулятивных сумм (прямой) |
0.000001 |
97/100 |
|
Тест кумулятивных сумм (обратный) |
0.000002 |
98/100 |
|
Тест на произвольные отклонения |
0.419021 |
100/100 |
|
Другой тест на произвольные отклонения |
0.779188 |
99/100 |
Другим распространенным способом исследования генераторов ПСП является корреляционный анализ, позволяющий обнаружить степень взаимосвязи между элементами набора данных. Известно, что последовательности с коэффициентом корреляции, меньшим 0.3, могут быть использованы для криптографических целей. Для всех пар последовательностей, рассмотренных в предыдущем эксперименте, был рассчитан коэффициент корреляции Пирсона. Распределение полученных значений показано на рис. 5.
Рис. 5. Распределение коэффициента корреляции
Пирсона для последовательностей, полученных
генератором ПСП на основе модели хаотической
системы с управляемой симметрией
Как можно увидеть, вычисленные значения для полученного набора последовательностей по модулю не превышают 0.005, что соответствует слабой корреляционной связи.
Таким образом, возмущение коэффициента симметрии расширяет период генерируемой последовательности и сохраняет свойства последовательностей близкими к свойствам случайных.
Заключение
В статье исследовалось применение модели хаотической системы с управляемой симметрией для генерации гамм в потоковых шифрах. Был предложен алгоритм возмущения коэффициента симметрии для продления периода хаотической последовательности. Предложенный метод основан на переключении двух значений коэффициента симметрии в соответствии с выходом РСЛОС. Результаты экспериментов показали, что применение такого подхода позволяет увеличивать период последовательности при вычислениях с числами с фиксированной запятой с 8-битной дробной частью. Для последовательностей, порожденных генератором ПСП на основе полученной модели с управляемой симметрией, был выполнен статистический анализ. Экспериментально показано, что сгенерированные последовательности удовлетворяют критериям пакета статистических тестов NIST и показывают корреляционные свойства, близкие к случайным последовательностям.
Полученные результаты могут быть использованы в хаотической криптографии для разработки новых методов шифрования данных. Теоретически хаотическое шифрование может быть вычислительно эффективнее, чем традиционные подходы [4], поэтому особый интерес представляет оценка скорости шифрования мультимедийных данных. Кроме того, одним из направлений дальнейших исследований является изучение возможности проведения различных атак, включая реконструкцию фазового пространства, поскольку известно, что некоторые системы шифрования на основе хаотических систем не способы противостоять такой атаке [16].
Д.Н. Бутусов, А.В. Тутуева, Т.И. Каримов получили поддержку Российского фонда фундаментальных исследований в рамках проекта 19-07-00496\19 «Основы
исследовательского проектирования мемристивных систем». А.И. Каримов получил финансирование по гранту Президента для молодых ученых – кандидатов
наук МК-811.2019.1.
1. Permyakov, V.B. Tehnologicheskie mashiny i kompleksy v dorozhnom stroitel'stve (proizvodstvennaya i tehnicheskaya ekspluataciya) / V.B. Permyakov, S.V. Mel'nik, V.I. Ivanov [i dr.]; pod red. V.B. Permyakova. - M.: BASTET, 2014. - 752 s.
2. Buryy, G.G. Greyfer sfericheskiy / G.G. Buryy, I.K. Poteryaev // Mir transporta i tehnologicheskih mashin. - 2017. - № 2. - S. 47-50.
3. Plonecki, L. A concept of digital control system to assist the operator of hydraulic excavators / L. Plonecki, W. Trampczynski, J. Cendrowicz // Automation in construction. - 1998. - № 5. - P. 401-411.
4. Zelenin, A.N. Mashiny dlya zemlyanyh rabot / A.N. Zelenin, V.I. Balovnev, I.P. Kerov. - M.: Mashinostroenie, 1975. - 424 s.
5. Landberg, L. Excavators combine compactness and power / L. Landberg // Construction equipment. - 2003. - № 8. - P. 58-59.
6. Pavlov, V.P. Rekomendacii po vyboru parametrov ekskavatornyh kovshey / V.P. Pavlov, A.N. Abramov // Transportnoe stroitel'stvo. - 1984. - № 7. - S. 35-36.
7. Pat. 2656286 Rossiyskaya Federaciya, MPK E02F 3/28. Kovsh ekskavatora sfericheskiy / Buryy G.G.; zayavitel' i patentoobladatel' Buryy G.G.
8. Zayavka 2018114378/20(022485) Rossiyskaya Federaciya, MPK E02F 3/40. Sposob kopaniya odnokovshovym gidravlicheskim ekskavatorom i odnokovshovyy gidravlicheskiy ekskavator / Buryy G.G., Scherbakov V.S.; zayavitel' Sibirskiy gosudarstvennyy avtomobil'no-dorozhnyy universitet (SibADI).
9. Sinclair, R. Hydraulic Excavators: Quarrying & Mining Applications / R. Sinclair. - London: Sinclair Publishing, 2011. - 388 p.
10. Vetrov, Yu.A. Rezanie gruntov zemleroynymi mashinami / Yu.A. Vetrov. - M.: Mashinostroenie, 1971. - 357 s.
11. Balovnev, V.I. Modelirovanie processov vzaimodeystviya so sredoy rabochih organov dorozhno-stroitel'nyh mashin / V.I. Balovnev. - M.: Vyssh. shk., 1981. - 335 s.
12. Demishcan, V. Experimental researches of the process of enterworking of the operational parts of excavators with soil / V. Demishcan // Vestnik Har'kovskogo nacional'nogo avtomobil'no-dorozhnogo universiteta. - 2008. - № 43. - S. 115-118.
13. Tarasov, V.N. Mehanika kopaniya gruntov, osnovannaya na teorii predel'nyh kasatel'nyh napryazheniy / V.N. Tarasov, M.V. Kovalenko // Stroitel'nye i dorozhnye mashiny. - 2003. - № 7. - S. 38-43.
14. Kuznecova, V.N. Obespechenie energoeffektivnosti razrabotki grunta za schet optimizacii uglov pozicionirovaniya rabochego oborudovaniya ekskavatora / V.N. Kuznecova, V.V. Savinkin // Stroitel'nye i dorozhnye mashiny. - 2015. - № 3. - S. 44-47.
