Перейти к содержимому

Когда впервые были введены клеточные автоматы

  • автор:

КЛЕТОЧНЫЕ АВТОМАТЫ И ИХ ОБОБЩЕНИЯ В ЗАДАЧАХ КРИПТОГРАФИИ. ЧАСТЬ 2 Текст научной статьи по специальности «Математика»

Цель статьи: аналитический обзор применения клеточных автоматов и их обобщений в криптографии.Метод исследования: анализ научных публикаций по теме статьи.Полученные результаты: в обзорной статье проанализирована литература, посвященная использованию как классических клеточных автоматов, так и их обобщений для построения криптографических алгоритмов. Статья состоит из двух частей. Первая часть была посвящена классическим клеточным автоматам и основанным на них симметричным криптографическим алгоритмам. В ней кратко обсуждалась история развития теории клеточных автоматов и ее применения в различных научных областях. Был приведен обзор работ ряда авторов, которыми предлагались симметричные криптографические алгоритмы и генераторы псевдослучайных последовательностей, основанные на одномерных клеточных автоматах. Стойкость таких криптоалгоритмов оказалось недостаточной. Далее был дан обзор статей, посвященных использованию двухмерных клеточных автоматов для построения симметричных криптоалгоритмов (этот подход давал лучшие результаты). Также были упомянуты многомерные клеточные автоматы. Настоящая вторая часть статьи содержит обзор работ, посвященных использованию обобщенных клеточных автоматов в криптографии — на основе таких автоматов возможно создавать алгоритмы симметричного шифрования и криптографические хэш-функции , обладающие высоким уровнем криптостойкости и высокой производительностью при аппаратной реализации (например, на программируемых логических интегральных схемах), а также предъявляющие достаточно низкие требования к аппаратным ресурсам. Кроме того, уделено внимание интересным связям обобщенных клеточных автоматов , в контексте их использования в криптографии, с теорией расширяющих графов; также уделено внимание вопросам стойкости криптоалгоритмов, основанных на обобщенных клеточных автоматах . Упомянуты работы, посвященные реализации различных криптографических алгоритмов, основанных на обобщенных клеточных автоматах , на программируемых логических интегральных схемах и графических процессорах. Дан обзор асимметричных криптоалгоритмов, основанных на клеточных автоматах . Рассмотрены вопросы о принадлежности некоторых задач на клеточных автоматах и их обобщениях к классу NP-полных задач, а также к некоторым другим классам сложности.

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Ключарёв Петр Георгиевич

КЛЕТОЧНЫЕ АВТОМАТЫ И ИХ ОБОБЩЕНИЯ В ЗАДАЧАХ КРИПТОГРАФИИ. ЧАСТЬ 1

Производительность и эффективность аппаратной реализации поточных шифров, основанных на обобщенных клеточных автоматах

Исследование характеристик лавинного эффекта обобщенных клеточных автоматов на основе графов малого диаметра

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

CELLULAR AUTOMATA AND THEIR GENERALIZATIONS IN CRYPTOGRAPHY. PART 2

The purpose of the article is an analytical review of the application of cellular automata and their generalizations in cryptography.Research method: an analysis of scienti c publications on the topic of the article.Results: The review article analyzes the literature devoted to the use of cellular automata and their generalizations for the construction of cryptographic algorithms. The article consists of two parts.The rst part was devoted to classical cellular automata and symmetric cryptographic algorithms based on them. It brie y discussed the history of the theory of cellular automata and its application in various scienti c elds. A review of the works of a number of authors who proposed symmetric cryptographic algorithms and pseudorandom sequence generators based on one-dimensional cellular automata was presented. The security of such cryptographic algorithms turned out to be insuf cient. The following was a review of articles devoted to the use of two-dimensional cellular automata for constructing ciphers (this approach gave the best results). Multidimensional cellular automata were also mentioned.This second part of the article is devoted to a review of works devoted to the use of generalized cellular automata in cryptography — on the basis of such automata, it is possible to create symmetric encryption algorithms and cryptographic hash functions that provide a high level of security and high performance in hardware implementation (for example, on FPGA), as well as having fairly low requirements for hardware resources. In addition, an attention is paid to interesting connections of generalized cellular automata, in the context of their use in cryptography, with the theory of expander graphs. Attention is also paid to the security of cryptographic algorithms based on generalized cellular automata. The works devoted to the implementation of various cryptographic algorithms based on generalized cellular automata on FPGA and GPU are mentioned. In addition, an overview of asymmetric cryptoalgorithms based on cellular automata is given. The questions about the belonging of some problems on cellular automata and their generalizations to the class of NP-complete problems, as well as to some other complexity classes, are also considered.

Текст научной работы на тему «КЛЕТОЧНЫЕ АВТОМАТЫ И ИХ ОБОБЩЕНИЯ В ЗАДАЧАХ КРИПТОГРАФИИ. ЧАСТЬ 2»

I КЛЕТОЧНЫЕ АВТОМАТЫ И ИХ ОБОБЩЕНИЯ В ЗАДАЧАХ КРИПТОГРАФИИ. ЧАсТь 2

Цель статьи: аналитический обзор применения клеточных автоматов и их обобщений в криптографии.

Метод исследования: анализ научных публикаций по теме статьи.

Полученные результаты: в обзорной статье проанализирована литература, посвященная использованию как классических клеточных автоматов, так и их обобщений для построения криптографических алгоритмов. Статья состоит из двух частей. Первая часть была посвящена классическим клеточным автоматам и основанным на них симметричным криптографическим алгоритмам. В ней кратко обсуждалась история развития теории клеточных автоматов и ее применения в различных научных областях. Был приведен обзор работ ряда авторов, которыми предлагались симметричные криптографические алгоритмы и генераторы псевдослучайных последовательностей, основанные на одномерных клеточных автоматах. Стойкость таких криптоалгоритмов оказалось недостаточной. Далее был дан обзор статей, посвященных использованию двухмерных клеточных автоматов для построения симметричных криптоалгоритмов (этот подход давал лучшие результаты). Также были упомянуты многомерные клеточные автоматы. Настоящая вторая часть статьи содержит обзор работ, посвященных использованию обобщенных клеточных автоматов в криптографии — на основе таких автоматов возможно создавать алгоритмы симметричного шифрования и криптографические хэш-функции, обладающие высоким уровнем криптостойко-сти и высокой производительностью при аппаратной реализации (например, на программируемых логических интегральных схемах), а также предъявляющие достаточно низкие требования к аппаратным ресурсам. Кроме того, уделено внимание интересным связям обобщенных клеточных автоматов, в контексте их использования в криптографии, с теорией расширяющих графов; также уделено внимание вопросам стойкости криптоалгоритмов, основанных на обобщенных клеточных автоматах. Упомянуты работы, посвященные реализации различных криптографических алгоритмов, основанных на обобщенных клеточных автоматах, на программируемых логических интегральных схемах и графических процессорах. Дан обзор асимметричных криптоалгоритмов, основанных на клеточных автоматах. Рассмотрены вопросы о принадлежности некоторых задач на клеточных автоматах и их обобщениях к классу NP-полных задач, а также к некоторым другим классам сложности.

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

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

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

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

1. Обобщенные клеточные автоматы в симметричной криптографии

1.1 Основные понятия

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

1 Ключарёв Петр Георгиевич, кандидат технических наук, доцент кафедры «Информационная безопасность», МГТУ им. Н.Э. Баумана, Москва. E-mail: pk.iu8@yandex.ru

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

Итак, назовем обобщенным клеточным автоматом ориентированный граф (граф обобщенного клеточного автомата) с множеством вершин V = vN>, с каждой вершиной v¡ которого ассоциированы:

— булева переменная т1, которая называется ячейкой;

— булева функция f (х1. хЛ ), которая называется локальной функцией связи вершины v¡ ( d¡ — степень захода вершины v¡).

Опишем теперь работу обобщенного клеточного автомата. В начальный момент времени каждая ячейка т1, i = l. N, имеет некоторое начальное значение т1 (0). Автомат работает пошагово. Значения ячеек на шаге номер t вычисляются по формуле:

где пО, j) — номер вершины, из которой выходит ребро, входящее в вершину v¡ и имеющее относительно этой вершины номер у.

Очевидно, что определенный таким образом обобщенный клеточный автомат является автономным конечным автоматом.

Заполнением обобщенного клеточного автомата М(/) на шаге t будем называть набор значений ячеек (т^),тг(). тм^)).

Назовем обобщенный клеточный автомат неориентированным, если для любого ребра (и,V) в его графе существует и ребро (V,и). Граф такого автомата можно рассматривать как неориентированный, для чего достаточно заменить каждую пару ориентированных ребер (и,V) и (V,и) на неориентированное ребро .

