Санкт-Петербург, г. Санкт-Петербург и Ленинградская область, Россия
Санкт-Петербург, г. Санкт-Петербург и Ленинградская область, Россия
сотрудник
Санкт-Петербург, г. Санкт-Петербург и Ленинградская область, Россия
Санкт-Петербург, г. Санкт-Петербург и Ленинградская область, Россия
УДК 62 Инженерное дело. Техника в целом. Транспорт
ГРНТИ 55.13 Технология машиностроения
Проведено исследование с целью повышения эффективности шифрования на основе хаотических систем за счет применения моделей с управляемым коэффициентом симметрии. В качестве методов исследования использованы вычислительный эксперимент, методы статистического анализа и теории численных методов интегрирования. Получены новые модели хаотических систем с управляемой симметрией и способ увеличения периода хаотической последовательности путем возмущения коэффициента симметрии.
хаотическая система, мемристор, шифрование, управляемая симметрия, полунеявное интегрирование
Введение
Хаотическое шифрование - одна из перспективных областей современной криптографии. Эргодичность, топологическое смешивание и высокая чувствительность к начальным условиям и изменениям параметров хаотических систем схожи с традиционно рассматриваемыми процессами перемешивания и рассеивания в традиционных алгоритмах криптографии [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. Пермяков, В.Б. Технологические машины и комплексы в дорожном строительстве (производственная и техническая эксплуатация) / В.Б. Пермяков, С.В. Мельник, В.И. Иванов [и др.]; под ред. В.Б. Пермякова. - М.: БАСТЕТ, 2014. - 752 с.
2. Бурый, Г.Г. Грейфер сферический / Г.Г. Бурый, И.К. Потеряев // Мир транспорта и технологических машин. - 2017. - № 2. - С. 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. Зеленин, А.Н. Машины для земляных работ / А.Н. Зеленин, В.И. Баловнев, И.П. Керов. - М.: Машиностроение, 1975. - 424 с.
5. Landberg, L. Excavators combine compactness and power / L. Landberg // Construction equipment. - 2003. - № 8. - P. 58-59.
6. Павлов, В.П. Рекомендации по выбору параметров экскаваторных ковшей / В.П. Павлов, А.Н. Абрамов // Транспортное строительство. - 1984. - № 7. - С. 35-36.
7. Пат. 2656286 Российская Федерация, МПК Е02F 3/28. Ковш экскаватора сферический / Бурый Г.Г.; заявитель и патентообладатель Бурый Г.Г.
8. Заявка 2018114378/20(022485) Российская Федерация, МПК E02F 3/40. Способ копания одноковшовым гидравлическим экскаватором и одноковшовый гидравлический экскаватор / Бурый Г.Г., Щербаков В.С.; заявитель Сибирский государственный автомобильно-дорожный университет (СибАДИ).
9. Sinclair, R. Hydraulic Excavators: Quarrying & Mining Applications / R. Sinclair. - London: Sinclair Publishing, 2011. - 388 p.
10. Ветров, Ю.А. Резание грунтов землеройными машинами / Ю.А. Ветров. - М.: Машиностроение, 1971. - 357 с.
11. Баловнев, В.И. Моделирование процессов взаимодействия со средой рабочих органов дорожно-строительных машин / В.И. Баловнев. - М.: Высш. шк., 1981. - 335 с.
12. Demishcan, V. Experimental researches of the process of enterworking of the operational parts of excavators with soil / V. Demishcan // Вестник Харьковского национального автомобильно-дорожного университета. - 2008. - № 43. - С. 115-118.
13. Тарасов, В.Н. Механика копания грунтов, основанная на теории предельных касательных напряжений / В.Н. Тарасов, М.В. Коваленко // Строительные и дорожные машины. - 2003. - № 7. - С. 38-43.
14. Кузнецова, В.Н. Обеспечение энергоэффективности разработки грунта за счет оптимизации углов позиционирования рабочего оборудования экскаватора / В.Н. Кузнецова, В.В. Савинкин // Строительные и дорожные машины. - 2015. - № 3. - С. 44-47.
