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

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

405 

 

Функции 

))

(

),

(

(

)

1

(

1

t

x

t

s

t

s

i

k

k

t

t

t









 

и 

))

(

),

(

(

)

(

t

x

t

s

t

y

i

k

j

t

t

t





 

 

можно  

представить в виде отношений:  









)

1

(

),

(

),

(

1

t

s

t

x

t

s

k

i

k

t

t

t

  и 

.

)

(

),

(

),

(





t

y

t

x

t

s

j

i

k

t

t

t

 

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

т.е.  функция  выхода  имеет  только  один  аргумент  –  состояние  автомата,  а  остальные 

параметры совпадают с параметрами автомата Мили.  

Если  обозначим  функцию  выхода  автомата  Мура  через 

Y

S 

:



,  то  

функионирование  автомата  Мура можно  описать  следующей  системой  рекуррентных 

соотношений:  

 



















))

(

(

)

(

))

(

),

(

(

)

1

(

1

t

s

t

y

t

x

t

s

t

s

k

j

i

k

k

t

t

t

t

t





               (4) 

Функциональная схема автомата Мура представлена на рисунке 2. 

 

 

 

 

 

 

 

 

 

Функция  выхода  автомата  Мура  ставит  метку  на  выходе  каждому  его  состоянию, 

поэтому эту функцию называют также функцией меток.  

Особенностью автомата  Мура является  то,  что  символ 

)

(t

y

j

t

  в  выходном  канале 

существует  все  время,  пока  автомат  находится  в  состоянии 

)

(t

s

k

t

для  любых  j=1,  2,  …,  m; 

k=1, 2, …, l;  t = 1, 2, 3, … .  . 

Следует  отметить,  что  для  любого  автомата  Мура  существует  автомат  Мили, 

реализующий  ту  же  самую  функцию.  И  наоборот:  для  любого  автомата  Мили  существует 

автомат Мура, возможно, со сдвигом по времени: 

.

)),

(

),

(

(

 

…

 

3,

 

2,

 

1,

 

=

t 

))

1

(

(

1

t

i

t

k

x

s

t

t

t

s

k

t











 

В  автоматах  Мили  и  Мура  входные  и  выходные  последовательности  вида 

],...

3

[

],

2

[

],

1

[

3

2

1

x

x

x

i

i

i

  и 

],...

3

[

],

2

[

],

1

[

3

2

1

y

y

y

j

j

j

  можно  считать  словами  (цепочками) 

конечной  длины  некоторого  языка  X*  и  Y*    соответственно.  Здесь  *  –  операция  итерации,  

результат  выполнения  которой  порождает  множество  всех  возможных  цепочек  (слов)  в 

алфавитах X и Y. 

  

 

Таким образом, последовательные автоматы (Мили и Мура) A, находясь в начальном 

состоянии s

0

, индуцирует автоматное отображение, которое ставит в соответствие входным 

словам 

 

*

 

...

2

1

X

n

x

x

x

i

i

i



  выходные  слова 

*

...

2

1

Y

y

y

y

j

j

m

j



.    При  этом  входные  слова 

определяют    множество  слов,  распознаваемых  этим  автоматом  (входной  язык  автомата), 

выходные слова -  множество слов, порождаемых этим автоматом (выходной язык автомата).  

Известно,  что  шифратор в  электронике  явяляется    комбинационным  устройством. 

Поэтому  для  демонстрации  построения  автоматной  модели  шифратора  в  электронике 

рассмотрим следующую задачу шифрования.  

)

(t

x

i

t

 

))

(

),

(

(

t

x

t

s

i

k

t

t



 

)

(t

y

j

t

 

Память 

))

