Некоторые приложения теории кодирования (150,00 руб.)

Стр.2

Стр.3

Стр.4

Стр.5

Стр.6

МИНИСТЕРСТВО НАУКИ И ВЫСШЕГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ Федеральное государственное автономное образовательное учреждение высшего образования «ЮЖНЫЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» Ю. В. Косолапов Некоторые приложения теории кодирования Учебное пособие Ростов-на-Дону – Таганрог Издательство Южного федерального университета 2024

Стр.2

УДК 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

Стр.3

Оглавление Глава 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-проблема . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 3

Стр.4

Оглавление 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. Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4

Стр.5

Оглавление 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 Литература . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5

Стр.6