Здесь мы будем в основном иметь дело с неориентированными однородными обобщенными клеточными автоматами. Такой автомат задается тройкой (в, \ ,ц) , где С — d-регулярный граф обобщенного клеточного автомата (множество его вершин

введенная выше функция (будем называть ее функцией нумерации ребер).

Некоторый набор ячеек обобщенного клеточного автомата будем называть выходом. Выходной последовательностью клеточного автомата А назовем функцию ГА :^ X N ^ (0,1>и, аргументами ко-

торой является начальное заполнение обобщенного клеточного автомата и номер шага, а значением -значение выхода на этом шаге (здесь m — длина выхода). Периодом клеточного автомата будем называть период последовательности его заполнений.

1.2 История развития обобщенных клеточных автоматов

Фактически, обобщения понятия клеточного автомата, подобные введенному выше, независимо предлагались разными авторами и применялись в различных областях. По-видимому, впервые подобное понятие появилось в 1969 г. в работе [1], где такие автоматы использовались в области биологии. После этого, в исследовании подобных моделей наступил перерыв, который закончился лишь после 2000 года, когда появился ряд работ, в которых их исследования продолжились. Называли такие автоматы в этих статьях по-разному, например, булевыми сетями (Boolean networks), сетями Кауфмана, графовыми клеточными автоматами и др. (отношение к таким моделям как к обобщению клеточных автоматов более характерно для российской научной школы). В работах [2, 3] рассматривались вероятностные варианты подобных моделей. Кроме того, такие модели исследовались с точки зрения теории динамических систем в работах [4-7] (в частности, изучались вопросы, связанные с числом аттракторов).

С точки зрения теории сложности булевых функций, обобщенные клеточные автоматы рассматривались в работе [8], где доказывается теорема о том, что булеву функцию ф( xv. xn), имеющую при реализации булевой схемой над базисом B сложность l и глубину h, можно вычислить с помощью обобщенного клеточного автомата, локальные функции связи которого принадлежат B, а граф имеет n +1 вершин, причем для этого требуется не более h шагов. Эта теорема, устанавливая связь между обобщенными клеточными автоматами и схемами из функциональных элементов, показывает универсальность обобщенных клеточных автоматов, как вычислительной модели. Фактически, такие автоматы можно рассматривать как вычислительную модель параллельной обработки информации.

1.3 Применение обобщенных клеточных автоматов в симметричной криптографии

Использовать обобщенные клеточные автоматы в симметричной криптографии впервые предложил Б.М. Сухинин в 2009 — 2011 гг. в работах [9,10] и др., в которых он называл аналогичную модель неоднородным клеточным автоматом (мы этот термин используем в другом значении). В его работах под этим термином понимается автономный конечный автомат, состояние которого задается совокупностью из N ячеек, значение каждой из которых обновляется на каждом шаге исходя из значений некоторой ее окрестности на предыдущем шаге с помощью булевой функции, называемой локальной функцией связи. Причем окрестность ячейки — это некоторый на-

бор ячеек, свой для каждой ячейки. Входящие в него ячейки могут быть выбраны произвольным образом из всей совокупности ячеек такого автомата так, чтобы окрестность каждой ячейки содержала одинаковое число ячеек. В диссертации [9] приведено строгое определение такого автомата. Там же на основе таких автоматов, выбранных методом рандомизированного перебора, построен генератор псевдослучайных последовательностей, в соответствии со схемой, приведенной на рис. 1 (Б.М. Сухининым было предложено два генератора на базе этой схемы: один — на основе двухмерных клеточных автоматов, а другой -на основе обобщенных клеточных автоматов). Такие генераторы показали высокую скорость работы при аппаратной реализации (на ПЛИС).

Рис. 1: Структура генератора псевдослучайных последовательностей, предложенная в работе [9]

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

— Можно ли на основе обобщенных клеточных автоматов построить не только поточные шифры, но и блочные шифры, а также криптографические хэш-функции?

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

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

В работах [8,11,12] исследованы свойства, которым должны удовлетворять граф, локальная функция

связи и функция нумерации ребер обобщенного клеточного автомата. Обосновано, что локальная функция связи должна быть равновесной, шефферовой и как можно более нелинейной, но линейно зависящей от одного из своих аргументов (напомним, что нелинейностью булевой функции называется расстояние Хем-минга от нее до множества аффинных булевых функций). Построено семейство локальных функций связи, удовлетворяющих этим требованиям. Введено понятие ¿-шаговой коллизии веса w, представляющей собой такие два различных заполнения x1,x2 g^ обобщенного клеточного автомата CA, что X © x2| = w и CA(t, xj) = CA(t, x2), но CA(t -1, x1) Ф CA(t -1, x2), где |x| — вес вектора x, CA(t,x) — заполнение на шаге t обобщенного клеточного автомата CA с начальным заполнением x. Доказано, что для обеспечения устойчивости однородных неориентированных обобщенных клеточных автоматов к одношаговым коллизиям веса 1 достаточно, чтобы локальная функция связи линейно зависела от одного из своих аргументов, а соответствующие этим аргументам ребра графа обобщенного клеточного автомата порождали 2-фактор.

В работе [13] на основе общей схемы (рис. 1), предложенной ранее в [9], построен поточный шифр, представляющий собой генератор гаммы, состоящий из двух различных неориентированных однородных обобщенных клеточных автоматов (CA1, CA2), к одной из ячеек (задающей ячейке) каждого из которых прибавляется по модулю 2 очередной разряд последовательности, порождаемой линейным регистром сдвига с обратной связью. При этом, в качестве графов этих автоматов взяты графы Рамануджана, в качестве локальных функций связи — различные функции из специально построенного семейства, а задающая ячейка выбрана из ряда теоретических соображений. На каждом шаге с каждого автомата снимаются значения определенного набора ячеек, и поразрядная сумма по модулю 2 полученных двух наборов значений подается на выход генератора гаммы. Начальным заполнением каждого обобщенного клеточного автомата является ключ key, конкатенированный с некоторой константой, дополняющей его до размера автомата. На основе ключа также вырабатывается начальное заполнение линейного регистра сдвига с обратной связью.

Обозначим заполнение обобщенного клеточного автомата CA с задающей ячейкой на шаге t, как CA(t, М, где M0 — начальное заполнение, а £ — подаваемая на задающую ячейку последовательность. Выход обобщенного клеточного автомата обозначим prm(CA(t, М0,£)), где m — длина выхода, а prm — функция, возвращающая некоторые m разрядов аргумента (имеющие наперед заданные номера). Последовательность £ вырабатывается линейным регистром сдвига с обратной связью, начальное заполнение которого получено на основе ключа key. Выход генератора гаммы на шаге t вычисляется по формуле:

= prm (CA (t, key || c,, 4)) © prm (C\ (t, key || c2, £)),

где с и с2 — константы, дополняющие ключ до размера обобщенного клеточного автомата, вес которых должен быть близок к половине длины; || — операция конкатенации.

Вырабатываемая генератором гамма представляет собой конкатенацию выходов, после определенного числа (т) холостых шагов: у = у(кеу,т +1) || у

Кроме того, в работе [13] понятие пространственной характеристики лавинного эффекта обобщено на обобщенные клеточные автоматы.

набора ячеек. Автомат синтезируется исходя из ряда теоретических соображений (в частности, в качестве графа используется тот или иной граф Рамануджана, а о выборе локальной функции связи сказано выше). На базе таких псевдослучайных функций-кандидатов предложено семейство блочных шифров [15]. Такие шифры (рис. 2) используют схему Фейстеля с небольшим числом раундов. В качестве раундовой функции используется псевдослучайная функция-кандидат. При этом, она используется, в том числе, и для смешивания подблока с ключом, что существенно затрудняет применение разностного криптоанализа к таким шифрам.

В работе [16] предложено использовать в аналогичных блочных шифрах вместо классической схемы Фейстеля обобщенную (в которой блок разделяется больше, чем на две части). В этом случае, можно использовать обобщенный клеточный автомат с меньшим числом ячеек, что приводит к меньшему объему вычислений на каждом шаге. Вместе с тем это, по-видимому, приведет к необходимости в увеличении числа раундов, так что влияние применения обобщенной схемы Фейстеля на быстродействие является спорным и требующим дополнительных исследований.

Кроме того, на обобщенных клеточных автоматах основаны два семейства криптографических хэш-функций: на основе древовидной схемы [17] и на основе конструкции, похожей на криптографическую губку [18], а также семейство алгоритмов выработки имитовставок [19].

1.4 Обобщенные клеточные автоматы и расширяющие графы

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

Напомним, что коэффициентом реберного расширения неориентированного ((-регулярного графа С с множеством вершин V называется величина

где | dS | — число ребер, каждое

Рис. 2: Общая схема алгоритма блочного шифрования, основанного на обобщенных клеточных автоматах

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

из которых соединяет вершину из множества S c вершиной из множества V\ S . Расширяющим графом (expander graph) называется неориентированный регулярный граф G, для которого h(G) > c , где c — некоторая наперед заданная положительная константа. Коэффициент реберного расширения неориентированного графа связан с его спектром (т.е. набором собственных значений его матрицы смежности, отсортирован-

ным по невозрастанию: к

что для ((-регулярных графов ^ = Ь и справедливо следующее соотношение (неравенство Чигера):

Для диаметра расширяющего графа имеет место неравенство: ^N -1)|. Оно является одним из аргументов в пользу того, что в качестве графов неориентированных обобщенных клеточных автоматов хорошо подходят графы с маленьким значением параметра Х2 (этот вопрос рассматривается, в частности, в работе [21]). Такими графами являются графы Рамануджана (т.е. связные ^регулярные графы, для_которых выполняется неравенство

В работе [22] изучантсн рандомизированный метод построения графов чамануджана, подходыцих для обобщенных клеточныи;ивтс^1\Лсаиои. А ез работе [21] изучаются графы рамануджана, которые строятся с помощью детерминированных методов. В нейс целью выбора графов, подходящих для построени я обобщенных клеточныхавтоаатов, рассмотрены четыре семейства графов Рамрауежанр: самейстра X и Y Любоцкого-ФилипсаиСарнака, сомоктвх Пайрера и семейство МоргенштернО1 Из них дрр об^неН^итжн нь>|у клеточных автоматов поджодит семевсдво ираОав По и-зера [23-25] (их также называют графамт очагонпИ суперсингулярных эллиптические коив ых [26,27]) с семейство Y графов Любоцкога-Флкапои-Оааннав (LPS-Y) [28].

Графы Пайзера устроены елдджющим обаоюом. Множеством вершин графе яаляетит 1П1но>дуктио чаив-сов изоморфизма зтджп-ических

кривых над полем Е к .Джс вершины гдхфо Нужник соединены ребром тогво и аптаид адгва.мачда мождн представителями соотвенжтвдющих гд классдн ризою 1). Такой граф являетяа к,^.иочтенипц,lVl + 1)-рдру-лярным графом Рамантджпюо. Интвристд, оти фафы изогений суперсингулиржмх эиннптиодских прс^ь^1н находят применение в теаюовантсвой удтптофафжи п на них основан постквантовыю о|сдтоксэ/г Ечь^р>^ботгки

общего ключа SIDH [29] и базирующийся на нем протокол Форзиция [30].

Графы LPS-Y строятся следующим образом. Выбираются простые числа р и д, для которых выполняет-

: p = 1 (mod4); q = 1 (mod4); p Ф q;

символ Лежандра. Множеством V вершин

этого графа является проективная прямая над конечным полем , т.е., V = и . Каждая вершина и е V соединена ребром с вершиной с, такой что:

(a0 + ia1 )u + (a2 + ia3)

если (a2 — i’a3)u Ф—ас-1а^) и иф u, oo, если (ас -iaa)u = (a — -Ц) и аф o-0,

, еали аз ф а2 и u = оо,

исаи Мс = а2 и и = и,

для каждой четверки (a,aj,a2, a)G Z4, такой, что а — нечетное положительное, а^ам — четные и выполняется равенство: a0 + al + a22 + a32 = p . Здесь

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

i eF такое, что i2 +1 = 0 . Такие графы являются (p+1)-регулярнымиграфамиРамануджана[28].

1.5Окриптоанализесимметричных криптографическихалгоритмов,основанных на обобщенныхклеточныхавтоматах

Различные аспекты стойкости криптографических алгоритмов, основанных на обобщенных клеточных автоматах, исследуются в ряде работ. Так, в работе [31] получены условия стойкости рассматриваемых алгоритмов блочного шифрования по отношению к линейному криптоанализу. Соображения, связанные с квантовым криптоанализом рассматриваемых криптоалгоритмов, приведены в работе [32]. В ряде работ приведены экспериментальные исследования криптостойкости основанных на обобщенных клеточных автоматах криптоалгоритмов по отношению к различным методам криптоанализа. В частности, в работе [33] приведены результаты экспериментов, связанных с алгебраическим криптоанализом. Решается система полиномиальных уравнений, описывающая преобразование, выполняемое обобщенным клеточным автоматом, посредством построения базиса Гребнера, для чего используется алгоритм Фужера F4, реализованный в библиотеке Polybori и в системе компьютерной алгебры Magma. Оказывается, что при правильном выборе параметров обобщенного клеточного автомата, такую систему можно решить лишь

для совсем маленьких автоматов, состоящих из не более чем двух десятков ячеек (на практике используются обобщенные клеточные автоматы из сотен, а то и тысяч ячеек). В работе [34] эмпирически исследуется применимость логического метода криптоанализа к обобщенным клеточным автоматам — строится конъюнктивная нормальная форма, описывающая преобразование, выполняемое обобщенным клеточным автоматом, и производится решение задачи КНФ-выполнимости посредством SAT-решателей. Снова оказалось, что при правильно выбранных параметрах, на практике можно решить эту задачу лишь для очень маленьких обобщенных клеточных автоматов, причем за время существенно (на несколько порядков) большее, чем полный перебор.

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

1.6 О реализации симметричных криптографических алгоритмов, основанных на обобщенных клеточных автоматах, для различных платформ

Производительности и эффективности реализации рассматриваемых криптоалгоритмов на программируемых логических интегральных схемах (ПЛИС) посвящены работы [35,36], согласно которым такие криптографические алгоритмы являются очень эффективными при аппаратной реализации. Так, производительность поточного шифра, основанного на обобщенных клеточных автоматах, при определенных параметрах, на ПЛИС Altera Stratix V, превышает 1100 Гбит/с, что в десятки раз выше производительности традиционных поточных шифров, ориентированных на аппаратную реализацию (таких, как Trivium [37]). Кроме того, такие шифры могут быть реализованы на системах с ограниченными ресурсами (от 1 тыс. LE).

Криптографические алгоритмы, основанные на обобщенных клеточных автоматах, рассчитаны, в первую очередь, на аппаратную реализацию. В то же время, при программной реализации на обычных CPU их производительность невелика. Заметим, что это является не недостатком таких криптоалгоритмов, а особенностью их сферы применимости. Вместе с тем, тот факт, что обобщенный клеточный автомат состоит из набора ячеек, над которыми производятся однотипные вычисления, позволяет добиться эффективной реализации на современных графических процессорах. Реализации криптографических алгоритмов, основанных на обобщенных клеточных автоматах, для графических процессоров посвящены работы [38-40]. В них достигнута производительность в сотни Мбит/с. Учитывая, что графические процессоры присутствуют в большинстве современных персональных компьютеров, а также в смартфонах, планшетах и др., этот факт существенно расширяет область применимости таких шифров.

2. Асимметричные криптосистемы на основе клеточных автоматов

В настоящее время асимметричная криптография (криптография с открытым ключом) переживает своеобразный кризис — наиболее часто используемые асимметричные криптографические алгоритмы и протоколы, основанные на высокой вычислительной сложности задач факторизации целых чисел или дискретного логарифмирования (в частности, алгоритмы RSA и Эль-Гамаля, протокол Диффи-Хеллмана и др.), окажутся нестойкими в случае появления практических образцов квантовых компьютеров, на которых эти задачи решаются за полиномиальное время с помощью квантовых алгоритмов Шора. Поэтому сейчас развивается постквантовая криптография — дисциплина, изучающая асимметричные криптографические алгоритмы, для которых неизвестны эффективные, работающие на квантовом компьютере, методы криптоанализа.

На основе клеточных автоматов наиболее известны две довольно похожие асимметричные криптосистемы: криптосистема Дж. Кари и криптосистема П. Гуаня. Обе они основаны на идее построения конечно-автоматной асимметричной криптосистемы FAPKC (Finite Automaton Public Key Cryptosystems). Эта криптосистема была предложена в работе [41], ей также посвящена работа [42]. В криптосистеме FAPKC закрытый ключ состоит из двух обратимых конечных автоматов, а открытый ключ представляет собой их композицию, которую, вообще говоря, сложно обратить. Было предложено достаточно много вариантов этой криптостисте-мы. Некоторые из них были взломаны (см., например, работы [43,44]), однако каких-либо фундаментальных уязвимостей этого подхода неизвестно.

Криптосистема, предложенная Дж. Кари в работе [45], основана на доказанной им теореме о том, что задача определения обратимости двухмерного клеточного автомата с бесконечным множеством ячеек является алгоритмически неразрешимой. В этой криптосистеме берется конечная последовательность заведомо обратимых клеточных автоматов специального вида (так называемых маркеров) C1 . Cn, клеточные автоматы, обратные к которым, известны. Если эта последовательность известна, то по ней можно вычислить как композицию этих клеточных автоматов:

с = Cn о Cn_1 о . о Ç, (4)

так и клеточный автомат, обратный к ней:

с-1 = сг1 о с- о . о с;1, (5)

Однако если эта последовательность неизвестна, а известен только клеточный автомат C, то задача его обращения, по-видимому, является вычислительно сложной.

В этой криптосистеме закрытым ключом является последовательность клеточных автоматов специального вида C1 . Cn, а открытым ключом — их композиция C. Шифрование осуществляется следующим образом: сообщение размещается в ячейках клеточного

автомата С, осуществляется некоторое фиксированное число шагов этого автомата, после чего состояние клеточного автомата С трактуется как шифртекст. Расшифрование осуществляется аналогично — с помощью клеточного автомата СС1, который вычисляется по закрытому ключу. При этом клеточные автоматы должны быть к-мерными, где к^2 .

Безопасность этой криптосистемы рассматривается, в частности, в статье [46] и в диссертации [47].

Более ранняя криптосистема, предложенная П. Гу-анем в работе [48], тоже основана на трудности обращения клеточного автомата. Закрытым ключом в ней являются два легко обратимых клеточных автомата, а открытым ключом — их композиция. В остальном данная криптосистема аналогична криптосистеме Кари. На подобном принципе (композиции легко обратимых клеточных автоматов) построена и менее известная криптосистема, предложенная в работе [49].

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

3. Клеточные автоматы и теория сложности алгоритмов

Вопросы, связанные с вычислительной сложностью некоторых задач на клеточных автоматах, очень важны для обоснования стойкости основанных на них криптоалгоритмов. В частности, с этой точки зрения интересны результаты о ИР-полноте. Класс ИР-полных задач занимает важнейшее место в теории алгоритмов [52]. Принадлежность распознавательного аналога задачи к классу ИР-полных задач говорит о ее высокой вычислительной сложности (в естественном и широко принятом предположении, что Р Ф №). Также могут быть интересны результаты о принадлежности некоторых задач к другим классам сложности. Поэтому в данном разделе мы упомянем некоторые основные результаты по ИР-полноте некоторых задач на клеточных автоматах.

В работе [53] доказывается, что задача определения того, существует ли заполнение данного клеточного автомата, приводящее через t шагов к заполнению, содержащему данную подстроку длины t, является ИР-полной. Там же доказывается, что задача о том, чтобы определить, существует ли для данного клеточного автомата заполнение, содержащее данную подстроку э длины ^ переходящее за t шагов в заполнение, содержащее ту же подстроку, также является ИР-полной.

В работе [54] исследовались сложность некоторых задач на так называемых аддитивных автоматах на графах, представляющих собой, по существу, обобщенные клеточные автоматы, ячейки которых явля-

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

В работе [55] рассматривается задача определения по данному клеточному автомату и данной паре заполнений (X,У), существует ли такое натуральное число t, что автомат перейдет из заполнения X в заполнение У за / шагов. Причем рассматривается она для класса предсказуемых в слабом смысле ^еак1у-р^юШе) клеточных автоматов, т.е. таких, что состояние клеточного автомата через / шагов вычисляется за время О N), где N — число

ячеек, а к — некоторая константа. Оказалось, что эта задача принадлежит классу соАМ для двух подклассов предсказуемых в слабом смысле клеточных автоматов: являющихся инвертируемыми и являющихся аддитивными. Напомним здесь, что класс АМ — это класс задач распознавания, которые могут быть решены за полиномиальное время с помощью протокола Артур-Мерлин с двумя сообщениями. Класс соАМ — это дополнение к классу АМ.

Перейдем теперь к результату [56], интересному в контексте обоснования стойкости криптоалгоритмов, основанных на обобщенных клеточных автоматах, связанному с исследованием вычислительной сложности задачи о восстановлении предыдущего состояния такого автомата. Пусть дан обобщенный клеточный автомат и его заполнение после первого шага М(1). Назовем задачей о восстановлении предыдущего состояния обобщенного клеточного автомата задачу нахождения такого его начального заполнения М(0), которое после первого шага перейдет в заполнение М(1). Сформулируем теперь эту задачу в форме распознавания. Назовем задачей о существовании предыдущего состояния обобщенного клеточного автомата следующую задачу. Дан обобщенный клеточный автомат и его заполнение после первого шага М(1). Распознать, существует ли его начальное заполнение М(0), которое после первого шага перейдет в заполнение М(1).

В работе [56] доказана теорема о том, что задача о существовании предыдущего состояния однородного обобщенного клеточного автомата является ИР-полной. Соответственно, задача восстановления этого состояния является ИР-трудной. При этом, ИР-трудность этой задачи сохраняется, если рассматривать все обобщенные клеточные автоматы, отличные от классических. Этот результат достаточно важен для задачи обоснования стойкости криптографических алгоритмов, основанных на обобщенных клеточных автоматах.

Итак, использование клеточных автоматов в качестве основы для криптографических алгоритмов выглядит весьма перспективным. Хотя одномерные клеточные автоматы, по-видимому, не позволяют обе-

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

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

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 20-17-50258. Литература

1. Kauffman S. A. Metabolic stability and epigenesis in randomly constructed genetic nets // Journal of theoretical biology. — 1969. — Vol. 22, No. 3. — P. 437-467.

2. Aldana M., Coppersmith S., Kadanoff L. P. Boolean dynamics with random couplings // Perspectives and Problems in Nolinear Science. — Springer, 2003. — P. 23-89.

3. Gershenson C. Introduction to random boolean networks // arXiv preprint nlin/0408006. — 2004.

4. Bilke S., Sjunnesson F. Stability of the Kauffman model // Physical Review E. — 2001. — Vol. 65, No. 1. — P. 016129.

5. Socolar J. E., Kauffman S. A. Scaling in ordered and critical random boolean networks // Physical review letters. — 2003. — Vol. 90, No. 6. — P. 068702-1-068702-4.

6. Samuelsson B., Troein C. Superpolynomial growth in the number of attractors in Kauffman networks // Physical Review Letters. -2003. — Vol. 90, No. 9. — P. 098701.

7. Mihaljev T., Drossel B. Scaling in a general class of critical random boolean networks // Physical Review E. — 2006. — Vol. 74, No. 4. -P. 046101.

8. Ключарёв П. Г. Обеспечение криптографических свойств обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2012. — № 3. — Режим доступа: http://technomag.edu.ru/doc/358973.html.

9. Сухинин Б. М. Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей на основе клеточных автоматов: Дис. канд. техн. наук: 05.13.17 / Борис Михайлович Сухинин; МГТУ им. Н.Э. Баумана. — М., 2011. — 224 с.

10. Сухинин Б. М. Применение классических и неоднородных клеточных автоматов при построении высокоскоростных генераторов псевдослучайных последовательностей // Проектирование и технология электронных средств. — 2009. — № 3. — С. 47-51.

11. Ключарёв П. Г. О периоде обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. -2012. — № 2. — Режим доступа: http://technomag.edu.ru/doc/340943.html.

12. Ключарёв П. Г. Об устойчивости обобщенных клеточных автоматов к некоторым типам коллизий // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2014. — № 9. — С. 194-202. — Режим доступа: http://technomag.edu.ru/doc/727086.html.

13. Ключарёв П. Г. Клеточные автоматы, основанные на графах Рамануджана, в задачах генерации псевдослучайных последовательностей // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2011. — № 10. — Режим доступа: http://www. technomag.edu.ru/doc/241308.html.

14. Ключарёв П. Г. Построение псевдослучайных функций на основе обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2012. — № 10. — С. 263-274.

15. Ключарёв П. Г. Блочные шифры, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2012. — № 12. — С. 361-374. — Режим доступа: http://engineering-science.ru/doc/517543.html.

16. Жуков А. Е. Клеточные автоматы в криптографии. Часть 2 // Вопросы кибербезопасности. — 2017. — № 4(22). — С. 47-66. D0I:10.21681/2311-3456-2017-4-47-66

17. Ключарёв П. Г. Криптографические хэш-функции, основанные на обобщённых клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2013. — № 1. — С. 161-172.

18. Ключарёв П. Г. Метод построения криптографических хэш-функций на основе итераций обобщенного клеточного автомата // Вопросы кибербезопасности. — 2017. — № 1(19). — С. 45-50. DOI: 10.21681/2311-3456-2017-1-45-50

19. Ключарёв П. Г. Построение алгоритмов выработки имитовставок на основе обобщённых клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2016. — № 11. — С. 142-152. — Режим доступа: http://engineering-science.ru/ doc/849590.html.

20. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bulletin of the American Mathematical Society. — 2006. -Vol. 43, No. 4. — P. 439-562.

21. 21. Ключарёв П. Г. Детерминированные методы построения графов Рамануджана, предназначенных для применения в криптографических алгоритмах, основанных на обобщённых клеточных автоматах // Прикладная дискретная математика. — 2018. — № 42. — С. 76-93.

22. Ключарёв П. Г. Построение случайных графов, предназначенных для применения в криптографических алгоритмах, основанных на обобщенных клеточных автоматах // Математика и математическое моделирование. — 2017. — № 3. — С. 77-90. — Режим доступа: https://www.mathmelpub.ru/jour/article/view/76.

23. Pizer A. K. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Vol. 23, No. 1. — P. 127-137.

24. Charles D., Lauter K., Goren E. Cryptographic hash functions from expander graphs // J. Cryptology. — 2009. — Vol. 22, No. 1. — P. 93-113.

25. Petit C. On Graph-Based Cryptographic Hash Functions: Ph. D. thesis / C. Petit ; Catholic University of Louvain. — 2009. — 286 p.

26. Ramanujan graphs in cryptography / Anamaria Costache, Brooke Feigon, Kristin Lauter et al. // Research Directions in Number Theory. — Springer, 2019. — P. 1-40.

27. Adj G., Ahmadi O., Menezes A. On isogeny graphs of supersingular elliptic curves over finite fields // Finite Fields and Their Applications. -2019. — Vol. 55. — P. 268-283.

28. Sarnak P. Some applications of modular forms. — Cambridge University Press, 1990. — Vol. 99. — 111 p.

29. De Feo L., Jao D., Plut J. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies // Journal of Mathematical Cryptology. — 2014. — Vol. 8, No. 3. — P. 209-247.

30. Постквантовый криптографический протокол выработки общего ключа, основанный на изогениях суперсингулярных эллиптических кривых / С. В. Гребнев, П. Г. Ключарёв, А. М. Коренева и др. // Безопасные информационные технологии. Сборник трудов XI международной научно-технической конференции. — М.: МГТУ им. Н.Э. Баумана, 2021. — С. 99-103.

31. Ключарёв П. Г. Исследование стойкости блочных шифров, основанных на обобщенных клеточных автоматах, к линейному криптоанализу // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2013. — № 5. — С. 235-246. — Режим доступа: http:// engineering-science.ru/doc/574231.html.

32. Ключарёв П. Г. Квантовые вычисления и атаки на криптоалгоритмы, основанные на обобщенных клеточных автоматах // Безопасные информационные технологии. Сборник трудов Восьмой всероссийской научно-технической конференции. — М.: МГТУ им. Н.Э. Баумана, 2017. — С. 234-236.

33. Ключарёв П. Г. Исследование практической возможности решения связанных с криптоанализом задач на обобщенных клеточных автоматах алгебраическими методами // Математика и математическое моделирование. — 2017. — № 5. — С. 29-44.

34. Ключарёв П. Г. Исследование практической возможности решения одной задачи на обобщенных клеточных автоматах с использованием SAT-решателей // Машиностроение и компьютерные технологии. — 2018. — № 11. — С. 11-22. — Режим доступа: https://www.elibrary.ru/item.asp?id=37315433.

35. Ключарёв П. Г. Производительность и эффективность аппаратной реализации поточных шифров, основанных на обобщенных клеточных автоматах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2013. — № 10. — С. 299-314. — Режим доступа: http://engineering-science.ru/doc/624722.html.

36. Ключарёв П. Г. Реализация криптографических хэш-функций, основанных на обобщенных клеточных автоматах, на базе ПЛИС: производительность и эффективность // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2014. — № 1. — С. 214-223. — Режим доступа: http://engineering-science.ru/doc/675812.html.

37. De Canniere C. Trivium: A stream cipher construction inspired by block cipher design principles // Information Security. — Springer, 2006. — P. 171-186.

38. Ключарёв П. Г. Производительность поточных шифров, основанных на клеточных автоматах, при реализации на графических процессорах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2016. — № 6. — С. 200-213. — Режим доступа: http:// engineering-science.ru/doc/842091.html.

39. Ключарёв П. Г. Производительность древовидных криптографических хэш-функций, основанных на клеточных автоматах, при их реализации на графических процессорах // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2016. — № 10. — С. 132-142. — Режим доступа: http://engineering-science.ru/doc/847891.html.

40. Ключарёв П. Г. О производительности блочных шифров, основанных на клеточных автоматах, при их реализации на графических процессорах // Радиооптика. — 2016. — № 6. — С. 24-34.

41. Shihua T. R. C. A finite automaton public key cryptosystem and digital signatures [j] // Chinese Journal of Computers. — 1985. — Vol. 6.

42. Агибалов Г. Конечные автоматы в криптографии // Прикладная дискретная математика. — 2009. — № Приложение к №2. — С. 43-73.

43. Bao F., Igarashi Y. Break finite automata public key cryptosystem // International Colloquium on Automata, Languages, and Programming / Springer. — 1995. — P. 147-158.

44. Dai Z. D., Ye D. F., Lam K. Y. Weak invertibility of finite automata and cryptanalysis on FAPKC // International Conference on the Theory and Application of Cryptology and Information Security / Springer. — 1998. — P. 227-241.

45. Kari J. Cryptosystems based on reversible cellular automata // Manuscript, August. — 1992.

46. Clarridge A., Salomaa K. A cryptosystem based on the composition of reversible cellular automata // International Conference on Language and Automata Theory and Applications / Springer. — 2009. — P. 314-325.

47. Santos T. Cellular automata and cryptography // Dissertao de Mestrado apresentada Faculdade de Cincias da Universidade do Porto em Cincia de Computadores. — 2014.

48. Guan P. Cellular automaton public-key cryptosystem // Complex Systems. — 1987. — Vol. 1. — P. 51-57.

49. A new public key encryption scheme based on layered cellular automata / Xing Zhang, Rongxing Lu, Hong Zhang, Chungen Xu // KSII Transactions on Internet and Information Systems (TIIS). — 2014. — Vol. 8, No. 10. — P. 3572-3590.

50. Чиликов А. А., Жуков А. Е., Верховский А. И. Исследование обратимых клеточных автоматов с конечной решеткой // Безопасные информационные технологии. Сборник трудов Десятой международной научно-технической конференции. — М.: МГТУ им. Н.Э. Баумана, 2019. — С. 354-360.

51. Жуков А. Е. Клеточные автоматы и запреты булевых функций // Безопасные информационные технологии. Сборник трудов XI международной научно-технической конференции. — М.: МГТУ им. Н.Э. Баумана, 2021. — С. 108-119.

52. Arora S., Barak B. Computational Complexity: A Modern Approach. — Cambridge University Press, 2009. — 594 p.

53. Green F. NP-complete problems in cellular automata // Complex Systems. — 1987. — Vol. 1, No. 3. — P. 453-474.

54. Sutner K. Additive automata on graphs // Complex Systems. — 1988. — Vol. 2, No. 6. — P. 649-661.

55. Clementi A., Impagliazzo R. The reachability problem for finite cellular automata // Information processing letters. — 1995. — Vol. 53, No. 1. — P. 27-31.

56. Ключарёв П. Г. NP-трудность задачи о восстановлении предыдущего состояния обобщенного клеточного автомата // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. — 2012. — № 1. — Режим доступа: http://technomag.edu.ru/doc/312834.html.

57. Ключарёв П.Г. Клеточные автоматы и их обобщения в задачах криптографии. Часть 1. // Вопросы кибербезопасности. 2021. № 6 (46). С. 90-101. DOI: 10.21681/2311-3456-2021-6-90-101

CELLULAR AUTOMATA AND THEIR GENERALIZATIONS

IN CRYPTOGRAPHY. PART 2.

The purpose of the article is an analytical review of the application of cellular automata and their generalizations in cryptography.

Research method: an analysis of scientific publications on the topic of the article.

Results: The review article analyzes the literature devoted to the use of cellular automata and their generalizations for the construction of cryptographic algorithms. The article consists of two parts.

The first part was devoted to classical cellular automata and symmetric cryptographic algorithms based on them. It briefly discussed the history of the theory of cellular automata and its application in various scientific fields. A review of the works of a number of authors who proposed symmetric cryptographic algorithms and pseudorandom sequence generators based on one-dimensional cellular automata was presented. The security of such cryptographic algorithms turned out to be insufficient. The following was a review of articles devoted to the use of two-dimensional cellular automata for constructing ciphers (this approach gave the best results). Multidimensional cellular automata were also mentioned.

This second part of the article is devoted to a review of works devoted to the use of generalized cellular automata in cryptography — on the basis of such automata, it is possible to create symmetric encryption algorithms and cryptographic hash functions that provide a high level of security and high performance in hardware implementation (for example, on FPGA), as well as having fairly low requirements for hardware resources. In addition, an attention is paid to interesting connections of generalized cellular automata, in the context of their use in cryptography, with the theory of expander graphs. Attention is also paid to the security of cryptographic algorithms based on generalized cellular automata. The works devoted to the implementation of various cryptographic algorithms based on generalized cellular automata on FPGA and GPU are mentioned. In addition, an overview of asymmetric cryptoalgorithms based on cellular automata is given. The questions about the belonging of some problems on cellular automata and their generalizations to the class of NP-complete problems, as well as to some other complexity classes, are also considered.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Keywords: cellular automation, generalized cellular automation, stream cipher, block cipher, hash function, Ramanujan graph, public-key cryptography

Acknowledgments: The reported study was funded by RFBR, project number 20-17-50258.

1. Kauffman S. A. Metabolic stability and epigenesis in randomly constructed genetic nets // Journal of theoretical biology. — 1969. — Vol. 22, No. 3. — P. 437-467.

2. Aldana M., Coppersmith S., Kadanoff L. P. Boolean dynamics with random couplings // Perspectives and Problems in Nolinear Science. — Springer, 2003. — P. 23-89.

3. Gershenson C. Introduction to random boolean networks // arXiv preprint nlin/0408006. — 2004.

4. Bilke S., Sjunnesson F. Stability of the Kauffman model // Physical Review E. — 2001. — Vol. 65, No. 1. — P. 016129.

5. Socolar J. E., Kauffman S. A. Scaling in ordered and critical random boolean networks // Physical review letters. — 2003. — Vol. 90, No. 6. — P. 068702-1-068702-4.

6. Samuelsson B., Troein C. Superpolynomial growth in the number of attractors in Kauffman networks // Physical Review Letters. -2003. — Vol. 90, No. 9. — P. 098701.

7. Mihaljev T., Drossel B. Scaling in a general class of critical random boolean networks // Physical Review E. — 2006. — Vol. 74, No. 4. -P. 046101.

8. Klyucharev P. G. Obespechenie kriptograficheskix svojstv obobshhyonny’x kletochny’x avtomatov // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2012. — № 3. — Rezhim dostupa: http://technomag.edu.ru/doc/358973.html.

9. Suxinin B. M. Razrabotka i issledovanie vy’sokoskorostny’x generatorov psevdosluchajny’x ravnomerno raspredelenny’x dvoichny’x posledovatel’nostej na osnove kletochny’x avtomatov: Dis. kand. texn. nauk: 05.13.17 / Boris Mixajlovich Suxinin ; MGTU im. N.E’. Baumana. — M., 2011. — 224 s.

10. Suxinin B. M. Primenenie klassicheskix i neodnorodny’x kletochny’x avtomatov pri postroenii vy’sokoskorostny’x generatorov psevdosluchajny’x posledovatel’nostej // Proektirovanie i texnologiya e’lektronny’x sredstv. — 2009. — № 3. — S. 47-51.

11. Klyucharev P. G. O periode obobshhyonny’x kletochny’x avtomatov // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. -2012. — № 2. — Rezhim dostupa: http://technomag.edu.ru/doc/340943.html.

12. Klyucharev P. G. Ob ustojchivosti obobshhenny’x kletochny’x avtomatov k nekotory’m tipam kollizij // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2014. — № 9. — S. 194-202. — Rezhim dostupa: http://technomag.edu.ru/doc/727086.html.

2 Petr G. Klyucharev, Ph.D., associate professor of Information Security department, Bauman Moscow State Technical University, Moscow, Russia. E-mail: pk.iu8@yandex.ru

13. Klyucharev P. G. Kletochny’e avtomaty’, osnovanny’e na grafax Ramanudzhana, v zadachax generacii psevdosluchajny’x posledovatel’nostej // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2011. — № 10. — Rezhim dostupa: http:// www.technomag.edu.ru/doc/241308.html.

14. Klyucharev P. G. Postroenie psevdosluchajny’x funkcij na osnove obobshhyonny’x kletochny’x avtomatov // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2012. — № 10. — S. 263-274.

15. Klyucharev P. G. Blochny’e shifry’, osnovanny’e na obobshhyonny’x kletochny’x avtomatax // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2012. — № 12. — S. 361-374. — Rezhim dostupa: http://engineering-science.ru/doc/517543.html.

16. Zhukov A. E. Kletochny’e avtomaty’ v kriptografii. chast’ 2 // Voprosy’ kiberbezopasnosti. — 2017. — № 4(22). — S. 47-66.

17. Klyucharev P. G. Kriptograficheskie xe’sh-funkcii, osnovanny’e na obobshhyonny’x kletochny’x avtomatax // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2013. — № 1. — S. 161-172.

18. Klyucharev P. G. Metod postroeniya kriptograficheskix xe’sh-funkcij na osnove iteracij obobshhennogo kletochnogo avtomata // Voprosy’ kiberbezopasnosti. — 2017. — № 1(19). — S. 45-50.

19. Klyucharev P. G. Postroenie algoritmov vy’rabotki imitovstavok na osnove obobshhyonny’x kletochny’x avtomatov // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2016. — № 11. — S. 142-152. — Rezhim dostupa: http://engineering-science.ru/doc/849590.html.

20. Hoory S., Linial N., Wigderson A. Expander graphs and their applications // Bulletin of the American Mathematical Society. — 2006. -Vol. 43, No. 4. — P. 439-562.

21. Klyucharev P. G. Determinirovanny’e metody’ postroeniya grafov Ramanudzhana, prednaznachenny’x dlya primeneniya v kriptograficheskix algoritmax, osnovanny’x na obobshhyonny’x kletochny’x avtomatax // Prikladnaya diskretnaya matematika. —

2018. — № 42. — S. 76-93.

22. Klyucharev P. G. Postroenie sluchajny’x grafov, prednaznachenny’x dlya primeneniya v kriptograficheskix algoritmax, osnovanny’x na obobshhenny’x kletochny’x avtomatax // Matematika i matematicheskoe modelirovanie. — 2017. — No 3. — S. 77-90. — Rezhim dostupa: https://www.mathmelpub.ru/jour/article/view/76.

23. Pizer A. K. Ramanujan graphs and Hecke operators // Bulletin of the American Mathematical Society. — 1990. — Vol. 23, No. 1. — P. 127-137.

24. Charles D., Lauter K., Goren E. Cryptographic hash functions from expander graphs // J. Cryptology. — 2009. — Vol. 22, No. 1. — P. 93-113.

25. Petit C. On Graph-Based Cryptographic Hash Functions: Ph. D. thesis / C. Petit ; Catholic University of Louvain. — 2009. — 286 p.

26. Ramanujan graphs in cryptography / Anamaria Costache, Brooke Feigon, Kristin Lauter et al. // Research Directions in Number Theory. — Springer, 2019. — P. 1-40.

27. Adj G., Ahmadi O., Menezes A. On isogeny graphs of supersingular elliptic curves over finite fields // Finite Fields and Their Applications. —

2019. — Vol. 55. — P. 268-283.

28. Sarnak P. Some applications of modular forms. — Cambridge University Press, 1990. — Vol. 99. — 111 p.

29. De Feo L., Jao D., Plut J. Towards quantum-resistant cryptosystems from supersingular elliptic curve isogenies // Journal of Mathematical Cryptology. — 2014. — Vol. 8, No. 3. — P. 209-247.

30. Postkvantovy’j kriptograficheskij protokol vy’rabotki obshhego klyucha, osnovanny’j na izogeniyax supersingulyarny’x e’llipticheskix krivy’x / S. V. Grebnev, P. G. Klyucharev, A. M. Koreneva i dr.// Bezopasny’e informacionny’e texnologii. Sbornik trudov XI mezhdunarodnoj nauchno-texnicheskoj konferencii. — M.: MGTU im. N.E’. Baumana, 2021. — S. 99-103.

31. Klyucharev P. G. Issledovanie stojkosti blochny’x shifrov, osnovanny’x na obobshhenny’x kletochny’x avtomatax, k linejnomu kriptoanalizu // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2013. — No 5. — S. 235-246. — Rezhim dostupa: http://engineering-science.ru/doc/574231.html.

32. Klyucharev P. G. Kvantovy’e vy’chisleniya i ataki na kriptoalgoritmy’, osnovanny’e na obobshhenny’x kletochny’x avtomatax // Bezopasny’e informacionny’e texnologii. Sbornik trudov Vos’moj vserossijskoj nauchno-texnicheskoj konferencii. — M.: MGTU im. N.E’. Baumana, 2017. — S. 234-236.

33. Klyucharev P. G. Issledovanie prakticheskoj vozmozhnosti resheniya svyazanny’x s kriptoanalizom zadach na obobshhenny’x kletochny’x avtomatax algebraicheskimi metodami // Matematika i matematicheskoe modelirovanie. — 2017. — No 5. — S. 29-44.

34. Klyucharev P. G. Issledovanie prakticheskoj vozmozhnosti resheniya odnoj zadachi na obobshhenny’x kletochny’x avtomatax s ispol’zovaniem SAT-reshatelej // Mashinostroenie i komp’yuterny’e texnologii. — 2018. — № 11. — S. 11-22. — Rezhim dostupa: https:// www.elibrary.ru/item.asp?id=37315433.

35. Klyucharev P. G. Proizvoditel’nost’ i e’ffektivnost’ apparatnoj realizacii potochny’x shifrov, osnovanny’x na obobshhenny’x kletochny’x avtomatax // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2013. — No 10. — S. 299-314. — Rezhim dostupa: http://engineering-science.ru/doc/624722.html.

36. Klyucharev P. G. Realizaciya kriptograficheskix xe’sh-funkcij, osnovanny’x na obobshhenny’x kletochny’x avtomatax, na baze PLIS: proizvoditel’nost’ i e’ffektivnost’ // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2014. — No 1. — S. 214-223. -Rezhim dostupa: http://engineering-science.ru/doc/675812.html.

37. De Canniere C. Trivium: A stream cipher construction inspired by block cipher design principles // Information Security. — Springer, 2006. — P. 171-186.

38. Klyucharev P. G. Proizvoditel’nost’ potochny’x shifrov, osnovanny’x na kletochny’x avtomatax, pri realizacii na graficheskix processorax // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2016. — No 6. — S. 200-213. — Rezhim dostupa: http://engineering-science.ru/doc/842091.html.

39. Klyucharev P. G. Proizvoditel’nost’ drevovidny’x kriptograficheskix xe’sh-funkcij, osnovanny’x na kletochny’x avtomatax, pri ix realizacii na graficheskix processorax // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2016. — No 10. — S. 132-142. -Rezhim dostupa: http://engineering-science.ru/doc/847891.html.

40. Klyucharev P. G. O proizvoditel’nosti blochny’x shifrov, osnovanny’x na kletochny’x avtomatax, pri ix realizacii na graficheskix processorax // Radiooptika. — 2016. — No 6. — S. 24-34.

41. Shihua T. R. C. A finite automaton public key cryptosystem and digital signatures [j] // Chinese Journal of Computers. — 1985. — Vol. 6.

42. Agibalov G. Konechny’e avtomaty’ v kriptografii // Prikladnaya diskretnaya matematika. — 2009. — № Prilozhenie k No 2. — S. 43-73.

43. Bao F., Igarashi Y. Break finite automata public key cryptosystem // International Colloquium on Automata, Languages, and Programming / Springer. — 1995. — P. 147-158.

44. Dai Z. D., Ye D. F., Lam K. Y. Weak invertibility of finite automata and cryptanalysis on FAPKC // International Conference on the Theory and Application of Cryptology and Information Security / Springer. — 1998. — P. 227-241.

45. Kari J. Cryptosystems based on reversible cellular automata // Manuscript, August. — 1992.

46. Clarridge A., Salomaa K. A cryptosystem based on the composition of reversible cellular automata // International Conference on Language and Automata Theory and Applications / Springer. — 2009. — P. 314-325.

47. Santos T. Cellular automata and cryptography // Dissertao de Mestrado apresentada Faculdade de Cincias da Universidade do Porto em Cincia de Computadores. — 2014.

48. Guan P. Cellular automaton public-key cryptosystem // Complex Systems. — 1987. — Vol. 1. — P. 51-57.

49. A new public key encryption scheme based on layered cellular automata / Xing Zhang, Rongxing Lu, Hong Zhang, Chungen Xu // KSII Transactions on Internet and Information Systems (TIIS). — 2014. — Vol. 8, No. 10. — P. 3572-3590.

50. Chilikov A. A., Zhukov A. E., Verxovskij A. I. Issledovanie obratimy’x kletochny’x avtomatov s konechnoj reshetkoj // Bezopasny’e informacionny’e texnologii. Sbornik trudov Desyatoj mezhdunarodnoj nauchno-texnicheskoj konferencii. — M.: MGTU im. N.E’. Baumana, 2019. — S. 354-360.

51. Zhukov A. E. Kletochny’e avtomaty’ i zaprety’ bulevy’x funkcij // Bezopasny’e informacionny’e texnologii. Sbornik trudov XI mezhdunarodnoj nauchno-texnicheskoj konferencii. — M.: MGTU im. N.E’. Baumana, 2021. — S. 108-119.

52. Arora S., Barak B. Computational Complexity: A Modern Approach. — Cambridge University Press, 2009. — 594 p.

53. Green F. NP-complete problems in cellular automata // Complex Systems. — 1987. — Vol. 1, No. 3. — P. 453-474.

54. Sutner K. Additive automata on graphs // Complex Systems. — 1988. — Vol. 2, No. 6. — P. 649-661.

55. Clementi A., Impagliazzo R. The reachability problem for finite cellular automata // Information processing letters. — 1995. — Vol. 53, No. 1. — P. 27-31.

56. Klyucharev P. G. NP-trudnost’ zadachi o vosstanovlenii predy’dushhego sostoyaniya obobshhennogo kletochnogo avtomata // Nauka i obrazovanie. MGTU im. N.E’. Baumana. E’lektron. zhurn. — 2012. — No 1. — Rezhim dostupa: http://technomag.edu.ru/doc/312834.html.

57. Klyucharev P.G. Kletochnye avtomaty i ih obobshcheniya v zadachah kriptografii. CHast 1. Voprosy kiberbezopasnosti [Cybersecurity issues]. 2021. No 6 (46), pp. 90-101. DOI: 10.21681/2311-3456-2021-6-90-101.

По оценкам слепого рецензирования данной статьи (часть 1 — №6-2021 и часть 2 — №1-2022) рецензентом были отмечены следующие рекомендации:

1. В работе, на наш взгляд, несколько тенденциозно представлены работы зарубежных научных школ, в ущерб отечественным научным школам, в том числе родоначальникам русскоязычной терминологии КА (однородных структур в русскоязычной терминологии), и особенно весьма лаконично упомянуты ученые, находящиеся у истоков становления теории КА в СССР.

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

• Аладьев В.З. Классические однородные структуры. Клеточные автоматы.- CA: Palo Alto, Fultus Corporation, 2009, 536 c. (на русском языке).

• Матюшкин И. В., Заплетина М. А. Обзор по тематике клеточных автоматов на базе современных отечественных публикаций.// Компьютерные исследования и моделирование. 2019. Т. 11, No 1. С. 9-57 DOI: 10.20537/2076-76332019-11-1-9-57.

2. Полагаю, что публикация бы выиграла, если автор более полно учел и материалы индийского математика Palash Sarkar:

КЛЕТОЧНЫЕ АВТОМАТЫ И ИХ ОБОБЩЕНИЯ В ЗАДАЧАХ КРИПТОГРАФИИ. ЧАСТЬ 1 Текст научной статьи по специальности «Математика»

Цель статьи: аналитический обзор применения клеточных автоматов и их обобщений в криптографии.Метод исследования: анализ научных публикаций по теме статьи.Полученные результаты: в обзорной статье проанализирована литература, посвященная использованию как классических клеточных автоматов, так и их обобщений для построения криптографических алгоритмов . Статья состоит из двух частей. Первая часть посвящена классическим клеточным автоматам и основанным на них симметричным криптографическим алгоритмам. В ней кратко обсуждается история теории клеточных автоматов и ее применения в различных научных областях. Приведен обзор работ ряда авторов, которыми предлагались симметричные криптографические алгоритмы и генераторы псевдослучайных последовательностей, основанные на одномерных клеточных автоматах. Стойкость таких криптоалгоритмов оказалось недостаточной. Далее дан обзор статей, посвященных использованию двухмерных клеточных автоматов для построения симметричных криптоалгоритмов (этот подход давал лучшие результаты). Также упомянуты многомерные клеточные автоматы. Вторая часть статьи, которая будет опубликована, в следующем номере, будет посвящена обзору работ, посвященных использованию обобщенных клеточных автоматов в криптографии на основе таких автоматов возможно создавать алгоритмы симметричного шифрования и криптографические хэш-функции , обладающие высоким уровнем криптостойкости и высокой производительностью при аппаратной реализации (например, на программируемых логических интегральных схемах), а также предъявляющие достаточно низкие требования к аппаратным ресурсам. Кроме того, в ней будет уделено внимание интересным связям обобщенных клеточных автоматов, в контексте их использования в криптографии, с теорией расширяющих графов; также будет уделено внимание вопросам стойкости криптоалгоритмов , основанных на обобщенных клеточных автоматах. Будут упомянуты работы, посвященные реализации различных криптографических алгоритмов , основанных на обобщенных клеточных автоматах, на программируемых логических интегральных схемах и графических процессорах. Кроме того, будет дан обзор асимметричных криптоалгоритмов, основанных на клеточных автоматах. Будут рассмотрены вопросы о принадлежности некоторых задач на клеточных автоматах и их обобщениях к классу NP-полных задач, а также к некоторым другим классам сложности.

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Ключарёв Петр Георгиевич

Производительность и эффективность аппаратной реализации поточных шифров, основанных на обобщенных клеточных автоматах

Исследование характеристик лавинного эффекта обобщенных клеточных автоматов на основе графов малого диаметра

Метод построения криптографических хэш-функций на основе итераций обобщенного клеточного автомата
Криптографические хэш-функции, основанные на обобщённых клеточных автоматах
Клеточные автоматы в криптографии. Часть 2
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

CELLULAR AUTOMATA AND THEIR GENERALIZATIONS IN CRYPTOGRAPHY. PART 1

The purpose of the article is an analytical review of the application of cellular automata and their generalizations in cryptography. Research method: an analysis of scientific publications on the topic of the article. Results: The review article analyzes the literature devoted to the use of classical cellular automata and their generalizations for the construction of cryptographic algorithms. The article consists of two parts. The first part is devoted to classical cellular automata and symmetric cryptographic algorithms based on them. It briefly discusses the history of the theory of cellular automata and its applications in various scientific disciplines. The review of the works of a number of authors who proposed symmetric cryptographic algorithms and pseudorandom sequence generators based on one-dimensional cellular automata is presented. The security of such cryptographic algorithms turned out to be insufficient. The following is a review of articles devoted to the use of two-dimensional cellular automata for constructing ciphers (this approach gave the best results). Multidimensional cellular automata are also mentioned. The second part of the article will be devoted to a review of works devoted to the use of generalized cellular automata in cryptography — on the basis of such automata, it is possible to create symmetric encryption algorithms and cryptographic hash functions that provide a high level of security and high performance in hardware implementation (for example, on FPGA), as well as having fairly low requirements for hardware resources. In addition, an attention will be paid to interesting connections of generalized cellular automata, in the context of their use in cryptography, with the theory of expander graphs. Attention will also be paid to the security of cryptographic algorithms based on generalized cellular automata. The works devoted to the implementation of various cryptographic algorithms based on generalized cellular automata on FPGA and GPU will be mentioned. In addition, an overview of asymmetric cryptographic algorithms based on cellular automata will be given. The questions about the belonging of some problems on cellular automata and their generalizations to the class of NP-complete problems, as well as to some other complexity classes, will also be considered.

Текст научной работы на тему «КЛЕТОЧНЫЕ АВТОМАТЫ И ИХ ОБОБЩЕНИЯ В ЗАДАЧАХ КРИПТОГРАФИИ. ЧАСТЬ 1»

I клеточные автоматы и их обобщения

в задачах криптографии. часть 1

Цель статьи: аналитический обзор применения клеточных автоматов и их обобщений в криптографии.

Метод исследования: анализ научных публикаций по теме статьи.

Полученные результаты: в обзорной статье проанализирована литература, посвященная использованию как классических клеточных автоматов, так и их обобщений для построения криптографических алгоритмов. Статья состоит из двух частей. Первая часть посвящена классическим клеточным автоматам и основанным на них симметричным криптографическим алгоритмам. В ней кратко обсуждается история теории клеточных автоматов и ее применения в различных научных областях. Приведен обзор работ ряда авторов, которыми предлагались симметричные криптографические алгоритмы и генераторы псевдослучайных последовательностей, основанные на одномерных клеточных автоматах. Стойкость таких криптоалгоритмов оказалось недостаточной. Далее дан обзор статей, посвященных использованию двухмерных клеточных автоматов для построения симметричных криптоалгоритмов (этот подход давал лучшие результаты). Также упомянуты многомерные клеточные автоматы. Вторая часть .статьи, которая будет опубликована, в следующем номере, будет посвящена обзору работ, посвященных использованию обобщенных клеточных автоматов в криптографии — на основе таких автоматов возможно создавать алгоритмы симметричного шифрования и криптографические хэш-функции, обладающие высоким уровнем криптостойкости и высокой производительностью при аппаратной реализации (например, на программируемых логических интегральных схемах), а также предъявляющие достаточно низкие требования к аппаратным ресурсам. Кроме того, в ней будет уделено внимание интересным связям обобщенных клеточных автоматов, в контексте их использования в криптографии, с теорией расширяющих графов; также будет уделено внимание вопросам стойкости криптоалгоритмов, основанных на обобщенных клеточных автоматах. Будут упомянуты работы, посвященные реализации различных криптографических алгоритмов, основанных на обобщенных клеточных автоматах, на программируемых логических интегральных схемах и графических процессорах. Кроме того, будет дан обзор асимметричных криптоалгоритмов, основанных на клеточных автоматах. Будут рассмотрены вопросы о принадлежности некоторых задач на клеточных автоматах и их обобщениях к классу NP-полных задач, а также к некоторым другим классам сложности.

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

Бурное развитие информационных технологий привело к резкому повышению требований к защите информации. Одними из основных методов защиты информации являются криптографические методы. Современная криптография развивается весьма активно и становится все более и более востребованной. При этом предъявляются высокие требования не только к стойкости современных криптографических алгоритмов, но и к их быстродействию. Это связано с тем, что пропускная способность каналов связи быстро возрастает, например, в 2017 г. принят стандарт IEEE 802.3bs-2017 на протоколы организации компьютерных сетей, функционирующие на скоростях 200 и 400 Гбит/с, а в 2020 г. принят стандарт IEEE 802.3ck-2020 на протоколы, позволяющие достичь скорости 800 Гбит/с. В то же время все более часто используются вычислительные устройства с малыми вычислительными ресурсами. Такие устройства применяются в широчайшей гамме областей, начиная от многочисленных приме-

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

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

1 Ключарёв Петр Георгиевич, кандидат технических наук, доцент кафедры «Информационная безопасность» МГТУ им. Н.Э. Баумана, Москва, Россия. E-mail: pk.iu8@yandex.ru

Клеточные автоматы — модель, которая нашла применения в разных областях как чистой математики, так и ее приложений. Теория алгоритмов, теория хаоса, теоретическая физика, биология, эпидемиология, химия, экология, вирусология, социология — далеко не полный список научных дисциплин, в которых клеточные автоматы находят то или иное применение. Попытки применить клеточные автоматы в криптографии начались в середине 1980-х гг., причем их применение выглядело весьма многообещающим. С одной стороны, ряд их теоретических свойств позволял надеяться на то, что они позволят обеспечить высокий уровень криптостойко-сти, с другой стороны, присущий им параллелизм обработки информации давал основания ожидать высокой скорости работы основанных на них алгоритмов, в особенности, при аппаратной реализации. К сожалению, первые эксперименты в этой области оказались не очень удачными, что привело к определенному снижению интереса к криптографическому использованию этих моделей. В 2009 — 2011 гг. вышла серия работ, которая вновь подогрела интерес к этому направлению: оказалось, что с помощью двухмерных клеточных автоматов и обобщенных клеточных автоматов можно построить поточные шифры, обладающие высокой производительностью при аппаратной реализации и в то же время довольно низкими требованиями к аппаратным ресурсам. В дальнейшем вышло большое число работ, подводящих теоретический базис под использование обобщенных клеточных автоматов в симметричной криптографии и предлагающих новые криптоалгоритмы на основе таких автоматов. Кроме того, известны подходы к построению асимметричных криптоалгоритмов на основе клеточных автоматов. Есть определенная надежда, что такие подходы в будущем позволят получить новые асимметричные криптоалгоритмы, в том числе, постквантовые.

Данный обзор посвящен использованию клеточных автоматов (в том числе, обобщенных) в криптографии.

1. Клеточные автоматы

Неформально говоря, клеточный автомат — это автономный автомат, состояние которого задано упорядоченным набором ячеек памяти, образующих к-мерную решетку. В каждой ячейке такого автомата может храниться одно значение, принадлежащее некоторому конечному множеству (в большинстве случаев, в литературе рассматриваются двоичные клеточные автоматы, у которых этим множеством является й2).

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

решетки отождествляются (т.е. решетка превращается в тор). Набор значений ячеек на данном шаге называется заполнением клеточного автомата. Заполнение в начальный момент времени называется начальным заполнением.

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

Понятие клеточного автомата было предложено Джоном фон Нейманом в работе [1]. Фон Нейман использовал клеточные автоматы в качестве модели самоорганизующихся систем. На его исследования существенно повлиял Станислав Улам2, который пришел к подобным моделям, занимаясь математическим моделированием роста кристаллов. Затем такие автоматы широко исследовались различными авторами. Клеточным автоматам посвящено большое количество монографий (в частности, [2-11]) и статей (следует, в частности, упомянуть работы [12-14]). Особенно много клеточными автоматами занимался Стивен Вольфрам, который подробно исследовал различные их свойства, в том числе и те, которые относятся к криптографии и генерации случайных последовательностей. Основные результаты С. Вольфрама опубликованы в работах [11,12,14-16], а также многих других. Целый ряд его работ, посвященных клеточным автоматам, опубликован в книге [17].

Описанию истории развития теории клеточных автоматов посвящен обзор [18], а также книга [19]. Отметим также обзор [20].

Существует следующая классификация клеточных автоматов, предложенная С. Вольфрамом в книге [11]:

— Класс 1: Поведение автомата является очень простым. Почти все начальные заполнения быстро приводят к одному и тому же финальному состоянию.

— Класс 2: Существует большое количество возможных финальных состояний, но все они состоят из некоторого множества простых структур, которые либо остаются стабильными, либо повторяются с маленьким периодом. Локальные изменения в начальных условиях оказывают влияние локального характера на дальнейшую динамику автомата.

— Класс 3: Результатом эволюции почти всех начальных заполнений являются псевдослучайные последовательности. Стабильных структур не возникает. Локальные изменения в начальном

2 Станислав Улам, родился в 1909 г. в зажиточной еврейской семье, окончил Львовский политехнический институт (в то время Польша), получив в 1933 г степень доктора философии. В 1935 г. он познакомился в Варшаве с фон Нейманом, который пригласил его в Принстон, куда он переехал в 1936 г, что его и спасло, так как оставшиеся во Львове отец и сестра (мать, родом из Стрыя, умерла в 1938 г) погибли в гетто между 1941 и 1943 гг. Участвовал в создании водородной бомбы в Лос-Аламосской лаборатории. Выдвинул теорию ядерного ракетного двигателя, предложил вычислительный метод Монте-Карло, сформулировал вместе с Ферми и другими учеными парадокс в теории хаоса, сейчас называемый парадокс Ферми-Паста-Улама-Цинга. До конца жизни в мае 1984 г. жил и работал в США (прим. редакции).

заполнении оказывают сильное влияние на ход всей эволюции системы.

— Класс 4: Результатом эволюции почти всех начальных заполнений являются структуры, которые взаимодействуют сложным образом с формированием локальных устойчивых структур. Локальные изменения в начальном заполнении оказывают сильное влияние на ход всей эволюции системы. Некоторые клеточные автоматы этого класса являются полными по Тьюрингу.

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

2. Клеточные автоматы в науке и технике

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

Клеточные автоматы активно изучаются в различных областях математики и теоретической информатики, имеется огромное число публикаций. Интерес к клеточным автоматам объясняется, в частности тем, что они представляют собой как простую математическую модель, которая хорошо подходит для описания динамики разнообразных систем, так и весьма любопытную вычислительную модель параллельной обработки информации. Теорией клеточных автоматов, с точки зрения теории конечных автоматов, математической логики и смежных областей, много занималась и занимается научная школа В.Б. Кудрявцева. Среди большого числа работ, принадлежащих членам этой научной школы, отметим обзоры [21,22] и ставшую классической монографию [23]. Теорией клеточных автоматов, с точки зрения теории вычислимости и теории динамических систем, занимался С. Вольфрам, которому принадлежит целый ряд основополагающих работ в этой области (сошлемся здесь на сборник его статей по клеточным автоматам [24]). Также клеточные автоматы находят применение в области вычислительной геометрии и обработки изображений [10].

Теория динамических систем очень богата на применения клеточных автоматов [25]. Причем как с точки зрения теории, так и с точки зрения приложений в задачах имитационного моделирования в различных областях. Многие биологические системы естественным образом моделируются с помощью клеточных автоматов. Обзор этого направления можно найти, например, в книге [26]. В частности, клеточные автоматы

применяют для моделирования пролиферации и взаимодействия живых клеток, роста опухолей, динамики популяций организмов, развития эпидемий [27] и др. В области химии клеточные автоматы применяются для математического моделирования процессов диффузии жидкостей и газов, процессов кристаллизации, процессов адсорбции, процессов коррозии. Целый ряд химических реакций может быть описан в терминах клеточных автоматов. Хороший обзор этого направления представлен в работе [28], а также в монографии [29]. Также клеточные автоматы применяются в задачах анализа микроструктуры металлов [30]. В геоинформационных системах и связанных с ними задачах имитационного моделирования городов также активно применяются клеточные автоматы: [31-33]. Вообще, клеточные автоматы активно применяются в задачах имитационного моделирования сложных систем, в том числе, социальных и экономических [34].

Интереснейшие приложения клеточные автоматы нашли в теоретической физике, в рамках так называемой цифровой физики — совокупности теоретических взглядов, основанных на подходе к описанию Вселенной, как к результату работы некоторого вычислительного устройства. Родоначальником этой области являлся Конрад Цузе, который в книге [35] высказал мысль, что таким вычислительным устройством может являться клеточный автомат. Развитием клеточно-автоматно-го описания Вселенной занимался уже многократно упомянутый С. Вольфрам — этому он уделяет внимание в книге [11], а его недавняя книга [36] посвящена этому полностью.

Изучению клеточных автоматов и их приложений традиционно уделяется большое внимание в нашей стране. Российским публикациям в этой области посвящен отличающийся полнотой обзор [37].

Популяризации клеточных автоматов весьма содействовала игра «Жизнь», придуманная Джоном Конвеем в конце 1960х гг. и популяризованная Мартином Гарднером, который опубликовал статью о ней в научно-популярном журнале Scientific American [38]. Научным подробностям этой игры посвящена книга [3].

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

3. Одномерные клеточные автоматы в симметричной криптографии

3.1. Основные понятия

С. Вольфрамом было, прежде всего, исследовано применение в криптографии одномерных клеточных автоматов. Одномерный клеточный автомат — это автономный автомат, состояние которого задается набором ячеек памяти т. В теоретических работах достаточно часто рассматривают бесконечные одномерные клеточные автоматы, в которых набор ячеек представляет собой что-то вроде бесконечной в обе стороны ленты:

Щ (* + !) = / (Щ-а (?). rni+b (0), (1)

где функция f называется локальной функцией связи.

Щ(* + 1) = /H-2) modmod*(0). (2)

При этом, клеточный автомат может быть определен над тем или иным множеством. Чаще всего рассматривается двоичный случай, когда m^t) е Z2. В этом случае локальная функция связи является булевой.

Выделяют класс элементарных клеточных автоматов, у которых в формулах (1) и (2) полагают а-Ъ-1. Всего существует 256 элементарных клеточных автоматов. Для них вводят нумерацию (так называемые коды Вольфрама), рассматривая вектор значений локальной функции связи как число, следующим образом:

«ел = 27 /0) 1) 1) + 2б /(1,1,0) + 2s /(1,0,1) + 24 /(1,0,0) +

+23 /(0,1,1) + 22 ДО,1,0) + 2/(0,0,1) + /(0,0,0). (3)

Обычно элементарный клеточный автомат с номером пСА называют rule пСА.

3.2 Поточные шифры и генераторы псевдослучайных последовательностей на основе одномерных клеточных автоматов

Стивен Вольфрам впервые предложил использовать клеточные автоматы для генерации криптографически стойких псевдослучайных последовательностей и поточного шифрования в работах [14,16]. В них используется клеточный автомат rule 30, работа которого описывается уравнением:

mt (i + l) = (t) © mi (t) © mM (t) © mi (t)mM (t),

В начальный момент времени (при i = 0) ячейки инициализируются начальными значениями (вырабатываемыми на основе ключа). Выходной последовательностью такого генератора является последовательность значений некоторой ячейки клеточного автомата (с некоторым фиксированным индексом s): y, = ms(t), t = 1,2.

Такой генератор вырабатывает один двоичный разряд за один такт. Согласно результатам С. Вольфрама, выходная последовательность такого генератора имеет хорошие статистические свойства. Клеточный автомат rule 30 реализует функцию достаточно близкую к биек-ции (лишь около 0.85^ из 2N вершин графа состояний имеют больше одного предка, см. рис. 1). Также, по полученным С. Вольфрамом результатам, при достаточно большом N, подавляющее большинство состояний автомата лежат на одном большом цикле, длина которого приблизительно равна 20’61ЛГ.

