Перейти к основному содержанию
ИТарктика
УДК 004.056
Ланских Владимир Георгиевич, Гагаринов Станислав Михайлович, Шмакова Наталья Александровна, Родионов Кирилл Владиславович
к.т.н., доцент кафедры систем автоматизации управления,
Федеральное государственное бюджетное образовательное учреждение высшего образования «Вятский государственный университет»

магистрант кафедры систем автоматизации управления,
Федеральное государственное бюджетное образовательное учреждение высшего образования «Вятский государственный университет»

старший преподаватель кафедры систем автоматизации управления,
Федеральное государственное бюджетное образовательное учреждение высшего образования «Вятский государственный университет»

старший преподаватель кафедры систем автоматизации управления,
Федеральное государственное бюджетное образовательное учреждение высшего образования «Вятский государственный университет»
Исследование зависимости криптографических свойств генераторов псевдослучайных чисел на основе однородных клеточных автоматов от функции связи автомата
Аннотация:

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

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

Общая характеристика задачи и её актуальность

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

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

Можно выделить следующие проблемы, которые могут возникнуть при работе с цифровой информацией[5]:

  1. перехват информации – информация остается неизменной, но конфиденциальность её будет нарушена;
  2. модификация информации – исходная информация становится частично или полностью измененной;
  3. подмена авторства информации – подменяется отправитель информации;
  4. уничтожение информации – уничтожение исходной информации без возможности её восстановления.

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

Наиболее часто используемыми методами являются[5]:

  1. управление доступом – метод защиты информации, основанный на регулировании использования всех ресурсов системы, включает в себя:
  • идентификация ресурсов системы;
  • аутентификация (установление подлинности) объектов и субъектов системы;
  • проверка прав доступа и возможностей;
  • регистрация обращений к защищенным ресурсам;
  • пресечение попыток несанкционированного доступа;
  1. препятствование – метод физической защиты ресурсов системы;
  2. маскировка – метод защиты информации путём её преобразования в нечитаемый для нарушителя вид (криптографическое преобразование);
  3. регламентация – метод защиты, основанный на создании таких условий автоматизированной обработки, хранения и передачи информации, при котором снижается вероятность несанкционированного доступа;
  4. принуждение – соблюдение регламента пользователями и персоналом под угрозой личной ответственности (например: договор о неразглашении);
  5. побуждение – метод, мотивирующий пользователей и персонал соблюдать морально-этические нормы.

Эти методы позволяют максимально защитить информацию от несанкционированного доступа. К основным средствам защиты относят:

  1. физические;
  2. технические (программные и аппаратные);
  3. организационные;
  4. законодательные;
  5. психологические.

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

  1. защищенность автоматизированной обработки;
  2. защита при передаче данных;
  3. обеспечение конфиденциальности информации;
  4. сохранение целостности информации;
  5. сохранение подлинности информации.

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

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

Обзор

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

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

Нужно определить разницу между “истинно” случайным числом и псевдослучайным числом. Истинно случайное число – это число, получаемое в результате какого-либо физического процесса, например: бросок кубика и выпавшее значение. Псевдослучайное число – это число, полученное в результате каких-либо вычислений. К псевдослучайным последовательностям, порождаемым генератором, предъявляют очень высокие требования. Требуется исключить возможные статистические отклонения от эталона: вероятности порождения нуля и единицы должны быть в точности равны 1/2 и генерируемые числа должны быть независимы. Для проверки этих условий используют специальные тесты.

Большинство ГПСЧ может быть реализовано как функция двух переменных F(s, i), где i — номер генерируемого случайного двоичного слова некоторой фиксированной длины, а s — параметр или секретный ключ. Псевдослучайная последовательность образуется как цепочка этих слов. Каждый ГПСЧ должен соответствовать следующим правилам:

  1. генерируемая псевдослучайная последовательность должна быть статистически неотличима от абсолютно случайной;
  2. знание какой-либо части последовательности не должно позволять предсказывать следующий бит.