(

(

t

s

k

t



 

)

1

(

1





t

s

k

t

 

)

(t

x

i

t

 

)

(t

s

k

t

 

)

(t

s

k

t

 

Рисунок 2 - 

Функциональная схема автомата Мура

 

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

406 

 

Пусть  на  вход  комбинационному  шифратору  подается  три  последовательности,  а  на 

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

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

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

функции. 

 В  качестве  примера  такого  шифратора  рассмотрим  функциональную  модель, 

представленную в таблице 1. 

Таблица 1 

Шифрование с помощью подстановки 

Наборы 

0 

1 

2 

3 

4 

5 

6 

7 

Вход

 

x

1 

0 

0 

0 

0 

1 

1 

1 

1 

x

2

 

0 

0 

1 

1 

0 

0 

1 

1 

x

3

 

0 

1 

0 

1 

0 

1 

0 

1 

Выход 

y

1

 

1 

1 

1 

1 

0 

0 

1 

0 

y

2

 

1 

1 

0 

0 

1 

1 

1 

0 

 

В 

таблице 

1 

представлена 

работа 

однотактного 

шифратора 

и 

синтез 

соответствующего  автомата 

A

1

  сводится  к  записи  логических  функций  в  совершенной 

дизъюнктивной нормальной форме (СДНФ), которые он должен реализовать.  

Из 

таблицы 

2 

видно, 

что 

логические 

функции

)

,

,

(

3

2

1

1

1

x

x

x

y





 

и

)

,

,

(

3

2

2

1

2

x

x

x

y





 имеют значение 1 на пяти наборах данных входа: 

- номера  0, 1, 2, 3 и 6 для 



1

; 

- номера 0, 1, 4, 5 и 6 для



2

; 

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

СДНФ: 

 

;

3

1 2

3

2

3

2

3

2

3

2

1

1

1

1

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

y











 

.

3

1 2

3

2

3

2

3

2

3

2

2

1

1

1

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

y











 

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

непосредственных преобразований и правило полной склейки:   

.

)

(

)

(

)

(

3

2

2

1

2

1

1

1

3

2

3

3

2

1

3

3

2

1

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

y



















 

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

минимальную форму логической функции: 

.

)

(

3

2

1

3

2

2

2

1

3

2

2

1

2

1

1

x

x

x

x

x

x

x

x

x

x

x

x

x

x

y

















 

Аналогично минимизируем логическую функцию  

.

.

)

(

)

(

)

(

3

1

2

3

1

2

1

2

1

2

2

3

1

3

3

2

1

3

3

2

1

2

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

x

y























 

Объединяя  эти  логические  функции  получим  математическую  модель  автомата-

шифратора в виде логической функции 

x

x

x

x

x

x

y

y

A

3

1

2

3

1

1

2

2

1













    (5) 

Программная  реализация  этой  функци  нередставляет  никакой  трудности,  для  этого 

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

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

407 

 

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

входной последовательности. 

Для аппаратной реализации шифратора, математическая модель которого задана в (5), 

нужно  построить  комбинационную  цифровую  схему  из  логических  элементов.  Для  этого 

достаточно  взять  элементы  ИЛИ-НЕТ  –  дизъюнктор-инвертор.  Цифровая  схема  автомата-

шифратора показана на рисунке 3.  

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Синтез  обратного  автомата-дешифратора  аналогичен  синтезу  автомата-шифратора. 

Для этого достаточно в таблице 1 строки «вход» и  «выход» поменять местами и повторить 

приведенные выше вычисления и построения цифровой схемы. 

Рассмотренный  шифратор  является  очень  слабым,  так  как  частотные 

характеристики  открытого  сообщения  (входной  последовательности)  сохраняются  в 

шифртексте (выходной последовательности). 

Повысить 

стойкость 

шифра 

позволяют 

шифры 

многозначной 

замены 

(подстановки),  в  которой  каждому  символу  (кодовой  комбинации)  открытого 

(входного)  алфавита  ставится  в  соответствие  не  один,  а  несколько  символов 

шифртекста. Такую замену может осуществить последовательный шифратор. 

Ранее  было  замечено,  шифратор в  криптографии  явяляется    последовательным 

устройством.  Поэтому  для  построения  автоматной  модели  шифратора  в  криптографии 

необходимо дать некоторые определения:  

Криптографическим шифратором называется следующая пятерка: 

,

,

*,

~

*,

~

,





D

S

Y

X

K

C

            (6) 

где: 

K

– множество ключей; 

*

*

~

X

X 

– множество открытых (исходных) текстов; 

*

~

*

Y

Y



– множество закрытых (зашифрованных) текстов; 

*)

~

*,

~

(

:

Y

X

S k















– правило шифрования для 

K

k 

; 

*)

~

*,

~

(

:

X

Y

Dk















 – правило дешифрования для 

K

k 

; 

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

1.

;

))

