Криптографические методы защиты информации

КРИПТОГРАФИЧЕСКИЕ
МЕТОДЫ ЗАЩИТЫ
ИНФОРМАЦИИ

Том 2

УЧЕБНО-МЕТОДИЧЕСКОЕ ПОСОБИЕ

Второе издание

Рекомендовано Учебно-методическим объединением
по образованию в области прикладной информатики
в качестве учебно-методического пособия
для студентов высших учебных заведений,
обучающихся по специальности
080801 «Прикладная информатика»
и другим междисциплинарным специальностям

Москва
РИОР
ИНФРА-М

А.В. БАБАШ

УДК 004.056(075.8)
ББК 32.973.202я73
 
Б12

Бабаш А.В.
Криптографические методы защиты информации. Т. 2: Учеб.-метод. 
пособие. — 2-е изд. — М.: РИОР: ИНФРА-М, 2014. — 257 с. — (Высшее 
образование: Бакалавриат).

ISBN 978-5-369-01290-1 (РИОР)
ISBN 978-5-16-009247-8 (ИНФРА-М)

Пособие предназначено для студентов высших учебных заведений, обучающихся по 
специальности «Прикладная информатика (в экономике)». Оно также содержит методический 
материал для ряда инновационных курсов лекций по профилю «Информационная 
безопасность» и может быть использовано для блока дисциплин этого профиля. 
Ряд представленных результатов полезен специалистам и аспирантам, специализирующимся 
в указанной области.

Б12

УДК 004.056(075.8)
ББК 32.973.202я73

ISBN 978-5-369-01290-1 (РИОР)
ISBN 978-5-16-009247-8 (ИНФРА-М)

Оригинал-макет подготовлен в Издательском Центре РИОР

Подписано в печать 20.07.2013. 
Формат 60х88/8. Бумага офсетная. Гарнитура Newton. 
Печать офсетная. Усл. печ. л. 31,6. Уч.-изд. л. 24,7.
Тираж 200 экз. Заказ № 
Цена свободная.

ТК 241100 – 12654 – 200713

ООО «Издательский Центр РИОР»
127282, Москва, ул. Полярная, д. 31В.
Email: info@rior.ru
www.rior.ru

ООО «Научно-издательский центр ИНФРА-М»
127282, Москва, ул. Полярная, д. 31В, стр. 1.
Тел.: (495) 380-05-40, 380-05-43. Факс: (495) 363-92-12
E-mail: books@infra-m.ru    http://www.infra-m.ru

© Бабаш А.В., 2014

СОДЕРЖАНИЕ 
 
Введение ............................................................................................................................. 
7 
Определения, обозначения и сокращения ................................................................... 
10 
 
Часть 1. НЕОТЛИЧИМОСТЬ СОСТОЯНИЙ И ВХОДНЫХ СЛОВ АВТОМАТОВ 
 
Глава 1. Классы автоматов и операции над автоматами................................................. 
13 
1.1. Автономный линейный регистр сдвига................................................................................... 
13 
1.2. Неавтономный линейный регистр сдвига............................................................................... 
13  
1.3. Неавтономный регистр сдвига................................................................................................. 
13 
1.4. Проходная линия задержки...................................................................................................... 
14  
1.5. Шифрующий автомат ............................................................................................................... 
14  
1.6. Операции над автоматами....................................................................................................... 
15  
 
Глава 2. Неотличимость состояний автоматов................................................................. 
17  
2.1. Основные понятия .................................................................................................................... 
17 
2.2. Неотличимость состояний перестановочных автоматов...................................................... 
19  
2.3. Гомоморфизмы автоматов....................................................................................................... 
24  
 
Глава 3. Неотличимость входных слов автоматов ........................................................... 
27 
3.1. Автономность автоматов ......................................................................................................... 
27 
3.2. Степени перестановочных автоматов .................................................................................... 
27 
3.3. Псевдоавтономность перестановочных автоматов............................................................... 
30  
3.4. Слабая автономность автоматов ............................................................................................ 
36 
3.5. Слабый гомоморфизм автоматов ........................................................................................... 
40 
 
Глава 4. Декомпозиция автоматов ..................................................................................... 
44  
4.1. Разбиения и покрытия множества. Примеры......................................................................... 
44  
4.2. Фактор-автомат. Покрытие автомата...................................................................................... 
46  
4.3. Параллельное соединение автоматов ................................................................................... 
48 
4.4. Последовательное соединение автоматов............................................................................ 
50  
 
