«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
409
Таблица 2
Многозначная замена – выходы автомат Мили А
2
Состояние
Входные символы
000
001
010
011
100
101
110
111
00
010
111
100
110
001
000
101
011
01
011
010
000
101
110
111
001
100
10
110
100
001
111
010
011
000
101
Состояние
Выходные символы
При использовании шифров многозначной замены возникает трудности, связанные с
необходимостью запоминания ключа. Для задания порядка выбора подстановок требуется
построить функцию-распределитель.
Чтобы решить эту проблему нужно интерпретировать таблицу 2 как таблицу выходов
автомата Мили А
2
и определить таблицу переходов. Поскольку замена трехвариантная, то
автомат должен иметь три состояния. Тогда переходы автомата таблицей 3.
Состояние'>Таблица 3
Таблица переходов автомата Мили А
2
Состояние
Входные символы
000
001
010
011
100
101
110
111
00
01
00
10
00
01
01
10
00
01
10
10
00
10
00
01
00
10
10
00
01
01
01
01
00
10
01
Состояние
Состояния переходов
Функциональная модель автомата А
2
представляется системой логических (булевых)
функций, зависящих от пяти переменных:
)
,
,
,
,
(
)
,
,
,
,
(
)
,
,
,
,
(
)
,
,
,
,
(
)
,
,
,
,
(
3
2
2
3
3
3
3
3
2
1
2
1
1
2
1
2
1
1
1
2
1
2
1
1
2
1
2
1
1
2
2
1
2
1
1
1
1
x
x
x
s
s
s
x
x
x
s
s
s
x
x
x
s
s
y
x
x
x
s
s
y
x
x
x
s
s
y
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
(9)
Функции выходов и функции переходов строятся стандартным образом согласно
каноническому методу структурного синтеза автомата. Далее в качестве памяти возьмем
элементы задержки и полученную систему логических уравнений минимизируем методом
Квайна – Мак-Класски, который позволит минимизацию логической функции, заданной
таблицей истинности или совершенной дизъюнктивной нормальной формой. В результате
каноническая система уравнений автомата примет вид:
«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
410
.
2
,
,
3
,
,
3
2
2
1
3
2
1
1
3
2
1
2
3
2
2
1
3
1
2
1
2
1
2
1
1
3
2
2
1
3
2
1
2
3
2
2
1
2
1
2
1
1
3
1
2
1
2
1
2
1
3
2
1
1
3
1
2
1
3
2
1
2
1
2
1
2
1
3
2
1
2
1
3
2
1
2
1
3
2
1
2
1
3
2
2
1
2
1
2
1
2
2
1
3
2
1
2
2
1
1
3
2
1
2
2
3
2
2
1
3
2
2
1
3
2
2
1
2
1
2
1
3
1
2
2
1
2
1
1
1
x
x
s
s
x
x
x
s
x
x
x
s
x
x
s
s
x
x
s
s
x
x
s
s
s
x
x
s
s
x
x
x
s
x
x
s
s
x
x
s
s
s
x
x
s
s
x
x
s
s
x
x
x
s
x
x
s
s
x
x
x
s
s
x
x
s
s
x
x
x
s
s
x
x
x
s
s
x
x
x
s
s
y
x
x
s
s
x
x
s
s
x
s
s
x
x
x
s
x
x
s
x
x
x
s
y
x
x
s
s
x
x
s
s
x
x
s
s
x
x
s
s
x
x
s
x
x
s
s
y
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
t
(10)
Последний этап синтеза автомата – построение комбинационной части логической
схемы по системе логических функций не представляет трудности (пример такого
построения схемы показано на рисунке 3). Из-за громоздкости этого построения мы не
будем показывать построенную логическую схему требуемого автомата А
2
, и построим
только его структурную схему, которая представлена на рисунке 4.
По структурной схеме видно, что сначала в память запоминается начальное
(предыдущее) состояние, которое подается на вход КС, чтобы инициировать функции
выходов и функции переходов, затем порожденные новые состояния опять записываются в
память и т.д. автомат продолжает работать пока не выполняться условия для останова.
Для расшифровки необходимо существования обратного автомата.
Для обеспечения однозначности расшифровки необходимо и достаточно, чтобы в
шифраторе в каждой последовательности выходных сигналов, соответствующих одному
состоянию, все значения были различны. По таблице 2 несложно проверить, что это
требование выполнено: в пределах одной строки кодовые комбинации не повторяются. Для
проверки правильности синтеза шифратора А и дешифратора А
-1
сводится к
последовательному применению их к некоторому открытому тексту
*
X
, чтобы
выполнялось условие:
)).
(
(
1
A
A
(7)
Заметим,
что
построенный
автомат
А
2
одинаковых
фрагментов
входной
последовательности шифруют различными блоками. Например, кодовая комбинация «000»
может быть зашифрована одним из трех способов: «010», «011» или «110», в зависимости от
того, в каком состоянии находится автомат.
Предложенные в работе автоматные модели шифратора показывают возможность
использования для решения задач шифрования не традиционных математических моделей.
Такие модели могут служит инструментом для исследования алгоритмов шифрования.
Рисунок 4 - Структурная
схема автомата Мили – шифратора
А
2
.
КС
П
2
П
1
y
t
1
x
t
1
x
t
2
x
t
3
s
t
1
1
s
t
2
1
s
t
2
s
t
1
y
t
3
y
t
2
«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
411
Однако, как и все шифры замены, эти модели не смогут противостоять частотному анализу
при шифровании больших сообщений на одном ключе – автомате. Поэтому автоматное
шифрование
может
быть
использована
как
одна
из
компонентов
какой-либо
комбинированной криптосистемы, которая состоит из нескольких моделей и алгоритмов
шифрования.
Литература:
1.
Дж.Хопкрофт, Р.Мотвани, Дж. Ульман. Введение в теорию автоматов, языков и
вычислений– М.: Вильямс, 2002. – 528 с.
2.
https://ru.wikipedia.org/wiki/Шифратор (электроника)
3.
Богаченко Н.Ф. Применение теоретико-автоматных моделей в криптографии.
Математические структуры и моделирование, 2007, вып. 17, с. 112-120.
«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ» V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ
412
ТРУДЫ
V МЕЖДУНАРОДНОЙ НАУЧНО-ПРАКТИЧЕСКОЙ КОНФЕРЕНЦИИ
ИНФОРМАТИЗАЦИЯ ОБЩЕСТВА
Типография не несет ответственности за содержание
Тираж 70 экз.
Формат 60х84 1/16 Объем усл. 25,7
Бумага офсетная Шрифт «Тimes New Roman»
Заказ № 14061
Отпечатано в типографии ЕНУ им. Л.Н. Гумилева
г. Астана, 010008, ул. Кажымукана, 13/1