URSS.ru Магазин научной книги
Обложка Таранников Ю.В. Самокорректирующиеся коды и их применения в криптографии Обложка Таранников Ю.В. Самокорректирующиеся коды и их применения в криптографии
Id: 293272
769 р.

Самокорректирующиеся коды и их применения в криптографии № 24

2023. 256 с.
Типографская бумага

Аннотация

Книга написана на основе специальных курсов лекций «Теория кодирования и ее применения в криптографии» и «Теория кодирования и ее приложения к криптографии (дополнительные главы)», читавшихся автором более десяти лет на механико-математическом факультете МГУ, начиная с 2008 года.

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


Оглавление
top
Предисловие9
Глава 1. Основы теории самокорректирующихся кодов11
1.1. Передача информации по каналу связи. Помехи, ошибки11
1.2. Расстояние Хэмминга12
1.3. Кодовое расстояние13
1.4. Обнаружение и корректирование ошибок13
1.5. Линейный код15
1.6. Порождающая матрица15
1.7. Кодирование и декодирование с помощью порождающей матрицы16
1.8. Двойственный код17
1.9. Проверочная матрица18
1.10. Синдром19
1.11. Кодовое расстояние линейного кода19
1.12. Связь кодового расстояния со свойствами столбцов проверочной матрицы20
1.13. Вектор ошибок. Исправление небольшого числа ошибок20
1.14. Линейные коды с кодовым расстоянием 1 и 221
1.15. Линейные коды с кодовым расстоянием 324
1.16. Двоичный код Хэмминга. Кодирование, исправление ошибок и декодирование с помощью двоичного кода Хэмминга25
Глава 2. Верхние оценки мощности кодов28
2.1. Проблема верхних оценок мощности кодов28
2.2. Рекуррентные оценки30
2.3. Оценка Хэмминга (граница сферической упаковки)32
2.4. Достижимость оценки Хэмминга на коде Хэмминга34
2.5. Совершенные коды34
2.6. Оценка Синглтона35
2.7. Оценка Джонсона36
2.8. Следствие из оценки Джонсона39
2.9. Связь между максимальными мощностями кода на всем множестве наборов и на его подмножестве40
2.10. Оценка Элайеса–Бассалыго41
2.11. Оценка Плоткина41
2.12. Следствия из оценки Плоткина42
2.13. Достижимость оценки Плоткина на коде, двойственном к коду Хэмминга43
Глава 3. Матрицы Адамара45
3.1. Делимость порядка матрицы Адамара на 446
3.2. Связь матриц Адамара и кодов с большими кодовыми расстояниями. Достижимость оценки Плоткина на кодах, построенных с помощью матрицы Адамара46
3.3. Эквивалентность матриц Адамара и кодов, на которых достигается равенство в следствии из оценки Плоткина48
3.4. Теорема Левенштейна49
3.5. Кронекерово произведение матриц51
3.6. Кронекерово произведение матриц Адамара есть матрица Адамара52
3.7. Матрица Адамара–Сильвестра52
3.8. Квадратичные вычеты53
3.9. Символы Лежандра54
3.10. Построение матриц Адамара с помощью символов Лежандра55
3.11. Построение матриц Адамара всех порядков до 100, делящихся на 4, кроме 9257
3.12. Построение матриц Адамара методом Вильямсона59
Глава 4. Оценки разных параметров кодов62
4.1. Оценка Грайсмера62
4.2. Достижимость оценки Грайсмера на коде, двойственном к двоичному коду Хэмминга65
4.3. Коды Макдональда. Достижимость оценки Грайсмера на кодах Макдональда66
4.4. Максимальная размерность линейного кода. Рекуррентные оценки67
4.5. Точное значение максимальной размерности линейного двоичного кода в случае больших кодовых расстояний68
4.6. Оценка Варшамова–Гильберта70
4.7. Оценка Гильберта (сферическая нижняя оценка)71
4.8. Оценка Варшамова71
4.9. Двоичная энтропия73
4.10. Выражение биномиальных коэффициентов через энтропию74
4.11. Скорость кода75
4.12. Асимптотические оценки скорости кода через оценки Хэмминга, Элайеса–Бассалыго, Варшамова–Гильберта, их сравнение между собой76
Глава 5. Коды Голея80
5.1. Несуществование совершенных двоичных кодов с параметрами d = 7, n > 7, n 6= 2380
5.2. Расширенный двоичный код Голея, его кодовое расстояние81
5.3. Двоичный код Голея как совершенный код84
5.4. Расширенный троичный код Голея, его кодовое расстояние84
5.5. Троичный код Голея как совершенный код87
Глава 6. Распределение весов кода88
6.1. Число наборов веса 7 и 8 в двоичном коде Голея88
6.2. Распределение весов кода90
6.3. Теорема Шапиро–Злотника90
6.4. Тождества Мак-Вильямс91
Глава 7. Код Рида–Маллера96
7.1. Булевы функции96
7.2. Полином Жегалкина97
7.3. Код Рида–Маллера, его кодовое расстояние99
7.4. Дуальный код к коду Рида–Маллера100
7.5. Связь кода Рида–Маллера первого порядка с матрицей Адамара–Сильвестра100
7.6. Мажоритарное декодирование кодов Рида–Маллера101
7.7. Радиус покрытия кода103
7.8. Радиус покрытия кода Рида–Маллера первого порядка. Его значение для криптографии105
7.9. Быстрое умножение строки на матрицу Адамара–Сильвестра112
Глава 8. Коды Рида–Соломона114
8.1. Матрица Вандермонда, ее невырожденность114
8.2. Коды Рида–Соломона трех типов, их параметры. Достижимость оценки Синглтона на кодах Рида–Соломона115
8.3. Коды, двойственные к кодам Рида–Соломона второго и третьего типа118
8.4. Циклические коды120
8.5. Представление наборов линейных циклических кодов в виде многочленов120
8.6. Линейный циклический код как идеал в кольце классов вычетов многочленов121
8.7. Порождающий многочлен121
8.8. Проверочный многочлен123
8.9. Многочлен ошибок. Синдромный многочлен. Кодирование, исправление ошибок и декодирование линейных циклических кодов на языке многочленов124
8.10. Код Рида–Соломона первого типа как циклический код127
8.11. Порождающий многочлен кода Рида–Соломона первого типа128
Глава 9. Коды БЧХ129
9.1. Подполе и расширение поля. Коды Боуза–Чоудхури–Хоквингема (БЧХ), их проверочная матрица, оценки кодового расстояния и размерности129
9.2. Коды Хэмминга и Рида–Соломона первого типа как частные случаи кода БЧХ135
9.3. Взаимосвязь множества наборов кода БЧХ над F q с множеством наборов соответствующего кода Рида–Соломона над F q m136
9.4. Код БЧХ как циклический код138
9.5. Примеры кодов БЧХ138
9.6. Минимальные многочлены и сопряженные корни, порождающий многочлен кода БЧХ141
9.7. Алгоритм декодирования Питерсона–Горенстейна–Цирлера для кодов БЧХ, его трудоемкость144
Глава 10. Алгоритм Берлекэмпа–Месси149
10.1. Проблема быстрого решения системы линейных уравнений специального вида при исправлении ошибок в коде БЧХ149
10.2. Сведение к задаче нахождения регистра сдвига с линейной обратной связью минимальной длины, генерирующего данную последовательность150
10.3. Леммы о длине минимального регистра сдвига152
10.4. Алгоритм Берлекэмпа–Месси, его трудоемкость158
10.5. Синдромный многочлен и многочлен значений ошибок для кода БЧХ160
10.6. Алгоритм Форни нахождения значений ошибок161
Глава 11. Открытые системы шифрования на основе кодов, корректирующих ошибки165
11.1. Система открытого шифрования Мак-Элиса166
11.2. Система открытого шифрования Нидеррайтера168
11.3. Сравнение систем открытого шифрования Мак-Элиса и Нидеррайтера170
Глава 12. Ортогональные массивы172
12.1. Ортогональные массивы. Их параметры172
12.2. Корреляционно-иммунные функции173
12.3. Связь силы ортогонального массива, построенного по линейному коду, с кодовым расстоянием дуального кода174
12.4. Существование ортогональных массивов из выполнения условия границы Варшамова–Гильберта176
12.5. Ортогональный массив, построенный с помощью кода Рида–Соломона176
12.6. Конструкция Буша177
12.7. Рекуррентные соотношения для максимального числа столбцов в ортогональных массивах178
12.8. Неравенства Буша179
12.9. Неравенство Рао183
12.10. Неравенство Бирбрауэра–Фридмана185
12.11. Теорема Халявина190
12.12. Коды аутентификации. Их построение с помощью ортогональных массивов194
Глава 13. Дизъюнктные коды197
13.1. Построение системы разделения ключей с помощью дизъюнктных кодов199
13.2. Разделяющие коды200
13.3. Каскадная конструкция дизъюнктных кодов201
Глава 14. Задачи204
14.1. Основы теории самокорректирующихся кодов204
14.2. Верхние оценки мощности кодов209
14.3. Матрицы Адамара212
14.4. Оценки разных параметров кодов212
14.5. Коды Голея215
14.6. Распределение весов кода216
14.7. Код Рида–Маллера218
14.8. Коды Рида–Соломона221
14.9. Коды БЧХ224
14.10. Алгоритм Берлекэмпа–Месси229
14.11. Открытые системы шифрования на основе кодов, корректирующих ошибки238
14.12. Ортогональные массивы243
14.13. Дизъюнктные коды245
Литература248

