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

В Ы С Ш Е Е  О Б Р А З О В А Н И Е
В Ы С Ш Е Е  О Б Р А З О В А Н И Е

У Ч Е Б Н О Е  П О С О Б И Е
У Ч Е Б Н О Е  П О С О Б И Е

А.В. Бабаш
КРИПТОГРАФИЧЕСКИЕ
МЕТОДЫ  ЗАЩИТЫ  
ИНФОРМАЦИИ

Том 3

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

Том 3

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

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

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

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

А.В. БАБАШ

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

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

ISBN 978-5-369-01304-5 (РИОР)
ISBN 978-5-16-009336-9 (ИНФРА-М)

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

Б12

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

ISBN 978-5-369-01304-5 (РИОР)
ISBN 978-5-16-009336-9 (ИНФРА-М)

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

Подписано в печать 15.08.2013. 
Формат 60х88/8. Бумага офсетная. Гарнитура Newton. 
Печать офсетная. Усл. печ. л. 26,46. Уч.-изд. л. 20,57.
Тираж 300 экз. Заказ № 
Цена свободная.

ТК 248900 – 12734 – 150813

ООО «Издательский Центр РИОР»
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 
Определения, обозначения и сокращения ................................................................... 
8 
 
Часть 1. ЭКСПЕРИМЕНТЫ С АВТОМАТАМИ 
 
Глава 1. Определение заключительных состояний автомата по входной  
и выходной последовательностям. Автоматы с конечной памятью................................ 
11 
1.1. Основные понятия ................................................................................................................. 
11 
1.2. Свойства автоматов с конечной памятью........................................................................... 
12  
1.3. Алгоритм определения автоматов с конечной памятью.................................................... 
13  
 
Глава 2. Определение входного слова автомата по его начальному состоянию  
и выходной последовательности. Автоматы без потери информации........................... 
15 
2.1. Основные понятия ................................................................................................................. 
15  
2.2. Задача распознавания неизвестной входной последовательности автомата  
по его начальному состоянию и выходной последовательности............................................. 
16 
2.3. Автоматы без потери информации конечного порядка ..................................................... 
17  
 
Глава 3. Об экспериментах по распознаванию информации о входном слове  
автомата .............................................................................................................................. 
19 
3.1. Понятие закрытого однородного эксперимента с автоматами ......................................... 
19 
3.2. Закрытый однородный эксперимент по распознаванию информации  
о первом входном символе входного слова автомата по начальному  
состоянию и выходной последовательности ............................................................................. 
23  
3.3. Закрытый однородный эксперимент по распознаванию информации  
о входном слове перестановочного автомата по начальному состоянию  
и выходной последовательности ................................................................................................ 
25 
3.4. Закрытый однородный эксперимент по распознаванию информации  
о последнем символе входного слова автомата по заключительному  
состоянию и выходной последовательности ............................................................................. 
26 
3.5. Закрытый однородный эксперимент по распознаванию информации  
о входном слове автомата по заключительному состоянию  
и выходной последовательности ............................................................................................... 
28 
 
Глава 4. О восстановлении информации о входном слове перестановочного  
автомата Медведева по начальным и заключительным состояниям............................. 
29 
4.1. Основные обозначения и постановка задачи восстановления информации  
о входном слове перестановочного автомата Медведева по начальным  
и заключительным состояниям ................................................................................................... 
29 
4.2. Основные утверждения......................................................................................................... 
30 
4.3. Оценки параметров ............................................................................................................... 
33 
4.4. Оценки параметров полугруппы автомата.......................................................................... 
34 
4.5. Структура отношения эквивалентности П*k ..................................................................... 
35 
4.6. Алгоритм проверки свойства автомата А приближенно восстанавливать  
входные слова длины k по L начальным и заключительным состояниям .............................. 
36 
 
Глава 5. Определение входного слова векторного перестановочного автомата  
по множеству пар начальных и заключительных состояний с помощью  
вероятностной модели их статистических зависимостей ................................................ 
38 
5.1 Постановка задачи и план ее решения ................................................................................ 
38 
5.2. Реализация модернизации идеи Матсуи............................................................................. 
39 
5.3. Первый этап метода.............................................................................................................. 
40 
5.4. Второй этап метода............................................................................................................... 
41 
5.5. Третий этап метода ............................................................................................................... 
42 

5.6. Дополнительные пояснения ................................................................................................. 
43 
5.7. Об эффективности алгоритма.............................................................................................. 
47 
 
Глава 6. Случайное тестирование конечных автоматов по входной  
и выходной последовательностям..................................................................................... 
48 
 
Часть 2. МОДЕЛИ АВТОМАТОВ НА ОСНОВЕ СЛЕДСТВИЙ ЗАКОНОВ 
ИХ ФУНКЦИОНИРОВАНИЯ 
 
Глава 7. Модели автоматов–следствия уравнений их функционирования.................... 
52 
7.1. Основные обозначения......................................................................................................... 
52 
7.2. Построение моделей-следствий автомата ......................................................................... 
53 
7.3. Изучение примитивности степеней автомата..................................................................... 
55 
 
Глава 8. Модели автоматов, построенные с помощью обработки их выходных  
последовательностей инициальными автоматами........................................................... 
59 
8.1. Построение моделей-следствий автомата. Постановка задачи....................................... 
59 
8.2. Описание  слабо неприведенных автоматов относительно В(Х,Y).................................. 
60 
 
Глава 9. Функции - модели автоматов, построенные на основе следствий  
уравнений их функционирования....................................................................................... 
65 
9.1. Построение моделей-следствий автомата ......................................................................... 
65 
 
Часть 3. МОДЕЛИ АВТОМАТОВ НА ОСНОВЕ РАССТОЯНИЙ ХЭММИНГА 
 
Глава 10. Модели автоматов, построенные на основе расстояния Хэмминга  
между их табличными заданиями ...................................................................................... 
73 
10.1. О задаче определения начального состояния автомата по его входной  
и выходной последовательностям.............................................................................................. 
73 
10.2. Использование статистического аналога конечного автомата,  
построенного с помощью искажений его частичных функций переходов............................... 
74 
10.3. Использование статистического аналога конечного автомата,  
построенного с помощью искажений его частичных функций переходов  
и выходов ...................................................................................................................................... 
86 
10.4. Пороговый критерий с уровнем (m,c)................................................................................. 
87 
10.5. Метод максимального правдоподобия.............................................................................. 
88 
 
Глава 11.  Приближенные модели автоматов, построенные на основе  
расстояния Хэмминга между их выходными последовательностями............................. 
95 
11.1. Введение .............................................................................................................................. 
95 
11.2. Основные понятия и предварительные результаты ........................................................ 
95 
11.3. Вычисление значения меры неотличимости состояний по кратному 
 эксперименту с автоматами........................................................................................................ 
101 
11.4. Приближенные модели связных перестановочных автоматов....................................... 
102 
 
Глава 12. Неотличимость состояний конечных автоматов по мере 0........................... 111 
 
Глава 13. Приближенные модели автоматов, построенные на основе  
преднеотличимости состояний и частичных гомоморфизмов ......................................... 113 
13.1. Преднеотличимость состояний конечных автоматов ...................................................... 
113 
13.2. Преднеотличимость состояний автоматов без выхода ................................................... 
113 
13.3. Преднеотличимость состояний произвольных автоматов .............................................. 
115 
13.4. Частичные гомоморфизмы автоматов без выхода .......................................................... 
117 
13.5. Частичные гомоморфизмы произвольных автоматов ..................................................... 
124 
 

Глава 14. Метод приближенных моделей в решении задач определения  
начальных состояний и входных слов автомата............................................................... 128 
14.1. Постановка задачи .............................................................................................................. 
128 
14.2. Определение начального состояния и входного слова автомата  
по его выходному слову............................................................................................................... 
130 
14.3. Определение входного слова автомата по его начальному состоянию  
и выходному слову ....................................................................................................................... 
132 
14.4. Определение входного слова автомата по его начальному  
и заключительному состояниям .................................................................................................. 
134 
14.5. Определение входного слова автомата по его начальному  
и заключительному состояниям .................................................................................................. 
136 
14.6. Метод сведения изложенных задач к задачам решения системы  
уравнений с искаженными правыми частями ............................................................................ 
138 
 
Часть 4. МОДЕЛИ АВТОМАТОВ НА ОСНОВЕ ОБОБЩЕНИЯ ПОНЯТИЯ  
ГОМОМОРФИЗМА АВТОМАТОВ 
 
Глава 15. Многозначные гомоморфизмы конечных автоматов ....................................... 141 
15.1. Обозначения ........................................................................................................................ 
141 
15.2. Многозначные гомоморфизмы автоматов ........................................................................ 
141 
15.3. Описание многозначных гомоморфизмов для связных  
перестановочных автоматов ....................................................................................................... 
145 
15.4. Образы СМГ связных перестановочных автоматов......................................................... 
147 
15.5. Образы МГ произвольного автомата без выходов........................................................... 
148 
15.6. Пример использования МГ автомата ................................................................................ 
149 
15.7. Некоторые обобщения многозначных гомоморфизмов автомата.................................. 
150 
 