(

(

:

*,

~

















S k

Dk

K

k

X

 

x

x

x

3

1

2



1 

1 

x

1

 

x

2

 

x

3

 

1 

1 

1 

1 

1 

1 

x

1

 

x

2

 

x

x

x

x

3

2

3

2





x

x

x

x

3

3

1

1





x

x

x

3

2

1



 

x

x

x

3

2

1



x

x

x

3

1

2



 

y

1

 

y

2

 

Рисунок 3 - Цифровая схема автомата-шифратора

 

«ҚОҒАМДЫ АҚПАРАТТАНДЫРУ»  V ХАЛЫҚАРАЛЫҚ ҒЫЛЫМИ-ПРАКТИКАЛЫҚ КОНФЕРЕНЦИЯ 

 

 

408 

 

2. 

 

k

k

S

Y





)

(

*

~



. 

Последовательный  автомат,  который  будет  моделировать  работу  шифратора  (6) 

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

K

k 

,  т.е.  формальное 

определение такого автомата будет иметь вид:  











,

,

,

,

Y

X

K

S

A

      (7)         

В этом случае функциональная модель автомата Мили выглядит так: 























)

(

))

(

),

(

(

))

(

),

),

(

((

)

),

1

(

(

))

(

),

(

(

))

(

),

),

(

((

1

t

y

t

x

t

s

t

x

k

t

s

k

t

s

t

x

t

s

t

x

k

t

s

j

i

k

i

k

k

i

k

i

k

t

t

t

t

t

t

t

t

t

t









            (8)   

Для 

решения 

задачи 

дешифрования 

(задачи 

моделирования 

дешифратора) 

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

входных  последовательностей  в  выходные.  Обращение  отображения  имеет  направление: 

левое и правое.  Мы рассмотрим левое обращение и дадим следующее определение: 

Автомат 











~

,

~

,

,

,

~

1

X

Y

S

A

называется обратным слева к автомату  

,

,

,

,

,









Y

X

S

A

если 

 

S

s

S

s

~

~







такое, 

что 

*,

X







выполняется 

равенство 

.

))

(

(

1









A

A

s

s

  

Для  существования  обратного  автомата  необходимо  и  достаточно  инъективность 

автоматного  отображения 

A

s

для  любого  начального  состояния  s.  Инъективность 

автоматного  отображения  достигается  требованием  инъективности  функции  выхода  λ  при 

фиксированном  состоянии  s,  то  есть  частичной  функции 

Y

X

s



:



,  что  означает 

1

)

(

1



 y

s



. 

Итак,  для  получения  однозначности  дешифрования  шифрующий  автомат  (7),  (8) 

должен иметь инъективную частичную функцию выходов 

,



s

 что приводит к следующему 

алгоритму построения обратного автомата: 

1. 

Если  

,

1

)

(

1





y

s



 то 

)

(

)

,

(

~

1

y

y

s

s









 и  

)).

(

,

(

)

,

(

~

1

y

s

y

s

s











 

2. 

В противном случае, когда 

,

0

)

(

1





y

s



)

,

(

~

y

s



 – произвольный 

,

X

x

   

)

,

(

~

y

s



 – произвольное 

.

S

s

 

Если  мощности  алфавитом  Х  и  У  совпадают,  то  обратный  автомат  строится 

однозначно.  В  общем  случае  должно  выполняться  |Х|  ≤  |У|.  Если  неравенство  строгое,  то 

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

Заметим,  что  для  обратимости  автомата  необходимо  и  достаточно,  чтобы  в  его 

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

различны. 

Для демонстрации предложенных моделей и алгоритмов рассмотрим шифр замену на 

основе автомата Мили. 

Рассмотрим  многозначную  замену  (подстановку),  которая  моделируется  автоматом 

Мили А

2

 и представляется в таблице 2.   

 

 

жүктеу/скачать 14,62 Mb.

Достарыңызбен бөлісу: