Некоторые приложения теории кодирования
Покупка
Основная коллекция
Тематика:
Кибернетика
Издательство:
Южный федеральный университет
Автор:
Косолапов Юрий Владимирович
Год издания: 2024
Кол-во страниц: 102
Дополнительно
Вид издания:
Учебное пособие
Уровень образования:
ВО - Бакалавриат
ISBN: 978-5-9275-4854-5
Артикул: 870116.01.99
В учебном пособии рассматриваются вопросы применения линейных кодов в следующих схемах защиты информации: схема защиты в канале с помехами, схемы симметричного и асимметричного шифрования, схема цифровой подписи, схема защиты в канале с утечкой, схема защиты в канале с дефектами, схема разделения секрета, схема сокрытия информации. Настоящее пособие содержит материал, входящий в учебную программу курса «Криптография», изучаемого студентами по направлению подготовки «Прикладная математика и информатика», специализирующимися в области защиты информации.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 01.03.02: Прикладная математика и информатика
- ВО - Магистратура
- 01.04.02: Прикладная математика и информатика
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» Ю. В. Косолапов Некоторые приложения теории кодирования Учебное пособие Ростов-на-Дону – Таганрог Издательство Южного федерального университета
УДК 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]-код, удалив