ббк76. 0 Қ 54 Редакционная коллегия

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  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