Глава 5. Периодичность функционирования конечных автоматов ................................. 
57 
5.1. Вспомогательное почти тривиальное утверждение .............................................................. 
57  
5.2. Основные теоретико-автоматные обозначения..................................................................... 
58 
5.3. Оценка периодов последовательностей состояний автомата при заданной  
периодической входной последовательности............................................................................... 
59 
 
Глава 6. Гомоморфизмы неавтономных двоичных регистров сдвига............................. 
61 
6.1. Основные понятия .................................................................................................................... 
61 
6.2. Теорема А.Я. Прососова.......................................................................................................... 
62 
6.3. Теорема В.А. Башева ............................................................................................................... 
64  
6.4. Обзор по работе В.И. Солодовникова «Гомоморфизмы двоичных  
регистров сдвига» [20]..................................................................................................................... 
65 
 
Часть 2. СВОЙСТВА АВТОМАТОВ 
 
Глава 7. Верхняя оценка степени различимости связных перестановочных  
автоматов с заданным диаметром..................................................................................... 
73 
7.1. Формулировка основных  результатов ................................................................................... 
73 
7.2. Доказательство основной оценки ........................................................................................... 
73 
7.3. О роли диаметра перестановочного связного приведенного автомата  
в его оценке степени различимости............................................................................................... 
75 
7.4. Доказательство достижимости полученной оценки степени различимости ...................... 
82 
 
Глава 8. Неотличимость состояний перестановочных, аффинных и автономных  
нелинейных векторных автоматов ..................................................................................... 
91 
8.1. Основные понятия ................................................................................................................. 
91 

8.2. Неотличимость состояний перестановочных автоматов................................................... 
93 
8.3. Оценки вероятности k-неотличимости двух случайно и равновероятно  
выбранных состояний автомата.................................................................................................. 
96 

8.4. Неотличимость состояний n-й степени перестановочного автомата............................... 
98 
8.5. Неотличимость состояний аффинных автоматов .............................................................. 
99 
8.6. Неотличимость аффинных автоматов ................................................................................ 
103 

8.7. Неотличимость состояний автономных векторных нелинейных автоматов.................... 
104 
 
Глава 9. Неотличимость состояний автономного последовательного соединения  
перестановочных автоматов .............................................................................................. 107 
9.1. Оценки числа классов неотличимых состояний автономных  
последовательных соединений перестановочных автоматов ................................................ 
107 
9.2. Оценки мощностей классов неотличимых состояний автономных  
последовательных соединений перестановочных автоматов ................................................. 
115 
 
Глава 10. Алгоритмы нахождения минимальных систем областей импримитивности  
группы подстановок ............................................................................................................. 119 
10.1. Алгоритм нахождения минимальных систем импримитивности  
групп подстановок (M.D. Atkinson)............................................................................................... 
119 
10.2. Новый алгоритм получения минимальных систем областей  
импримитивности группы подстановок ...................................................................................... 
121 
 
Глава 11. Односторонняя неотличимость состояний конечных автоматов ................... 125 
11.1. Понятие (,)-неотличимости состояний автомата......................................................... 
125 
11.2. Определение начального состояния автомата по его входному и выходному слову........ 
126 
11.3. Свойства (,)-неотличимых состояний автомата .......................................................... 
126 
11.4. (,d)-периодические выходные последовательности автономного автомата............... 
129 
11.5. G-приведенность автономного последовательного соединения автоматов ................. 
131 
 
Глава 12. Сильно приведенные автоматы ........................................................................ 133 
 
Глава 13. Об одном подходе к линеаризации уравнений получения выходной 
последовательности векторного автомата ....................................................................... 136 
13.1. -размерность векторного автомата, -линейная размерность .................................... 
136 
13.2. Определение начального состояния векторного автомата A по его входной 
и выходной последовательностям.............................................................................................. 
137 
 
Глава 14. Запреты автоматов и двоичных функций ......................................................... 139 
14.1. Криптографические приложения........................................................................................ 
139 
14.2. Запреты автоматов.............................................................................................................. 
139 
14.3. Запреты двоичных функций ............................................................................................... 
143 
14.4. Критерии наличия запрета двоичной функции................................................................. 
144 
14.5. Оценки длины запрета двоичной функции........................................................................ 
144 
 
