На правах рукописи

БЕЗЗАТЕЕВ Сергей Валентинович

Кодовые конструкции на основе

классичеcких кодов Гоппы для

обработки и передачи информации

05.13.01 Системный анализ, управление и

обработка информации (в технике и технологиях)

Автореферат диссертации

на соискание ученой степени

доктора технических наук

Санкт-Петербург

2010

Работа выполнена на кафедре безопасности информационных систем в Государственном образовательном учреждении высшего профессионального образования “Санкт-Петербургский государственный университет аэрокосмического приборостроения”

Научный консультант Засл. деятель науки РФ, доктор технических наук, профессор Крук Евгений Аврамович

Официальные оппоненты: доктор технических наук, профессор Зяблов Виктор Васильевич Засл. деятель науки РФ, доктор технических наук, профессор Коржик Валерий Иванович доктор физ.-мат.наук, профессор Соловьева Фаина Ивановна

Ведущая организация: Государственное образовательное учреждение высшего профессионального образования "Московский физико-технический институт (государственный университет)"

Защита состоится 2011 г. в 14.00 часов на заседании диссертационного совета Д 212.233.02 при Государственном образовательном учреждении высшего профессионального образования “Санкт-Петербургский государственный университет аэрокосмического приборостроения” по адресу: 190000, СанктПетербург, ул.Большая Морская,

С диссертацией можно ознакомиться в библиотеке университета.

Автореферат разослан 2011 г.

Ученый секретарь диссертационного совета доктор технических наук, профессор Осипов Л. А.

Общая характеристика работы

Актуальность проблемы.

При разработке и создании распределенных автоматизированных систем обработки информации и управления(АСОИУ) центральной проблемой на протяжении многих лет является защита информации от случайных ошибок и преднамеренных угроз.

Обычно эту проблему разделяют на две: проблему повышения достоверности информации при ее передаче и хранении, и проблему информационной безопасности.

Для решения первой иcпользуется аппарат теории информации и теории помехоустойчивого кодирования.

Для решения второй проблемы до сих пор не существует единого математического аппарата. Частично проблема информационной безопасности АСОИУ решается криптографическими преобразованиями, частично системами управления доступом, в основе математических моделей которых лежит теория множеств.

В основе построения современных криптографических систем лежит теория сложности алгоритмов. Одной из самых перспективных задач этой теории для целей криптографии в настоящее время считается задача декодирования неизвестного(случайного) линейного блокового кода. В настоящее время известно несколько криптографических систем, построенных на базе помехоустойчивых кодов. Лучшими из этих конструкций являются криптосистемы, использующие коды Гоппы.

Коды Гоппы были описаны В.Д.Гоппой в 1970 году и названы им (L, G) кодами. В дальнейшем эти коды получили также название классических кодов Гоппы. Ф.Дж.Мак-Вильямс и Н.Дж.А.Слоэн называют их самым интересным объектом алгебраической теории кодирования. Р.Лидл и Г.Нидеррайтер позиционируют эти коды как самое удачное обобщение знаменитых БЧХ кодов. С момента опубликования в 1970 и 1971 году первых работ В.Д.Гоппы, (L, G) - коды привлекли к себе внимание как математиков, так и разработчиков систем и сетей передачи и обработки данных.

Конструкция, предложенная В.Д.Гоппой, оказалась плодотворной для дальнейших исследований: математики стали развивать ее по пути дальнейшей алгебраизации, и в дальнейшем В.Д.Гоппа, С.Г.Влэдуц,Г.Л.Кацман, М.А.Цфасман предложили и начали исследование алгебро-геометрических кодов, а разработчики технических приложений направили свои усилия на обобщение результатов в рамках принятого аппарата. M.Loeloeian, J.Conan в 1984 году смогли получить конкретный пример двоичного классического кода Гоппы с параметрами лучшими, чем у известных линейных кодов. Н.А.Шехунова, Е.Т.Мирончиков, A.M.Roseiro, J.I.Hall, J.E.Adney, M.Siegel, P.Veron получили результаты, позволившие улучшить оценки параметров кодов Гоппы. D.Mandelbaum,N.J.Patterson, Y.Sugiyama, M.Kasahara, S.Hirawawa, T.Namekawa предложили эффективные алгоритмы декодирования.

Предметом исследования данной диссертационной работы являются классические коды Гоппы. Интерес исследователей к этим кодам обусловлен следующими обстоятельствами:

во-первых, известно, что среди классических кодов Гоппы имеются коды, лежащие на границе Варшамова-Гилберта. Построение таких кодов является одной из важнейших задач теории помехоустойчивого кодирования, во-вторых, из существующих криптосистем, именно криптосистемы на базе классических кодов Гоппы рассматриваются специалистами как одно из самых перспективных направлений развития криптографических систем, особенно, учитывая возможность появления полноценных квантовых компьютеров.

В.Д.Гоппа описал широкий класс линейных блоковых кодов и предложил классификацию этих кодов: циклические, неприводимые, кумулятивные. Он показал, что среди неприводимых кодов имеются коды, лежащие на границе Варшамова-Гилберта.

В.Д. Гоппа указал, что единственным подклассом циклических (L, G) кодов (наиболее интересных с точки зрения практической реализации) являются коды БЧХ в узком смысле. В 1976 году В.Д.Гоппа предложил алгоритм декодирования (L, G) кодов в пределах их конструктивного расстояния. Открытыми оставались многие проблемы среди которых основными были :