Исследования способов построения качественных ГПСЧ ведутся довольно давно, поскольку даже на сегодняшний день они имеют существенные недостатки, такие как:

  1. очень короткий период – это значит, что генератор через какой-то промежуток времени начинает повторять одну и ту же последовательность чисел;
  2. наличие зависимости значений – последовательные значения имеют зависимость друг от друга;
  3. неравнозначная случайность битов – вероятность появления 1 или 0 больше или меньше 0.5;
  4. неравномерное распределение – одни из значений появляются чаще других;
  5. обратимость – вычисление предыдущих значений генератора по уже имеющимся.

Работа направлена на исследование способа построения генератора, максимально отвечающего двум главным правилам, описанным выше.

В статье рассматриваются ГПСЧ, основанные на клеточных автоматах.

Клеточный автомат (КА) – математическая модель, представляющая собой сетку произвольной размерности, каждая клетка которой в каждый момент времени может принимать одно из конечного множества состояний.

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

Однородный КА – клеточный автомат, в котором для всех ячеек одна функция связи.

Функция связи  – правило, по которому осуществляется смена значений в ячейках.

Простейший клеточный автомат представляет собой клеточный автомат, в котором состояние клетки в каждый момент времени зависит от состояний соседних с ней клеток в предыдущий момент времени.

Исследуемый[1] генератор имеет структуру, состоящую из следующих элементов (рисунок 1):

  1. два клеточных автомата;
  2. регистр сдвига с линейной обратной связью[2].

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

жю

Теоретическая постановка задачи

Как говорилось ранее, основой исследуемого генератора будет замкнутый однородный бинарный клеточный автомат.

Бинарный КА – клеточный автомат, ячейки которого могут находиться в состояниях 1 и 0.

Замкнутый КА – клеточный автомат, в котором граничная ячейка соединяется с противоположной граничной ячейкой.

Авторы [11] рассматривают четыре основных класса клеточных автоматов, приводя совокупность правил поведения КА, основные свойства которых и определяют характеристики классов. Это следующие классы (номера правил взяты из [7]):

  1. первый класс – вся система становится статичной (примером является правило 40);
  2. второй класс – вся система становится периодичной (пример: правила 3 и 33);
  3. третий класс – система становится хаотичной и непредсказуемой (пример: правило 22);
  4. четвертый класс – автомат порождает сложные, взаимодействующие между собой структуры. Формируются устойчивые структуры, способные выживать длительное время.

В данной работе будет использоваться третий класс КА. Небольшие изменения входных данных влекут сильное изменение поведения системы. Свойство, обеспечивающее это явление называется, называется “лавинный эффект”.

Лавинный эффект заключается в том, что изменение значения небольшого количества входных битов ведет к сильному изменению значений выходных битов.

Для того чтобы исследовать различное поведение клеточного автомата будут изменяться такие параметры как[6]:

  1. размерность решетки;
  2. функция связи;
  3. количество тактов автомата;
  4. исходное состояние автомата.

В основе генератора используется пара двумерных клеточных автоматов. В окрестность каждой клетки будут входить все ячейки, соседствующие с ней. Уменьшение данного числа ведет к снижению характеристик лавинного эффекта. Если увеличивать данное значение, то производительность КА резко снижается.

Моделирование и проектирование.

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

Для автоматизированного моделирования используются два метода:

  1. табличное моделирование в Excel;
  2. программная реализация.

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

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

Для реализации данного исследования используется предложенное выше приложение. Полученные ПСЧ проверяются статистическими тестами.

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

Реализация

Алгоритм работы клеточного автомата представлен на рисунке 2.

Для обеспечения минимально гарантированного периода выходной последовательности, в структуру генератора вводится регистр сдвига с линейными обратными связями R. Выход регистра на каждом такте работы прибавляется по модулю 2 к значению одной из ячеек клеточных автоматов.

Экранная форма прототипа программного обеспечения, которое реализует данный алгоритм с визуализацией каждого такта одного из КА, представлен на рисунке 3.

ло

Черным показаны значения ячеек, равные 1, белым – 0. Для каждой функции будет проводиться исследование со статичными параметрами. Сам же выбор функции осуществляется из заранее заданного списка. Для первоначального формирования списка функций используется работа[4].

Тестирование ГПСЧ является актуальной задачей, несмотря на значительные наработки в этой области. Пока что нет единственного «официального» набора тестов и инструментов, способных предоставить приемлемую метрику, которая позволит оценить степень случайности работы ГПСЧ[8].

Тестирование псевдослучайных последовательностей – совокупность методов определения меры близости заданной псевдослучайной последовательности к случайной.