Часть 3. ПЕРИОДЫ ВЫХОДНЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ АВТОМАТА 
 
Глава 15. Внешне периодические автоматы..................................................................... 148 
15.1. Введение .............................................................................................................................. 
148 
15.2. Автоматы с L-потерей информации о выходе .................................................................. 
148 
15.3. Критерий внешней периодичности автомата.................................................................... 
150 
 
Глава 16. Периодически внешне наследственные перестановочные автоматы ........... 153 
16.1. Автоматы с L-потерей информации................................................................................... 
153 

16.2. Периодически внешне наследственные автоматы .......................................................... 
155 

16.3. Критерий внешней наследственности автомата ............................................................. 
160 

Глава 17. Периоды выходных последовательностей автомата при заданной  
периодической входной последовательности................................................................... 163 
17.1. Краткий обзор результатов по данной теме. Обозначения, основные  
понятия, вспомогательные результаты...................................................................................... 
163 
17.2. Периоды выходных последовательностей автомата без внешне автономных  
состояний при входной периодической последовательности заданной полноты......................... 
165 
17.3. Периоды выходных последовательностей линейного векторного  
автомата при заданной входной периодической последовательности .................................. 
170 
17.4. Период внешнего функционирования автономного последовательного  
соединения автоматов ................................................................................................................ 
173 
17.5. Периоды выходных последовательностей перестановочного автомата  
без потери информации при заданных периодических входных  
последовательностях .................................................................................................................. 
175 
17.6. Периоды выходных последовательностей последовательного соединения  
автономного автомата с перестановочным автоматом без потери информации.................. 
179 
 
Глава 18. Классы автоматов с гарантированными периодами выходных  
последовательностей.......................................................................................................... 182 
18.1. Необходимость построения автоматов с гарантированными периодами  
выходных последовательностей ................................................................................................ 
182 
18.2. Кодирующее устройство с конечной памятью ................................................................. 
182 
18.3. Полноцикловый автомат .................................................................................................... 
185 
18.4. Обратимый автомат ........................................................................................................... 
189 
18.5. Обобщенный узел выборки ............................................................................................... 
190 
 
Глава 19. Классы автоматов с гарантированными параметрами подпериода  
выходных последовательностей ....................................................................................... 193 
19.1. Основные обозначения и понятие подпериода последовательности ........................... 
193 
19.2. Автомат Медведева ........................................................................................................... 
194 
19.3. Кодирующее устройство с конечной памятью (проходная линия задержки 
с функцией усложнения) .............................................................................................................. 
196 
19.4. Обратимые автоматы ......................................................................................................... 
199 
 
Часть 4. ПРИБЛИЖЕННЫЕ ПЕРИОДЫ ВЫХОДНЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ АВТОМАТА 
 
Глава 20. О периодичности последовательности состояний автомата, отвечающей его  
начальному состоянию и входной периодической последовательности.  
Приближенные периоды последовательности состояний автомата............................... 200 
20.1. Введение, вспомогательные обозначения, понятия и результаты................................. 
200 
20.2. Нижние оценки мер приближенных периодов последовательностей  
состояний автомата, отвечающих его начальным состояниям и входным  
смешанно-периодическим последовательностям..................................................................... 
204 
20.3. Нижние оценки мер приближенных периодов выходных последовательностей  
регистров сдвига, отвечающих его начальным состояниям и входным  
смешанно-периодическим последовательностям..................................................................... 
207 
 
Глава 21. Приближенные периоды выходных последовательностей полноциклового  
автомата, представимого последовательным соединением автономного автомата  
с неавтономным перестановочным автоматом................................................................. 209 
21.1. Полноцикловое последовательное соединение автоматов............................................ 
209 
21.2. Полноцикловое последовательное соединение автономного автомата  
с перестановочным коммутируемым автоматом....................................................................... 
211 
21.3. Класс функций выхода полноциклового последовательного соединения  
автономного автомата с перестановочным коммутируемым автоматом................................ 
212 
21.4. Автономное последовательное соединение автоматов со свойством  
принудительного восстановления состояния второго автомата.............................................. 
215 