Предисловие
top
Книга написана на основе специальных курсов лекций «Теория кодирования и ее применения в криптографии» и «Теория кодирования и ее приложения к криптографии (дополнительные главы)», читавшихся автором более десяти лет на механико-математическом факультете МГУ, начиная с 2008 года. Ранее курсы под теми же названиями долгие годы читал профессор Владимир Михайлович Сидельников, сделавший в этих областях много крупных открытий, а незадолго до смерти осенью 2008 года Владимир Михайлович на время своей болезни попросил автора продолжить чтение курса.

Книга дает необходимые общие сведения из теории самокорректирующихся кодов, уделяя при этом особое внимание приложениям в криптографии и смежных областях. Большая глава посвящена матрицам Адамара, являющимся важным теоретическим аппаратом исследований как в теории кодирования, так и в многочисленных приложениях. Подробно обсуждаются коды Рида–Маллера, строящиеся с помощью булевых функций и имеющие связь с нелинейностью булевых функций, — важным свойством, требующимся от булевых функций при их использовании в качестве узла криптосистем. Дается необходимый аппарат работы с коэффициентами Уолша или, как их еще называют, спектральными коэффициентами.

Алгоритм Берлекэмпа–Месси является алгоритмом двойного назначения, он одновременно и эффективно решает задачу декодирования кодов БЧХ, и не менее эффективно позволяет восстановить регистр сдвига с линейной обратной связью наименьшей длины, генерирующий имеющийся в распоряжении кусок последовательности. Такие регистры используются при генерировании псевдослучайных последовательностей и являются важной составной частью многих криптосистем. Надо сказать, что в литературе алгоритм Берлекэмпа–Мэсси изложен в разных местах и по-разному, причем часто это изложение достаточно тяжело для восприятия. Автор взял за основу изложение алгоритма Берлекэмпа–Мэсси в книге Блэйхута [3], однако, к сожалению, в нем присутствовало большое число опечаток и логических ошибок, которые, как автор надеется, удалось методически грамотно откорректировать.

