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



Pdf көрінісі
бет57/57
Дата03.03.2017
өлшемі14,62 Mb.
#5946
1   ...   49   50   51   52   53   54   55   56   57

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

 


Достарыңызбен бөлісу:
1   ...   49   50   51   52   53   54   55   56   57




©emirsaba.org 2024
әкімшілігінің қараңыз

    Басты бет