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

Москва

2023

Федеральное государственное образовательное бюджетное учреждение 

высшего образования «ФИНАНСОВЫЙ УНИВЕРСИТЕТ  
ПРИ ПРАВИТЕЛЬСТВЕ РОССИЙСКОЙ ФЕДЕРАЦИИ»

(Финансовый университет)

1919

В.М. Фомичев

КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ 

ЗАЩИТЫ ИНФОРМАЦИИ

(курс лекций)

Учебное пособие 

для академического бакалавриата

Рекомендовано Учебно-методическим отделом высшего образования 

в обучающихся по инженерно-техническим направлениям  

и специальностям

   

Ф76

Фомичев В.М.

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

ции (курс лекций): Учебное пособие. — М.: Прометей, 
2023. — 340 с.

ISBN 978-5-00172-538-1

В учебном пособии систематически изложены основы крипто-

графии. Описаны классы современных криптографических систем, 
предназначенных для обеспечения информационной безопасности 
информационно-технологических систем. Для закрепления знаний 
предложены задачи, упражнения и контрольные вопросы.

Книга предназначена для студентов, аспирантов и преподава-

телей в области криптографических методов защиты информационного 
обмена в ИТС, а также для практических работников в области 
криптографической защиты информации.

ISBN 978-5-00172-538-1

 
©  Фомичев В.М., 2023

 
© Издательство «Прометей», 2023

Автор: 

Фомичев Владимир Михайлович — доктор физико-математиче-

ских наук, профессор департамента информационной безопасности 
факультета «Информационные технологии и анализ 
больших данных» Финансового университета при Правительстве 
РФ, ведущий научный сотрудник Института 
проблем информатики ФИЦ «Информатика и управление» 
РАН (Federal Research Center "Computer Science and 
Control"). 

Рецензенты: 

Коренева Алиса Михайловна — кандидат физико-математиче-

ских наук, начальник отдела криптографического анализа 
Службы сертификации ООО «Код Безопасности». 

УДК 621.391(075.8)
ББК 32.811я73
 
Ф76

ОГЛАВЛЕНИЕ

Основные обозначения  . . . . . . . . . . . . . . . . . . . . . . . . . . .   5
Предисловие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   6

Глава I. Основы дискретной математики 

в криптографии

Л е к ц и я  1.  Комбинаторика. Бинарные отношения.  

Графы . . . . . . . . . . . . . . . . . . . . . . . . . . . . .   8

Л е к ц и я  2. Алгебраические структуры . . . . . . . . . . . .  31
Л е к ц и я  3.  Полугруппы, группы и графы 

преобразований  . . . . . . . . . . . . . . . . . . . . .  46

Л е к ц и я  4. Булевы функции  . . . . . . . . . . . . . . . . . . . .  59
Л е к ц и я  5. Дискретные функции  . . . . . . . . . . . . . . . .  70
Л е к ц и я  6.  Сбалансированность и биективность 

функций векторных пространств . . . . . . .  83

Л е к ц и я  7. Периодические последовательности  . . . . 100

Глава II. Симметричные криптосистемы

Л е к ц и я  8. Поточные системы шифрования . . . . . . . . 120
Л е к ц и я  9. Криптографические генераторы . . . . . . . . 135
Л е к ц и я 10. Симметричные блочные шифры . . . . . . . . 154
Л е к ц и я 11. Режимы шифрования СБШ . . . . . . . . . . . . 167
Л е к ц и я 12. Перемешивающие свойства функций  . . . 181
Л е к ц и я 13.  Примитивные множества матриц 

и орграфов. Локальная примитивность 
матриц и орграфов . . . . . . . . . . . . . . . . . . . 194

Л е к ц и я 14.  Троичные матрицы  

и помеченные орграфы  . . . . . . . . . . . . . . . 206

Л е к ц и я 15.  Характеристики перемешивания 

и нелинейности произведения 
преобразований . . . . . . . . . . . . . . . . . . . . . . 216

Л е к ц и я 16.  Использование МГП для оценки 

перемешивающих и нелинейных свойств 
криптографических функций . . . . . . . . . . 226

   

Глава III. Асимметричные криптосистемы

Л е к ц и я 17.  Кольца целых чисел и вычетов,  

алгоритм Евклида . . . . . . . . . . . . . . . . . . . 234

Л е к ц и я 18.  Функции теории чисел, 

основные теоремы . . . . . . . . . . . . . . . . . . . 245

Л е к ц и я 19. Решение сравнений . . . . . . . . . . . . . . . . . . 255
Л е к ц и я 20.  Системы шифрования RSA и Эль Гамаля. 

Распознавание и генерация больших 
простых чисел . . . . . . . . . . . . . . . . . . . . . . 265

Л е к ц и я 21.  Стойкость асимметричных 

криптосистем . . . . . . . . . . . . . . . . . . . . . . . 278

Л е к ц и я 22. Хэш-функции, электронная подпись  . . . 287

Глава IV. Ключевые системы и протоколы

Л е к ц и я 23. Основы анализа криптосистем . . . . . . . . . 300
Л е к ц и я 24. Ключевая подсистема криптосистемы . . . 313
Л е к ц и я 25. Криптографические протоколы . . . . . . . . 325

Использованная литература . . . . . . . . . . . . . . . . . . . . . . . 339

ОСНОВНЫЕ ОБОЗНАЧЕНИЯ

N 
— множество натуральных чисел;

N0 
= N 2 {0};

Z 
— множество целых чисел;

Q 
— множество рациональных чисел;

R 
— множество действительных чисел;

Nn 
= {1, … , n}, n ∈ N;

 a  
— наибольшее целое число, не большее a, a ∈ R;

 a  
— наименьшее целое число, не меньшее a, a ∈ R;

m | n 
— m делит n без остатка, где m, n ∈ N;

D(n) 
— множество всех делителей d числа n, где d, n ∈ N;

НОК(…) — наименьшее общее кратное чисел; НОК(n, m) = [n, m];
НОД(…) — наибольший общий делитель чисел; НОД(n, m) = (n, m);
| X  | 
— порядок конечного множества X; | X  | = ord X; 

X n 
— декартова n-я степень множества, где n ∈ N;

V n

  
— множество двоичных n-мерных векторов, где n ∈ N;

Z m 
— кольцо вычетов по модулю m, где m ∈ N;

GF  (  pn) — поле Галуа порядка pn, где n ∈ N, p — простое;
dimV 
— размерность векторного пространства; 

X ↔ Y — биекция множеств X  и  Y;
deg f 
— степень многочлена f;

s(n, d) 
—  число булевых мономов от n переменных степени 

не выше d; 

 f   
— вес булевой функции;

∏ n 
— моноид всех преобразований n-множества;

S n 
— полная симметрическая группа подстановок степени n;

ord g 
— порядок элемента g полугруппы (группы);

Γ (g) 
— граф преобразования g;

X
 
— последовательность над конечным множеством X;

ЛРП 
— линейная рекуррентная последовательность;

ЛРПmax-п — ЛРП порядка n с максимальной длиной периода;
ЛРС 
 — линейный регистр сдвига

ЛРСmax-п — ЛРС длины n с максимальной длиной периода;
⇔ 
— «… тогда и только тогда, когда …»;

v 
— «докажите, что …» или «докажите …»;

t и u — начало и завершение доказательства теоремы, леммы, …
w 
— завершение замечания (примера, формулировки, …).

ПРЕДИСЛОВИЕ

Это пособие, написанное как курс лекций для студентов 

(бакалавриата и магистратуры), включает основные разделы 
криптографии, позволяющие сформировать современного специалиста 
в области информационной безопасности. Книга 
также полезна молодым специалистам и аспирантам при подготовке 
к экзаменам, как вступительного в аспирантуру, так 
и кандидатского минимума.

Основное отличие этой книги от других учебных изданий 

в области криптографии состоит в системном изложении относительно 
новых результатов в области перемешивания элементов 
входных данных итеративными криптографическими 
функциями. Важность темы перемешивания информации 
в криптосистеме была обоснована в книге 40-х гг. 20-го века 
американского криптографа К. Шеннона. Эта тема получила 
дальнейшее развитие уже в XX веке в многочисленных трудах 
зарубежных и российских криптографов, конкретизирующих 
принципы Шеннона, и приобрела современный вид благодаря 
матрично-графовому подходу, развитому в ряде трудов автора 
и некоторых его учеников, опубликованных в последнее десятилетие. 
В лекциях отражен прикладной характер этого направления 
исследований в криптографии.

Материал 25 лекций, рассчитанный на изучение в течение 

двух семестров, тематически разбит на 4 главы. Каждая лекция 
снабжена списком заданий и упражнений, позволяющих 
студентам закреплять на семинарских занятиях основные понятия 
и результаты криптографии. Такие объекты, как теоремы, 
утверждения, примеры, рисунки, таблицы и формулы, 
имеют тройную нумерацию. Первый номер совпадает с номером 
лекции, второй номер — порядковый номер раздела лекции, 
третий номер — номер объекта в разделе лекции.

Изучение материала лекций предполагает знание обучаю-

щимся основ дискретной математики, математического анализа, 
линейной алгебры и теории вероятностей. 

Материал книги может быть использован читателем как от-

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

 
В.М. Фомичев

Гл а в а  I

u

ОСНОВЫ 

ДИСКРЕТНОЙ МАТЕМАТИКИ 

В КРИПТОГРАФИИ 

лекции 1-7

Л е к ц и я 1  

Комбинаторика, бинарные отношения, 

графы

1.1. Комбинаторные схемы

Предметом комбинаторики являются задачи перечисле-

ния, т.е. подсчета числа элементов множества с заданными 
свойствами. 

Основные правила перечисления. В комбинаторике под-

множество порядка r множества X называют выборкой размера 
r из X. Если порядок следования элементов не имеет 
значения, то выборку называют неупорядоченной. В противном 
случае выборка называется упорядоченной. Упорядоченные 
выборки, состоящие из одинаковых элементов 
и отличающиеся порядком их следования, считаются различными.


Для подсчета числа различных выборок с заданными 

свойствами используются следующие общие правила.

Правило суммы: если число различных выборок со свой-

ством 1 равно n1, и число различных выборок со свойством 2 
равно n2, и все выборки не обладают свойствами 1 и 2 одновременно, 
то число различных выборок со свойством 1 или 
со свойством 2 равно n
n
1
2
+
.

Правило произведения: если число различных выборок 

из X со свойством 1 равно n1 и число различных выборок из 
Y со свойством 2 равно n2, (свойства могут совпадать), то 
число различных пар из X
Y
×
 таких, что первая выборка 

пары имеет свойство 1 и вторая выборка пары имеет свойство 
2, равно n n
1
2.

П р и м е р 1.1.1. Правило суммы. В университете число 

студентов, обучающихся по экономическим специальностям, 
равно 800, и число студентов, обучающихся по инже-

Лекция 1. Комбинаторика, бинарные отношения, графы 

нерным специальностям, равно 100. Тогда число студентов, 
обучающихся по экономическим или инженерным специальностям, 
равно 900. 

Правило произведения и его обобщение. а) Число пар 

студентов, обучающихся по экономическим и инженерным 
специальностям, равно 80000.

б) Число 7-значных телефонных номеров с ненулевой 

первой цифрой равно 9 × 106.

в) Число строк длины n, состоящих из «нулей» и «еди-

ниц», равно 2n. w

Схемы выборок, биномиальные коэффициенты. Пусть 

выборка образуется в результате последовательного извлечения 
элементов из n-множества X. Различаются выборки 
с возвращением, или с повторением, когда очередной выбранный 
элемент запоминается и сразу возвращается во 
множество X, и выборки без возвращения, или бесповторные 
выборки, когда очередной выбранный элемент во множество 
X не возвращается. Размер выборки без возвращения 
не превышает n, с возвращением не ограничен. Всякая 
выборка размера r — элемент множества Xr.

Упорядоченная выборка размера r
n
<
 без возвращения 

называется размещением r элементов n-множества или размещением 
из n по r (при r
n
=
 перестановкой степени n). 

По правилу произведения число размещений из n по r (обозначается 
An
r или n r
( ) ) равно:

 
n
n n
n
r
n
n
r
r
( )
=
−
(
)…
−
+
(
) =
−
(
)

1
1
!

!.  
(1.1.1)

Число различных перестановок элементов n-множества 

равно A
n
n
n =
!.

Упорядоченную выборку с возвращением размера r на-

зывают размещением с повторениями (словом длины r в алфавите 
порядка n). По правилу произведения число размещений 
размера r с повторениями (обозначается An
r ) равно:

 
A
n
n
r
r
=
. 
(1.1.2)

Глава I. Основы дискретной математики в криптографии

Неупорядоченную выборку без возвращения размера r 

называют сочетанием из n по r (сочетанием r элементов 
n-множества), r ≤ n. Число сочетаний из n по r (обозначается 

Cn
r или n

r




 ) равно:

 
C
A
A

n

r
n
r
n
r
n
r

r
r
=
=
−
(
)
!
!
!. 
(1.1.3)

Неупорядоченная выборка с возвращением размера r на-

зывается 
сочетанием 
с 
повторениями 
r 
элементов 

n-множества, кратко — сочетанием с повторениями из n 
по r. Число сочетаний с повторениями из n по r (обозначается 
Cn

r)) совпадает с числом разбиения строки длины n
r
+
 

на n непустых отрезков. Это число равно:
 
C
C
C
n
r
n r
n
n r
r
=
=
+ −
−
+ −
1
1
1 . 
 (1.1.4)

При расчетах полагается: 
A
С
С
n
n
0
0
0
0
0
1
=
=
=
=
!
 и 

A
С
n
r
n
r
=
= 0 при n
r
<
.

Числа Cn
r называют биномиальными коэффициентами 

(б.к.), они используются в формуле бинома Ньютона. Формула 
верна для элементов a и b любого множества X, в котором 
задано сложение и умножение:

 
a
b
C a b
n

r

n

n
r
r
n r
+
(
)
=

=

−
∑

0

. 
 (1.1.5)

При расчетах используют свойства б.к.:
1) свойство симметрии: C
C
n
r
n
n r
=
− , 0 ≤ r ≤ n;

2) рекуррентное соотношение: C
C
C
n
r
n
r
n
r
=
+
−
−
−
1
1
1;

3) сумма б.к.:r

n

n
r
n
C

=∑
=

0

2 ;

4) знакопеременная сумма б.к.: 

r

n
r
n
r
C

=∑ −
(
)
=

0
1
0;

5) cумма четных (нечетных) б.к.:

 

r

n

n
r

r

n

n

r
n
C
C

=






=






+
−
∑
∑
=
=

0

2
2

0

2
2
1
1
2
;

Лекция 1. Комбинаторика, бинарные отношения, графы 

6) свертка Вандермонда и ее следствие, 0 ≤
≤
+
r
n
m:

 

r

n

n
i
m
r i

n m
r
C C
C

=

−
+
∑
=

0

; 

r

n

n
r

n
n
C
C

=∑(
)
=

0

2
2 .

Свойство симметрии и рекуррентное соотношение сле-

дуют из равенства (1.1.3). Сумма биномиальных коэффициентов 
следует из бинома Ньютона (1.1.5) при a
b
=
= 1. Зна-

копеременная сумма следует из (1.1.5) при b
a
= −
= 1. 

Сумма четных (нечетных) биномиальных коэффициентов 
образуется как полусумма (полуразность) 3-го и 4-го соотношений. 
Свертка Вандермонда следует из тождества многочленов 

x
x
x

n
m
n m
+
(
)
+
(
)
=
+
(
)
+
1
1
1
и бинома Ньютона. 