1. Построение новых классов (L, G) кодов с оценками параметров лучшими, чем были предложены В.Д. Гоппой.

2. Определение минимального расстояния кодов Гоппы, так как известно, что во многих случаях конструктивное расстояние этих кодов существенно меньше их истинного расстояния.

3. Разработка алгоритмов, реализующих декодирование (L, G) кодов за конструктивное расстояние.

4. Построение кодов, лежащих на границе ВаршамоваГилберта или построение кодов с параметрами, лучшими, чем у известных.

5. Развитие предложенной В.Д.Гоппой классификации (L, G) 6. Построение обобщений (L, G) кодов.

7. Построение (L, G) кодов для метрик, отличных от метрики Хэмминга.

В настоящей диссертационной работе исследуется ряд из перечисленных проблем, решение которых позволит добиться эффективного использования потенциала, заложенного в классических кодах Гоппы, для обеспечения надежного хранения, обработки и передачи информации от случайных и преднамеренных искажений.

Первая проблема связана с улучшением существующих оценок размерности и минимального расстояния для классических кодов Гоппы. Построение новых классов (L, G) кодов c улучшенными оценками размерности и минимального расстояния по сравнению с известными позволит получить новые линейные коды с хорошими параметрами, возможно даже лучшими среди известных, которые могли бы эффективно использоваться в системах передачи и обработки информации для обеспечения достоверности и целостности данных, кроме того, такие коды могут быть успешно использованы в системах информационной безопасности.

Второй проблемой является разработка алгоритма декодирования, позволяющего исправлять число ошибок, превышающее половину конструктивного расстояния кода. Классические алгоритмы позволяют исправлять ошибки вплоть до половины конструктивного расстояния кода. Коды Гоппы, лежащие на границе Варшамова -Гилберта, имеют минимальное расстояние существенно превышающее их конструктивное, определяемое степенью многочлена Гоппы. Нахождение эффективного алгоритма декодирования за половину конструктивного расстояния позволит использовать корректирующую способность кода и, кроме того, может быть использовано для повышения уровня защищенности систем защиты информации, построенных на помехоустойчивых кодах.

Третья проблема заключается в расширении класса классических кодов Гоппы.

Цель диссертационной работы.

Решение научной проблемы защиты информации от случайных и преднамеренных искажений на основе построения новых классов кодов Гоппы, имеющих улучшенные оценки для размерности и минимального расстояния с эффективным алгоритмом декодирования. Применение этих кодов в системах обработки и передачи информации обеспечит повышение достоверности передачи и хранения информации, а использование их в системах информационной безопасности позволит создать надежные средства защиты информации.

Для достижения поставленной цели в работе исследуются следующие основные задачи.

Основные задачи

1. Построение новых классов классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния.

2. Построение новых классов кодов Гоппы, имеющих более простую схему кодирования и декодирования.

3. Построение оптимальных кодов во взвешенной метрике Хэмминга, которые могут быть эффективно использованы для исправления ошибок в каналах с неравномерным распределением ошибок.

4. Расширение класса циклических кодов Гоппы.

5. Разработка эффективных декодеров (L, G) кодов, позволяющих реализовать корректирующую способность кода.

6. Использование предложенных классов кодов Гоппы для обеспечения безопасности в информационных системах.

Методы исследования. Для решения поставленных задач в работе использовались методы системного анализа, теории кодирования, комбинаторного анализа, алгебры, теорий групп, конечных полей, матриц. При построении таблиц проводились вычисления с помощью ЭВМ.

Научная новизна работы. Научная новизна работы заключается в следующем:

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

2. Выявлены взаимосвязи новых классов кодов Гоппы и предложена их классификация в виде ”цепи” вложенных и эквивалентных кодов, что позволило получить более точные оценки, а в некоторых случаях и точное значение для минимального расстояния и размерности кодов, входящих в такую цепь.

3. Введен класс кумулятивно-сепарабельных кодов Гоппы, показано, что среди кодов этого класса имеются коды с параметрами существенно улучшающими известные оценки для классических кодов Гоппы, среди кодов из этого класса получены новые коды с параметрами лучшими известных.

4. Получен новый класс оптимальных обобщенных (L, G) кодов во взвешенной метрике Хэмминга, которые эффективны в каналах с неравномерным распределением ошибок. Предложено описание линейных кодов с неравной защитой как обобщенных (L, G)- кодов.

5. Предложен модифицированный расширенный алгоритм Евклида, позволяющий декодировать алгебраические коды за половину конструктивного расстояния.

Практическая ценность работы. Практическая ценность работы состоит в том, что разработка основных вопросов диссертации позволила:

• Предложить эффективные кодовые конструкции для исправления ошибок в каналах с различными характеристиками.

• Предложить алгоритмы декодирования позволяющие повысить помехоустойчивость систем передачи информации.

• Разработать систему многоуровневого и иерархического разграничения доступа к информации на основе системы вложенных (L, G) кодов.

• Предложить протокол анонимных запросов к информации, использующий систему вложенных (L, G) кодов.

• Разработать систему распределения ключей с использованием обобщенных (L, G) кодов во взвешенной метрике Хэмминга.

