Актуальность темы
При разработке и создании распределенных автоматизированных систем обработки информации и управления (АСОИУ) центральной проблемой на протяжении многих лет является защита информации от случайных ошибок и преднамеренных угроз. Обычно эту проблему разделяют на две: проблему повышения достоверности информации при ее передаче и хранении и проблему информационной безопасности.
Для решения первой используется аппарат теории информации и теории помехоустойчивого кодирования.
Для решения второй проблемы до сих пор не существует единого математического аппарата. Частично проблема информационной безопасности АСОИУ решается криптографическими преобразованиями, частично системами управления доступом, в основе математических моделей которых лежит теория множеств. В основе построения современных криптографических систем лежит теория сложности алгоритмов. Одной из самых перспективных задач этой теории для целей криптографии в настоящее время считается задача декодирования неизвестного (случайного) линейного блокового кода. В настоящее время известно несколько криптографических систем, построенных на базе помехоустойчивых кодов. Лучшими из этих конструкций являются криптосистемы, использующие коды Гоппы.
Коды Гоппы были описаны В. Д. Гоппой в 1970 году [30] и названы им (?, О) кодами. В дальнейшем эти коды получили также название классических кодов Гоппы. Ф.Дж.Мак-Вильямс и Н.Дж.А. Слоэн [41] называют их самым интересным объектом алгебраической теории кодирования. Р. Лидл и Г. Нидеррайтер [40] позиционируют эти коды как самое удачное обобщение знаменитых БЧХ — кодов. С момента опубликования первых работ В. Д. Гоппы [30,31] (Ь, (?) — коды привлекли к себе внимание как математиков, так и разработчиков систем и сетей передачи и обработки данных.
Конструкция, предложенная В. Д. Гоппой, оказалась плодотворной для дальнейших исследований: математики стали развивать ее по пути дальнейшей алгебраизации, и здесь были предложены алгебро-геометрические коды [28,33,34,146], а разработчики технических приложений направили свои усилия на обобщение результатов в рамках принятого аппарата, поиск конкретных классов классических кодов Гоппы [118,119], улучшение оценок их параметров [43,138,149−151], а также построение эффективных алгоритмов декодирования [122,128,144].
Предметом исследования данной диссертационной работы являются классические коды Гоппы. Интерес исследователей к этим кодам обусловлен следующими обстоятельствами: во-первых, известно [30], что среди классических кодов Гоппы имеются коды, лежащие на границе Варшамова-Гилберта. Построение таких кодов является одной из важнейших задач теории помехоустойчивого кодирования. во-вторых, из существующих криптосистем, именно криптосистемы на базе классических кодов Гоппы рассматриваются специалистами как одно из самых перспективных направлений развития криптографических систем, особенно учитывая возможность появления полноценных квантовых компьютеров [49,98].
В.Д. Гоппа описал широкий класс линейных блоковых кодов и предложил классификацию этих кодов: циклические, неприводимые, кумулятивные. Он показал, что среди неприводимых кодов имеются коды, лежащие на границе Варшамова-Гилберта. В. Д. Гоппа указал, что единственным подклассом циклических кодов (наиболее интересных с точки зрения практической реализации) являются коды БЧХ в узком смысле. В работе [32] В. Д. Гоппа предложил алгоритм декодирования (L, G) кодов в пределах их конструктивного расстояния. Открытыми оставались многие вопросы среди которых основными были [41]: с.
1. Улучшение оценок параметров кодов, так как в общем случае оценка для размерности (L, G) кодов оказывалась хуже чем известные оценки,.
2. Определение минимального расстояния кодов Гоппы, так как известно, что во многих случаях конструктивное расстояние этих кодов сущеs ственно меньше их истинного расстояния,.
3. Построение конкретных классов кодов с параметрами, соответствующими улучшенным оценкам,.
4. Разработка алгоритмов реализующих декодирование (Д С) кодов с исправлением числа ошибок, превышающем половину конструктивного расстояния кода,.
5. Построение кодов, лежащих на границе Варшамова-Гилберта или построение кодов с параметрами, лучшими, чем у известных,.
6. Развитие предложенной В. Д. Гоппой классификации (Ь, С?) кодов,.
7. Построение обобщений кодов, предложенных В. Д. Гоппой ,.
8. Построение (X, С) кодов для метрик, отличных от метрики Хэмминга.
В настоящей диссертационной работе исследуется ряд из перечисленных проблем, решение которых позволит добиться эффективного использования потенциала, заложенного в классических кодах Гоппы для обеспечения надежного хранения, обработки и передачи информации от случайных и преднамеренных искажений.
Первая проблема связана с улучшением существующих оценок размерности и минимального расстояния для классических кодов Гоппы. Построение классов кодов Гоппы с улучшенными оценками размерности и минимального расстояния по сравнению с известными позволит получить новые линейные коды с хорошими параметрами, возможно даже лучшими среди известных, которые могли бы эффективно использоваться в системах передачи и обработки информации для обеспечения достоверности и целостности данных, кроме того, такие коды могут быть успешно использованы в системах информационной безопасности.
Второй проблемой является разработка алгоритма декодирования, позволяющего исправлять число ошибок, превышающее половину конструктивного расстояния кода. Классические алгоритмы позволяют исправлять ошибки вплоть до половины конструктивного расстояния кода. Коды Гоппы, лежащие на границе ВаршамоваГилберта имеют минимальное расстояние существенно превышающее их конструктивное, определяемое степенью многочлена Гоппы. Нахождение эффективного алгоритма декодирования за половину конструктивного расстояния позволит использовать корректирующую способность кода и кроме того может быть использовано для повышения уровня защищенности систем защиты информации, построенных на помехоустойчивых кодах.
Третья проблема заключается в расширении класса классических кодов Гоппы.
Цель диссертационной работы.
Решение научной проблемы защиты информации от случайных и преднамеренных искажений на основе построения новых классов кодов Гоппы, имеющих улучшенные оценки для размерности и минимального расстояния с эффективным алгоритмом декодирования. Применение этих кодов в системах обработки и передачи информации повысит достоверность передачи и хранения информации, а использование их в системах информационной безопасности позволит создать надежные средства защиты информации.
Для достижения поставленной цели в работе исследуются следующие основные задачи.
Основные задачи.
1. Построение новых классов классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния.
2. Построение новых классов кодов Гоппы, имеющих более простую схему кодирования и декодирования.
3. Построение оптимальных кодов во взвешенной метрике Хэмминга, которые могут быть эффективно использованы для исправления ошибок в каналах с неравномерным распределением ошибок.
4. Расширение класса циклических кодов Гоппы.
5. Разработка эффективных декодеров (?, О) кодов, позволяющих реализовать корректирующую способность кода.
6. Использование предложенных классов кодов Гоппы для обеспечения безопасности в информационных системах. Методы исследования. Для решения поставленных задач в работе использовались методы системного анализа, теории кодирования, комбинаторного анализа, алгебры, теорий групп, конечных полей, матриц. При построении таблиц проводились вычисления с помощью ЭВМ.
Научная новизна работы Научная новизна работы заключается в следующем.
1. Введены новые классы классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, представители этих классов имеют параметры лучшие, чем известные коды.
2. Выявлены взаимосвязи новых классов кодов Гоппы и предложена их классификация в виде «цепи» вложенных и эквивалентных кодов, что позволило получить более точные оценки, а в некоторых случаях и точное значение для минимального расстояния и размерности кодов, входящих в такую цепь.
3. Введен класс кумулятивно-сепарабельных кодов Гоппы, показано, что среди кодов этого класса имеются коды с параметрами существенно улучшающими известные оценки для классических кодов Гоппы, среди кодов из этого класса получены новые коды с параметрами лучшими известных.
4. Получен новый класс оптимальных обобщенных (?, С) кодов во взвешенной метрике Хэмминга, которые эффективны в каналах с неравномерным распределением ошибок. Предложено описание линейных кодов с неравной защитой как обобщенных (I/, (У) — кодов.
5. Предложен модифицированный расширенный алгоритм Евклида, позволяющий декодировать алгебраические коды за половину конструктивного расстояния.
Практическая ценность работы Практическая ценность работы состоит в том, что разработка основных вопросов диссертации позволила:
• Предложить эффективные кодовые конструкции для исправления ошибок в каналах с различными характеристиками.
• Предложить алгоритмы декодирования позволяющие повысить помехоустойчивость систем передачи информации.
• Разработать систему многоуровневого и иерархического разграничения доступа к информации на основе системы вложенных (Д (3) кодов.
• Предложить протокол анонимных запросов к информации, использующий систему вложенных (Ь, (?) кодов.
• Разработать систему распределения ключей с использованием обобщенных (I/, (2) кодов во взвешенной метрике Хэмминга.
Результаты диссертационной работы использованы в научноисследовательских работах и внедрены в ряде организаций. Использование результатов подтверждено соответствующими актами.
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на:
1. Всесоюзных конференциях по теории информации и передачи информации (Куйбышев 1981, Одесса 1988);
2. Всесоюзных симпозиумах по проблеме избыточности в информационных системах (СПб, 1983;1989);
3. Общероссийских научно-технической конференциях «Методы и технические средства обеспечения безопасности информации (СПб, 19 952 009);
4. Международных симпозиумах по проблеме избыточности в информационных системах (СПб, 2007;2009);
5. Международных конференциях по алгебраической и комбинаторной теории кодирования (АССТ, 1988;2010);
6. Международных симпозиумах по теории информации (1Э1Т, 1995;2008);
7. Международном симпозиуме по конечным полям и их приложениям9, Дублин, 2009);
8. Международных Советско-Шведских симпозиумах по теории информации (1991;1995);
9. Международных симпозиумах по оптимальным кодам (Золотой берег, 2001; Варна, 2009), а также на семинарах:
1. по теории кодирования Института проблем передачи информации РАН (Москва).
2. кафедры информационных систем и кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения.
Публикации. По теме диссертации опубликовано более 50 печатных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе: 12 статей в журналах, включенных в Перечень ВАК, 1 авторское свидетельство СССР и 3 патента США.
Основные положения диссертации, выносимые на защиту.
1. Новые классы кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, представители этих классов имеют параметры лучше, чем известные коды.
2. Взаимосвязи предложенных новых классов кодов Гоппы представленные в виде «цепей» вложенных и эквивалентных кодов.
3. Новый класс совершенных двоичных линейных кодов во взвешенной метрике Хэмминга, описанный как класс обобщенных (?, (?) кодов.
4. Алгоритм декодирования (I/, О) кодов с исправлением числа ошибок, превышающего половину конструктивного расстояния, использующий модифицированный расширенный алгоритм Евклида.
5. Описание линейных кодов с неравной защитой символов как обобщенных (Д С) — кодов.
Структура и объем работы. Диссертационная работа со стоит из введения, пяти глав, заключения, списка литературы и приложения. Работа содержит 340 страниц машинописного текста, 12 рисунков и 39 таблиц. Список использованной литературы содержит 159 наименований.
В первой главе даются основные понятия и определения, приводятся параметры и свойства классических кодов Гоппы. Рассмотрены основные существующие алгоритмы их декодирования в пределах половины конструктивного расстояния кода. Исходя из свойств кодов Гоппы делается вывод об актуальности задачи разработки алгоритмаих декодирования за половину конструктивного расстояния. Приводится алгоритм декодирования, основанный на модифицированном алгоритме Евклида, позволяющий исправлять число ошибок, превышающее половину конструктивного расстояния кода.
Во второй главе рассмотрены новые классы сепарабельных кодов Гоппы с множествами нумераторов позиций Ь С СР (с{21) и Ь С СР (д31). Показана взаимосвязь полученных классов и построены улучшенные оценки для минимального расстояния и размерности новых классов кодов. Построены примеры конкретных кодов, принадлежащих этим классам и являющихся лучшими известными на настоящий момент. Показано, что предложенные сепарабель-ные коды являются квазициклическими. Приведены параметры конкретных квазициклических кодов, имеющих лучшие на настоящий момент параметры.
В третьей главе рассмотрен новый класс кумулятивно-сепарабельных кодов. Для кодов из этого класса определены оценки на минимальное расстояние и размерность существенно улучшающие известные. Показана закономерность этих оценок от порядка кумулятивности многочлена Гоппы, используемого для задания кода. Определена взаимосвязь различных подклассов кумулятивно-сепарабельных кодов.
В четвертой главе рассматриваются обобщенные (Ь, (7) коды, дается их определение и оценки для минимального расстояния и избыточности. Приводится новый подкласс обобщенных (?, С?) кодов с улучшенной оценкой на размерность кода. Определяются коды во взвешенной метрике Хэмминга и предлагается новый класс совершенных кодов в этой метрике. Рассматриваются обобщенные (?, (2) коды суффиксной конструкции и доказывается возможность описания известных ранее (2,1) и (? + 1.1) кодов с неравной защитой символов как обобщенных (X, С) кодов при специальном задании множества нумераторов позиций. Приводятся алгоритмы декодирования для таких кодов. Рассматриваются обобщенные циклические (Д С) коды. Вводится понятие «локаторного» кода, использование которого позволяет построить множество нумераторов для известных циклических кодов лежащих на границе Хартмана-Тзенга и тем самым описать их как циклические (Ь, О) коды. Тем самым доказывается, что известное ранее ограничение класса циклических кодов Гоппы лишь классом примитивных БЧХ кодов может быть существенно откорректировано и многие циклические коды, минимальное расстояние которых превышает оценку БЧХ могут быть описаны как (Ь, (?) коды Приводится алгоритм декодирования обобщенных (?-, С) кодов.
В пятой главе рассмотрены практические применения (Ь, О) кодов в системах защиты информации. Предложена система многоуровневого и иерархического разграничения доступа, использующая классы вложенных кодов Гоппы. Рассмотрен вариант выбора ключей для пользователей, находящихся на разных уровнях системы разграничения доступа и определены свойства такой системы. Предложена система разделения секрета, использующая обобщенные (X, С?) коды с множеством нумераторов позиций, содержащим рациональные функции со знаменателями различных степеней. Использование таких классов кодов позволило предложить весовую схему разделения секрета. Рассмотрен протокол анонимности запросов и продемонстрирована возможность использования в нем (Ь, С) кодов. Рассмотрена модифицированная схема Рао-Нам для маскирования видеоизображения.
В заключении приведены основные результаты полученные в диссертационной работе.
В приложении, А приведены доказательства теорем и лемм из второй главы.
Основные результаты, полученные в работе, можно сформулировать следующим образом.
1. Введены новые классы классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, среди кодов из этих классов получены коды с параметрами лучшими известных.
2. Определено соотношение между полученными классами кодов и показано, что они могут быть представлены общей «цепью» вложенных и эквивалентных кодов. Такое представление позволило получить точное значение минимального расстояния и размерности предложенных классов кодов.
3. Введен класс кумулятивно-сепарабельньтх кодов Гоппы, показано, что среди кодов этого класса имеются коды с параметрами существенно улучшающими известные оценки для классических кодов Гоппы.
4. Выявлены взаимосвязи различных классов кодов Гоппы из предложенного семейства классов кумулятпвно-сепарабельных кодов.
5. Получен класс совершенных кодов во взвешенной метрике Хэмминга, частным случаем которых являются коды с неравной защитой символов.
6. Предложен модифицированный расширенный алгоритм Евклида, позволяющий декодировать алгебраические коды за половину конструктивного расстояния,.
7. Предложены варианты использования (Ь, (2) кодов для защиты информации.
Заключение
.
В данной диссертационной работе рассмотрены кодовые конструкции на основе классических кодов Гоппы. Предложены новые классы (Ь, С?) кодов, имеющие улучшенные значения минимального расстояния и размерности. Проанализирована взаимосвязь различных классов сепарабельных кодов Гоппы и доказано что предложенные новые классы кодов образуют «цепь» вложенных и эквивалентных кодов. Для некоторых из введенных классов кодов удалось найти точное значение для минимального расстояния и размерности кода. Среди кодов из предложенных новых классов найдены лучшие известные на настоящий момент линейные коды. Показано, что многие из предложенных новых классов являются квазициклическими кодами. Наличие у предложенных классов такого свойства позволяет упростить алгоритмы кодирования/декодирования.
Предложен алгоритм декодирования позволяющий более эффективно использовать реальную корректирующую способность (Ьу С?) кодов, декодируя их за половину конструктивного расстояния. Рассмотрены обобщенные (Ь, С?) коды и показано что используя введенное в диссертационной работе понятие «локаторного» кода можно описать все известные в настоящее время циклические коды, лежащие на границе Хартмана-Тзенга как циклические обобщенные (Ь, С) коды, множество нумераторов позиций которых определяется найденным «локаторным кодом» .
Использование обобщенных (I/, (2) с множествами нумераторов Ь, состоящим из рациональных функций, знаменатели которых имеют различные степени позволило построить совершенные двоичные линейные коды во взвешенной метрике Хэмминга. Построены таблицы всех известных в настоящее время совершенных двоичных линейных кодов во взвешенной метрике Хэмминга с длиной менее 1500. Показано, что такие коды могут быть использованы для повышения помехозащищенности в каналах с неравномерным распределением ошибок, а также для исправления ошибок заданной конфигурации, например в логических схемах. Использование обобщенных^, С) кодов суф-фиксной конструкции позволило описать коды с неравной защитой символов как (Ь, 6?) коды и предложить для них соответствующий алгоритм декодирования.
Кроме очевидного использования предложенных классов (Ь, 6?) кодов в системах передачи информации для повышения помехозащищенности, рассмотрены варианты использования таких кодов в системах информационной безопасности. Предложена схема использования классов вложенных (Ь, С) кодов в системах многоуровневого и иерархического разграничения доступа. Для обобщенных (Ь, О) кодов рассмотрена схема взвешенного распределения секрета для коалиции пользователей. Показана возможность использования специальным образом выбранных кодов Гоппы для реализации протоколов анонимных запросов к записям в базах данных.