Глава 22. G-изопериод выходной последовательности автономного 
последовательного соединения автоматов....................................................................... 218 
22.1. Основные понятия и предварительные результаты ........................................................ 
218 
22.2. Изопериод последовательности внешнего функционирования  
перестановочного автомата при заданной входной периодической  
последовательности..................................................................................................................... 
221 
22.3. Изопериоды полноциклового автомата, представимого последовательным  
соединением двух автоматов...................................................................................................... 
222 
22.4. Изопериоды последовательного соединения автоматов с выходным  
алфавитом-группой ...................................................................................................................... 
225 
 
Глава 23. Оценки параметров обобщенной периодичности выходных  
последовательностей некоторых полноцикловых автоматов с выходным  
алфавитом, являющимся группой...................................................................................... 227 
23.1. Основные понятия, постановка задачи ............................................................................. 
227 
23.2. -периоды последовательности АH(P1) для стабильных слева (справа)  
бинарных отношений на G........................................................................................................... 
229 
23.3. Оценки мер приближенных -периодов последовательности АH(P1)  
для стабильных слева (справа) бинарных отношений на группе G ........................................ 
231 
23.4. Примеры стабильных слева (справа) бинарных отношений на группе G...................... 
237 
23.5. -периоды последовательности АH(P1)  для автоморфизмов  группы G ..................... 
238 
23.6. Оценки мер приближенных -периодов последовательности АH(P1)  
для автоморфизмов группы......................................................................................................... 
240 
 
Глава 24. Классы векторных автоматов с гарантированными периодами выходных  
последовательностей при заданной входной периодической последовательности ..... 244 
24.1. Основные понятия. Вспомогательные результаты .......................................................... 
244 
24.2. Способ построения векторного автомата с гарантированным выходным  
периодом на основе оценки его слабой автономности............................................................. 
246 
24.3. Способ построения векторного автомата с гарантированным выходным  
периодом на основе нахождения его сильно различимых входных слов............................... 
249 
24.4. Пример синтеза векторного нелинейного автомата с гарантированным  
выходным периодом..................................................................................................................... 
252 
 
Список использованных источников ............................................................................ 255 
 

ВВЕДЕНИЕ 
 
Тома 2, 3 пособия посвящены теоретико-автоматному подхода к синтезу и ана-
лизу криптографической защиты информации. Обобщение и универсальность из-
ложения методов синтеза шифраппаратуры и ее криптоанализа достигается выбором 
теоретико-автоматного языка. Одновременно, постановка задач криптографической 
защиты в терминах теории автоматов и их решения существенно расширили класси-
ческое содержание теории автоматов.  
В данном втором томе пособия представлена методика оценки периодов и 
приближенных периодов выходных последовательностей автоматов при заданных 
начальных состояниях и входных периодических последовательностях. В третьем то-
ме пособия дается методика построения приближенных (численно приближенных) 
моделей сложных автоматов, моделирующих современные дискретные устройства 
криптографической защиты информации. 
Второй том пособия решаются задачи, связанные: 
 
с неотличимостью состояний перестановочных автоматов и их слабой авто-
номностью;  
 
с запретами автоматов и двоичных функций; 
 
с оценкой периодов выходных последовательностей конечных автоматов; 
 
с оценкой приближенных периодов выходных последовательностей автоматов; 
 
с оценками мер приближенных периодов выходных последовательностей автоматов, 
моделирующих поточные шифры.  
 
Представлены следующие классы автоматов: 
 
автоматы без потери информации; 
 
перестановочные автоматы; 
 
автоматы без внешне автономных состояний; 
 
автономные последовательные соединения автоматов; 
 
линейные векторные автоматы; 
 
автоматы Медведева; 
 
кодирующие устройства с конечной памятью;  
 
обратимые автоматы; 
 
полноцикловые автоматы.  
 
Цель второго тома пособия состоит:  
 
в описании новых методов оценки количества эквивалентных ключей шифров, 
основанных на представлении шифрсистемы или ее отдельного блока конечным 
автоматом; 
 
оценки мощностей классов неотличимых состояний автономных последовательных 
соединений перестановочных автоматов, моделирующих шифры 
предварительного шифрования; 
 