К сожалению, в результате проведенного в работе [39] криптоанализа, предложенный С. Вольфрамом шифр оказался нестойким.

Рис. 1. Граф переходов одномерного элементарного клеточного автомата Rule 30 с 11 ячейками (иллюстрация из статьи [14]).

На основе одномерных клеточных автоматов предлагались и более сложные шифры. Так, в работе [40] предлагался поточный шифр, в котором, в сочетании с довольно простыми нелинейными преобразованиями, использовался одномерный клеточный автомат с линейной локальной функцией связи, но в работе [41] этот шифр был взломан. В работе [42] был предложен шифр, использующий ту же схему, что и известный поточный шифр Trivium [43], однако вместо нелинейных регистров сдвига с обратными связями, в нем использовались одномерные клеточные автоматы. В работе [44] был предложен еще один поточный шифр, в котором используется своеобразный «сэндвич» из одномерных клеточных автоматов с линейными и нелинейными локальными функциями связи, часть из которых генерируется динамически. К сожалению, криптостойкость этих шифров не была удовлетворительно исследована.

Криптографические свойства одномерных клеточных автоматов изучались в ряде работ. В частности, в работах [45,46] изучается связь линейных одномерных клеточных автоматов с линейными регистрами сдвига с обратной связью и структурами на них основанными. В работе [47] выбираются одномерные клеточные автоматы с хорошими статистическими свойствами выходной последовательности, а в работе [48] для решения этой задачи применяются генетические алгоритмы.