Результаты диссертационной работы использованы в научно- исследовательских работах и внедрены в ряде организаций. Использование результатов подтверждено соответствующими актами.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на:

1. Всесоюзных конференциях по теории информации и передачи информации (Куйбышев 1981, Одесса 1988);

2. Всесоюзной школе-семинаре по вычислительным сетям (Тбилиси 1985);

3. Всесоюзных симпозиумах по проблеме избыточности в информационных системах (СПб,1983-1989);

4. Общероссийских научно-технической конференциях "Методы и технические средства обеспечения безопасности информации (СПб, 1995-2009);

5. Международнх симпозиумах по проблеме избыточности в информационных системах (СПб, 2007-2009);

6. Международных конференциях по алгебраической и комбинаторной теории кодирования (ACCT, 1988-2010) 7. Международных симпозиумах по теории информации (ISIT, 1995-2008);

8. Международном симпозиуме по конечным полям и их приложениям (Fq9, Дублин, 2009) 9. Международных Советско-Шведских симпозиумах по теории информации(1991-1995) 10. Международных симпозиумах по оптимальным кодам (Золотой берег, 2001; Варна, 2009) а также на семинарах:

1. по теории кодирования Института проблем передачи информации РАН (Москва).

2. кафедры информационных систем и кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения Публикации. По теме диссертации опубликовано более печатных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе: 12 статей в журналах, включенных в Перечень ВАК, 1 авторское свидетельство СССР и 3 патента США.

Основные положения диссертации, выносимые на защиту.

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

2. Взаимосвязи предложенных новых классов кодов Гоппы представленные в виде ” цепей” вложенных и эквивалентных кодов.

3. Новый класс совершенных двоичных линейных кодов во взвешенной метрике Хэмминга, описанный как класс обобщенных (L, G) кодов.

4. Алгоритм декодирования (L, G) кодов с исправлением числа ошибок, превышающего половину конструктивного расстояния, использующий модифицированный расширенный алгоритм Евклида.

5. Описание линейных кодов с неравной защитой символов как обобщенных (L, G)- кодов.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения. Работа содержит 340 страниц машинописного текста, рисунков и 39 таблиц. Список использованной литературы содержит 159 наименований.

Основное содержание работы

Во введении обоснована актуальность построения новых классов кодов Гоппы, имеющих улучшенные оценки для размерности и минимального расстояния, и целесообразность разработки эффективных алгоритмов декодирования классических кодов Гоппы для обеспечения надежной передачи, обработки и хранения информации, представлена научная новизна диссертационной работы и ее практическая ценность, сформулированы основные положения, выносимые на защиту, приведено краткое содержание диссертационной работы по главам.

В первой главе даются основные понятия и определения, приводятся оценки параметров и свойства классических кодов Гоппы. Рассмотрены основные алгоритмы их декодирования в пределах половины конструктивного расстояния кода. Исходя из свойств кодов Гоппы делается вывод о целесообразности разработки алгоритма их декодирования за половину конструктивного расстояния. Приводится новый алгоритм декодирования, основанный на модифицированном расширенном алгоритме Евклида, позволяющий исправлять число ошибок превышающее половину конструктивного расстояния кода.

В разделе 1.1 рассмотрены классические коды Гоппы.

Определение 1. Код Гоппы (L, G) состоит из всех q-ичных векторов a = (a1, a2,..., an ), для которых выполняется следующее сравнение:

где G(x) - многочлен степени t с коэффициентами из поля GF(q m ), называемый многочленом Гоппы, и элементы i образуют подмножество L = {1, 2,... n } GF(q m ), называемое множеством нумераторов позиций кодового слова.

Размерность k и минимальное расстояние d этих кодов удовлетворяют следующим неравенствам Величину dG = t + 1 принято называть конструктивным расстоянием кода Гоппы. Отметим здесь, что для двоичного кода Гоппы, задаваемого сепарабельным многочленом G(x) степени t, конструктивное расстояние определяется величиной dG = 2t + 1.

В.Д. Гоппой было доказано, что среди классических (L, G) кодов существуют коды, лежащие на границе Варшамова-Гилберта, и указано на существование кодов с минимальным расстоянием отличным от конструктивного. Было так же показано, что именно среди этих кодов имеются коды, лежащие на границе ВаршамоваГилберта. Таким образом, актуальной является задача декодирования кодов Гоппы за границу, определяемую степенью многочлена Гоппы.

Пусть при передаче кодового слова a = (a1, a2,..., an ), (L, G)- кода имел место вектор ошибки e = (e1, e2,..., en ) такой, что число его ненулевых компонент не превышает половину deg G(x), т.е. половину конструктивного расстояния (L, G)- кода.

В этом случае можно записать следующее сравнение Отсюда, очевидно, получим Причем и, следовательно, Многочлен (x) принято называть многочленом локаторов ошибок.

то есть где (x) многочлен значений ошибок.

Очевидно, что для любого многочлена E(x) степени меньшей deg G(x) существует единственная несократимая дробь B(x) такая что В разделе 1.2 описаны алгоритм Берлекэмпа - Мэсси и расширенный алгоритм Евклида, используемые для решении ключевого уравнения и позволяющие исправлять число ошибок, определяемое величиной dG2.