Обсуждаются основанные на самокорректирующихся кодах криптосистемы с открытым ключом, в том числе криптосистемы МакЭлиса и Нидеррайтера. Стойкость таких криптосистем основана на сложности решения задач декодирования кодов общего вида, поэтому знания и дальнейших теоретические исследования задач эффективного декодирования могут как влиять на стойкость криптосистем, так и давать дополнительный толчок к их совершенствованию. Большая глава посвящена ортогональным массивам, — объекту, который имеет множественное применение в математике и ее приложениях. Изначально ортогональные массивы возникли в статистике в задачах планирования экспериментов, быстро установили связи с теорией комбинаторных дизайнов, аппарат исследования ортогональных массивов оказался тесно увязан с теорией распределений весов кода и дуального кодового расстояния. Двоичные ортогональные массивы без повторяющихся строк оказались эквивалентны корреляционно-иммунным булевым функциям, противодействующим корреляционным и другим видам криптографических атак, а также использующимся в кодах аутентификации. Последняя глава теоретической части рассказывает о дизъюнктных кодах, применяемых в системах разделения доступа.

Завершает книгу большой набор задач, как правило, прошедших апробацию в ходе образовательного процесса. Студенты внесли огромный вклад как в совершенствование и корректирование задач, так и своими замечаниями по теоретическому материалу, за что автор им безмерно благодарен.

Автор благодарен за полезные обсуждения в различных областях теории кодирования и ее приложений коллегам с кафедры дискретной математики механико-математического факультета и других кафедр МГУ им. М. В. Ломоносова, из института математики им. С. Л. Соболева, института прикладной математики им. М. В. Келдыша, института проблем передачи информации им. А. А. Харкевича, МФТИ, МГТУ им. Н. Э. Баумана и других научных и образовательных учреждений.

Безусловно, огромное влияние на автора оказало общение с покойными Владимиром Михайловичем Сидельниковым и Владимиром Иосифовичем Левенштейном, особенно ярким является воспоминание о том, как мы втроем возвращались в 2003 году на электричке с конференции в Ратмино под Дубной.


Об авторе
top
photoТаранников Юрий Валерьевич
Кандидат физико-математических наук, доцент кафедры дискретной математики механико-математического факультета Московского государственного университета имени М. В. Ломоносова. Специалист в области дискретной математики и математической кибернетики. Область научных интересов включает комбинаторную теорию дискретных структур, приложения булевых функций в криптологии, теорию кодирования.

Автор 70 научных работ, в том числе монографии «Комбинаторные свойства дискретных структур и приложения к криптологии» и задачника по дискретной математике. Читает курсы лекций по дискретной математике, комбинаторике, кодированию и криптологии, руководит работой учебных и научных семинаров. Под научным руководством Ю. В. Таранникова защищено 4 кандидатских диссертации и 38 дипломных работ.