Несмотря на то, что с помощью одномерных клеточных автоматов возможно получить достаточно хорошие статистические свойства выходной последовательно-

сти, основанные на них криптографические алгоритмы имеют ряд проблем с криптостойкостью и невысокую производительность. Криптостойкость ряда предлагавшихся поточных шифров, основанных на одномерных клеточных автоматах, не была удовлетворительно исследована, а те из них, чья криптостойкость была исследована, оказались нестойкими. Подобные криптоалгоритмы критикуются, например в работах [39,49,50] и др. В связи с этими недостатками, алгоритмы, основанные на одномерных клеточных автоматах, редко используются для генерации псевдослучайных последовательностей на практике. Один из позитивных примеров практического применения подобных алгоритмов — в системе компьютерной алгебры Wolfram Mathematica

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

3.3 Блочные шифры на основе одномерных клеточных автоматов

Рядом авторов были построены блочные шифры, основанные на одномерных клеточных автоматах. В работе

[52] предложен блочный шифр, один раунд которого представляет собой смешивание с раундовым ключом (путем поразрядного сложения по модулю 2 с ним), за которым следует применение трех преобразований: нелинейного, линейного и обратного к нелинейному. Нелинейное преобразование состоит из определенного числа шагов элементарного клеточного автомата rule 30, а линейное преобразование состоит из определенного числа шагов элементарного клеточного автомата rule 153. К сожалению, криптостойкость данного шифра не исследовалась.

В работе [53] предложен блочный шифр, основанный на схеме Фейстеля, в качестве раундовой функции которой используется одномерный клеточный автомат rule 30. На этот автомат подается поразрядная сумма подблока и раундового ключа. Между раундами применяются обратимый S-блок и P-блок. В работе [53] проведено исследование статистических свойств данного шифра, однако убедительных обоснований преимуществ такого шифра не приведено, как не приведено и удовлетворительного исследования его криптостойкости.

Из общих соображений представляется интересной концепция использования обратимых клеточных автоматов для построения блочных шифров. Действительно, это может позволить получить высокое быстродействие таких шифров. К сожалению, теория синтеза обратимых клеточных автоматов все еще недостаточно развита. Например, в статье [54] предлагается использовать обратимый одномерный клеточный автомат из некоторого семейства. Причем конкретный автомат выбирается на основе ключа. В статье заключается, что использование одного автомата не позволяет добиться высокой криптостойкости. Тем не менее, этот подход развит в статье [55], в которой используется несколько одномерных клеточных автоматов, а ключ подмешивается с помощью поразрядного сложения по модулю 2. Достаточного обоснования криптостойкости такого подхода не приводится.

К сожалению, для большинства известных блочных шифров, основанных на клеточных автоматах, не про-

водилось независимых попыток криптоанализа. Исключением является предложенный в работе [56] блочный шифр, основанный на одномерном клеточном автомате над полем F28, состоящим из 16 ячеек. Таких автоматов в нем используется два. Один из них применяется для генерации второго клеточного автомата и других параметров, исходя из ключа, а с помощью второго — происходит шифрование очередного блока (кроме второго автомата в шифровании участвуют другие преобразования, зависящие от сгенерированных параметров). Шифр обладает достаточно сложной и остроумной структурой, однако, согласно работе [57], в нем, к сожалению, были найдены уязвимости.

3.4 Криптографические хэш-функции

на основе одномерных клеточных автоматов

Пожалуй, впервые криптографическая хэш-функция на основе клеточного автомата была предложена И. Дамгордом в работе [58]. Основной принцип работы этой хэш-функции заключался в использовании одномерного элементарного клеточного автомата rule 30. Причем выполняется 384 шага этого клеточного автомата. Способ построения коллизий к этой хэш-функции был предложен в работе Й. Даймена [59]. В ней же предложена другая хэш-функция, отличающаяся тем, что используется более сложная локальная функция связи, такая что каждая ячейка зависит от девяти ячеек на предыдущем шаге.

Далее рядом авторов был предложен целый ряд разнообразных криптографических хэш-функций на базе клеточных автоматов. В частности, хэш-функции, основанные на одномерных клеточных автоматах, предлагаются в работах [60-67]. К сожалению, использование одномерных клеточных автоматов не позволяет достичь высокой производительности, что продемонстрировано в статье [67], где производительность такой функции на ПЛИС не достигает даже 0.5 МБ/с.

Предложенные в упомянутых работах хэш-функции основаны либо на схеме Меркла-Дамгорда [58], либо на древовидной схеме, либо на схеме криптографической губки [68]. В случае схемы Меркла-Дамгорда, на которой основаны хэш-функции, предложенные в работах [62,63,65], и древовидной схемы, на которой основаны хэш-функции, предложенные в работах [60,61], однонаправленная функция сжатия построена на базе нескольких шагов одномерного клеточного автомата, в сочетании с некоторыми другими преобразованиями, такими как S-блоки, циклические сдвиги и др. В случае схемы криптографической губки, на которой основаны хэш-функции, предложенные в работах [64,66], в качестве функции преобразования также используется несколько шагов одномерного клеточного автомата.

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

3.5 Перспективы одномерных клеточных автоматов в симметричной криптографии

Несмотря на то, что существовало достаточно много попыток применения одномерных клеточных

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

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

4. Двух- и более мерные клеточные автоматы в симметричной криптографии

4.1. Двух- и более мерные клеточные автоматы: основные понятия

Двухмерным клеточным автоматом будем называть автономный автомат, состояние которого задается набором ячеек памяти, расположенных в узлах целочисленной решетки на плоскости. Как уже говорилось, в теоретических работах могут рассматриваться клеточные автоматы с бесконечным числом ячеек. Для прикладных целей более интересны автоматы с конечным числом ячеек, образующих на плоскости прямоугольник. При этом, достаточно часто отождествляют противоположные края решетки, чтобы правила перехода можно было сделать одинаковыми для каждой ячейки. В начальный момент времени каждая ячейка т^ имеет некоторое начальное значение ти(0) . Автомат работает пошагово. Значение каждой ячейки на шаге £ вычисляется как функция /, называемая локальной функцией связи, от значений ячеек, принадлежащих некоторой окрестности этой ячейки.

