Обеспечение информационной защиты беспроводных сенсорных сетей…
3
параллельные способы решения триединой задачи: криптозащиты,
имитозащиты и защиты данных от случайных сбоев при преобразо-
вании и передаче.
В качестве такой вычислительной модели может выступать кле-
точный автомат (КЛА) — бесконечная сеть одинаковых автоматов
Мура, расположенных в точках пространства с целочисленными ко-
ординатами, связанных одинаковым образом друг с другом и изме-
няющих состояние в зависимости от состояний соседей и своего соб-
ственного. Динамика состояний однородной пространственно рас-
пределенной дискретной системы с локальным взаимодействием
элементов может представлять разнообразные варианты поведения
(устойчивые конфигурации, циклы, хаос), в том числе не имеющие
прямого аналога среди аттракторов непрерывных динамических си-
стем. Такая система в силу однородности и локальности преобразо-
ваний устойчива к сбоям отдельных элементов.
Алгоритмическая неразрешимость прямой задачи — синтеза
функции глобальных (для всех элементарных автоматов) переходов
КЛА по локальной функции и обратной задачи — определения
структуры и параметров КЛА по множеству его состояний позволяет
использовать такую модель в качестве криптосистемы.
Криптосистемы на клеточных автоматах могут быть как симмет-
ричными, так и асимметричными. В случае симметричных криптоси-
стем ключом может служить, например, начальное состояние кле-
точного автомата, осуществляющего генерацию псевдослучайной
последовательности состояний и преобразование открытого текста на
основе только локальных правил перехода. Для реализации асиммет-
ричных криптосистем могут использоваться обратимые клеточные
автоматы [2]. В этом случае в качестве открытого ключа может вы-
ступать, например, локальная функция переходов. Для двумерных
КЛА отыскание функции, инверсной к заданной локальной функции
переходов, относится к числу алгоритмически неразрешимых за-
дач [1]. Поэтому важным направлением исследования является поиск
универсальных обратимых КЛА.
Проблему универсальности КЛА можно рассматривать в двух ас-
пектах. В рамках первого универсальность сводится к представлению
одних КЛА в других. Клеточный автомат является универсальным,
если он моделирует поведение любого другого КЛА той же размер-
ности.
Другой подход к универсальности восходит к универсальной вы-
числимости. Клеточный автомат является универсальным, если он
моделирует универсальную машину Тьюринга. Представляет интерес
поиск КЛА с минимальными значениями параметров. Следует отме-