Для расширенного алгоритма Евклида доказана следующая теорема, используемая в дальнейшем при декодировании за конструктивное расстояние.

Теорема 2. Среди двух последовательных пар многочленов {Ui (x), ai (x)}, {Ui+1 (x), ai+1 (x)}, полученных в процессе выполнения расширенного алгоритма Евклида для многочленов a(x), b(x) = xt, хотя бы одна состоит из взаимно простых многочленов, то есть:

либо НОД(Ui (x), ai (x)) = C, либо НОД(Ui+1 (x), ai+1 (x)) = D, где C и D - некоторые константы.

В разделе 1.3 предложен модифицированный расширенный алгоритм Евклида [24, 38, 39] для декодирования кодов Гоппы за границу, определяемую конструктивным расстоянием кода. Основная идея предлагаемого алгоритма состоит в аппроксимации искомой дроби (x) множеством подходящих дробей, полученных в процессе реализации расширенного алгоритма Евклида. То есть, предлагается использовать представление многочлена локаторов ошибок как линейной комбинации многочленов i (x), полученных в процессе выполнения расширенного алгоритма Евклида:

Аналогичным образом может быть представлен и многочлен значений ошибок где многочлены i (x) и Pi (x) получаются из соответствующих многочленов Uj (x) и aj (x).

Доказано, что использование модифицированного расширенного алгоритма Евклида позволяет построит базис, определяющий все возможные подходящие дроби, задающие известную синдромную последовательность E(x).

Теорема 3. Используя модифицированный расширенный алгоритм Евклида, можно получить множество из m = 20 + пар линейно независимых многочленов таких, что Будем считать, что deg A(x), так как в противном случае не существует многочленов i (x), степень которых не превосходит величины T.

Теорема 4. Пусть {i (x), Pi (x)} - множество из 20 + 1 пар многочленов, вычисленных с помощью модифицированного расширенного алгоритма Евклида по исходным многочленам A(x) и G(x). Любая пара многочленов {P (x), Q(x)}, для которых выполняется сравнение при где 2, t = deg G(x) и t = 2 20 может быть представлена как линейная комбинация 20 + 1 пар многочленов {i (x), Pi (x)} в следующей форме В разделе 1.4 показано, что предложенный алгоритм может быть использован для декодирования циклических кодов Гоппы до границы, определяемой оценками Hartmann-Tzeng, Roos и Shaohua. Приведены конкретные примеры использования такого алгоритма для кодов на границе Hartmann-Tzeng и Shaohua. Рассмотрен пример декодирования за половину минимального расстояния [24, 38, 39] с использованием предложенного модифицированного расширенного алгоритма Евклида. Рассмотрены совершенные коды в классе классических кодов Гоппы и их декодирование. Предложен матричный алгоритм декодирования кода Голея (24,12,8) [1].

Во второй главе рассмотрены новые классы сепарабельных кодов Гоппы с улучшенной оценкой на размерность и минимальное расстояние [2, 3, 7, 12, 20, 25, 36].

В разделе 2.1 рассмотрены q -ичные сепарабельные коды Гоппы с множеством нумераторов L GF (q 2l )[7]:

где t = q l, q простое число большее 2. Приведены улучшенные оценки на размерность этих классов кодов и показана их взаимосвязь в виде ”цепи кодов”. В разделе 2.2 приведены теоремы для минимального расстояния кодов из рассмотренных классов, при этом для некоторых классов доказано точное значение минимального расстояния.

Рис. 1: Цепь вложенных и эквивалентных недвоичных сепарабельных кодов c L GF (q 2l ) Теорема 5. [10] Минимальное расстояние кода 1 равно его оценке, получаемой по степени многочлена Гоппы G1 (x) = xt1 + 1, то есть d1 = t.

Теорема 6. [10] Минимальное расстояние кода 6 равно его оценке, получаемой по степени многочлена Гоппы G6 (x) = xt+1 + 1, то есть d6 = t + 2.

Приведены примеры представителей этих классов.

В разделе 2.3 рассмотрены классы вложенных и эквивалентных двоичных сепарабельных кодов Гоппы с L GF (22l ), для которых доказаны точные значения размерности и минимального расстояния [10, 12]. Построены примеры кодов, принадлежащих этим классам, с параметрами лучшими чем у известных [3].

Показано, что предложенные сепарабельные коды являются квазициклическими [31, 37]. Приведены параметры конкретных квазициклических кодов, имеющих лучшие на настоящий момент параметры.

В разделе 2.4 рассмотрены специальные классы двоичных сепарабельных кодов Гоппы с множеством локаторов позиций L GF (23l ) [11].

где t = 2l. Приведены улучшенные оценки на размерность этих классов кодов и показана их взаимосвязь в виде ”цепи кодов”.

Для класса кодов (L1, G1 ) с многочленом G1 (x), представляюРис. 2: Цепь вложенных и эквивалентных двоичных сепарабельных кодов c L GF (23l ) щим собой функцию следа элемента GF (t3 ), получена улучшенная по сравнению с предложенной P.Veron в 1998 году оценка размерности кода :

где k1V er = n3l ·22l +3l - оценка, предложенная P.Veron. Построены примеры конкретных кодов, принадлежащих этим классам.