Обычно значения ячеек являются двоичными (хотя, как уже говорилось, могут рассматриваться и клеточные автоматы над другими множествами). Под окрестностью порядка 5 ячейки ти обычно понимается набор ячеек, находящихся от нее на расстоянии, не превышающим 5. При этом, можно использовать разные метрики. Например, если использовать манхеттенское расстояние, то получится окрестность фон Неймана: , а если использовать расстояние Чебышева, то получится окрестность Мура: | V —у’1 Часто в окрестность не включают центральную ячейку (т.е. саму ячейку в этом случае, окрестность называется неполной.

Кроме двухмерных можно рассматривать и к-мерные клеточные автоматы при А^З, заменив плоскость к-мерным пространством.

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

ритмы на основе одномерных клеточных автоматов, т.к. в случае использования правильно выбранного k-мерного клеточного автомата с N ячейками, чтобы обеспечить зависимость значений всех ячеек от начального значения каждой из них, требуется порядка шагов.

4.2 Криптоалгоритмы на основе двухмерных клеточных автоматов

Долгое время заслуживающих упоминания криптографических алгоритмов, основанных на двухмерных клеточных автоматах, не предлагалось. Однако в 2009 — 2011 гг. вышла целая серия статей [69-78] и диссертация [79] Б.М. Сухинина, который смог весьма удачно применить двумерные клеточные автоматы для генерации псевдослучайных последовательностей. Им введено понятие интегральной и пространственной характеристик лавинного эффекта для клеточных автоматов и предложен генератор псевдослучайных последовательностей, основанный на клеточных автоматах.

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

Предложенная Б.М. Сухининым схема генератора псевдослучайных последовательностей состоит из двух клеточных автоматов и регистра сдвига. Схема такого генератора изображена на рис. 2. Оба клеточных автомата являются двухмерными, имеют размер 37×11 ячеек, при этом используется неполная окрестность Мура. Выход каждого автомата снимается с ячеек, образующих прямоугольник 32×8. При этом локальная функция связи является равновесной булевой функцией. Она, путем рандомизированного перебора, выбиралась так, чтобы выходная последовательность такого генератора успешно проходила статистические тесты из комплекта NIST Statistical Test Suite. Линейный регистр сдвига с обратной связью используется в этой схеме для обеспечения гарантированной длины периода выходной последовательности. Его выход на каждом шаге прибавляется по модулю 2 к значению одной из ячеек каждого клеточного автомата. Такой генератор можно рассматривать как генератор гаммы поточного шифра. Он имеет высокую производительность при аппаратной реализации (на ПЛИС): была достигнута производительность в 34 Гбит/с при требованиях к аппаратным ресурсам 21892 LE.

Рис. 2: Структура генератора псевдослучайных последовательностей, предложенная в работе [79]

Предлагались и другие криптоалгоритмы на основе двухмерных клеточных автоматов. В частности, в работах [80,81] построены криптографические хэш-функции, основанные на двухмерных клеточных автоматах. Они используют схему криптографической губки (Sponge), в

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

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

Исследование выполнено при финансовой поддержке РФФИ в рамках научного проекта № 20-17-50258. Литература

1. von Neumann J. The general and logical theory of automata // Proc. Hixon Symposium on Cerebral Mechanisms in Behavior / Ed. by L. A. Jeffress. New York, 1951. P. 1-31.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

2. Тоффоли Т., Марголус Н. Машины клеточных автоматов. М.: Мир, 1991. 280 с.

3. Adamatzky A. Game of Life Cellular Automata. Springer London, 2010. 579 p.

4. Ceccherini-Silberstein T., Coornaert M. Cellular Automata and Groups. Springer Berlin Heidelberg, 2010. 440 p.

5. Codd E., Ashenhurst R. Cellular Automata. Academic Press, 1968. 132 p.

6. Gutowitz H. Cellular Automata: Theory and Experiment. MIT Press, 1991. 483 p.

7. Ilachinski A. Cellular Automata: A Discrete Universe. World Scientific, 2001. 808 p.

8. Margenstern M. Small Universal Cellular Automata in Hyperbolic Spaces: A Collection of Jewels. Springer Berlin Heidelberg, 2013. 320 p.

9. Mcintosh H. One Dimensional Cellular Automata. Luniver Press, 2009. 280 p.

10. Rosin P., Adamatzky A., Sun X. Cellular Automata in Image Processing and Geometry. Springer International Publishing, 2014. 304 p.

11. Wolfram S. A New Kind of Science. Wolfram Media, 2002. 1192 p.

12. Wolfram S. Cellular automata // Los Alamos Science. 1983. Vol. 9. P. 2-21.

13. Packard N., Wolfram S. Two-dimensional cellular automata // Journal of Statistical Physics. 1985. Vol. 38. P. 901-946.

14. Wolfram S. Cryptography with cellular automata // Lecture Notes in Computer Science. 1986. Vol. 218. P. 429-432.

15. Wolfram S. Cellular automation supercomputing // High-speed computing: scientific applications and algorithm design / Ed. by Robert B. Wilhelmson. University of Illinois Press, 1988. P. 40-48.

16. Wolfram S. Random sequence generation by cellular automata // Advances in Applied Mathematics. 1986. Vol. 7. P. 123-169.

17. Wolfram S. Cellular automata and complexity: collected papers. Addison-Wesley Reading, MA, 1994. Vol. 1. 608 p.

18. Sarkar P. A brief history of cellular automata // Acm computing surveys (csur). 2000. Vol. 32, no. 1. P. 80-107.

19. Schiff J. L. Cellular automata: a discrete view of the world. John Wiley & Sons, 2011. Vol. 45. 272 p.

20. Жуков А. Е. Клеточные автоматы в криптографии. Часть 1 // Вопросы кибербезопасности. 2017. № 3(21). С. 70-76.

21. Кудрявцев В. Б., Подколзин А. С. Об основных направлениях в теории однородных структур // Дискретная математика. 1989. Т. 1, № 3. С. 229-250.

22. Кудрявцев В. Б., Подколзин А. С. Клеточные автоматы. // Интеллектуальные системы. 2006. Т. 10, № 1-4. С. 657-692.

23. Кудрявцев В. Б., Подколзин А. С., Болотов А. А. Основы теории однородных структур. М.: Наука, 1992. 298 с.

24. Wolfram S. Cellular Automata And Complexity: Collected Papers. CRC Press, 2018. 608 p.

25. Термодинамика необратимых процессов и нелинейная динамика / Е.М. Кольцова, Л.С. Гордеев, Третьяков Ю.Д., Вертегел А.А. М.: Юрлайт, 2019. 430 p.

26. Deutsch A., Dormann S. et al. Cellular automaton modeling of biological pattern formation. Springer, 2005. 464 p.

27. White S. H., Del Rey A. M., Sanchez G. R. Modeling epidemics using cellular automata // Applied mathematics and computation. 2007. Vol. 186, no. 1. P. 193-202.

28. Menshutina N. V., Kolnoochenko A. V., Lebedev E. A. Cellular automata in chemistry and chemical engineering // Annual Review of Chemical and Biomolecular Engineering. 2020. Vol. 11. P. 87-108.

29. Kier L., Seybold P., Cheng C. Modeling Chemical Systems Using Cellular Automata. Springer, 2005. ISBN: 9781402036576.

30. Андреева О. В. Модель и алгоритмы для оценки поврежденности микроструктуры поверхности металлов и сплавов по изображениям: Дис. канд. техн. наук: 05.13.01 / Ольга Вячеславовна Андреева; Нижегор. гос. техн. ун-т им Р.Е. Алексеева. Нижний Новгород, 2017. 162 с.

31. Wagner D. F. Cellular automata and geographic information systems // Environment and planning B: Planning and design. 1997. Vol. 24, no. 2. P. 219-234.

32. Batty M., Xie Y., Sun Z. Modeling urban dynamics through gis-based cellular automata // Computers, environment and urban systems. 1999. Vol. 23, no. 3. P. 205-233.

33. Torrens P. M., O’Sullivan D. Cellular automata and urban simulation: where do we go from here? 2001.

34. Hoekstra A. G., Kroc J., Sloot P. M. Simulating complex systems by cellular automata. Springer, 2010. 384 p.

35. Zuse K. Calculating Space. MIT technical translation. — Massachusetts Institute of Technology, Project MAC, 1970. 188 p.

36. Wolfram S. A Project to Find the Fundamental Theory of Physics. Wolfram Media, Incorporated, 2020. 770 p. ISBN: 9781579550356.

37. Матюшкин И. В., Заплетина М. А. Обзор по тематике клеточных автоматов на базе современных отечественных публикаций // Компьютерные исследования и моделирование. 2019. № 1. С. 9-57.

38. Gardner M. The fantastic combinations of John Conway’s new solitaire game ^[^Л // Scientific American. 1970. Vol. 223. P. 120-123.

39. Meier W., Staffelbach O. Analysis of pseudo random sequences generated by cellular automata // Workshop on the Theory and Application of of Cryptographic Techniques / Springer. 1991. P. 186-199.

40. Sarkar P. Hiji-bij-bij: A new stream cipher with a self-synchronizing mode of operation // International Conference on Cryptology in India / Springer. 2003. P. 36-51.

41. Joux A., Muller F. Two attacks against the hbb stream cipher // International Workshop on Fast Software Encryption / Springer. 2005. P. 330-341.

42. Karmakar S., Mukhopadhyay D., Chowdhury D. R. Cavium-strengthening trivium stream cipher using cellular automata. // J. Cell. Autom. 2012. Vol. 7, no. 2. P. 179-197.

43. De Canniere C. Trivium: A stream cipher construction inspired by block cipher design principles // Information Security. Springer, 2006. P. 171-186.

44. Das S., Chowdhury D. R. Castream: A new stream cipher suitable for both hardware and software // International Conference on Cellular Automata / Springer. 2012. P. 601-610.

45. Bardell P. H. Analysis of cellular automata used as pseudorandom pattern generators // Proceedings. International Test Conference 1990 / IEEE. 1990. P. 762-768.

46. Fuster-Sabater A., Caballero-Gil P. On the use of cellular automata in symmetric cryptography // Acta Applicandae Mathematica. 2006. Vol. 93, no. 1. P. 215-236.

47. Bouvry P., Seredynski F., Zomaya A. Y. Application of cellular automata for cryptography // International conference on parallel processing and applied mathematics / Springer. 2003. P. 447-454.

48. Tomassini M., Perrenoud M. Cryptography with cellular automata // Applied Soft Computing. 2001. Vol. 1, no. 2. P. 151-160.

49. Henricksen M. A critique of some chaotic-map and cellular automata-based stream ciphers // Annual Asian Computing Science Conference / Springer. 2009. P. 69-78.

50. Bao F. Cryptanalysis of a partially known cellular automata cryptosystem // IEEE Transactions on Computers. 2004. Vol. 53, no. 11. P. 1493-1497.

51. Random number generation — Wolfram Mathematica 7 documentation. Access mode: http://reference.wolfram.com/mathematica/ tutorial/RandomNumberGeneration.html.

52. Mukhopadhyay D., RoyChowdhury D. Cellular automata: an ideal candidate for a block cipher // International Conference on Distributed Computing and Internet Technology / Springer. 2004. P. 452-457.

53. Achkoun K., Hanin C., Omary F. SPF-CA: A new cellular automata based block cipher using key-dependent S-boxes // Journal of Discrete Mathematical Sciences and Cryptography. 2020. Vol. 23, No. 8. P. 1529-1544.

54. Seredynski M., Bouvry P. Block encryption using reversible cellular automata // International Conference on Cellular Automata / Springer. 2004. P. 785-792.

55. Seredynski M., Bouvry P. Block cipher based on reversible cellular automata // New Generation Computing. 2005. Vol. 23, No. 3. P. 245-258.

56. Cellular automata based cryptosystem (CAC) / Subhayan Sen, Chandrama Shaw, Dipanwita Roy Chowdhuri et al. // International Conference on Information and Communications Security / Springer. 2002. P. 303-314.

57. Bao F. Cryptanalysis of a new cellular automata cryptosystem // Australasian Conference on Information Security and Privacy / Springer. 2003. P. 416-427.

58. Dam^ard I. B. A design principle for hash functions // Conference on the Theory and Application of Cryptology / Springer. 1989. P. 416-427.

59. Daemen J., Govaerts R., Vandewalle J. A framework for the design of one-way hash functions including cryptanalysis of dam^ard’s one-way function based on a cellular automaton // International Conference on the Theory and Application of Cryptology / Springer. 1991. P. 82-96.

60. HCAHF: A New Family of CA-based Hash Functions / Anas Sadak, Fatima Ezzahra Ziani, Bouchra Echandouri et al. // International Journal of Advanced Computer Science and Applications. 2019. Vol. 10. P. 12.

61. ElRakaiby M. M. Cryptographic hash function using cellular automata // International Journal of Computer Applications Technology and Research. 2016. Vol. 5, No. 5. P. 238-240.

62. Jeon J.-C. Cellular automata based cryptographic hash function // Proceedings of the International Conference on Scientific Computing (CSC) / The Steering Committee of The World Congress in Computer Science, Computer . 2011. P. 1.

63. Jeon J.-C. One-way hash function based on cellular automata // IT Convergence and Security 2012. Springer, 2013. P. 21-28.

64. 64. Cash: cellular automata based parameterized hash / Sukhendu Kuila, Dhiman Saha, Madhumangal Pal, Dipanwita Roy Chowdhury // International Conference on Security, Privacy, and Applied Cryptography Engineering / Springer. 2014. P. 59-75.

65. Rajeshwaran K., Kumar K. A. Cellular automata based hashing algorithm (cabha) for strong cryptographic hash function // 2019 IEEE International Conference on Electrical, Computer and Communication Technologies (ICECCT) / IEEE. 2019. P. 1-6.

66. A lightweight hash function based on cellular automata for mobile network / Xing Zhang, Qinbao Xu, Xiaowei Li, Changda Wang // 2019 15th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN) / IEEE. 2019. P. 247-252.

67. Tanasyuk Y., Perepelitsyn A., Ostapov S. Parameterized fpga-based implementation of cryptographic hash functions using cellular automata // 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT) / IEEE. 2018. P. 225-228.

68. Sponge functions / Guido Bertoni, Joan Daemen, MichaJel Peeters, Gilles Van Assche // ECRYPT hash workshop / Citeseer. Vol. 2007. 2007.

69. Сухинин Б. М. Применение классических и неоднородных клеточных автоматов при построении высокоскоростных генераторов псевдослучайных последовательностей // Проектирование и технология электронных средств. 2009. № 3. С. 47-51.

70. Сухинин Б. М. Высокоскоростные генераторы псевдослучайных последовательностей на основе клеточных автоматов // Прикладная дискретная математика. 2010. № 2. С. 34-41.

71. Сухинин Б. М. О влиянии параметров локальной функции связи на распределение значений ячеек двоичных клеточных автоматов // Объединенный научный журнал. 2010. № 8. С. 39-41.

72. Сухинин Б. М. О лавинном эффекте в клеточных автоматах // Объединенный научный журнал. 2010. № 8. С. 41-46.

73. Сухинин Б. М. О новом классе генераторов псевдослучайных последовательностей на основе клеточных автоматов // Объединенный научный журнал. 2010. № 8. С. 46-49.

74. Сухинин Б. М. Практические аспекты оценки качества генераторов случайных последовательностей с равномерным распределением // Объединенный научный журнал. 2010. № 8. С. 49-55.

75. Сухинин Б. М. Исследование характеристик лавинного эффекта в двоичных клеточных автоматах с равновесными функциями переходов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 8.

76. Сухинин Б. М. Разработка генераторов псевдослучайных двоичных последовательностей на основе клеточных автоматов // Наука и образование. МГТУ им. Н.Э. Баумана. Электрон. журн. 2010. № 9.

77. Сухинин Б. М. О некоторых свойствах клеточных автоматов и их применении в структуре генераторов псевдослучайных последовательностей // Вестник Московского государственного технического университета им. Н.Э. Баумана. Серия: Приборостроение. 2011. № 2. С. 68-76.

78. Сухинин Б. М. Однородные двумерные булевы клеточные автоматы и их свойства применительно к генерации псевдослучайных последовательностей // Системы высокой доступности. 2011. Т. 7, № 2. С. 39-41.

79. Сухинин Б. М. Разработка и исследование высокоскоростных генераторов псевдослучайных равномерно распределенных двоичных последовательностей на основе клеточных автоматов : Дис. канд. техн. наук: 05.13.17 / Борис Михайлович Сухинин: МГТУ им. Н.Э. Баумана. М., 2011. 224 с.

80. Haldar T., Chowdhury D. R. Design of hash function using two dimensional cellular automata // Proceedings of the Fifth International Conference on Mathematics and Computing / Springer. 2021. P. 33-45.

81. Tanasyuk Y., Ostapov S. Development and research of cryptographic hash functions based on two-dimensional cellular automata // Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Srodowiska. 2018. Vol. 8.

cellular automata and their generalizations

in cryptography. part 1

The purpose of the article is an analytical review of the application of cellular automata and their generalizations in cryptography.

Research method: an analysis of scientific publications on the topic of the article.

Results: The review article analyzes the literature devoted to the use of classical cellular automata and their generalizations for the construction of cryptographic algorithms. The article consists of two parts. The first part is devoted to classical cellular automata and symmetric cryptographic algorithms based on them. It briefly discusses the

3 Petr G. Klyucharev, Ph.D., Associate Professor of Information Security department, Bauman Moscow State Technical University, Moscow, Russia. E-mail: pk.iu8@yandex.ru

history of the theory of cellular automata and its applications in various scientific disciplines. The review of the works of a number of authors who proposed symmetric cryptographic algorithms and pseudorandom sequence generators based on one-dimensional cellular automata is presented. The security of such cryptographic algorithms turned out to be insufficient. The following is a review of articles devoted to the use of two-dimensional cellular automata for constructing ciphers (this approach gave the best results). Multidimensional cellular automata are also mentioned. The second part of the article will be devoted to a review of works devoted to the use of generalized cellular automata in cryptography — on the basis of such automata, it is possible to create symmetric encryption algorithms and cryptographic hash functions that provide a high level of security and high performance in hardware implementation (for example, on FPGA), as well as having fairly low requirements for hardware resources. In addition, an attention will be paid to interesting connections of generalized cellular automata, in the context of their use in cryptography, with the theory of expander graphs. Attention will also be paid to the security of cryptographic algorithms based on generalized cellular automata. The works devoted to the implementation of various cryptographic algorithms based on generalized cellular automata on FPGA and GPU will be mentioned. In addition, an overview of asymmetric cryptographic algorithms based on cellular automata will be given. The questions about the belonging of some problems on cellular automata and their generalizations to the class of NP-complete problems, as well as to some other complexity classes, will also be considered.

Keywords: cellular automation, stream cipher, block cipher, hash function. Acknowledgments: The reported study was funded by RFBR, project number 20-17-50258.

1. Von Neumann J. The general and logical theory of automata // Proc. Hixon Symposium on Cerebral Mechanisms in Behavior / Ed. by L. A. Jeffress. — New York, 1951. — P. 1-31.

2. Toffoli T., Margolus N. Mashiny kletochnykh avtomatov. — M. : Mir, 1991. — 280 p.

3. Adamatzky A. Game of Life Cellular Automata. — Springer London, 2010. — 579 p.

4. Ceccherini-Silberstein T., Coornaert M. Cellular Automata and Groups. — Springer Berlin Heidelberg, 2010. — 440 p.

5. Codd E., Ashenhurst R. Cellular Automata. — Academic Press, 1968. — 132 p.

6. Gutowitz H. Cellular Automata: Theory and Experiment. — MIT Press, 1991. — 483 p.

7. Ilachinski A. Cellular Automata: A Discrete Universe. — World Scientific, 2001. — 808 p.

8. Margenstern M. Small Universal Cellular Automata in Hyperbolic Spaces: A Collection of Jewels. — Springer Berlin Heidelberg, 2013. — 320 p.

9. Mcintosh H. One Dimensional Cellular Automata. — Luniver Press, 2009. — 280 p.

10. Rosin P., Adamatzky A., Sun X. Cellular Automata in Image Processing and Geometry. — Springer International Publishing, 2014. — 304 p.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

11. Wolfram S. A New Kind of Science. — Wolfram Media, 2002. — 1192 p.

12. Wolfram S. Cellular automata // Los Alamos Science. — 1983. — Vol. 9. — P. 2-21.

13. Packard N., Wolfram S. Two-dimensional cellular automata // Journal of Statistical Physics. — 1985. — Vol. 38. — P. 901-946.

14. Wolfram S. Cryptography with cellular automata // Lecture Notes in Computer Science. — 1986. — Vol. 218. — P. 429-432.

15. Wolfram S. Cellular automation supercomputing // High-speed computing: scientific applications and algorithm design / Ed. by Robert B. Wilhelmson. — University of Illinois Press, 1988. — P. 40-48.

16. Wolfram S. Random sequence generation by cellular automata // Advances in Applied Mathematics. — 1986. — Vol. 7. — P. 123-169.

17. Wolfram S. Cellular automata and complexity: collected papers. — Addison-Wesley Reading, MA, 1994. — Vol. 1. — 608 p.

18. Sarkar P. A brief history of cellular automata // Acm computing surveys (csur). — 2000. — Vol. 32, no. 1. — P. 80-107.

19. Schiff J. L. Cellular automata: a discrete view of the world. — John Wiley & Sons, 2011. — Vol. 45. — 272 p.

20. Zhukov A. E. Kletochnye avtomaty v kriptografii. Chast’ 1 // Voprosy kiberbezopasnosti. — 2017. — № 3(21). — P. 70-76.

21. Kudryavtsev V. B., Podkolzin A. S. Ob osnovnykh napravleniyakh v teorii odnorodnykh struktur // Diskretnaya matematika. — 1989. — T. 1, № 3. — P. 229-250.

22. Kudryavtsev V. B., Podkolzin A. S. Kletochnye avtomaty. // Intellektual’nye sistemy. — 2006. — T. 10, № 1-4. — P. 657-692.

23. Kudryavtsev V. B., Podkolzin A. S., Bolotov A. A. Osnovy teorii odnorodnykh struktur. — M.: Nauka, 1992. — 298 p.

24. Wolfram S. Cellular Automata And Complexity: Collected Papers. — CRC Press, 2018. — 608 p.

25. Termodinamika neobratimykh protsessov i nelineinaya dinamika / E.M. Kol’tsova, L.S. Gordeev, Tret’yakov Yu.D., Vertegel A.A. — M.: Yurlait, 2019. — 430 p.

26. Deutsch A., Dormann S. et al. Cellular automaton modeling of biological pattern formation. — Springer, 2005. — 464 p.

27. White S. H., Del Rey A. M., Sanchez G. R. Modeling epidemics using cellular automata // Applied mathematics and computation. — 2007. — Vol. 186, no. 1. — P. 193-202.

28. Menshutina N. V., Kolnoochenko A. V., Lebedev E. A. Cellular automata in chemistry and chemical engineering // Annual Review of Chemical and Biomolecular Engineering. — 2020. — Vol. 11. — P. 87-108.

29. Kier L., Seybold P., Cheng C. Modeling Chemical Systems Using Cellular Automata. — Springer, 2005. — ISBN: 9781402036576.

30. Andreeva O. V. Model’ i algoritmy dlya otsenki povrezhdennosti mikrostruktury poverkhnosti metallov i splavov po izobrazheniyam : Dis. kand. tekhn. nauk: 05.13.01 / Ol’ga Vyacheslavovna Andreeva ; Nizhegor. gos. tekhn. un-t im R.E. Alekseeva. — Nizhnii Novgorod, 2017. — 162 p.

31. Wagner D. F. Cellular automata and geographic information systems // Environment and planning B: Planning and design. — 1997. — Vol. 24, no. 2. — P. 219-234.

32. Batty M., Xie Y., Sun Z. Modeling urban dynamics through gis-based cellular automata // Computers, environment and urban systems.

— 1999. — Vol. 23, no. 3. — P. 205-233.

33. Torrens P. M., O’Sullivan D. Cellular automata and urban simulation: where do we go from here? — 2001.

34. Hoekstra A. G., Kroc J., Sloot P. M. Simulating complex systems by cellular automata. — Springer, 2010. — 384 p.

35. Zuse K. Calculating Space. MIT technical translation. — Massachusetts Institute of Technology, Project MAC, 1970. — 188 p.

36. Wolfram S. A Project to Find the Fundamental Theory of Physics. — Wolfram Media, Incorporated, 2020. — 770 p. — ISBN: 9781579550356.

37. Matyushkin I. V., Zapletina M. A. Obzor po tematike kletochnykh avtomatov na baze sovremennykh otechestvennykh publikatsii // Komp’yuternye issledovaniya i modelirovanie. — 2019. — № 1. — P. 9-57.

38. Gardner M. The fantastic combinations of John Conway’s new solitaire game FLifeL // Scientific American. — 1970. — Vol. 223. — P. 120-123.

39. Meier W., Staffelbach O. Analysis of pseudo random sequences generated by cellular automata // Workshop on the Theory and Application of of Cryptographic Techniques / Springer. — 1991. — P. 186-199.

40. Sarkar P. Hiji-bij-bij: A new stream cipher with a self-synchronizing mode of operation // International Conference on Cryptology in India / Springer. — 2003. — P. 36-51.

41. Joux A., Muller F. Two attacks against the hbb stream cipher // International Workshop on Fast Software Encryption / Springer. — 2005.

42. Karmakar S., Mukhopadhyay D., Chowdhury D. R. Cavium-strengthening trivium stream cipher using cellular automata. // J. Cell. Autom. — 2012. — Vol. 7, no. 2. — P. 179-197.

43. De Canniere C. Trivium: A stream cipher construction inspired by block cipher design principles // Information Security. — Springer, 2006. — P. 171-186.

44. Das S., Chowdhury D. R. Castream: A new stream cipher suitable for both hardware and software // International Conference on Cellular Automata / Springer. — 2012. — P. 601-610.

45. Bardell P. H. Analysis of cellular automata used as pseudorandom pattern generators // Proceedings. International Test Conference 1990 / IEEE. — 1990. — P. 762-768.

46. Fuster-Sabater A., Caballero-Gil P. On the use of cellular automata in symmetric cryptography // Acta Applicandae Mathematica. — 2006. — Vol. 93, no. 1. — P. 215-236.

47. Bouvry P., Seredynski F., Zomaya A. Y. Application of cellular automata for cryptography // International conference on parallel processing and applied mathematics / Springer. — 2003. — P. 447-454.

48. Tomassini M., Perrenoud M. Cryptography with cellular automata // Applied Soft Computing. — 2001. — Vol. 1, no. 2. — P. 151-160.

49. Henricksen M. A critique of some chaotic-map and cellular automata-based stream ciphers // Annual Asian Computing Science Conference / Springer. — 2009. — P. 69-78.

50. Bao F. Cryptanalysis of a partially known cellular automata cryptosystem // IEEE Transactions on Computers. — 2004. — Vol. 53, no. 11. — P. 1493-1497.

51. Random number generation — Wolfram Mathematica 7 documentation. — Access mode: http://reference.wolfram.com/mathematica/ tutorial/RandomNumberGeneration.html.

52. Mukhopadhyay D., RoyChowdhury D. Cellular automata: an ideal candidate for a block cipher // International Conference on Distributed Computing and Internet Technology / Springer. — 2004. — P. 452-457.

53. Achkoun K., Hanin C., Omary F. SPF-CA: A new cellular automata based block cipher using key-dependent S-boxes // Journal of Discrete Mathematical Sciences and Cryptography. — 2020. — Vol. 23, no. 8. — P. 1529-1544.

54. Seredynski M., Bouvry P. Block encryption using reversible cellular automata // International Conference on Cellular Automata / Springer. — 2004. — P. 785-792.

55. Seredynski M., Bouvry P. Block cipher based on reversible cellular automata // New Generation Computing. — 2005. — Vol. 23, no. 3. — P. 245-258.

56. Cellular automata based cryptosystem (CAC) / Subhayan Sen, Chandrama Shaw, Dipanwita Roy Chowdhuri et al. // International Conference on Information and Communications Security / Springer. — 2002. — P. 303-314.

57. Bao F. Cryptanalysis of a new cellular automata cryptosystem // Australasian Conference on Information Security and Privacy / Springer. — 2003. — P. 416-427.

58. DamgAard I. B. A design principle for hash functions // Conference on the Theory and Application of Cryptology / Springer. — 1989. — P. 416-427.

59. Daemen J., Govaerts R., Vandewalle J. A framework for the design of one-way hash functions including cryptanalysis of damgAard’s one-way function based on a cellular automaton // International Conference on the Theory and Application of Cryptology / Springer.

60. HCAHF: A New Family of CA-based Hash Functions / Anas Sadak, Fatima Ezzahra Ziani, Bouchra Echandouri et al. // International Journal of Advanced Computer Science and Applications. — 2019. — Vol. 10. — P. 12.

61. ElRakaiby M. M. Cryptographic hash function using cellular automata // International Journal of Computer Applications Technology and Research. — 2016. — Vol. 5, no. 5. — P. 238-240.

62. Jeon J.-C. Cellular automata based cryptographic hash function // Proceedings of the International Conference on Scientific Computing (CSC) / The Steering Committee of The World Congress in Computer Science, Computer . — 2011. — P. 1.

63. Jeon J.-C. One-way hash function based on cellular automata // IT Convergence and Security 2012. — Springer, 2013. — P. 21-28.

64. Cash: cellular automata based parameterized hash / Sukhendu Kuila, Dhiman Saha, Madhumangal Pal, Dipanwita Roy Chowdhury // International Conference on Security, Privacy, and Applied Cryptography Engineering / Springer. — 2014. — P. 59-75.

65. Rajeshwaran K., Kumar K. A. Cellular automata based hashing algorithm (cabha) for strong cryptographic hash function // 2019 IEEE International Conference on Electrical, Computer and Communication Technologies (ICECCT) / IEEE. — 2019. — P. 1-6.

66. A lightweight hash function based on cellular automata for mobile network / Xing Zhang, Qinbao Xu, Xiaowei Li, Changda Wang // 2019 15th International Conference on Mobile Ad-Hoc and Sensor Networks (MSN) / IEEE. — 2019. — P. 247-252.

67. Tanasyuk Y., Perepelitsyn A., Ostapov S. Parameterized fpga-based implementation of cryptographic hash functions using cellular automata // 2018 IEEE 9th International Conference on Dependable Systems, Services and Technologies (DESSERT) / IEEE. — 2018.

68. Sponge functions / Guido Bertoni, Joan Daemen, MichaJel Peeters, Gilles Van Assche // ECRYPT hash workshop / Citeseer. — Vol. 2007. — 2007.

69. Sukhinin B. M. Primenenie klassicheskikh i neodnorodnykh kletochnykh avtomatov pri postroenii vysokoskorostnykh generatorov psevdosluchainykh posledovatel’nostei // Proektirovanie i tekhnologiya elektronnykh sredstv. — 2009. — № 3. — P. 47-51.

70. Sukhinin B. M. Vysokoskorostnye generatory psevdosluchainykh posledovatel’nostei na osnove kletochnykh avtomatov // Prikladnaya diskretnaya matematika. — 2010. — № 2. — P. 34-41.

71. Sukhinin B. M. O vliyanii parametrov lokal’noi funktsii svyazi na raspredelenie znachenii yacheek dvoichnykh kletochnykh avtomatov // Ob»edinennyi nauchnyi zhurnal. — 2010. — № 8. — P. 39-41.

72. Sukhinin B. M. O lavinnom effekte v kletochnykh avtomatakh // Ob»edinennyi nauchnyi zhurnal. — 2010. — № 8. — P. 41-46.

73. Sukhinin B. M. O novom klasse generatorov psevdosluchainykh posledovatel’nostei na osnove kletochnykh avtomatov // Ob»edinennyi nauchnyi zhurnal. — 2010. — № 8. — P. 46-49.

74. Sukhinin B. M. Prakticheskie aspekty otsenki kachestva generatorov sluchainykh posledovatel’nostei s ravnomernym raspredeleniem // Ob»edinennyi nauchnyi zhurnal. — 2010. — № 8. — P. 49-55.

75. Sukhinin B. M. Issledovanie kharakteristik lavinnogo effekta v dvoichnykh kletochnykh avtomatakh s ravnovesnymi funktsiyami perekhodov // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. — 2010. — № 8.

76. Sukhinin B. M. Razrabotka generatorov psevdosluchainykh dvoichnykh posledovatel’nostei na osnove kletochnykh avtomatov // Nauka i obrazovanie. MGTU im. N.E. Baumana. Elektron. zhurn. — 2010. — № 9.

77. Sukhinin B. M. O nekotorykh svoistvakh kletochnykh avtomatov i ikh primenenii v strukture generatorov psevdosluchainykh posledovatel’nostei // Vestnik Moskovskogo gosudarstvennogo tekhnicheskogo universiteta im. N.E. Baumana. Seriya: Priborostroenie.

— 2011. — № 2. — P. 68-76.

78. Sukhinin B. M. Odnorodnye dvumernye bulevy kletochnye avtomaty i ikh svoistva primenitel’no k generatsii psevdosluchainykh posledovatel’nostei // Sistemy vysokoi dostupnosti. — 2011. — T. 7, № 2. — P. 39-41.

79. Sukhinin B. M. Razrabotka i issledovanie vysokoskorostnykh generatorov psevdosluchainykh ravnomerno raspredelennykh dvoichnykh posledovatel’nostei na osnove kletochnykh avtomatov : Dis. kand. tekhn. nauk: 05.13.17 / Boris Mikhailovich Sukhinin ; MGTU im. N.E. Baumana. — M., 2011. — 224 p.

80. Haldar T., Chowdhury D. R. Design of hash function using two dimensional cellular automata // Proceedings of the Fifth International Conference on Mathematics and Computing / Springer. — 2021. — P. 33-45.

81. Tanasyuk Y., Ostapov S. Development and research of cryptographic hash functions based on two-dimensional cellular automata // Informatyka, Automatyka, Pomiary w Gospodarce i Ochronie Srodowiska. — 2018. — Vol. 8.

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

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

1. понятие клеточного автомата

Понятие клеточного автомата не является новым. Оно описано во многих книгах [1, 9] и, более того, есть люди, которые посвятили клеточным автоматам всю жизнь . История клеточных автоматов начинается более полувека назад. Многие книги указывают, что клеточный автомат – это результат работы Джона фон Немана (John von Neumann) и Конрада Цузе (Konrad Zuse), которые в начале сороковых годов 20 века разработали в идею универсальной вычислительной среды для построения, анализа и сравнения характеристик алгоритмов [10]. Работы этих ученых базируются на исследованиях Станислава Улама (Stanislaw Ulam) [11]. Клеточный автомат — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Включает регулярную решетку ячеек, каждая из которых может находиться в одном из конечного множества состояний, таких как 1 и 0. Решетка может быть любой размерности. Для каждой ячейки определено множество ячеек, называемых окрестностью. К примеру, окрестность может быть определена как все ячейки на расстоянии не более 2 от текущей (окрестность фон Неймана ранга 2). Для работы клеточного автомата требуется задание начального состояния всех ячеек и правил перехода ячеек из одного состояния в другое. На каждой итерации, используя правила перехода и состояния соседних ячеек, определяется новое состояние каждой ячейки. Обычно правила перехода одинаковы для всех ячеек и применяются сразу ко всей решетке. Основное направление исследования клеточных автоматов — алгоритмическая разрешимость тех или иных задач. Также рассматриваются вопросы построения начальных состояний, при которых клеточный автомат будет решать заданную задачу. На сегодняшний день клеточные автоматы нашли широкое распространение во всех сферах человеческой деятельности: математика, физика, биология [12], химия, механика, криптография [13], гидродинамика, газодинамика [14, 15] и т.д. Основным направлением применения клеточных автоматов является моделирование динамических процессов, например, движение толпы [16] или распространение тепловых потоков [17]. Некоторые ученые считают, что клеточные автоматы – это принцип, по которому сама природа действует в повседневной жизни. Наиболее подробно об этом описано в книге Стивена Вольфрама (Stephen Wolfram) «A New Kind of Science» . Принцип клеточных автоматов основан на локальных взаимодействиях. Все элементы в любой рассматриваемой системе действуют по одинаковым принципам. В совокупности результаты работы простых правил, на которых основаны взаимодействия, позволяют получать сложное поведение. Джон фон Нейман дает следующее определение клеточным автоматам: «Клеточные автоматы являются дискретными динамическими системами, поведение которых полностью определяется в терминах локальных зависимостей. В значительной степени также обстоит дело для большого класса непрерывных динамических систем, определенных уравнениями в частных производных. В этом смысле клеточные автоматы в информатике являются аналогом физического понятия «поля»… клеточный автомат может мыслиться как стилизованный мир. Пространство представлено равномерной сеткой, каждая ячейка или клетка которой содержит несколько битов данных; время идет вперед дискретными шагами, а законы мира выражаются единственным набором правил, скажем, небольшой справочной таблицей, по которой любая клетка на каждом шаге вычисляет свое новое состояние по состояниям ее близких соседей. Таким образом, законы системы являются локальными и повсюду одинаковыми. «Локальный» означает, что для того, чтобы узнать, что произойдет здесь мгновение спустя, достаточно посмотреть на состояние ближайшего окружения: никакое дальнодействие не допускается. «Одинаковость» означает, что законы везде одни и те же: я могу отличить одно место от другого только по форме ландшафта, а не по какой-то разнице в законах» Формально клеточный автомат можно определить как набор , где G – метрика поля, на котором действует клеточный автомат; Z – множество состояний каждой клетки; N – окрестность клетки, которая влияет на состояние данной клетки; f – правила клеточного автомата, которые в математическом виде могут быть записано Z x Z ^ |N| -> Z. Свойствами клеточного автомата являются: локальность правил, однородность системы, конечность множества состояний клетки, одновременность изменений для всех клеток. Более подробно и формально основные свойства классического клеточного автомата приведены в работе [18]. Клеточные автоматы могут работать в нескольких измерениях: он может обрабатывать вектор состояний клеток, плоскость или трехмерную модель. Во всех случаях для визуализации работы автомата часто добавляют дополнительное измерение – время, которое позволяет оценить изменения состояний поля в динамике. Наиболее известным приложением клеточных автоматов можно считать игру «Жизнь» Джона Конвея (John Conway) [10, 19]. Существует несколько разновидностей клеточных автоматов. Ниже перечислены их основные типы из книги Стивена Вольфрама «A New Kind of Science» .

История

Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решеточную модель . В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого «запаса частей», из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решетке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий «внутри» клеточного автомата с окрестностью, включающей непосредственно прилегающие ячейки, и имеющего 29 состояний. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя. Также в 1940-е годы, Норберт Винер и Артуро Розенблют (англ. Arturo Rosenblueth) разработали клеточно-автоматную модель возбудимой среды. Целью было математическое описание распространения импульса в сердечных нервных узлах. Их оригинальная работа продолжает цитироваться в современных исследованиях по аритмии и возбудимым средам. В 1960-е годы клеточные автоматы изучались как частный тип динамических систем, и впервые была установлена их связь с областью символьной динамики. В 1969 году Г. А. Хедланд (англ. Gustav A. Hedlund) провел обзор результатов, полученных в этом направлении. Наиболее значимым результатом явилось описание набора правил клеточного автомата как множества непрерывных эндоморфизмов в сдвиговом пространстве. В 1970-е получила известность двухмерная клеточно-автоматная модель с двумя состояниями, известная как игра «Жизнь». Изобретенная Джоном Конвеем и популяризованная Мартином Гарднером, она использует следующие правила: если клетка имеет двух «живых» соседей, она остается в прежнем состоянии. Если клетка имеет трех «живых» соседей, она переходит в «живое» состояние. В остальных случаях клетка «умирает». Несмотря на свою простоту, система проявляет огромное разнообразие поведения, колеблясь между очевидным хаосом и порядком. Одним из феноменов игры «Жизнь» являются глайдеры — сочетания клеток, движущиеся по сетке как единое целое. Возможно построить автомат, в котором глайдеры будут выполнять некоторые вычисления, и впоследствии было показано, что игра «Жизнь» может эмулировать универсальную машину Тьюринга. В 1969 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой. В 1983 Стивен Вольфрам опубликовал первую из серии статей, исследующих очень простой, но до сих пор неизученный класс клеточных автоматов, называемых элементарными клеточными автоматами. Неожиданная сложность поведения этих простых автоматов привела Вольфрама к предположению, что сложность естественных систем обусловлена сходным механизмом. Кроме того, в течение этого периода Вольфрам формулирует концепцию истинной случайности и вычислительной неприводимости, и выдвигает предположение, что Правило 110 может быть универсальным — факт, доказанный в 1990 году ассистентом Вольфрама Мэтью Куком. В 1987 году Брайан Сильверман (англ. Brian Silverman) предложил клеточный автомат Wireworld. В 2002 году Вольфрам публикует 1280-страничный текст «Наука нового типа» (A New Kind of Science), где широко аргументирует, что достижения в области клеточных автоматов не являются изолированными, но весьма устойчивы и имеют большое значение для всех областей науки. 11-го ноября 2002 года Пауль Чепмен (англ. Paul Chapman) построил образец Жизни, который является РММ (Регистровой Машиной Минского). Фактически РММ эквивалентна машине Тьюринга. Первая версия образца была большой (268’096 живых ячеек на площади 4,558 x 21,469 клеток) и медленной (20 поколений/сек при использовании Life32 Иогана Бонтеса (англ. Johan Bontes) на 400 MHz AMD K6-II). Таким образом, в игре Жизнь можно выполнить любой алгоритм, который можно реализовать на современном компьютере.

Математическое определение

Двумерный клеточный автомат можно определить как множество конечных автоматов на плоскости, помеченных целочисленными координатами (i, j), каждый из которых может находиться в одном из состояний : . Изменение состояний автоматов происходит согласно правилу перехода , где — некоторая окрестность точки . К примеру, окрестность фон Неймана определяется как , а окрестность Мура . Число всех возможных правил перехода определяется числом состояний и количеством соседей n и составляет

Классификация

Классификация по типам поведения

Понятие клеточного автомата. Виды и последовательности клеточных автоматовПравило 40 (Класс 1) со случайными начальными условиями. Как видно, информация быстро исчезает в этой системе. Понятие клеточного автомата. Виды и последовательности клеточных автоматовПравило 3 (Класс 2) со случайными начальными условиями. Очевидно появление периодических структур Понятие клеточного автомата. Виды и последовательности клеточных автоматовПравило 18 (Класс 3) со случайными начальными условиями. Видно, что начальные условия порождают хаотические движения внутри системы. Понятие клеточного автомата. Виды и последовательности клеточных автоматовПравило 193 (Класс 4) со случайными начальными условиями. Можно увидеть порождение устойчивых структур (колонка белых треугольников) и взаимодействие таких структур в других частях изображения. Стивен Вольфрам в своей книге A New Kind of Science предложил 4 класса, на которые все клеточные автоматы могут быть разделены в зависимости от типа их эволюции. Классификация Вольфрама была первой попыткой классифицировать сами правила, а не типы поведения правил по отдельности. В порядке возрастания сложности классы выглядят следующим образом:

  • Класс 1: Результатом эволюции почти всех начальных условий является быстрая стабилизация состояния и его гомогенность. Любые случайные конструкции в таких правилах быстро исчезают.
  • Класс 2: Результатом эволюции почти всех начальных условий является быстрая стабилизация состояния, либо возникновение колебаний. Большинство случайных структур в начальных условиях быстро исчезает, но некоторые остаются. Локальные изменения в начальных условиях оказывают локальный характер на дальнейший ход эволюции системы.
  • Класс 3: Результатом эволюции почти всех начальных условий являются псевдо-случайные, хаотические последовательности. Любые стабильные структуры, которые возникают почти сразу же уничтожаются окружающим их шумом. Локальные изменения в начальных условиях оказывают широкое, неопределяемое влияние на ход всей эволюции системы.
  • Класс 4: Результатом эволюции почти всех правил являются структуры, которые взаимодействуют сложным и интересным образом с формированием локальных, устойчивых структур, которые способны выживать длительное время. В результате эволюции правил этого класса могут получаться некоторые последовательности Класса 2, описанного выше. Локальные изменения в начальных условиях оказывают широкое, неопределяемое влияние на ход всей эволюции системы. Некоторые клеточные автоматы этого класса обладают свойством универсальности по Тьюрингу. Последний факт был доказан для Правила 110 и игры «Жизнь».

Такого рода определения носят по большей части качественный характер и их можно по-разному интерпретировать. Вот что Вольфрам говорит об этом:

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

Оригинальный текст (англ.)

Тоталистичные клеточные автоматы

Существует специальный класс клеточных автоматов, называемых тоталистичными. На каждом шаге эволюции клеточного автомата значение ячейки равно какому-либо целому числу (обычно выбираемого из конечного множества), а новое состояние клетки определяется суммой значений клеток-соседей и, возможно, предыдущим состоянием клетки. Если состояние клетки на новом шаге зависит от ее предыдущего состояния, то такой клеточный автомат называется внешним тоталистичным. Игра Жизнь является примером внешнего тоталистического клеточного автомата с набором значений ячеек >.

Термин тоталистичный происходит от английского totalistic. В свою очеред total может быть переведено как сумма, что и отражено в принципе действия этого типа автоматов, когда новое значение клетки зависит от суммы значений других клеток.

Связанные определения клеточных автоматов

Существует множество возможных обобщений концепций клеточных автоматов.

Понятие клеточного автомата. Виды и последовательности клеточных автоматов Понятие клеточного автомата. Виды и последовательности клеточных автоматовПонятие клеточного автомата. Виды и последовательности клеточных автоматов

Клеточный автомат, работающий на сетке, компонентами которой являются шестиугольники, а не квадраты (правило 34/2)

Один из них — использование сетки не с квадратами (гиперкубами в многомерном случае), а с другими геометрическими фигурами в ее основе. Например, если поле представлено шестиугольным паркетом, то шестиугольники будут клетками. Однако иногда такие клеточные автоматы оказывались идентичными клеточным автоматам на сетке с квадратными клетками, только при этом было необходимо ввести специальные правила отношений с клетками-соседями. Другой способ обобщения — использование нерегулярной сетки(например, в виде Мозаики Пенроуза).

Еще один способ — использование вероятностных правил. Такие клеточные автоматы называются стохастическими. В таких системах задается вероятность, что на следующем шаге клетка сменит свой цвет на другой. Или, например, в игре «Жизнь» добавляется правило, что клетка с определенной вероятностью может изменить свой цвет на противоположный, а другие правила этого клеточного автомата остаются без изменений.

Определение соседства клетки может меняться с течением времени и/или пространства. Например, на первом шаге соседями будут горизонтально смежные клетки, а на другом — вертикально смежные.

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

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

Свойство обратимости

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

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

Обратимые клеточные автоматы часто используют для моделирования таких физических феноменов, как динамика жидкости и газа, поскольку они подчиняются законам термодинамики. Такие автоматы специально создаются обратимыми. Такие системы изучались Томасо Тоффоли (Tommaso Toffoli) и Норманом Марголусом (Norman Margolus). Существует несколько типов обратимых конечных автоматов. Наиболее известными являются клеточный автомат второго порядка и блочный клеточный автомат. Обе эти модели следуют несколько модифицированному варианту определения клеточного автомата, однако доказано, что они могут быть эмулированы традиционным клеточным автоматом со значительно большим размером окрестности и числом состояний. Также, было доказано, что любой обратимый клеточный автомат может быть сэмулирован блочным клеточным автоматом.

1.1 Стандартные клеточные автоматы

Стандартные клеточные автоматы на основе классического определения.

Клетки поля такого автомата изменяют состояние в зависимости от

состояний соседних клеток, и, таким образом, поле изменяет свое состояние.

Примеры стандартных одномерных клеточных автоматов представлены на

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Рис. 1. Клеточные структуры, созданные с помощью стандартных клеточных автоматов

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

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

1.2 Мобильные автоматы

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

1.3 Тьюринговые машины

Тьюринговые машины наподобие мобильного клеточного автомата имеет только одну активную клетку. Дополнительное условие – определение

нескольких состояний у активной клетки, как показано на рис. 3.

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

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

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

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

1.4. Системы подстановок

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

1.5. Последовательные подстановочные системы

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

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

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

1.6 Системы тэгов

Правила, которые удаляют элементы из начала цепочки клеток и добавляют другие клетки в конец цепочек, называются системами тэгов. Пример представлен на рис. 6.

1.7 Цикличные системы тэгов

Цикличность системы тэгов может достигаться за счет поочередного использования разных систем правил. В результате характер поведения клеточного автомата становится специфическим, что видно на рис. 7

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Рис. 7. Структура, созданная с помощью цикличной системы тэгов

Рис. Об этом говорит сайт https://intellect.icu . 8. Структура, созданная с помощью регистровой машины

1.8 Регистровые машины

Регистровые машины выполняют заданную программу. При успешном выполнении элемента программы происходит заданный переход, иначе

переход на следующий элемент. Пример приведен на рис. 8.

1.9 Символьные системы

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

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Рис. 9. Структура, созданная с помощью символьной системы

2. Клеточный автомат с метками

Понятие клеточного автомата с метками введено автором данной работы. Причиной его создания являлась необходимость достижения

заданных характеристик клеточных автоматов при разработке алгоритмов процесса распознавания текста. Как будет показано далее, это понятие

позволяет эффективно реализовать алгоритмы выделения признаков символов.

В процессе работы над дисертацией – анализа литературы – обнаружено понятие памяти в теории тьюринговых машин [20]. Оно определяет, что

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

ленты машины или передвижения ее головки. Данное понятие при введении некоторых ограничений и перехода на теорию клеточных автоматов может

быть также сведено к клеточным автоматам с метками. Принцип клеточной системы с метками заключается в ассоциации

каждой клетки поля с одним или несколькими метками.

Примером клеточного автомата с метками может служить набор: поле, на котором определены только клетки черного и белого цветов, метка,

которая может присутствовать или отсутствовать в клетках поля, и правила, учитывающие наличие меток у соседних клеток. В случае определения одной

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

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

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Рис. 10. Пример правила клеточного автомата с метками

В данном примере используется правило, основанное на восьми соседях. Без меток количество вариантов подобных правил (в случае определения

только двух цветов клеток) будет 2^10= 1024 (девять клеток условий и одна — результата). Добавляя метку, получится (2 · 2)^10= 1024^2= 1 048 576

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

10, номером может служить 1:340 (или в двоичном виде 0000000001:0101010100, где каждая цифра определяет состояние клетки,

клетки нумеруются слева направо сверху вниз), где первое число определяет правило преобразования цвета, а второе число – правило изменения метки.

Правило для поля, на котором определено более одной метки, нумеруется аналогичным образом: для правила с двумя метками – x : y : z,

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

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

заданного изображения, данный автомат позволяет определить некоторые свойства данного изображения и выделить его характерные признаки без

Клеточный автомат с метками – это набор . Описание каждого элемента представлено ниже.

1. G – конечное дискретное метрическое множество, гарантирующее конечность расстояний между клетками.

2. M – конечное множество меток, определенное для каждой клетки.

3. Z – конечный набор состояний клеток.

4. N – конечное множество, определяющее окрестность клетки таким образом, что каждый элемент множества позволяет определить соседа для

каждой клетки. |N| – количество соседних клеток, которые влияют на состояние данной.

5. f – правила клеточного автомата, соответствующие математической функции переходов:

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

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

По определению клеточный автомат задается четырьмя элементами [18]. Элементы G и N клеточного автомата с метками

соответствуют классическим элементам G* и N*.

Введем Z^ = Z x C таким образом, что |Z^| = |Z| x |C|. Множество Z^ будет соответствовать Z* классического определения клеточного автомата,

так как оно является конечным и определяет все варианты состояний клетки автомата.

Аналогично, f^ = (Z^ x Z^ )^ |N| -> Z^ будет соответствовать f*, так как учитываются все состояния на первом и втором временном слое.

Таким образом, получен набор клеточного автомата, в котором выполняются все свойства: локальность правил (обеспеченное N),

однородность системы на основе метрики G, конечность множества

состояний клетки Z^, одновременность изменений для всех клеток,гарантируемое набором правил f^.

Пример клеточного автомата с метками

Рассмотрм пример клеточного автомата с метками «шахматная доска». Задача автомата «шахматная доска» заключается в отрисовке

чередующихся черно-белых точек на белом изображении. Для выполнения задачи клеточному автомату с метками «шахматная

доска» достаточно восьми правил: 0:257, 0:65, 0:321, 1:52, 513:52, 256:52, 64:52, 320:52 (нерассмотренные состояния девяти исходных клеток не

изменяют состояние результирующей клетки). Эти правила изображены на рис. 11

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Рис. 11. Правила клеточного автомата «шахматная доска», правила:

а – 0:257, б – 0:65, в – 0:321, г – 1:52, д – 513:52, е — 256:52, ж – 64:52, з – 320:52

Для начала работы автомата необходимо поставить метку на стартовой точке поля. Результат работы автомата на шагах 1, 3, 5, 10, 20 изображены на

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Рис. 12. Результат работы клеточного автомата с метками «шахматная доска» на шагах

: а – первом, б – третьем, в – пятом, г – десятом, д – двадцатом

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

2.3. Последовательность клеточных автоматов

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

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

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

Более того, для решения части задач может потребоваться последовательность из клеточных автоматов, каждый из которых решает

Последовательность клеточных автоматов – это совокупность клеточных автоматов, каждый из которых основан на специфических правилах.

Клеточные автоматы в последовательности запускаскаются в заданной последовательности и каждый очередной клеточный автомат начинает

работу на поле, который был сформирован предыдущим клеточным автоматом в последовательности.

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

последовательности клеточных автоматов помогает обходиться небольшим числом правил для каждого клеточного автомата при решении

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

одинаковый набор M возможных меток клеток поля каждого автомата. Это поможет поддерживать последовательность в работоспособном состоянии.

Элементарные клеточные автоматы

Простейшим нетривиальным клеточным автоматом будет одномерный клеточный автомат с двумя возможными состояниями, а соседями клетки будут смежные с ней клетки. Такие автоматы называются элементарными. Три клетки (центральная, ее соседи) порождают комбинаций состояний этих трех клеток. Далее на основе анализа текущего состояния тройки принимается решение о том, будет ли центральная клетка белой или черной на следующем шаге. Всего существует возможных правил. Эти 256 правил кодируются в соответствии с кодом Вольфрама — стандартному соглашению, правилу, которое было предложено Вольфрамом. В некоторых статьях эти 256 правил были исследованы и сравнены. Наиболее интересными представляются правила с номерами 30 и 110. На двух изображениях ниже представлены эволюции указанных правил. Начальное условие для каждого автомата — одна центральная клетка — черная, остальные — белые. По оси откладывается дискретное время, а по оси откладываются состояния клеток автомата.

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Правило 30

Текущее состояние 111 110 101 100 011 010 001 000
Новое состояние центральной клетки 0 0 0 1 1 1 1 0

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Правило 110

Текущее состояние 111 110 101 100 011 010 001 000
Новое состояние центральной клетки 0 1 1 0 1 1 1 0

Понятие клеточного автомата. Виды и последовательности клеточных автоматов

Правило 161

Текущее состояние 111 110 101 100 011 010 001 000
Новое состояние центральной клетки 1 0 1 0 0 0 0 1

Правило 30 проявляет поведение класса 3, что означает, что эволюция простых начальных условий приводит к хаотической, кажущейся случайной динамике.

Правило 110, как и игра «Жизнь» проявляет поведение класса 4, которое не является полностью случайным, но при этом отсутствует периодичность. При этом возникают структуры, которые взаимодействуют друг с другом неочевидным, сложным образом. Во время написания книги A New Kind of Science ассистент Стивена Вольфрама Мэттью Кук в 1994 году доказал, что некоторые из порождаемых правилом структур достаточно разнообразны, чтобы обладать полнотой по Тьюрингу. Этот факт представляет собой интерес, потому что в своей сути Правило 110 является простой одномерной системой. Также это хороший аргумент в пользу того, что системы класса 4 являются в некотором смысле универсальными. Мэттью Кук представил свое доказательство на конференции Института Санта-Фе в 1998 году, но Вольфрам запретил включать это доказательство в бумажную версию материалов конференции, потому что не хотел, чтобы оно было опубликовано до издания книги A New Kind of Science. В 2004 году доказательство Кука было опубликовано в журнале Вольфрама «Complex Systems»(выпуск 15, том 1), через 10 лет после того как Кук впервые представил его. Правило 110 было основой для построения наименьших Тьюринг-машин.

Правило 161 порождает фрактальные структуры, которые можно увидеть на рисунке. Можно видеть вложенные подобные треугольники.

Пространство правил клеточных автоматов

Простейший одномерный клеточный автомат задается с помощью восьми бит. Таким образом, все правила клеточного автомата располагаются на вершинах 8-мерного единичного куба. Такой гиперкуб является пространством всех возможных одномерных клеточных автоматов. Для одномерного клеточного автомата, где соседями одной клетки являются соседи ее соседей необходимо бита и пространством всех возможных правил будет 32-мерный единичный куб. Расстоянием между двумя клеточными автоматами может считаться количество шагов, необходимых для того, чтобы перейти от одного правила к другому по ребрам многомерного куба. Такое расстояние называется расстоянием Хэмминга.

Исследования пространства правил клеточных автоматов позволяет ответить нам на вопрос, который ставится следующим образом: близко ли расположены относительно друг друга правила, которые порождают похожие друг на друга(в плане динамики) клеточные автоматы. Графическое представление гиперкуба высокой размерности на двумерной плоскости — весьма сложная задача. Однако на двумерной плоскости можно легко представить процесс эволюции одномерного клеточного автомата. При этом по одной оси откладывается дискретное время, а по другой — соответствующие состояния клеточного автомата. В случае двумерного клеточного автомата можно добавить третью ось. При этом две оси будут соответствовать состояниям клеточного автомата, а третья — дискретному времени. Процесс эволюции такого автомата представляет собой некоторую трехмерную фигуру в пространстве. Подробнее такие эксперименты описаны в книге Стивена Вольфрама A New Kind of Science. Исследования показали, что клеточные автоматы, классифицированные как класс 1, имели меньшее количество единичных бит в строке правила и они были сконцентрированы примерно в одном месте на гиперкубе. В то же время правила класса 3 имели большее (порядка 50 %) количество единичных бит.

Для пространств правил клеточных автоматов большей размерности было показано, что правила класса 4 расположены между классами 1 и 3.

Это наблюдение приводит к понятию грани хаоса применительно к теории клеточных автоматов и напоминает понятие фазового перехода в термодинамике.

Клеточные автоматы в естественной среде

Узор на поверхности раковины Conus textile формируется по механизму клеточного автомата

Некоторые живые организмы проявляют свойства клеточных автоматов. Раскраска раковин ряда морских моллюсков, например, родов Conus или Cymbiola, генерируется естественным одномерным клеточным автоматом, результат эволюции которого похож на Правило 30. Их пигментные клетки располагаются тонкой полоской вдоль края раковины. Секреция пигмента каждой клетки зависит от активирующей и ингибиторной активности соседних клеток. В процессе роста раковины полоса клеток формирует цветной узор на ее поверхности. Окраска чешуек ящерицы Timon lepidus описывается стохастическим клеточным автоматом .

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

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

Понятие клеточного автомата. Виды и последовательности клеточных автоматовПонятие клеточного автомата. Виды и последовательности клеточных автоматов

Компьютерное моделирование реакции Белоусова — Жаботинского в тонком слое жидкости в чашке Петри.

Реакция Белоусова — Жаботинского представляет собой пространственно-временной химический осциллятор, который может быть смоделирован клеточным автоматом. В 1950-х годах А. М. Жаботинский, продолжая работу Б. П. Белоусова, обнаружил, что тонкий однородный слой смеси определенных химических веществ способен образовывать движущиеся геометрические узоры, такие как концентрические круги и спирали.

Клеточные автоматы также используются в моделировании экосистем и популяционной динамики .

Применения клеточных автоматов

Компьютерные процессоры

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

Криптография

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

Моделирование физических процессов

Клеточные автоматы используются в компьютерном моделировании процессов рекристаллизации .

Фундаментальная физика

Как указывает Andrew Ilachinski в своей книге Клеточные автоматы (оригинальное название — Cellular Automata), многие исследователи задавались вопросом является ли наша вселенная клеточным автоматом. Andrew Ilachinski указывает, что смысл этого вопроса может быть понят лучше с помощью простого наблюдения, которое можно произвести следующим образом. Рассмотрим эволюцию Правила 110: если бы это было что-то вроде «инопланетной физики» (оригинал — alien physics), то как можно было бы описать возникающие закономерности? Если бы вы не знали, как получены конечное изображение эволюции автомата, вы могли бы предположить, что данный рисунок отражает некоторым образом движение каких-либо частиц. Тогда делается следующее предположение: возможно, наш мир, хорошо описываемый физикой элементарных частиц, может быть клеточным автоматом на фундаментальном уровне.

Однако, законченная теория, базирующаяся на этих утверждениях все еще далека от того, чтобы считаться законченной (равно как и сколько-нибудь общепринятой). Увлекаясь и развивая эту гипотезу, исследователи приходят к интересным заключениям, как можно использовать эту теорию для описания мира вокруг. Марвин Минский, пионер ИИ, разработал способ для изучения взаимодействия частиц с помощью четырехмерного клеточного автомата. Конрад Цузе, известный как создатель первого действительно работающего программируемого компьютера Z3 занимался клеточным автоматами на нерегулярных решетках для исследования вопроса информационного содержания частиц. Эдвард Фредкин представил то, что он называет «гипотезой конечной вселенной» (оригинал — finite nature hypothesis). Смысл гипотезы заключается в том, что

…всякая величина в физике, включая время и пространство, является конечной и дискретной.

Оригинальный текст

Фредкин и Вольфрам — последовательные приверженцы цифровой физики.

Герард ’т Хоофт разработал теорию квантовой физики, основывающуюся на клеточных автоматах[7

Вау!! �� Ты еще не читал? Это зря!

  • представление конечных автоматов ,
  • простейший автомат , детерминированный автомат ,
  • конечные автоматы , понятие автомата ,
  • эквивалентность конечных автоматов , теорема мура ,
  • Конечные автоматы как структуры данных — Индексируйте ключей с помощью автоматов
  • конечные автоматы , виды конечных автоматов ,
  • Автомат Мили
  • Автомат Мура
  • JFLAP — кроссплатформенная программа симулятор (автоматов, машины Тьюринга, грамматик)
  • Автоматное программирование
  • Sequential Function Chart
  • Компилятор
  • Транслятор
  • Сети Петри
  • Секвенциальная логика (Последовательностная логика)
  • Таблица принятия решений
  • Суффиксный автомат

Игра «Жизнь» Конвея и другие клеточные автоматы

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

Ответы на вопросы для самопроверки пишите в комментариях, мы проверим, или же задавайте свой вопрос по данной теме.

Исследование процесса формирования общественного мнения с использованием клеточных автоматов

Клименко, О. А. Исследование процесса формирования общественного мнения с использованием клеточных автоматов / О. А. Клименко, А. А. Патухин. — Текст : непосредственный // Молодой ученый. — 2014. — № 16 (75). — С. 161-164. — URL: https://moluch.ru/archive/75/12873/ (дата обращения: 30.10.2023).

Общественное мнение существовало во все исторические эпохи, однако сам термин, обозначающий этот уникальный феномен общественной жизни человечества, появился в Англии в XII веке. Первые попытки специального исследования такого феномена как «общественное мнение» были предприняты в конце XVIII — начале XIX вв. английским философом Иеремией Бентамом (1748–1832 гг.), который подчеркивал значимость общественного мнения как способа социального контроля над деятельностью государства со стороны общественности и указывал на роль прессы как основного средства, с помощью которого можно одновременно выражать и формировать общественное мнение.

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

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

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

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

Исходным пунктом формирования общественного мнения является информированность по проблеме, которая зависит от социально-экономических и политических условий жизни общества. Информированность может быть охарактеризована диапазоном обладания знаниями и их глубиной (количеством и качеством информации). Еще одна характеристика — компетентность общественного мнения. Здесь огромную роль играют СМИ и Интернет.

Этапы формирования общественного мнения:

1) возникновение чувств и представлений в сфере индивидуального сознания (первичное ознакомление с проблемой);

2) истолкование мнений посредством обмена информацией, обсуждение проблемы;

3) распространение сложившегося типизированного мнения в определенном социальном ареале;