в описании новых методов оценки периодов выходных последовательностей 
конечных автоматов, моделирующих шифры предварительного шифрования. 
Другими словами, данная цель состоит в нахождении новых классов дискретных 
устройств с гарантированными периодами выходных псевдослучайных 
последовательностей; 

 
в получении методики оценки мер приближенных периодов выходных последовательностей 
конечных автоматов, моделирующих шифры предварительного 
шифрования.  
Для класса перестановочных автоматов указаны новые алгоритмы доказательства 
их приведенности. Разработаны новые способы проверки наличия у автоматов 
автономных и слабо автономных состояний. Приведены доказательства верхних оценок 
сложности таких алгоритмов.  
Указаны новые методы доказательства приведенности автоматов из следующих 
классов: перестановочных, аффинных и автономных нелинейных векторных автоматов, 
автономного последовательного соединения перестановочных автоматов. При 
этом  даны удобные для применения в криптографической практике методы оценки 
числа неэквивалентных ключей шифров построенных по классической схеме – 
управляющий блок и шифрующий блок (число классов неотличимых состояний автономных 
последовательных соединений перестановочных автоматов и оценки их 
мощностей. Приведенный в работе алгоритм нахождения областей импримитивно-
сти групп подстановок, заданных системой образующий элементов более эффекти-
вен, чем известные ранее и позволяет для ряда шифрсистем применять новый способ 
доказательства отсутствие в них эквивалентных  ключей. Дело в том, что нетривиаль-
ная система классов эквивалентных ключей в этих шифрсистемах является и некото-
рой системой областей импримитивности группы подстановок. Полученная оценка 
длины запрета 
2
3
2 n
n
 произвольной двоичной функции говорит о намного меньшей 
трудоемкости известного метода распознавания закона функционирования проход-
ной линии задержки с неизвестной функцией выхода, основанного на наличии за-
претов у данного криптографического узла. Описаны методы построения новых 
классов автоматов с гарантированными периодами их выходных последовательно-
стей. Так, в частности, найдены условия кратности периодов выходных последова-
тельностей автоматов из построенных классов периоду входной последовательности. 
Эти классы таковы: автоматы без потери информации, перестановочные автоматы, 
автоматы без внешне автономных состояний, автономные последовательные соеди-
нения автоматов, линейные векторные автоматы, автоматы Медведева, кодирующие 
устройства с конечной памятью, обратимые автоматы.  
 
Введены понятия: 
 
меры приближенного периода периодической последовательности элементов, 
отражающее Хэмминговую близость последовательности к периодической по-
следовательности заданного периода; 
 
изопериода периодической последовательности элементов; 
 
-периода периодической последовательности элементов. 
 
Приведены:  
 
оценки приближенных периодов выходных последовательностей полноцикло-
вого автомата, представимого последовательным соединением автономного ав-
томата с неавтономным перестановочным автоматом; 
 
оценки изопериода и -периода последовательностей специальных автоматов, 
моделирующих получение суммарных шифров поточных шифров. 
Приведенные алгоритмы и методы являются новыми и более эффективными, 
чем ранее известные.  

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

ОПРЕДЕЛЕНИЯ, ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ  
 
Для множества Z, состоящего из элементов 1,2,…,k используется обозначение 
Z={1,2,…,k} или Z=1,k.  
Далее:  
– (a,b) – наибольший общий делитель двух чисел a,b, или ОНД(а, b);  
НОК(a,b) – наибольшее общее кратное чисел a,b , в ряде случае для удобства использует-
ся и обозначение [a,b];  
– a|b – a делит b; 
XY – декартовым произведением множеств X и Y; 
Xk – множество слов в алфавите X длины k; 
|M| – мощность множества М; 
h(M’) – образ подмножества M’М для отображения  h: MV. Часто мы будем опускать 
скобки и писать hM’, а для элемента mM будем писать h(m) или hm. 
Под словом автомат подразумевается конечный автомат A=(X, S, Y, h, f), где: 
X – конечное непустое множество, названное множеством входных символов (входной 
алфавит); 
X* – множество всех слов конечной длины в алфавите X; 
S – конечное непустое множество, названное множеством состояний (внутренний алфавит); 
Y – конечное непустое множество, названное множеством выходных символов (выходной 
алфавит); 
h: SX → S – функция переходов;  
f: SX→ Y – функция выхода. 
Если в момент времени t=1,2… .  Автомат A находится в состоянии s(t)S и на его 
вход поступил символ x(t)X, то в этот же момент времени на выходе автомата A образуется 
символ f(s(t),x(t)) и автомат A переходит в новое состояние s(t+1)=h(s(t),i(t)). 
При условии, что f(s,x)=λ(s) для любых xX, sS, где λ: S→Y, автомат Мили A может 
рассматриваться как автомат Мура и будет обозначатся через:  
A=(X, S, Y, h, λ). 
Если X состоит из одного элемента |X|=1, то такой автомат называется автономным, 
и обозначается через A = (S,Y,h,λ).  
Автомат часто задают его графом переходов: вершинами графа являются 
состояния автомата. Из каждого состояния s и каждого xX проводится ориентированная 
дуга (стрелка) в состояние s`=h(x,s). Она помечается двумя символами (x,y), где y=f(x,s). 
Таким образом, из каждого состояния выходят |X| дуг. Говорят, что состояние s` 
достижимо из s в автомате A,  если в его графе переходов существует ориентированный 
путь из s в s`.  Для таких пар  состояний (s,s`) можно ввести минимальное расстояние 
m(s,s`) от s до s`, как минимальное число дуг, по которым можно перейти из s в s`.  
Диаметром автомата A называют величину 
( , `)
max
( , `)
s s
m s s
, где максимум берется по 

всем парам состояний (s,s`), для которых существует m(s,s`).  
Граф переходов автомата (или просто, автомат) называют связным, если для 
любых его двух состояний s, s` в графе существует неориентированный путь  из s в s`, что 
равносильно существованию неориентированного пути из s` в s. Неориентированный путь 
это путь по состояниям графа переходов, использующий обычные дуги  и обратные к 
ним – . Если автомат не связный, то его граф переходов состоит из нескольких связных 
компонент – связных подавтоматов автомата.  

Автономный автомат A = (S,Y,h,λ) называют полноцикловым, если его граф 
состоит из цикла, содержащего все его состояния. 
Граф переходов автомата (автомат) называют сильно связным, если для любой 
пары упорядоченных его состояний (s,s`) существует ориентированный путь из  s в s`. В 
любом связном автомате можно выделить сильно связный подавтомат автомата.  
Нам удобно зачастую использовать несколько другое обозначение автомата 
A=(X,S,Y,h,f). 
Определим так называемые частичные функции переходов (hx)xX и выходов  
(fx)xX через h и f следующим образом: 
hx: SS,  hx(s)=h(x,s); fx:SY,  fx(s)=f(x,s). 
Новое обозначение автомата A имеет вид  
A=(X, S, Y, (hx)xX, (fx)xX). 
 
Итак: 
- hx: S→S – частичная функция переходов автомата A соответствующая входному символу  
xX, задаваемая соотношением hx(s) = h(s, x), sS (для удобства ниже в этой записи мы 
опускаем скобки при hx: hxs = h(s, x); 
hx(Z) – образ  множества Z, ZS  при отображении hx; 
- fx: S→Y – частичная функция выхода соответствующая входному символу xX, задаваемая 
соотношением fx(s) = f(s,x), sS (для удобства ниже в этой записи мы опускаем скобки 
при fx : fxs = f(s, x)); 
Читателю необходимо помнить, что cлово в каком-либо алфавите мы пишем 
отделяя буквы запятыми.  
Используются  дополнительные обозначения: 
- P = x(1), x(2), …, x(k), x(j)X, j{1,2,…, k} – входное слово длины k автомата A;  
- в ряде случаев, например, чтобы отличить обозначение вероятности P, мы используем и 
другие обозначения, в частности, обозначение: =x(1),x(2),…,x(k), или J= x(1),x(2),…,x(k); 
- |P| – длина входного слова P автомата A;  

- 
....
(
1)
(
2)
(1)
h
h
h
h
x k
x k
x
P



– отображение S→S, осуществляемое автоматом A в 

результате приложение к нему входного слова P=x(1),x(2),…,x(k);  
- каждое состояние вида 
( )
x
h s  называется 1-приемником состояния s;  

- состояние вида 
....
( )
(
1)
(1)
( ) h
h
h
s
x k
x
x k

 называется k-м преемником состояния s. 

- 
....
(
1)
(
1)
(1)
( )
f
h
h
h
f
P
x k
x k
x
x k



– отображение S→Y, осуществляемое автоматом 

A в результате приложения к нему входного слова P= x(1), x(2), …., x(k); 
- fPs или P(s) – заключительное состояние автомата, полученное с начального состояния  s 
при водном слове (последовательности) Р; 
- A(s,P) =y1,y2,….,yk, yiY, j[1, k] – выходное слово автомата A, полученное в результате  
приложения входного слова P= x(1), x(2), …., x(k) к автомату A с начальным состоянием 
sS; 
- АМ(s,P)=s1,s2,…,sj,… – последовательность состояний автомата А=(X,S,Y,h,f), отвечающая 
его входной последовательности Р и начальному состоянию s=s1 из S; 
- полугруппа G=<(hx)xX>автомата A это полугруппа отображений множества S в себя, порожденная 
частичными функциями перехода (hx)xX  автомата A и тождественным отображением 
S  в себя; 
Автомат A называют перестановочным, если его частичные функции переходов 
(hx)xX осуществляют взаимно однозначные отображения S в S, говорят также: биекции S в 
S, (подстановки на S). 

Имея дело с несколькими автоматами, будем отмечать пятерки X, S, Y, h, f различ-
ными символами (верхними и нижними), например, A = (XA, SA, YA, hA , fA). Если же авто-
мат обозначается символом A с каким – ни будь индексом, например, A’, то иногда для 
простоты мы будем помечать элементы его пятерки тем же индексом, например, (X’, S’, 
Y’, h’, f’). Аналогичным образом мы будем поступать и для различения введенных пара-
метров автоматов, например, полугруппа автоматов A и B удобно обозначать через GA и 
GB, соответственно.  
Напомним следующие основные понятия. 
ОПРЕДЕЛЕНИЕ 1. Состояние s и s’ автомата A называется k-неотличимыми, если  
A(s, P)) = A(s’,P) 
для любого входного слова P = x(1), x(2),…, x(k) длины k автомата A. В противном случае 
они называются k-различимыми.  
ОПРЕДЕЛЕНИЕ 2. Состояния s и s’ автомата A называются неотличимыми, если 
они k-неотличимы для любого k. В противном случае они называются различными (от-
личными).  
Хорошо известна  
ТЕОРЕМА 1. [6, 10]. Для неотличимости двух состояний автомата A = (X, S, Y, h, f) 
достаточна их (│S│- 1)–неотличимость.  
Поскольку бинарное отношение k – неотличимости состояний автомата является 
отношением эквивалентности, все множество состояний S автомата A разбивается на не-
пересекающиеся классы k-неотличимых состояний.  
 
Будем обозначать это разбиение через: 
Nk = (
1
2
,
,.....,
k
k
k
k
l
N
N
N
), 

k
j
N , j є [1, l k] – классы k-неотличимых состояний автомата A, а lk – число классов 

 k-неотличимых состояний автомата A. Классы неотличимых состояний автомата A бу-
дем обозначать через Nj , j є [1, l], а само разбиение множества S эти классы через  
N = (N1, N2, …., Nl), 
l – число классов неотличимых состояний автомата A.  
ОПРЕДЕЛЕНИЕ 3. Число R называется степенью различимости автомата A, если  
NR = N и Nk ≠ N при k<R. 
ОПРЕДЕЛЕНИЕ 4. Автомат A называется приведенным (или находится в приве-
денной форме), если │Nj│ = 1 для любого j[1, l].  
Очевидно, если A приведенный автомат, то l = │S│. 
 
 
 

Часть 1. НЕОТЛИЧИМОСТЬ СОСТОЯНИЙ 
И ВХОДНЫХ СЛОВ АВТОМАТОВ 
 
Глава 1 
Классы автоматов 
и операции над автоматами 
 
 
Ниже приводятся некоторые классы автоматов, используемые при синтезе сим-
метричных шифрсистем [2]. 
 
 
1.1. Автономный линейный регистр сдвига 
 
Обозначим через F2 из двух элементов, 
2
n
F  – координатное векторное пространство 

размерности n над полем F2 (вектора – двоичные наборов длины n). Выберем некоторую 
линейную двоичную функцию на 
2
n
F  , которую запишем в виде  

(а,x)=a1x1a2x2…anxn, 
(a1,a2…an) 
2
n
F , x=(x1,…,xn) – двоичные переменные,  – сложение по модулю 2. 

Автономным линейным регистром сдвига называется автономный автомат A=(S,Y,h,), 
где S=
2
n
F \(o), – 
2
n
F  с исключенным нулевым вектором, Y= F2, h:SY, для v=(v1,v2,…,vn) 

2
n
F \(o) 

h(v1,v2,…,vn)= (v2,…,vn,(a,v)) 
 – произвольная отличная от нуля линейная функция на 
2
n
F  (ее ограничение на  
2
n
F \(o) 

мы обозначили той же буквой).  
 
 
1.2. Неавтономный линейный регистр сдвига  
 
Используем введенные обозначения. Неавтономным линейным регистром сдвига 
называется автомат A=(X,S,Y,(hx)xX,), где X=F2, S=
2
n
F \(0), Y=F2, 

h0(v1,v2,…,vn)=(v2,…,vn, ,(a,v)), 
h1(v1,v2,…,vn)=(v2,…,vn, 1,(a,v)), 
 –  произвольная отличная от нуля линейная функция на 
2
n
F . 
 
 
1.3. Неавтономный регистр сдвига  
 
Используем введенные обозначения и дополнительно через (x1,…,xn) обозначим 
произвольную двоичную функцию на 
2
n
F . Неавтономным регистром сдвига называется 

автомат A=(X,S,Y,(hx)xX,), где X=F2, S=
2
n
F , Y=F2, 

h0(v1,v2,…,vn)=(v2,…,vn, ( v1,v2,…,vn)), 
h1(v1,v2,…,vn)=(v2,…,vn, 1( v1,v2,…,vn)), 
(v1,v2,…,vn) 
2
n
F ,  – произвольная двоичная функция на 
2
n
F .   

Автономный регистр сдвига A=(S,Y,h,), отличается от неавтономного наличием 
одной частичной функции перехода 
h(v1,v2,…,vn)=(v2,…,vn, (x1,…,xn)). 
 
 
1.4. Проходная линия задержки  
 
Проходная линия задержки это неавтономный автомат A=(X,S,Y,(hx)xX,) вида  
X=F2, S=
2
n
F , Y=F2, h0(v1,v2,…,vn)=(v2,…,vn-1,0), h1(v1,v2,…,vn)=(v2,…,vn-1,1),  – произвольная 

двоичная функция.  
В качестве упражнения: 
 определите аналогичные автоматы для произвольного конечного поля Fq; 
 докажите, что неавтономный регистр сдвига будет перестановочным автоматом тогда 
и только тогда, когда двоичная функция  имеет вид 
(x1,…,xn)=x1  `(x2…,xn), 
где `(x2,…,xn) – произвольная функция от двоичных переменных x2,…,xn. 
 
 
1.5. Шифрующий автомат  
 
Понятие шифрующего автомата трактуется неоднозначно (см. том 1 или [25]).  
Первое определение состоит в том, что шифрующий автомат есть множество автома-
тов А(r), rR c начальными состояниями s(r)S(r). Такое определение равносильно тому, 
что под шифрующим автоматом понимают некоторое множество автоматных отображе-
ний множества открытых текстов в шифрованные.  
Второе 
определение 
шифрующего 
автомата 
состоит 
в 
том, 
что 
автомат 
А=(X,S,Y,(hx)xX,(fx)xX) является шифрующим автоматом, если его автоматные отображения 
А,s X*Y* , sS являются инъективными отображениями. Такое определение согласуется с 
определением шифра (Х,К,У,f) в том смысле, что в качестве отображений f берутся авто-
матные инъективные отображения.  
Для большей общности, иногда второе определение обобщают. Именно, рассмат-
ривают автоматы, у которых X=Г@, где Г – алфавит внешней части ключа, часть ключа: 
=1,2,…L, jГ; @- алфавит открытого текста. При фиксированных частях ключа ГL и 
sS требуют инъективность отображения @L в YL, то есть при входных различных после-
довательностях вида P=(a1,1),(a2,2),…(aL,L) и P`= (a`1,1), (a`2,2),…(a`L,L) требуют, 
чтобы А(s,P)А(s,P`) при любом натуральном L. 
Выясним условия, при которых автомат А=(X,S,Y,h,f) является шифрующим авто-
матом, то есть автоматные отображения А,s X*Y* , sS являются инъективными ото-
бражениями. Для отображения f: XSY обозначим через fs отображение X в Y: 
fs(x)=f(x,s). Через Ss обозначим множество состояний автомата А, содержащее s и все со-
стояния s`S, достижимые из s в графе переходов автомата А, то есть для которых есть 
пути из s в s`. На множестве Ss определен подавтомат Аs=(X,Ss,Y,h,f) автомата А (здесь ог-
раничения отображений h, f обозначены теми же буквами). С использованием введенных 
определений несложно доказывается.