Алгебраическая теория кодирования и криптография в Sage
Покупка
Новинка
Основная коллекция
Тематика:
Криптография
Издательство:
Казанский (Приволжский) федеральный университет
Автор:
Насрутдинов Марат Фаритович
Год издания: 2024
Кол-во страниц: 78
Дополнительно
В пособии рассматриваются приложения абстрактной алгебры в теории кодирования и криптографии. Основной целью пособия является демонстрация возможностей использовании системы компьютерной алгебры (СКА) Sage
в решении задач курса. Кроме того при помощи СКА можно быстро проверять свои гипотезы на небольших объектах прежде чем пытаться доказать их в общем виде.
Тематика:
ББК:
УДК:
ОКСО:
- ВО - Бакалавриат
- 09.03.02: Информационные системы и технологии
- ВО - Магистратура
- 09.04.02: Информационные системы и технологии
ГРНТИ:
Скопировать запись
Фрагмент текстового слоя документа размещен для индексирующих роботов
КАЗАНСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ ИНСТИТУТ МАТЕМАТИКИ И МЕХАНИКИ ИМ. Н.И. ЛОБАЧЕВСКОГО Кафедра компьютерной математики и информатики М.Ф. НАСРУТДИНОВ АЛГЕБРАИЧЕСКАЯ ТЕОРИЯ КОДИРОВАНИЯ И КРИПТОГРАФИЯ В SAGE Учебное пособие Казань 2024
УДК 512 Рецензент: доцент кафедры цифровой аналитики и технологий искусственного интеллекта Института информационных технологий и интеллектуальных систем КФУ, кандидат физико-математических наук Е.К. Липачев Насрутдинов М.Ф. Алгебраическая теория кодирования и криптография в Sage: Учебное пособие/ М.Ф. Насрутдинов. – Казань: Казанский федеральный университет, 2024. – 78 c. В пособии рассматриваются приложения абстрактной алгебры в теории кодирования и криптографии. Основной целью пособия является демонстрация возможностей использовании системы компьютерной алгебры (СКА) Sage в решении задач курса. Кроме того при помощи СКА можно быстро проверять свои гипотезы на небольших объектах прежде чем пытаться доказать их в общем виде. © Насрутдинов М.Ф. 2024 © Казанский университет, 2024
Оглавление Глава 1. Введение в теорию кодирования . . . . . . . . . . . . . . . . . . . . . . . . §1. Блоковые коды. Расстояние Хэмминга . . . . . . . . . . . . . . 7 §2. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 Глава 2. Линейные коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 §1. Порождающая и проверочная матрица . . . . . . . . . . . . . . 11 §2. Кодовое расстояние линейного кода . . . . . . . . . . . . . . . . 12 §3. Декодирование линейного кода . . . . . . . . . . . . . . . . . . 13 §4. Построение линейных кодов в Sage . . . . . . . . . . . . . . . . 14 §5. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 Глава 3. Границы объемов кодов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 §1. Граница сферической упаковки . . . . . . . . . . . . . . . . . . 23 §2. Граница Синглтона . . . . . . . . . . . . . . . . . . . . . . . . . 24 §3. Граница Варшамова-Гилберта . . . . . . . . . . . . . . . . . . . 25 Глава 4. БХЧ-коды и коды Рида-Соломона . . . . . . . . . . . . . . . . . . . . . . 27 §1. Коды Боуза-Хоквингема-Чоудхури . . . . . . . . . . . . . . . . 27 §2. Код Рида-Соломона . . . . . . . . . . . . . . . . . . . . . . . . . 28 §3. Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 §4. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Глава 5. Циклические коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 §1. Идеалы и циклические коды . . . . . . . . . . . . . . . . . . . . 35 §2. Примеры циклических кодов . . . . . . . . . . . . . . . . . . . 39 §3. Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 §4. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 Глава 6. Групповые коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 §1. Определение групповых кодов . . . . . . . . . . . . . . . . . . . 44 §2. Лабораторная работа . . . . . . . . . . . . . . . . . . . . . . . . 46 Глава 7. Алгебраическая криптография . . . . . . . . . . . . . . . . . . . . . . . . . . 52 §1. Криптосистемы симметричного шифрования . . . . . . . . . . 53 §2. Исторические шифры . . . . . . . . . . . . . . . . . . . . . . . . 53 2.1. Шифр Цезаря . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2. Шифры перестановки . . . . . . . . . . . . . . . . . . . . . 56
Оглавление 2.3. Шифр Виженера . . . . . . . . . . . . . . . . . . . . . . . . §3. Современные криптосистемы симметричного шифрования . . . 57 §4. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 Глава 8. Асимметричное шифрование . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 §1. Криптосистема RSA . . . . . . . . . . . . . . . . . . . . . . . . 61 §2. Алгоритмы цифровой подписи RSA . . . . . . . . . . . . . . . . 63 §3. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 §4. Алгоритм Диффи-Хеллмана распределения ключей . . . . . . 64 §5. Криптосистема Эль-Гамаля . . . . . . . . . . . . . . . . . . . . 65 5.1. Реализация на группе Z* 𝑝 . . . . . . . . . . . . . . . . . . . 66 5.2. Реализация схемы Эль-Гамаля на эллиптических кривых в Sage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 Глава 9. Приложения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 §1. Конечные поля . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 §2. Строение конечных полей . . . . . . . . . . . . . . . . . . . . . 72 §3. Конечные поля в Sage . . . . . . . . . . . . . . . . . . . . . . . 74 §4. Упражнения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 §5. Варианты тем дипломных работ . . . . . . . . . . . . . . . . . . 76
Предисловие В пособии рассматриваются приложения абстрактной алгебры в теории кодирования и криптографии. Основной целью пособия является демонстрация возможностей использовании системы компьютерной алгебры (СКА) Sage в решении задач курса. Не пытаясь заменить обстоятельные учебники, мы хотели продемонстрировать возможности Sage при работе с алгебраическими объектами. Применение СКА позволяет студентам ’не утонуть’ в больших и зачастую рутинных выкладках и сконцентрироваться на основных идеях. Кроме того при помощи СКА можно быстро проверять свои гипотезы на небольших объектах прежде чем пытаться доказать их в общем виде.
Глава 1
Введение в теорию кодирования
Рассматривается задача обнаружения и исправления ошибок при передачи сообщений по каналам связи.
Рис. 1. Система связи по каналу с шумом.
Мы рассматриваем передачу сообщений блоками размера 𝑛над некоторым алфавитом 𝑋.
Общая схема работы подразумевается следующей:
Источник формирует сообщение 𝑢= (𝑢1, 𝑢2, . . . , 𝑢𝑘) длины 𝑘.
Кодер добавляет проверочные символы к сообщению (само сообщение
тоже может изменятся).
Сообщение передается по каналу связи, в котором возможны помехи.
Декодер проверяет наличие ошибок, при возможности исправляет их и
предает декодированное сообщение получателю.
Пример 0.1. Код с повторениями. Пользователь хочет передать сообщение 1 или 0 (информационное сообщение, 𝑘= 1). Для уменьшения ошибки
символ дублируется 5 раз. По каналу связи будет передано либо 00000, либо
11111.
Если будет получено, например, сообщение 01000, то значит в момент передачи произошла ошибка (обнаружение ошибки).
Если вероятность ошибки в каждом символе меньше 0.5, то вероятнее всего
было передано сообщение 00000 (исправление ошибки).
Пример 0.2. Код проверки на четность. Пользователь передает сообщение (𝑢1, 𝑢2, . . . , 𝑢𝑘), состоящее из 0 и 1. Кодер добавляет один дополнительный
символ 𝑢𝑘+1 ∈{0, 1}, так чтобы сумма 𝑢1+𝑢2 . . .+𝑢𝑘+𝑢𝑘+1 была четная. Если
§1. Блоковые коды. Расстояние Хэмминга в канале произойдет одна ошибка (или любое нечетное количество ошибок), то сумма станет нечетной и мы зафиксируем наличие ошибки. В этом случае восстановить сообщение мы не сможем. Такие коды используют в системах, где вероятность ошибки очень маленькая, например, в вычислительных машинах для контроля передач информации между регистрами и для контроля считываемой информации в оперативной памяти. Пример 0.3. ISBN-код. Международный стандартный книжный номер (англ. International Standard Book Number, сокращённо – англ. ISBN) – уникальный номер книжного издания, необходимый для распространения книги в торговых сетях и автоматизации работы с изданием. Пример ISBN-кода: ISBN 3-88053-002-5. Изначально ISBN имел длину из 10 символов (сейчас 13), символы состоят из цифр от "0"до "9"и буквой "X". Между информационными символами стоят дефисы, которые нужны для удобства восприятия длинного числа, буква "X"служит для обозначения числа 10 и может стоять только на последней позиции. Код состоит из четырех частей (между которыми располагается дефис): идентификаторы группы, издателя, книги для издателя, и контрольная цифра. Идентификатор группы используется для обозначения страны, географического региона, языка и прочее.Четвертая, заключительная часть (контрольная цифра), используется в коде алгоритме другими цифрами для получения поддающегося проверке ISBN. Количество цифр, содержащееся в первых трех частях, может быть различным, но контрольная цифра всегда содержит один символ (расположенный между "0"и "9"включительно, или "X"для величины 10), а само ISBN в целом имеет длину тринадцать символов (десять чисел плюс три дефиса, разделяющих три части ISBN). Последний символ – проверочный. Если 𝑥1, 𝑥2, . . . , 𝑥9 – информационные символы, то проверочный символ 𝑥10 выбирается из условия 10 ∑︁ 𝑖=1 𝑖· 𝑥𝑖= 0 mod 11. §1. Блоковые коды. Расстояние Хэмминга В нашем курсе мы рассматриваем только блоковые коды. Это означает, что сообщения передаются блоками длины 𝑛над некоторым алфавитом 𝐹, состоящим из 𝑞элементов.
Глава 1. Введение в теорию кодирования
В качестве алфавита берут обычно какой-либо алгебраический объект, в
приложениях это чаще всего конечное поле. Есть исследования, в которых
алфавит это конечные кольца, группы и полугруппы, лупы.
Определение 1.1. Кодом длины 𝑛называется любое непустое подмножество 𝐶∈𝐹𝑛. Если количество элементов |𝐶| = 𝑀, то говорят, что 𝐶является
(𝑛, 𝑀)-кодом.
Элементы кода называются кодовыми словами.
Величина 𝑘= log𝑞𝑀называется размерностью (или информационной
длиной) кода 𝐶. Информационная длина показывает долю полезных (информационных) символов, которые передаются по каналу связи.
Фактически декодер проверяет принадлежит ли принятое слово множеству 𝐶или нет. Если слово не принадлежит 𝐶, то значит произошла ошибка.
Далее будем решать следующие задачи:
1. Как задать 𝐶, чтобы проверка принадлежности была простой.
2. Если произошла ошибка, то можно ли восстановить исходное сообщение.
3. Как увеличить долю информационных символов, сохраняя корректирующие возможности кода.
Определение 1.2. Расстояние Хэмминга на множестве 𝐹𝑛определяется
следующим образом:
𝑑(𝑥, 𝑦) = |{𝑖|𝑥𝑖̸ = 𝑦𝑖}|,
где 𝑥= (𝑥1, . . . , 𝑥𝑛), 𝑦= (𝑦1, . . . , 𝑦𝑛), 𝑥, 𝑦∈𝑋𝑛.
Теорема 1.3. Расстояние Хэмминга задает на 𝐹𝑛структуру метрического пространства.
Определение 1.4. Минимальное расстояние (кодовое расстояние) кода
определяется следующим образом:
𝑑(𝐶) = min 𝑑(𝑥, 𝑦),
где минимум берется по всем парам элементов 𝑥, 𝑦∈𝐶, 𝑥̸ = 𝑦.
Теорема 1.5. Если кодовое расстояние 𝑑(𝐶) = 2𝑡+ 1, то код может исправлять 𝑡и обнаруживать 2𝑡ошибок.
Если кодовое расстояние 𝑑(𝐶) = 2𝑡, то код может исправлять 𝑡−1 и
обнаруживать 2𝑡−1 ошибку.