Введение к работе
Актуальность проблемы.
При разработке и создании распределенных автоматизированных систем обработки информации и управления(АСОИУ) центральной проблемой на протяжении многих лет является защита информации от случайных ошибок и преднамеренных угроз. Обычно эту проблему разделяют на две: проблему повышения достоверности информации при ее передаче и хранении и проблему информационной безопасности.
Для решения первой используется аппарат теории информации и теории помехоустойчивого кодирования.
Для решения второй проблемы до сих пор не существует единого математического аппарата. Частично проблема информационной безопасности АСОИУ решается криптографическими преобразованиями, частично системами управления доступом, в основе математических моделей которых лежит теория множеств. В основе построения современных криптографических систем лежит теория сложности алгоритмов. Одной из самых перспективных задач этой теории для целей криптографии в настоящее время считается задача декодирования неизвестного (случайного) линейного блокового кода. В настоящее время известно несколько криптографических систем, построенных на базе помехоустойчивых кодов. Лучшими из этих конструкций являются криптосистемы, использующие коды Гоппы.
Коды Гоппы были описаны В.Д.Гоппой в 1970 году и названы им (L, G) кодами. В дальнейшем эти коды получили также название классических кодов Гоппы. Ф.Дж.Мак-Вильямс и Н.Дж.А. Слоэн называют их самым интересным объектом алгебраической теории кодирования. Р.Лидл и Г.Нидеррайтер позиционируют эти коды как самое удачное обобщение знаменитых БЧХ -кодов. С момента опубликования в 1970 и 1971 году первых работ В.Д. Гоппы, (L, G) - коды привлекли к себе внимание как математиков, так и разработчиков систем и сетей передачи и обработки данных.
Конструкция, предложенная В.Д.Гоппой, оказалась плодотворной для дальнейших исследований: математики стали развивать ее по пути дальнейшей алгебраизации, и в дальнейшем В.Д Гоппа, Влэдуц Г., Кацман Г.Л., Цфасман М.А. предложили и начали исследование алгебро-геометрических кодов , а разработчики технических приложений направили свои усилия на обобщение результатов в рамках принятого аппарата. Loeloeian М., Conan J. в 1984 году смогли получить конкретный пример двоичного классического кода Гоппы с параметрами лучшими чем у известных линейных кодов. Шехунова Н.А., Мирончиков Е.Т., Roseiro A.M., Hall J.I., Adney J.E., Siegel M., Veron P. получили результаты, позволившие улучшить оценки параметров кодов Гоппы. Mandelbaum D.,Patterson N.J., Sugiyama Y., Kasahara M., Hirawawa S., Namekawa Т. предложили эффективные алгоритмы декодирования.
Предметом исследования данной диссертационной работы являются классические коды Гоппы. Интерес исследователей к этим кодам обусловлен следующими обстоятельствами:
во-первых, известно, что среди классических кодов Гоппы имеются коды, лежащие на границе Варшамова-Гилберта. Построение таких кодов является одной из важнейших задач теории помехоустойчивого кодирования.
во-вторых, из существующих криптосистем, именно криптосистемы на базе классических кодов Гоппы рассматриваются специалистами как одно из самых перспективных направлений развития криптографических систем особенно учитывая возможность появления полноценных квантовых компьютеров.
В.Д. Гоппа описал широкий класс линейных блоковых кодов и предложил классификацию этих кодов: циклические, неприводимые, комулятивные. Он показал, что среди неприводимых кодов имеются коды , лежащие на границе Варшамова-Гилберта. В.Д. Гоппа указал, что единственным подклассом циклических кодов (наиболее интересных с точки зрения практической реализации)
являются коды БЧХ в узком смысле. В 1976 году В.Д. Гоппа предложил алгоритм декодирования (L, G) кодов в пределах их конструктивного расстояния. Открытыми оставались многие вопросы среди которых основными были :
-
Улучшение оценок параметров кодов, так как в общем случае оценка для размерности (L, G) кодов оказывалась хуже чем известные оценки,
-
Определение минимального расстояния кодов Гоппы, так как известно, что во многих случаях конструктивное расстояние этих кодов существенно меньше их истинного расстояния,
-
Построение конкретных классов кодов с параметрами, со-ответсвующими улучшенным оценкам,
-
Разработка алгоритмов реализующих декодирование (L, G) кодов с исправлением числа ошибок, превышающем половину конструктивного расстояния кода,
-
Построение кодов, лежащих на границе Варшамова-Гилберта или построение кодов с параметрами, лучшими, чем у известных,
-
Развитие предложенной В.Д. Гоппой классификации (L,G) кодов,
-
Построение обобщений кодов, предложенных В.Д.Гоппой ,
-
Построение (L, G) кодов для метрик, отличных от метрики Хэмминга.
В настоящей диссертационной работе исследуется ряд из перечисленных проблем, решение которых позволит добиться эффективного использования потенциала, заложенного в классических кодах Гоппы для обеспечения надежного хранения , обработки и передачи информации от случайных и преднамеренных искажений.
Первая проблема связана с улучшением существующих оценок размерности и минимального расстояния для классических кодов Гоппы. Построение классов кодов Гоппы с уточненными или улучшенными оценками размерности и минимального расстояния по сравнению с известными позволит получить новые линейные коды с хорошими параметрами, возможно даже лучшими среди известных , которые могли бы эффективно использоваться в системах передачи и обработки информации для обеспечения достоверности и целостности данных, кроме того, такие коды могут быть успешно использованы в системах информационной безопасности.
Второй проблемой является разработка алгоритма декодирования, позволяющего исправлять число ошибок, превышающее половину конструктивного расстояния кода. Классические алгоритмы позволяют исправлять ошибки вплоть до половины конструктивного расстояния кода. Коды Гоппы, лежащие на границе Варшамова -Гилберта имеют минимальное расстояние существенно превышающее их конструктивное, определяемое степенью многочлена Гоппы. Нахождение эффективного алгоритма декодирования за половину конструктивного расстояния позволит использовать корректирующую способность кода и кроме того может быть использовано для повышения уровня защищенности систем защиты информации, построенных на помехоустойчивых кодах.
Третья проблема заключается в расширении множества линейных блоковых кодов, описываемых аппаратом рациональных функций над конечными полями. Для таких кодов применима техника, используемая при декодирования классических кодов Гоппы.
Цель диссертационной работы.
Решение научной проблемы защиты информации от случайных и преднамеренных искажений на основе построения новых классов кодов Гоппы, имеющих улучшенные оценки для размерности и минимального расстояния с эффективным алгоритмом декодирования. Применение этих кодов в системах обработки и передачи информации обеспечит повышение достоверности передачи и хранения информации, а использование их в системах ин-
формационной безопасности позволит создать надежные средства защиты информации.
Для достижения поставленной цели в работе исследуются следующие основные задачи.
Основные задачи
-
Построение новых классов классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния,
-
Построение квазициклических кодов Гоппы, имеющих более простую схему кодирования,
-
Построение недвоичных обобщенных (L, G) кодов, имеющих хорошие параметры, сравнимые с параметрами лучших известных линейных кодов, и эффективный алгоритм декодирования,
-
Построение оптимальных кодов в метрике взвешенного расстояния Хэмминга, которые могут быть эффективно использованы для исправления ошибок известной структуры,
-
Описание оптимальных (2,1) и ( + 1,1) двоичных кодов с неравной защитой как особого подкласса обобщенных (L, G) кодов с эффективным алгоритмом декодирования,
-
Описание циклических кодов отличных от примитивных БЧХ как специального класса обобщенных циклических (L, С)-кодов,
-
Разработка эффективных декодеров (L, G) кодов, позволяющих в полной мере реализовать корректирующую способность кода,
-
Использование предложенных классов кодов Гоппы для обеспечения безопасности в информационных системах.
Методы исследования. Для решения поставленных задач в работе использовались методы системного анализа, оптимизации
и обработки информации, теории кодирования, комбинаторного анализа, алгебры, теорий групп, конечных полей, матриц. При построении таблиц проводились вычисления с помощью ЭВМ.
Научная новизна работы. Научная новизна работы заключается в следующем:
-
Введены новые классы классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, среди кодов из этих классов получены новые коды с параметрами лучшими известных.
-
Введен класс кумулятивно-сепарабельных кодов Гоппы, показано, что среди кодов этого класса имеются коды с параметрами существенно улучшающими известные оценки для классических кодов Гоппы, среди кодов из этого класса получены новые коды с параметрами лучшими известных.
-
Выявлены взаимосвязи новых классов кодов Гоппы и предложена их классификация в виде "цепи" вложенных и эквивалентных кодов, что позволило получить более точные оценки, а в некоторых случаях и точное значение для минимального расстояния и размерности кодов, входящих в такую цепь.
-
Получен новый класс оптимальных обобщенных (L,G) кодов в метрике взвешенного расстояния Хэмминга, которые эффективны в каналах с неравномерным распределением ошибок.
-
Предложен модифицированный расширенный алгоритм Евклида, позволяющий декодировать алгебраические коды за половину конструктивного расстояния.
-
Введено понятие "локаторного"кода, использование которого позволило представить все известные циклические коды, лежащие на границе Хартманна-Тзенга как обобщенные циклические (L, G)- коды с соответствующим алгоритмом декодирования.
7. Предложено описание линейных кодов с неравной защитой как обобщенных (L,G)- кодов.
Практическая ценность работы. Практическая ценность работы состоит в том, что разработка основных вопросов диссертации позволила:
Построить новые линейные коды с параметрами лучшими чем известные.
Построить новый класс кодов для исправления ошибок имеющих неравномерное распределение,
Предложить эффективные алгоритмы декодирования линейных кодов с неравной защитой.
Разработать систему многоуровневого и иерархического разграничения доступа к информации на основе системы вложенных (L,G) кодов.
Предложить протокол анонимных запросов к информации, использующий систему вложенных (L, G) кодов.
Разработать систему распределения ключей с использованием обобщенных (L, G) кодов в метрике взвешенного расстояния Хэмминга.
Результаты диссертационной работы использованы в научно- исследовательских работах и внедрены в ряде организаций. Использование результатов подтверждено соответствующими актами.
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на:
-
Всесоюзных конференциях по теории информации и передачи информации (Куйбышев 1981, Одесса 1988);
-
Всесоюзной школе-семинаре по вычислительным сетям (Тбилиси 1985);
-
Всесоюзных симпозиумах по проблеме избыточности в информационных системах (СПб, 1983-1989);
-
Общероссийских научно-технической конференциях "Методы и технические средства обеспечения безопасности информации (СПб, 1995-2009);
-
Международнх симпозиумах по проблеме избыточности в информационных системах (СПб, 2007-2009);
-
Международных конференциях по алгебраической и комбинаторной теории кодирования (АССТ, 1988-2010)
-
Международных симпозиумах по теории информации (ISIT, 1995-2008);
-
Международном симпозиуме по конечным полям и их приложениям (Fq9, Дублин, 2009)
-
Международных Советско-Шведских симпозиумах по теории информации(1991-1995)
10. Международных симпозиумах по оптимальным кодам (Золотой берег, 2001; Варна, 2009)
а также на семинарах:
-
на постоянно действующем семинаре по теории кодирования Института проблем передачи информации РАН (Москва).
-
кафедры информационных систем и кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения
Публикации. По теме диссертации опубликовано более 50 печатных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе: 10 статей в
журналах, включенных в Перечень ВАК, 1 авторское свидетельство СССР и 3 патента США.
Основные положения диссертации, выносимые на защиту.
-
Новые классы кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, среди которых получены новые коды с параметрами лучшими известных,
-
Новый класс кумулятивно-сепарабельных кодов Гоппы, в котором имеются коды с параметрами существенно улучшающими известные оценки для классических кодов Гоппы,
-
Взаимосвязи предложенных новых классов кодов Гоппы представленные в виде " цепей" вложенных и эквивалентных кодов,
-
Новый класс оптимальных обобщенных (L, G) кодов в метрике взвешенного расстояния Хэмминга,
-
Алгоритм декодирования (L, G) кодов с исправлением числа ошибок, превышающего половину конструктивного расстояния, использующий модифицированный расширенный алгоритм Евклида,
-
"Локаторный"код, позволяющий представить все известные циклические коды, лежащие на границе Хартманна-Тзенга как обобщенные циклические (L, G)- коды,
-
Описание линейных кодов с неравной защитой символов как обобщенных (L, G)- кодов
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения , списка литературы и приложения. Работа содержит 323 страницы машинописного текста, 12 рисунков и 38 таблиц. Список использованной литературы содержит 152 наименования.