Глава 16. Модели конечных автоматов, построенные на основе  
гомоморфизмов поведения................................................................................................. 152 
16.1. Обозначения ........................................................................................................................ 
152 
16.2. Обобщенный гомоморфизм поведения автоматов.......................................................... 
152 
16.3. Гомоморфизм поведения автоматов................................................................................. 
154 
16.4. Построение всех конгруэнций поведения автомата без выходов .................................. 
155 
16.5. Полностью определенные образы автомата при гомоморфизмах поведения........................ 
156 
16.6. Частные случаи гомоморфизма поведения автоматов ................................................... 
158 
16.7. Обобщенный многозначный гомоморфизм автоматов.................................................... 
160 
 
Глава 17. Методы определения начального состояния автомата по входной  
и выходной последовательностям с использованием обобщений понятия  
гомоморфизма автоматов .................................................................................................. 163 
17.1. Постановка задачи определения начального состояния автомата 
по входной и выходной последовательностям с использованием 
гомоморфного образа ассоциированного с ним автомата Медведева................................... 
163 
17.2. Определение начального состояния автомата по входной и выходной  
последовательностям с использованием гомоморфного образа  
ассоциированного с ним автомата Медведева ........................................................................ 
164 
17.3. Определение начального состояния перестановочного автомата  
по входным и соответствующим выходным последовательностям  
с использованием меры неотличимости состояний ............................................................... 
170 
17.4. Определение начального состояния s(0) автомата A  
по его входной Q=x(1),x(2),…,x(L) и выходной A(s(0),Q)=Z последовательностям................ 
171 
17.5. Определение начального состояния автомата по входной и выходной  
последовательностям с использованием -неотличимых состояний.................................... 
172 
17.6. Определение начального состояния перестановочного автомата  
по входной и выходной последовательностям с использованием  
-гомоморфизмов автоматов..................................................................................................... 
173 

17.7. Определение начального состояния s0 автомата по известным входным  
словам XN и соответствующим им выходным словам A(s0,)=Q() .................................. 
175 

17.8. Определение начального состояния 

1
2
0
0
,
s
s
 по выходной последовательности 

A

1
2
0
0
,
s
s
=g(1),g(2),…,g(N) последовательного соединения автоматов................................. 
176 

17.9. Гомоморфизмы автоматов по мере ................................................................................ 
177 
 
Глава 18. Системные множества со свойством подстановки .......................................... 181 
18.1. Введение .............................................................................................................................. 
181 
18.2. Основные определения и обозначения работы [52. А. Фридман,  
П. Менон “Теория и проектирования переключательных схем”. М., “Мир”, 1978]............................. 
181 
18.3. Системные множества со свойством подстановки........................................................... 
182 
18.4. Неточности, обнаруженные в работе [52] ......................................................................... 
182 
18.5. Алгоритм поиска всех системных множеств со свойством  
подстановки работы [52] .............................................................................................................. 
184 
18.6. Новый алгоритм поиска всех системных множеств  
со свойством подстановки ........................................................................................................... 
185 
18.7. Поиск систем слабой импримитивности для заданного автомата.................................. 
188 
 
Часть 5. ПОМЕХОУСТОЙЧИВЫЕ АВТОМАТЫ 
 
Глава 19. Автоматные отображения периодических последовательностей,  
не размножающие искажений............................................................................................. 189 
19.1. Введение .............................................................................................................................. 
189 
19.2. Основные обозначения и понятия ..................................................................................... 
190 
19.3. Описание множества GA(XП,YП, =, μ)............................................................................... 
191 
19.4. Описание множества GA(XП,YП,≥,μ)................................................................................. 
195 
 