юб

Заключение

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

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

  1. Сухинин,  Б. М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов [Электронный ресурс] / Б.М. Сухинин // Наука и образование: электронное научно–техническое издание. – 2010. – №09. – 21 с. – Режим доступа: http://technomag.edu.ru/doc/159714.html –  (Дата обращения: 24.10.2018).
  2. Песошин, В. А. Генераторы псевдослучайных последовательностей немаксимальной длины на основе регистра с внутренними сумматорами по модулю два (Часть 3) [Текст] / В. А. Песошин, В. М. Кузнецов, А. Х. Рахматуллин //  Вестник Чувашского университета. – 2017. – № 3. – С.251–261.
  3. Рябко,  Б. Я. Криптографические методы защиты информации [Текст] : учебное пособие для вузов / Б. Я. Рябко, А. Н.Фионов / – 2–е издание.  – Москва : Горячая линия. –Телеком, 2012. – 229 с.
  4. Тоффоли,  Т. Машины клеточных автоматов [Текст] / Т. Тоффоли, Н. Марголус. – Москва : Мир, 1991. – 280 с.
  5. Королёв, О. Л. Методы защиты информации [Текст] / О. Л. Королёв, Д. В. Иванюта // Актуальные проблемы и перспективы развития экономики : труды XVI Международной научно–практической конференции  (Симферополь–Гурзуф. 19–21 октября 2017 год). – Саки : ИП Бровко А.А., 2017.  – С. 192–193.
  6. Сухинин,  Б. М. О некоторых свойствах клеточных автоматов и их применении в структуре генераторов  псевдослучайных последовательностей [Текст] / Б. М.Сухинин // Вестник МГТУ им. Н.Э. Баумана. Серия: Приборостроение. – 2011. – №2. – С. 68–76.
  7. Хорев, П. Б. Программно–аппаратная защита информации [Тест] / П. Б.Хорев. Москва : ФОРУМ, 2015. – 212 с.
  8. Иванов,  М. А. Теория, применение и оценка качества генераторов псевдослучайных последовательностей [Тест]  / М. А.Иванов, И. В. Чугунков. – Москва : КУДИЦ–ОБРАЗ, 2003. – 240 с.

References

1.      Sukhinin, B. M. development of pseudorandom binary sequence generators based on cellular automata [Electronic resource] / B. M. Sukhinin / / Science and education: electronic scientific and technical publication. – 2010. – №09. – 21 p. – access Mode: http://technomag.edu.ru/doc/159714.html – (date of application: 24.10.2018).

2.      Pesoshin, V. A. generators of pseudorandom sequences of non–maximal length on the basis of register with internal summators modulo two (Part 3) [Text] / V. A. Pesoshin, V. M. Kuznetsov, A. H. Rakhmatullin // Bulletin of Chuvash University. – 2017. – № 3. – P. 251–261.

3.      Ryabko, B. Ya Cryptographic methods of information security [Text] : textbook for universities / B. Y. Ryabko, A. N. Fionov / – 2nd edition.  – Moscow: Hotline. – Telecom, 2012. – 229 p.

4.      Toffoli, T. machines of cellular automata [Text] / T. Toffoli, N. Margolus. – Moscow: Mir, 1991. – 280 p.

5.      Korolev, O. L. Methods of information security [Text] / O. L. Korolev, D. V. Ivanyuta / / Actual problems and prospects of economic development : proceedings of the XVI International scientific–practical conference (Simferopol–Gurzuf. 19–21 October 2017). – Saki: SP Brovko AA, 2017.  – Pp. 192–193.

6.      Sukhinin, B. M. on some properties of cellular automata and their application in the structure of pseudorandom sequence generators [Text] / B. M. Sukhinin // Vestnik MGTU im. N. Eh. Bauman. Series: Instrumentation. – 2011. – №2. – P. 68–76.

7.      Khorev, P. B. hardware and Software protection of information [Test] / P. B. Khorev. – Moscow : FORUM, 2015. – 212 p.

8. Ivanov, M. A. Theory, application and quality assessment of pseudorandom sequence generators [Text] / M. A. Ivanov, I. V. Chugunkov. – Moscow : KUDITS–OBRAZ, 2003. - 240 p.