Показано, что некоторые из них лежат на границе Грайсмера, и доказано существование алгебро-геометрических кодов Гоппы рода 1, лежащих на границе Грайсмера [5]. Используя предложенные классы кодов, удалось построить более пятидесяти конкретных кодов с параметрами, лучшими среди известных.

В третьей главе предложены новые классы кумулятивносепарабельных кодов с улучшенными оценками на размерность и минимальное расстояние [42].

где t = q l, q простое число. Кумулятивно-сепарабельный код j получается из исходного кода j повышением кратности исi) пользуемого многочлена Гоппы, то есть Gj (x) = (Gj (x))i.

Предложена систематизация и определены взаимосвязи введенных классов кумулятивно-сепарабельных кодов. Показана возможность их описания в виде "цепи"вложенных и эквивалентных кодов, что в дальнейшем позволило получить улучшенные оценки на минимальное расстояние и размерность для всех предложенных классов. Найдено точное значение минимального расстояния для класса кодов 6, являющегося замыкающим в ”цепи” предложенного семейства классов кумулятивно-сепарабельных кодов.

Теорема 7. Минимальное расстояние кода 6 при 1 < i < q в точности равно i(t + 1) + 1.

Получена улучшенная оценка размерности для класса кодов Рис. 3: Цепь вложенных и эквивалентных кумулятивносепарабельных кодов с L GF (q 2l ) Приведены улучшенные оценки для минимального расстояния и размерности всех предложенных классов кумулятивносепарабельных кодов. Приведены таблицы с конкретными значениями параметров кодов из всех рассмотренных классов при q = 3, 5, 7, 9, среди которых имеются коды с параметрами лучшими известных.

В четвертой главе рассматриваются обобщенные (L, G) коды, впервые предложенные Н.А.Шехуновой и Е.Т.Мирончиковым в 1981г. Предлагаются новые специальные классы обобщенных (L, G) кодов и даются оценки для их минимального расстояния и избыточности.

В разделе 4.1 дается определение обобщенных (L, G) кодов и приводятся оценки размерности и минимального расстояния.

Обобщенный (L, G) код состоит из всех q-ичных векторов a = (a0, a1,..., an1 ), для которых выполняется сравнение:

где НОД(fi (x), fj (x)) = 1 для всех i = j, si = deg gi (x) < deg fi (x) = ri и НОД(gi (x), fi (x)) = 1, НОД(G(x), fi (x)) = 1 для всех i = 0,..., n 1, и коэффициенты многочленов gi (x), fi (x) лежат в поле GF (q m ). G(x) - многочлен степени t с коэффициентами из GF (q m ).

Размерность k и минимальное расстояние d обобщенного (L, G)- кода определяется неравенствами:

и d - наибольшее целое число, для которого выполняется В разделе 4.2 предлагается новый класс обобщенных (L, G) кодов с улучшенной оценкой на размерность кода.

Приводятся конкретные примеры кодов из предложенного класса, являющиеся оптимальными и имеющими лучшие из известных в настоящее время параметры.

В разделе 4.3 предложены новые классы кодов, исправляющих ошибки заданной конфигурации, кодов исправляющих ошибки, имеющие неравномерное распределение на длине кодового слова [29, 34, 41] и определяются коды во взвешенной метрике Хэмминга.

Определение 8. Взвешенное расстояние Хэмминга dwH (a, b) между векторами a = (a1 a2... an ) и b = (b1 b2... bn ) определяется следующим образом где d(ai, bi ) = 1 если ai = bi и d(ai, bi ) = 0 если ai = bi.

Предлагается новый класс совершенных двоичных линейных кодов в этой метрике.

Теорема 9. Двоичные обобщенные (L, G) коды, задаваемые неприводимым многочленом G(x) степени с коэффициентами из GF (2m ) и множеством нумераторов позиций где ui (x)- неприводимый многочлен степени j с коэффициентами из GF (2m ) и G(x) = ui (x) при всех i, лежат на границе Хэмминга, то есть, являются совершенными кодами во взвешенной метрике Хэмминга.

где n = nj - длина кода, k - размерность кода, Wn - число векторов длины n в шаре радиуса во взвешенной метрике Хэмминга.

Приводится таблица всех известных в настоящее время совершенных двоичных линейных кодов во взвешенной метрике Хэмминга описанных как обобщенные (L, G) коды c длиной менее 1500.

В разделе 4.4 рассматриваются (L, G) коды суффиксной конструкции и доказывается возможность описания известных ранее (2, 1) и (t + 1, 1) кодов с неравной защитой символов как частного случая, предложенных автором кодов в метрике взвешенного расстояния Хэмминга [40]. Приводится множество нумераторов позиций L, используемое для описания оптимальных (2,1) и (t + 1,1) кодов И.М.Бояринова, Г.Л.Кацмана как обобщенных (L, G) кодов [43].

В разделе 4.5 предлагается алгоритм декодирования оптимальных (t+1, 1) кодов с неравной защитой [43] с использованием стандартного алгоритма декодирования (L, G) кодов.

В разделе 4.6 рассматриваются обобщенные циклические (L, G) коды [13]. Вводится понятие ”локаторного” кода, использование которого позволяет построить множество нумераторов для всех известных циклических кодов, лежащих на границе Хартманна-Тзенга, и тем самым описать их как циклические (L, G) коды.