4) воздействие общественного мнения на поведение людей, социальную практику.

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

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

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

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

А1 — аксиома восприятия. Чем выше уровень когнитивной вовлеченности индивида, тем более вероятно, что он будет воспринимать, т. е. обращать внимание и понимать, политические сообщения, связанные с тем или иным вопросом.

А2 — аксиома сопротивления. Люди склонны критически воспринимать аргументы, не согласующиеся с их политическими предрасположенностями, но только лишь в той мере, в какой они обладают контекстной информацией, необходимой для понимания отношений между этими аргументами и своими политическими предрасположенностями.

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

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

В психологической литературе об изменении общественного мнения также отмечается, что индивиды обычно затрудняются объяснить значение тех убеждающих сообщений, с которыми им доводится сталкиваться [2]. Решая, какую им занять позицию по определенному вопросу, люди обычно полагаются на «подсказки» об источниках сообщения.

А3 — аксиома доступности. Чем ближе по времени данное представление было актуализировано, обсуждалось или обдумывалось, тем меньше времени требуется для актуализации этого и аналогичных представлений в памяти, сознании.

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

А4 — аксиома реакции. Индивиды отвечают на вопросы интервью, обдумывая только те суждения, которые оказываются немедленно доступны или мобилизованы в их сознании.

Основные аксиомы ВПФ-модели (Восприятие — Принятие — Формулировка) позволяют сформулировать автору [3] четкие выводы о том, как изменяются установки:

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

