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

---

Предисловие				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 и 2				21
1.15. Линейные коды с кодовым расстоянием 3				24
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. Делимость порядка матрицы Адамара на 4				46
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, кроме 92				57
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= 23				80
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 m				136
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

---

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

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

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

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

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

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

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

---