Пусть исходный (n, k, d) циклический код A имеет множество корней порождающего многочлена E = {i1, i2,... ink }, GF (q m ). При этом часть из этих корней являются элементами последовательности M = {b, b+1, b+2, b+3,..., b+t1 }. Будем считать, что в последовательности M имеется f нулей исходного кода: {b+ij }j=1,f, где ij принимает значения из множества {0,..., t 1}.Обозначим Z = {i1, i2,..., if } подмножество индексов, определяющих такие нули кода.

Множество элементов {b+jl }jl Z M определяет подмножество ненулей исходного кода. Обозначим соответствующее подмножество индексов как N = {j1, j2,..., jtf }.

Определение 10. Локаторным кодом для исходного циклического (n, k, d) кода с подмножеством нулей Z и не нулей N в последовательности M будем называть циклический код длины c, НОД(c, n) = 1, среди нулей которого имеется множество элементов v+j1, v+j2,..., v+jtf, – корень c-ой степени из 1.

Показано, что известное ранее ограничение класса циклических кодов Гоппы лишь классом примитивных БЧХ кодов может быть существенно откорректировано и многие циклические коды, минимальное расстояние которых превышает оценку БЧХ могут быть описаны как циклические (L, G) коды [33].

Лемма 11. Пусть b+i1, b+i2,..., b+ij ; где 0 i1 < i2 <... < ij < t являются нулями исходного циклического (n, k, d) кода A.

Обозначим R набор из j чисел {i1, i2,..., ij } и N R - набор из t j чисел {{1, 2,..., t} \ R}.

Если существуют циклический локаторный код (c, k, ), корнями порождающего многочлена которого являются все где - корень степени c из единицы и (c, n) = 1, то циклический код A имеет минимальное расстояние не меньшее d, где d оценивается в соответствии с неравенством :

Теорема 12. Пусть ненулями локаторного кода C длины c является множество элементов:

i1, где 1 i1 v < c и - корень степени c из единицы.

Если исходный циклический код A длины n среди своих корней имеет следующее множество элементов:

то циклический код A имеет минимальное расстояние по крайней мере d, где d-максимальное целое, удовлетворяющее следующему неравенству:

что эквивалентно Приводится алгоритм декодирования обобщенных (L, G) кодов [13, 33, 45], представляющий собой модификацию известного расширенного алгоритма Евклида. Приводятся таблицы циклических кодов, минимальное расстояние которых отлично от конструктивного, определяемого границей БЧХ, описанных как обобщенные (L, G) - коды, что позволяет декодировать их с исправлением числа ошибок, большего, чем гарантирует граница БЧХ.

В пятой главе рассмотрены практические применения классических кодов Гоппы в системах защиты информации.

В разделе 5.1 рассматривается проблема разграничения доступа в разнородных структурах. Под разнородными структурами хранения и обработки данных понимают такие, в которых данные имеют различную значимость или принадлежат разным пользователям. Предложена система многоуровневого и иерархического разграничения доступа, использующая классы вложенных кодов Гоппы [9, 16, 18, 22, 28, 45, 47]. Рассмотрен вариант выбора ключей для пользователей, находящихся на разных уровнях системы разграничения доступа и определены свойства такой системы. Безопасность информации каждого пользователя определяется параметрами n, k и d используемого кода Гоппы и весом случайного вектора ошибки e.

В разделе 5.2 предложена система разделения секрета, использующая обобщенные (L, G) коды с множеством нумераторов позиций, содержащим рациональные функции со знаменателями различных степеней. Использование таких классов кодов позволило предложить весовую схему разделения секрета [46].

В разделе 5.3 рассмотрены схемы анонимности запросов и продемонстрирована возможность использования в них кодов Гоппы [8].

В разделе 5.4 рассмотрены вопросы, связанные с маскированием изображения и предложено использование для этих целей модифицированной схемы Рао-Нам [4, 6].

В заключении приведены основные результаты полученные в диссертационной работе и сделаны выводы.

В приложении приведены доказательства теорем и лемм из второй главы.

Основные результаты работы Основные результаты работы можно сформулировать следующим образом.

1. Введены новые классы классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, среди кодов из этих классов получены коды с параметрами лучшими известных.

2. Определено соотношение между полученными классами кодов и показано, что они могут быть представлены общей ” цепью” вложенных и эквивалентных кодов. Такое представление позволило получить точное значение минимального расстояния и размерности предложенных классов кодов.

3. Введен класс кумулятивно-сепарабельных кодов Гоппы, показано, что среди кодов этого класса имеются коды с параметрами существенно улучшающими известные оценки для классических кодов Гоппы.

4. Выявлены взаимосвязи различных классов кодов Гоппы из предложенного семейства классов кумулятивносепарабельных кодов.

5. Получен класс совершенных кодов во взвешенной метрике Хэмминга, частным случаем которых являются коды с неравной защитой символов.

6. Предложен модифицированный расширенный алгоритм Евклида, позволяющий декодировать алгебраические коды за половину конструктивного расстояния, 7. Предложены варианты использования (L, G) кодов для защиты информации.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

ОПУБЛИКОВАНЫ В СЛЕДУЮЩИХ РАБОТАХ:

(статьи 1-12 - опубликованы в изданиях, включенных в Перечень ВАК) 1. Беззатеев С.В., Алгоритм декодирования кода Голея (24,12,8) // Пробл. передачи информ. 1986. Т.22.

2. Беззатеев С.В., Шехунова Н.А., О конструктивном расстоянии лучшего известного (55,16,19) кода Гоппы // Пробл. передачи информ. 1987. Т.23. № 4.

3. Беззатеев С. В., Мирончиков Е.Т., Шехунова Н.А., Подкласс двоичных кодов Гоппы // Пробл. передачи 4. Беззатеев С.В., Литвинов М.Ю., Трояновский Б.К., Использование помехоустойчивых кодов для шифрации видеоинформации // ИнформационноC. 23-26.

управляющие системы геометрические коды на границе Грайсмера // Информационно-управляющие системы 6. Беззатеев С.В.,Литвинов М.Ю., Трояновский Б.К., Филатов Г. П., Выбор алгоритма преобразования, обеспечивающего изменение структуры изображения // Информационно-управляющие системы 2006.

7. Беззатеев С.В., Шехунова Н.А., Специальные классы кодов Гоппы с улучшенными оценками параметров // Пробл. передачи инф. 2010. Т.46. № 3. С.

8. Беззатеев С.В., Коды Гоппы в протоколах анонимного запроса к данным, // ИнформационноС.86-87.

управляющие системы 9. Беззатеев С.В., Многоуровневая система разграничения доступа на схеме Мак Элиса, // Проблемы информационной безопасности. Компьютерные системы, 2010. № 3 - С.42-44.

10. Bezzateev S., Shekhunova N., Subclass of binary Goppa codes with minimal distance equal to the design distance // IEEE Trans. on Information Theory 1995. V.41.

P.554-555.

11. Bezzateev S.V., Shekhunova N.A., A subclass of binary Goppa codes with improved estimation of the code dimension, //Designs, Codes and Cryptography 12. Bezzateev S., Shekhunova N., Chain of separable binary Goppa codes and their minimal distance // IEEE Transaction on Information Theory N.12 P.5773-5778.

13. Беззатеев С.В., Мирончиков Е.Т., Шехунова Н.А., О декодировании циклических (L, g) - кодов, // Тезисы докладов VIII Всесоюзной конференции по теории кодирования и передачи информации, Москва-Куйбышев, 1981, ч.2 C. 115-119.

14. Беззатеев С.В.,Мирончиков Е.Т., Шехунова Н.А., Оценка Хартмана - конструктивна,// Тезисы докладов VIII Симпозиума по проблемам избыточности в информационных системах, Ленинград, 1983. С.80-82.

15. Беззатеев С.В., Мирончиков Е.Т., Шехунова Н.А., Использование циклических кодов Гоппы в адаптивных системах передачи данных, //Тезисы докладов Всесоюзного совещаниясеминара "Гибкие автоматизированные производственные системы", Ленинград, 1984 ч.5. C.75-76.

16. Беззатеев С.В., Мирончиков Е.Т., Шехунова Н.А., Использование (L, G) кодов в информационных системах коллективного пользования //Тезисы докладов XV военной научнотехнической конференции, Киев. 1984. ч.2. С.307.

17. Беззатеев С.В., Один метод кодирования и декодирования для кодов суффиксной конструкции,// Системы обработки и передачи информации, ЛИАП, Ленинград, 1984. вып. 172.

18. Беззатеев С.В., Мирончиков Е.Т., Шехунова Н.А., Применение (L, g) - кодов суффиксной конструкции для защиты информации в сетевых системах, //Тезисы докладов X Всесоюзной школы-семинара по вычислительным сетям, МоскваТбилиси, 1985. ч.1 С.9-11.

19. Беззатеев С.В., Шехунова Н.А., Декодирование циклических кодов выше конструктивного расстояния, //Помехоустойчивость и эффективность систем передачи информации, Тезисы докладов, Одесса. 1986 С.55-56.

Беззатеев С. В., Мирончиков Е.Т., Шехунова Н.А., Один 20.

подкласс двоичных кодов Гоппы, // Тезисы докладов IX Симпозиума по проблемам избыточности в информационных системах, Ленинград, 1986 C. 140-141.

21. Беззатеев С.В., Обобщенная оценка Хартмана-Тзенга для минимального расстояния кодов Гоппы, // Тезисы докладов IX Симпозиума по проблемам избыточности в информационных системах, Ленинград, 1986, ч.1 C. 67-69.

22. Беззатеев С.В., Иерархическая структура информации в компьютерных сетях, // Информатика и вычислительная техника, М: Наука, 1986. С.258.

23. Беззатеев С.В., Шехунова Н.А., Семейство вложенных кодов Гоппы, //Тезисы докладов IX Всесоюзной конференции по теории кодирования и передачи информации,Одесса. 24. Беззатеев С.В. Декодирование кодов Гоппы за конструктивное расстояние // Техника средств связи, Общетехническая серия 1988. №.2 С. 3-18.

25. Беззатеев С.В., Шехунова Н.А., О параметрах одного подкласса неприводимых кодов Гоппы,// Тезисы докладов X Симпозиума по проблемам избыточности в информационных системах, Ленинград, 1989 ч.1 С. 11-13.