2. Распространение неконсистентного сообщения средней интенсивности приводит к формированию немонотонного паттерна изменения установок, при котором чаще всего изменяются установки граждан со средним уровнем осведомленности.

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

4. Изменение установок по менее знакомым вопросам, по сравнению с более знакомыми, также в большей степени затрагивает более осведомленных людей.

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

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

Исследование общественного мнения.

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

Вместе с тем, при изучении общественного мнения используются также разновидности фокус-групп и глубинные интервью, которые относят к качественным методам. Это менее традиционный подход, но активно внедряемый психологами и социологами в последнее время. Качественные методы менее стандартизованы, в большей степени основаны на интуиции, опыте самого исследователя, чем количественные методы. Они часто оказываются более эффективными по отношению к таким изменчивым явлениям, как динамика целей, состояний, настроений и т. п. В данном подходе исследователь скорее отвечает на вопросы: «почему» и «как». Исследователи в данном случае пытаются понять, почему люди мыслят так или иначе, как они делают свой выбор, какова логика их рассуждений, а также какими чувствами сопровождаются эти процессы. Сложность интерпретации и анализа данных качественного исследования состоит в том, что необходимо улавливать эти групповые мнения и умонастроения, не «скатываясь», на трактовку индивидуального сознания.

Однако помимо традиционного исследования общественного мнения применялись попытки математического моделирования общественного мнения. В частности, в книге «Математические модели социальных систем» [1] приводится модель формирования общественного мнения, сочетающая элементы полевой и стохастической моделей. Предполагается, что общественное мнение α может выражать точку зрения α = +1, либо допускать противоположное воззрение α = — 1. Формирование общественного мнения можно представить как аналог броуновского движения, в котором участвуют индивиды, взаимодействующие посредством поля коммуникации. Это поле учитывает пространственное распределение мнений индивидов, имеет определенное время жизни, отражающее эффект коллективной памяти, и распространяется в обществе, моделируя перенос информации.

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

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

Более формализовано клеточный автомат можно определить как математических объект с дискретными пространством и временем. Каждое положение в пространстве представлено отдельной клеткой, каждый момент времени отображается дискретным временным шагом (поколением). Состояние каждой клетки определяется простыми правилами взаимодействия, которые предписывают изменение состояния клетки в следующем такте.

В исследуемой задаче моделирования изменения общественного мнения участвуют «клетки-индивиды», а и их состояние — это возможная смена мнения. На данном этапе исследования рассматривается упрощенная модель, в которой исследуется процесс смены мнения по отношению к одной проблеме. Мнения могут быть отрицательные, нейтральные и положительные. «Клетки-индивиды» не перемещаются, потому что это привело бы к неправильным результатам анализа мнений, окружающих индивида. За основу модели была взята игра «Жизнь». Поле проверки окружения увеличено с 3х3 до 5х5. Анализ окружения тоже претерпел изменения: поле увеличено, следовательно, число возможных соседей возросло с 8 до 24, и прежние правила становятся непригодными. Теперь анализ окружения построен по принципу «разности мнений» в окружении. Если индивида с положительным отношением по рассматриваемому вопросу окружают 5 единомышленников и 3 индивида с противоположным мнением, то разность мнений будет равна 2 в сторону первых, однако это приведет к смене мнения на нейтральное (если бы соотношение было бы не 5 и 3, а 8 и 3, то разность стала бы равной 5 и это привило бы к сохранению мнения). При составлении правил для исследуемой модели можно руководствоваться аксиомами, предложенными Цаллером. Кроме того, при назначении коэффициентов для смены состояния необходимо учитывать факторы, влияющие на мнение индивида по тому или иному вопросу. В программе это может быть легко реализовано заданием нужного значения для каждого частного случая (например, влияние традиций, религии или идеологии для конкретного региона).

Правила смены мнения можно предложить следующие:

— если разность (Положительное_отношение — Отрицательное_отношение) больше 4, тогда цвет клетки соответствует Положительному_отношению;

— если разность (Отрицательное_отношение — Положительное_отношение) больше 4 тогда цвет клетки соответствует Отрицательному_отношению;

— если разность (Положительное_отношение — Отрицательное_отношение) положительна, но меньше 3, ИЛИ разность (Отрицательное_отношение — Положительное_отношение) положительна, но меньше 3, тогда цвет, приобретаемый клеткой на следующем шаге, Нейтральное_отношение.

Эксперимент заключается в проведении нескольких запусков программы с разными начальными данными и сравнении результатов. В ходе эксперимента были получены следующие результаты:

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

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

— если начальная генерация модели не предусматривает наличие нейтрального мнения, то в ходе моделирования соотношение между индивидами с негативным отношением по рассматриваемому вопросу и индивидами с положительным отношением остается примерно на одном уровне, с погрешностью не более 10 %, и появление «нейтральных» индивидов в данном случае несет не только разграничительный характер, но и демонстрирует создание скопления индивидов с данным мнением.

1. Гуц А. К., Коробицын В. В., Лаптев А. А. Математические модели социальных систем. — Омск: Омск. гос. ун-т, 2000.

2. Липман У. Общественное мнение / Пер. с англ. — М.: Институт Фонда «Общественное мнение», 2004.

3. Цаллер Дж. Происхождение и природа общественного мнения / Пер. с англ. А. А. Петровой. Науч. ред. перевода И. Н. Тартаковская. — М.: Институт Фонда «Общественное мнение», 2004.

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

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *