Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Некоторые приложения теории кодирования

Покупка
Основная коллекция
Артикул: 870116.01.99
Доступ онлайн
350 ₽
В корзину
В учебном пособии рассматриваются вопросы применения линейных кодов в следующих схемах защиты информации: схема защиты в канале с помехами, схемы симметричного и асимметричного шифрования, схема цифровой подписи, схема защиты в канале с утечкой, схема защиты в канале с дефектами, схема разделения секрета, схема сокрытия информации. Настоящее пособие содержит материал, входящий в учебную программу курса «Криптография», изучаемого студентами по направлению подготовки «Прикладная математика и информатика», специализирующимися в области защиты информации.
Косолапов, Ю. В. Некоторые приложения теории кодирования : учебное пособие / Ю. В. Косолапов ; Южный федеральный университет. – Ростов-на-Дону ; Таганрог : Издательство Южного федерального университета, 2024. - 102 с. – ISBN 978-5-9275-4854-5. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2233076 (дата обращения: 19.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ 
РОССИЙСКОЙ ФЕДЕРАЦИИ 
Федеральное государственное автономное образовательное 
учреждение высшего образования 
«ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 
Ю. В. Косолапов
Некоторые приложения 
теории кодирования
Учебное пособие  
Ростов-на-Дону – Таганрог 
Издательство Южного федерального университета 


 
УДК 003.26:512.64(075.8) 
ББК  16.84+22.1я73 
   К71 
 
Печатается по решению кафедры алгебры и дискретной математики 
Института математики, механики и компьютерных наук им. И. И. Воровича  
Южного федерального университета  
(протокол № 7 от 10 июня 2024 г.) 
 
Рецензенты: 
доктор физико-математических наук, профессор кафедры алгебры  
и дискретной математики Института математики, механики  
и компьютерных наук им. И. И. Воровича  
Южного федерального университета В. А. Скороходов; 
 
кандидат технических наук, доцент, заместитель директора по науке  
ООО «Стэл КС»  А. В. Балакин 
 
 
 
К71 
Косолапов, Ю. В.     
      Некоторые приложения теории кодирования : учебное пособие  /  
Ю. В. Косолапов ; Южный  федеральный  университет. – Ростов-наДону ; Таганрог : Издательство Южного федерального университета, 2024. – 100 с. 
     ISBN 978-5-9275-4854-5   
 
 
 
   В учебном пособии рассматриваются вопросы применения линейных 
кодов в следующих схемах защиты информации: схема защиты в канале с помехами, схемы симметричного и асимметричного шифрования, 
схема цифровой подписи, схема защиты в канале с утечкой, схема защиты в канале с дефектами, схема разделения секрета, схема сокрытия 
информации.  
   Настоящее пособие содержит материал, входящий в учебную программу курса «Криптография», изучаемого студентами по направлению подготовки «Прикладная математика и информатика», специализирующимися в области защиты информации. 
 
УДК 003.26:512.64(075.8)  
ББК 22.18я73 
ISBN 978-5-9275-4854-5  
©  Южный федеральный университет,  2024 
©  Косолапов Ю. В.,  2024 


Оглавление
Глава 1. Линейные блоковые коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.1. Носитель, вес, расстояние . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
1.2. Линейный код и его характеристики
. . . . . . . . . . . . . . . . . . . . . . . . .
10
1.3. Минимальные векторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
1.4. Сумма кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.5. Покрывающий код . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
14
1.6. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
Глава 2. Схема защиты в канале с помехами
. . . . . . . . . . . . . . . . . . . . .
16
2.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16
2.2. Обнаружение ошибок . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
17
2.3. Исправление ошибок. Декодер в ближайшее кодовое слово . . . . . . . . . .
18
2.4. Исправление стираний . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
20
2.5. Декодирование по информационным совокупностям . . . . . . . . . . . . . . .
20
2.6. Исправление ошибок и стираний в случае F2 . . . . . . . . . . . . . . . . . . . .
23
2.7. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
24
2.8. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
25
Глава 3. Схема симметричного шифрования . . . . . . . . . . . . . . . . . . . . . .
26
3.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
26
3.2. Определение схемы симметричного шифрования . . . . . . . . . . . . . . . . .
27
3.3. Наивная симметричная кодовая схема шифрования . . . . . . . . . . . . . . .
29
3.4. Стойкость наивной схемы шифрования . . . . . . . . . . . . . . . . . . . . . . . .
29
3.5. Схема Рао-Нама
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
30
3.6. Стойкость схемы Рао-Нама . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
31
3.7. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
33
3.8. Модификация схемы Рао-Нама . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
34
3.9. LPN-проблема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
35
3.10.Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
37
3.11.Схема шифрования LPN-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.12.Стойкость LPN-C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
38
3.13.RSD-проблема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Оглавление
3.14.Схема SYND . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
42
3.15.Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
44
Глава 4. Схема асимметричного шифрования . . . . . . . . . . . . . . . . . . . . .
45
4.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
45
4.2. Определение схемы асимметричного шифрования. KEM . . . . . . . . . . . .
46
4.3. Схема типа Мак-Элиса . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.4. Схема типа Нидеррайтера . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
49
4.5. KEM на основе схем типа Мак-Элиса и типа Нидеррайтера
. . . . . . . . .
49
4.6. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
51
4.7. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
52
Глава 5. Схема цифровой подписи . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
5.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
53
5.2. Определение схемы подписи для модели без доверия . . . . . . . . . . . . . .
54
5.3. Схема CFS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
55
5.4. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
56
Глава 6. Схема защиты в канале с утечкой . . . . . . . . . . . . . . . . . . . . . . .
57
6.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
57
6.2. Защита от утечки. Кодовое зашумление . . . . . . . . . . . . . . . . . . . . . . .
58
6.3. Стойкость кодового зашумления . . . . . . . . . . . . . . . . . . . . . . . . . . . .
59
6.4. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
60
6.5. Защита от утечки и искажений. Обобщенное кодовое зашумление . . . . .
61
6.6. Стойкость обобщенного кодового зашумления . . . . . . . . . . . . . . . . . . .
63
6.7. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
65
6.8. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
67
Глава 7. Схема защиты в канале с дефектами
. . . . . . . . . . . . . . . . . . . .
68
7.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
68
7.2. Математическая модель канала с дефектами . . . . . . . . . . . . . . . . . . . .
68
7.3. Способ кодирования для канала с дефектами
. . . . . . . . . . . . . . . . . . .
70
7.4. Устойчивость к дефектам . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
71
7.5. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
72
7.6. Способ кодирования для канала с дефектами и ошибками
. . . . . . . . . .
72
7.7. Устойчивость к дефектам и ошибкам . . . . . . . . . . . . . . . . . . . . . . . . .
73
7.8. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
74
7.9. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
75
Глава 8. Схема разделения секрета
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
76
8.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Оглавление
8.2. Схемы разделения секрета
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
78
8.3. Линейная СРС
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
79
8.4. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
8.5. Связь ЛСРС и линейных кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
8.6. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
85
8.7. Выявление активных нарушителей в одномерных ЛСРС . . . . . . . . . . . .
86
8.8. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
87
Глава 9. Схема сокрытия информации . . . . . . . . . . . . . . . . . . . . . . . . . .
88
9.1. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
9.2. Наивное сокрытие . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
9.3. Матричное сокрытие
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
9.4. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
91
9.5. Метод «мокрая бумага» . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
92
9.6. Конструкция ZZW . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
9.7. Пример . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
9.8. Вопросы для самоконтроля . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Основные обозначения
∅
пустое множество
N
множество натуральных чисел
Zm
кольцо вычетов по модулю m ∈N
|A|
мощность множества A
2A
множество всех подмножеств множества A
a ←A
равновероятный выбор элемента a из множества A
[n]
множество натуральных чисел в диапазоне от 1 до n
A = [n] \ A
дополнение множества A
Fq
поле Галуа мощности q, где q — степень простого числа
Kn
линейное пространство над полем K
0n
нулевой вектор из Kn, 0n = (0, . . . , 0)
1n
вектор, состоящий из единиц, 1n = (1, . . . , 1)
dim(V )
размерность пространства V
x
вектор x = (x1, ..., xn) ∈Fn
q
supp(x)
носитель x = (x1, ..., xn), supp(x) = {i ∈[n]: xi ̸= 0}
wt(x)
вес Хэмминга вектора x, wt(x) = |supp(x)|
ρ(x, y)
расстояние Хэмминга между x и y, ρ(x, y) = wt(x −y)
AT
транспонированная матрица A
A|τ
матрица, составленная из столбцов матрицы A с номерами из τ
A|τ
матрица, составленная из строк матрицы A с номерами из τ
L(A)
линейная оболочка, натянутая на строки матрицы A
rank(A)
ранг матрицы A
Ik
единичная (k × k)-матрица
V + W
сумма подпространств V (⊆Fn
q ) и W(⊆Fn
q )
[n, k, d]q
линейный код размерности k, длины n с минимальным расстоянием d над полем Fq
Sn
симметрическая группа подстановок, действующая на [n]
PAut(C)
группа
перестановочных
автоморфизмов
[n, k, d]q-кода
C,
PAut(C) ⊆Sn
(a, b)
конкатенация векторов a и b
⟨a, b⟩
скалярное произведение векторов a и b


Оглавление
a ⋆b
покомпонентное произведение a = (a1, ..., an) и b = (b1, ..., bn)
(A|B)
приписывание матрицы B справа к матрице A
O
нулевая матрица, размер определяется из контекста
n
k

число сочетаний из n по k
pX(x)
вероятность появления значения x случайной величины X; если
из контекста ясно, о какой случайной величине идет речь, то
вместо pX(x) будем писать p(x)
⌈a⌉
для a ∈R обозначает ближайшее целое сверху
⌊a⌋
для a ∈R обозначает ближайшее целое снизу


Введение
Традиционно методы помехоустойчивого кодирования применяются в
области, где необходима защита целостности информации от искажений,
носящих случайный характер. Так, например, коды используются для защиты информации от искажений, возникающих в линиях связи и системах
хранения. Но в настоящее время применение теории помехоустойчивого кодирования уже не ограничивается рамками только этой области. Все больше коды находят применение при решении задач, в которых деструктивные
воздействия носят не случайный характер, а являются преднамеренными.
Такие воздействия могут быть направлены на нарушение не только свойства целостности, но и конфиденциальности, а также скрытности информации. Имеющиеся результаты в области линейных кодов позволяют адаптировать методы кодирования для борьбы с такими воздействиями. Например, вычислительная трудность некоторых задач, возникающих в теории
линейных кодов, является для ряда схем шифрования и цифровой подписи
основой стойкости к атакам, использующим квантовые вычисления. Кроме того, характеристики схем защиты (такие, как стойкость, скрытность и
т.п.) часто могут быть описаны, используя уже разработанный понятийный
аппарат теории линейных кодов.
В настоящем пособии сначала приводятся необходимые сведения из теории линейных кодов, а затем рассматриваются некоторые схемы защиты,
построенные на таких кодах: 1) схема защиты в канале с помехами, 2) схема симметричного шифрования, 3) схема асимметричного шифрования, 4)
схема цифровой подписи, 5) схема защиты в канале с утечкой, 6) схема защиты в канале с дефектами, 7) схема разделения секрета, 8) схема сокрытия
информации.