Cледствие свертки Вандермонда получается при n
m
r
=
=
.

П р и м е р 1.1.2. Число двоичных строк длины n, содер-

жащих k единиц, равно Cn
k, k = 0, 1, … , n. Тогда число всех 

двоичных строк длины n (в соответствии со свойством 3 б.к.) 
равно 2n. w

Покрытия и разбиения множеств, принцип включе ния-

исключения. Покрытием множества X называется система 
множеств 
X
Xk
1,
,
…
{
}, если X
X
Xk
=
1 …
, k ≥ 1. 

Разбиением 
множества 
X 
называют 
его 
покрытие 

X
Xk
1,
,
…
{
}, если X
X
i
j
= ∅ для различных i j
k
,
,
,
∈
…
{
}
1
.

Множества X
Xk
1,
,
…
 называются блоками покрытия 

(разбиения), число k блоков — порядком покрытия (разбиения). 
Последовательность записи блоков несущественна 
в силу коммутативности операции объединения. Тривиальным 
блоком разбиения называют одноэлементный блок. 
Для множества X разбиение Y
Ym
1,
,
…
{
} называется продол-

жением разбиения 
X
Xk
1,
,
…
{
}, где m
k
≥
, если для 

i
m
=
…
1,
,
 найдется номер j
k
∈
…
{
}
1,
,
 такой, что Y
X
i
j
⊆
.

Для любого разбиения конечного множества Х верно 

правило суммы:
 
X
X
Xk
=
+ … +
1
.

Для точного подсчета или оценки порядка множества X 

Глава I. Основы дискретной математики в криптографии

через порядки блоков покрытия применяют метод включения-
исключения.

Для покрытия порядка 2 метод дает формулу:

 
X
X
X
X
X
=
+
−
1
2
1
2
. 
(1.1.6)

В правой части формулы (1.1.6) слагаемое −
(
)
X
X
1
2


учитывает, что в сумме X
X
1
2
+
 элементы множества  

X1 3 X2 перечислены дважды.

Для покрытия порядка 3 метод дает формулу:

 

X
X
X
X

X
X
X
X
X
X
X
X
X

=
+
+
−

−
−
−
+

1
2
3

1
2
1
3
2
3
1
2
3
,

в правой части каждый элемент множества X учтен ровно 
один раз, например, если X1 3 X2 3 X3 ≠ ∅, то элементы этого 
множества перечислены 4 раза со знаком «плюс» и трижды 
со знаком «минус».

При любом k > 1 верна формула, включающая 2
1
k −
 

слагаемых:

 
X
X
X
X
k
i

k
i

t
t
k

t
t

i

i
1
1

1

1
1

1

1
…
…

…
=
−
(
)

=

+

≤
<
<
≤
∑
∑
. 
(1.1.7)

Приведем формулу включения-исключения (1.1.7) в бо-

лее общем виде. Пусть имеется n > 1 элементов, и каждый 
из них обладает или не обладает свойствами z1, …, z
k
k,> 1. 

Обозначим через n t
ti
1,
,
…
(
) число элементов, обладающих 

свойствами zt1, …, zti (возможно, и некоторыми другими), 
где t
t
k
i
1
1
,
,
,
,
…
{
} ⊆
…
{
}, 1 ≤ i ≤ k, и через n∅ — число элемен-

тов, не обладающих ни одним из свойств z1, …, zk. Тогда:
 
n
n
s
s
s
s
i
i
k
k
∅ =
−
+
+ … + −
(
)
+ … + −
(
)
1
2
1
1
, (1.1.8)

где s
n t
t
i

t
t
k

i

i
=
…
(
)

≤
<…<
≤
∑
1

1

1

,
,
, i = 1, … , k. w

П р и м е р 1.1.3. В учебной группе каждый из 11 студен-

тов владеет либо английским, либо немецким, либо китайским 
языком. Английским языком владеют 7 студентов, 
немецким языком 6 студентов, китайским языком 4 сту-