Глава 20. Автоматные отображения слов, размножающие искажения  
в метриках Хэмминга и Левенштейна не более чем в К раз............................................ 201 
20.1. Историческая справка ......................................................................................................... 
201 
20.2. Обозначения и основные понятия ..................................................................................... 
201 
20.3. Описание множества А((X*,Y*,К)...................................................................................... 
203 
20.4. Описание множества АG((X*,Y*,К).................................................................................... 
210 
20.5. Описание множества АG((X*,Y*,D,К).................................................................................. 
212 
 
Список использованных источников..................................................................................... 
214 
 

ВВЕДЕНИЕ 
 
В данном (третьем) томе пособия представлены несколько методик построения 
приближенных (численно приближенных) моделей сложных автоматов, моделирующих 
современные дискретные устройства криптографической защиты информации. Пусть 
задан некоторый конечный автомат A. Для криптографических приложений задача моделирования в теории автоматов состоит в том, чтобы, исходя из данных о внешнем 
функционировании автомата A, построить «более простой» автомат A', достаточно адекватно описывающий поведение автомата A. Под словами «более простой» обычно понимают автомат с меньшим числом состояний по сравнению с исходным автоматом. При 
этом автомат A' может описывать внешнее поведение автомата A не полностью, а приближенно. В этом случае говорят о приближенных моделях автоматов. Мы предлагаем четыре 
подхода к решению задачи приближенного моделирования шифрующих автоматов. 
Первый подход к решению проблемы моделирования состоит в построении для 
исходного автомата A нового автомата, являющегося некоторым следствием законов 
функционирования автомата A.  
Второй подход состоит в том, что на множестве всех автоматов с общими входным 
и выходным алфавитами вводится функция близости , для определения которой используется расстояние Хэмминга между выходными последовательностями. 
Третий подход к построению приближенных моделей обобщает идеи приближения сложной дискретной функции более простой функцией (например, линейной). 
В автоматной трактовке этот подход состоит в замене исходного автомата A на его статистический аналог A'. Аналог выбирается так, чтобы решаемая задача для автомата A 
имела для автомата A' достаточно простое по сложности решение, и одновременно табличное задание автомата A' ненамного отличалось от табличного задания автомата A. 
В этом случае замена A на A' позволяет снизить сложность решения за счет некоторой 
ненадежности ее решения. 
Четвертый подход состоит в получении следствий из уравнений функционирования автомата A путем обобщения понятия гомоморфизма автоматов и построения 
«обобщенных» образов автомата A при таких обобщенных гомоморфизмах. Этот подход 
связан с тем, что гомоморфный образ автомата в ряде практических задач играет роль его 
модели. Суть обобщения понятия гомоморфизма состоит в рассмотрении бинарных отношений вместо отображений, входящих в определение гомоморфизма. Таким образом, 
расширяется класс автоматов, имеющих гомоморфный образ с меньшим числом состояний, до класса автоматов, имеющих обобщенный гомоморфный образ с меньшим числом 
состояний.  
Представленные результаты являются частью фундамента для построения новых 
методов криптографического анализа и синтеза. Они могут быть использованы в криптографической практике.  
Пособие предназначено для студентов высших учебных заведений, обучающихся 
по различным специальностям, связанным с защитой информации. Оно содержит методический материал для ряда инновационных курсов лекций по профилю «Криптографическая защита информации». Ряд представленных результатов полезен специалистам 
и аспирантам, специализирующихся в указанной области.  
В пособии учтены тенденции развития образования в части перехода обучения на 
бакалавриат и магистратуру. 

, Z, 1,2,…,k, Z={1,2,…,k}.
:
XY – X Y;
Xk – X k;
|M| – ;
h(M’) – M’h: MV. hM’, mM h(m) hm.
A=(X, S, Y, h, f), :
X – , ();
X* – X;
S – , ();
Y – , ();
h: SX S – ;
f: SY – .
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) xX, sS, : SY, A :
A=(X, S, Y, h, ).
X |X|=1, , A = (S,Y,h,).
: . s xX () s`=h(x,s). (x,y), y=f(x,s).
, |X| . , s`
sA, s s`. (s,s`) m(s,s`) s s`, , s s`.
A = (S,Y,h,) , , .
() , (s,s`) s s`.
.
A=(X,S,Y,h,f).
(h x)xX(fx)xXh f :
hx: SS,  hx(s)=h(x,s); fx:SY,  fx(s)=f(x,s).
A :
A=(X, S, Y, (hx)xX, (fx)xX).
:
hx: SS – A 

xX, hx(s) = h(s, x), sS (hx: hxs = h(s, x);
hx(Z) – Z, ZS  hx;
fx: SY – xX, fx(s) = f(s,x), sS (fx : fxs = f(s, x)).
, .
:
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)
....
x k
x k
x
P
h
h
h
h
– SS, A P=x(1),x(2),…,x(k);
( )
x
h s 1-s;

....
( )
( )
(
1)
(1)
s
x k
x k
x
h
h
h
k-s.

(
1)
(
1)
(1)
....
( )
P
k
k
f
f
h
h
h
x k
x
x
x
– SY, A P= x(1), x(2), …., x(k);
fPs P(s) – , s
() ;
A(s,P) =y1,y2,….,yk, yiY, j[1, k] – A, P= x(1), x(2), …., x(k) A sS;
(s,P)=s1,s2,…,sj,… – =(X,S,Y,h,f), s=s1 S;
G=<(hx)xX>A S , (hx)xX A S  ;
A , (hx)xX 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 GAGB, .
.
1. s s’ A k-, A(s, P)) = A(s’,P)
P = x(1), x(2),…, x(k) k A. k-.