26. Беззатеев С.В., Шехунова Н.А., Помехоустойчивые коды в постквантовой криптографии, // Тезисы докладов VVIII общероссийской научно- технической конференции "Методы и технические средства обеспечения безопасности информации,Санкт-Петербург, 2009 С. 104.

27. Bezzateev S.V., Shekhunova N.A., On the Subcodes of one class Goppa codes, // Proceedings of ACCT-1. Sept.1988 P.143Bezzateev S.V., Shekhunova N.A., Multilevel Cryptosystem Based on Embedded Goppa Codes, // Proccedings of the Workshop on Information Protection, Moscow, December 1993. P.6-9.

29. Bezzateev S.V., Shekhunova N.A., Class of the block codes with unequal error-correcting capability on length, // Proceedings of VI Joint Russian-Sweedish International Workshop on Information Theory, Moscow, 1993, P.54-60.

30. Bezzateev S.V., Shekhunova N.A., On subcodes of one class of quasi-cyclic Goppa codes, // Proceedings of VII Joint SwedishRussian International Workshop on Information Theory, St.

.Petersburg, 1995. P. 34-35.

31. Bezzateev S.V., Shekhunova N.A., Quasi-cyclic Goppa codes // Proceedings of IEEE International Symposium on Information Theory Canada 1995. P.499.

32. Bezzateev S.V., Shekhunova N.A, One construction of quasicyclic codes // Proceedings of ACCT-4, Sozopol, Bulgaria, 33. Bezzateev S.V., Shekhunova N.A., One generalization of Goppa codes, // Proceedings of IEEE International Symposium on Information Theory, Ulm, Germany, 1997. P.299.

34. Bezzateev S.V., Shekhunova N.A., Generalized Goppa codes for correcting localized errors, // Proceedings of IEEE International Symposium on Information Theory, Boston, USA, 1998.

35. Bezzateev S.V., Shekhunova N.A., Generalized q-ary Goppa codes with good parameters, // Proceedings of ACCT-8, Tzarskoye Selo, St.Petersburg, Russia 2002 P.38-42.

36. Bezzateev S.V., Shekhunova N.A., Best Known Binary Goppa Code’s Chain, // Proc. of XI International Symposium on Probl.

of Redundancy in Inf. and Control Systems, St.Petersburg, 2007 P.56-58.

37. Bezzateev S.V., Shekhunova N.A., Relation between Two Classes of Binary Quasi-Cyclic Goppa codes, // Proc. of ACCT-11, 2008 P.255-259.

38. Bezzateev S.V, Kampf S., Bossert M., Some Results on List Decoding of Interleaved Reed-Solomon Codes with the Extended Euclidean Algorithm, // Proceedings of Workshop "Coding Theory Days in St. Petersburg", 2008, P. 31-36.

39. Bezzateev S., Bossert M., Decoding of Interleaved RS codes with the Euclidean algorithm, // Proceedings of IEEE International Symposium on Information Theory, Canada, 2008. P.1803Bezzateev S.V., Shekhunova N.A., Design of Linear Unequal Error Protecting Codes as Generalized (L,G) Codes, //Proceedings of XII International Symposium on Problems of Redundancy in Information and Control Systems, Saint-Petersburg, Russia, May 26-30, 2009 P.44-47.

41. Bezzateev S.V., Shekhunova N.A., Goppa codes for correcting nonuniform distributed errors,//Proceedings of Euroworkshop "Optimal Codes and Related Topics", Varna, Bulgaria, June 16-22 2009 P.11-15.

42. Bezzateev S.V., Shekhunova N.A., Subclass of nonbinary cumulative Goppa codes, //The 9th International Conference on Finite Fields and their Applications,University College Dublin, July 13-17. 2009 P.7, (http://www.shannoninstitute.ie/fq9/AllFq9Abstracts.pdf) 43. Bezzateev S.V., Shekhunova N.A., Binary unequal error protection codes as a subclass of generalized (L,G) - codes, //Proceedings of ACCT-12, Novosibirsk, 2010 - P. 37-42.

Авторские свидетельства и патенты на изобретения 44. А.с. 1339901 СССР МКИ H 03 M 13/02. Устройство для декодирования двоичного циклического кода. Беззатеев С.В., Мирончиков Е.Т., Шехунова Н.А. Опубл. 23.09.87. Бюл.№ 35. (Личное участие 33 % ) 45. Patent USA 7532724 H04L 9/00. Method for encrypting and decrypting data for multi-level access control in an ad-hoc network. Bezzateev S., Jung Tae-chul, Lee Kyung-hee, Krouk E., Sitalov A. Iss. 12.05.09 (Личное участие 25 % ) 46. Patent USA 7551740 H04L 9/00. Weighted secret sharing and reconstructing method. Bezzateev S., Jung Tae-chul, Lee Kyunghee, Krouk E., Linsky E. Iss. 23.06.09 (Личное участие 25% ) 47. Patent USA 0117745 H04L 9/00. Data encryption and decryption method using a public key. Bezzateev S., Fomin A., Jung Taechul, Lee Kyung-hee, Krouk E. Iss. 02.06.05 (Личное участие Формат бумаги 60 84 1/16. Бумага офсетная. Усл. печ. л. 2.

Отпечатано в редакционно-издательском центре ГУАП 190000, Санкт-Петербург, Б. Морская ул.,