Глава 1
Линейные блоковые коды
В основе схем защиты данных, рассматриваемых в этом пособии, лежат
линейные блоковые коды. Поэтому в первой главе приводится определение
таких кодов, а также свойства этих кодов, используемые при описании характеристик схем защиты. Термины, обозначения, а также формулировки,
по большей части, приводятся в соответствии с [1].
1.1.
Носитель, вес, расстояние
Пусть K — поле, V = Kn — пространство размерности n ∈N над этим
полем. Носителем вектора x = (x1, ..., xn) ∈V называется множество ненулевых координат этого вектора, которое далее обозначается supp(x):
supp(x) = {i : xi ̸= 0}.
Носителем вектора a · 1n = (a, . . . , a) для a ∈K \ {0} будет множество
[n] = {1, . . . , n}, а носителем вектора 0 · 1n = 0n — пустое множество.
Весом вектора x ∈Fn
q называется мощность носителя этого вектора:
wt(x) = |supp(x)|.
В частности, wt(1n) = n, wt(0n) = 0. Умножение вектора x ∈V на ненулевой скаляр a ∈K не меняет веса вектора, так как K — поле.
Расстоянием Хэмминга между последовательностями x = (x1, ..., xn)
и y = (y1, ..., yn) называется число координат ρ(x, y), где эти последовательности отличаются:
ρ(x, y) = |{i : xi ̸= yi}|.


Глава 1. Линейные блоковые коды
Если x, y ∈V , то
ρ(x, y) = |supp(x −y)| = wt(x −y).
(1.1)
В частности, ρ(a1n, b1n) = n для a ̸= b. Расстояние Хэмминга является
метрикой на V , так как
(i) ρ(x, y) ⩾0, причем равенство выполняется тогда и только тогда,
когда x = y;
(ii) ρ(x, y) = ρ(y, x);
(iii) выполняется неравенство треугольника: ρ(x, y) ⩽ρ(x, z) + ρ(z, y).
1.2.
Линейный код и его характеристики
В теории помехоустойчивых кодов линейные коды рассматриваются как
подпространства пространств над конечным полем K = Fq мощности q =
pr, где p — простое число, r ∈N.
Определение 1. Линейным блоковым [n, k, d]q-кодом C называется
подпространство размерности k линейного пространства Fn
q, такое, что
min
c,c′∈C,c̸=c′{ρ(c, c′)} = d.
Так как C — подпространство, то из (1.1) получаем, что линейный
[n, k, d]q-код C — это подпространство размерности k линейного пространства Fn
q, такое, что
min
c∈C\{0n}{wt(c)} = d.
Характеристика d называется кодовым расстоянием кода C, а k и n
— соответственно размерностью и длиной. В случае, когда кодовое расстояние d неизвестно или не используется в контексте, то код C называется
[n, k]q-кодом. Элементы кода будем называть кодовыми векторами или кодовыми словами. Матрица, строками которой являются все кодовые слова
кода C, называется кодовой матрицей. Если в кодовой матрице имеются f
нулевых столбцов с номерами {i1, ..., if} ⊆[n], то координаты с номерами
из {i1, ..., if} называются фиктивными. [n, k, d]q-код с f фиктивными координатами можно преобразовать в изоморфный ему [n −f, k, d]-код, удалив


Доступ онлайн
350 ₽
В корзину