Geum.ru
   Авторефераты по всем темам  >>  Авторефераты по техническим специальностям

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

Беззатеев Сергей Валентинович

Кодовые конструкции на основе классичеcких кодов Гоппы для обработки и передачи информации

05.13.01 Системный анализ, управление и обработка информации (в технике и технологиях)

Автореферат диссертации на соискание ученой степени доктора технических наук

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

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования УСанктПетербургский государственный университет аэрокосмического приборостроенияФ Научный консультант Засл. деятель науки РФ, доктор технических наук, профессор Крук Евгений Аврамович

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

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

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

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

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

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

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

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

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

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

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

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

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

Конструкция, предложенная В.Д.Гоппой, оказалась плодотворной для дальнейших исследований: математики стали развивать ее по пути дальнейшей алгебраизации, и в дальнейшем В.Д Гоппа, Влэдуц Г., Кацман Г.Л., Цфасман М.А. предложили и начали исследование алгебро-геометрических кодов, а разработчики технических приложений направили свои усилия на обобщение результатов в рамках принятого аппарата. Loeloeian M., 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 T. предложили эффективные алгоритмы декодирования.

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

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

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

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

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

1. Улучшение оценок параметров кодов, так как в общем случае оценка для размерности (L, G) кодов оказывалась хуже чем известные оценки, 2. Определение минимального расстояния кодов Гоппы, так как известно, что во многих случаях конструктивное расстояние этих кодов существенно меньше их истинного расстояния, 3. Построение конкретных классов кодов с параметрами, соответсвующими улучшенным оценкам, 4. Разработка алгоритмов реализующих декодирование (L, G) кодов с исправлением числа ошибок, превышающем половину конструктивного расстояния кода, 5. Построение кодов, лежащих на границе ВаршамоваГилберта или построение кодов с параметрами, лучшими, чем у известных, 6. Развитие предложенной В.Д. Гоппой классификации (L, G) кодов, 7. Построение обобщений кодов, предложенных В.Д.Гоппой, 8. Построение (L, G) кодов для метрик, отличных от метрики Хэмминга.

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

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

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

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

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

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

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

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

1. Построение новых классов классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, 2. Построение квазициклических кодов Гоппы, имеющих более простую схему кодирования, 3. Построение недвоичных обобщенных (L, G) кодов, имеющих хорошие параметры, сравнимые с параметрами лучших известных линейных кодов, и эффективный алгоритм декодирования, 4. Построение оптимальных кодов в метрике взвешенного расстояния Хэмминга, которые могут быть эффективно использованы для исправления ошибок известной структуры, 5. Описание оптимальных (2, 1) и (t + 1, 1) двоичных кодов с неравной защитой как особого подкласса обобщенных (L, G) кодов с эффективным алгоритмом декодирования, 6. Описание циклических кодов отличных от примитивных БЧХ как специального класса обобщенных циклических (L, G)-кодов, 7. Разработка эффективных декодеров (L, G) кодов, позволяющих в полной мере реализовать корректирующую способность кода, 8. Использование предложенных классов кодов Гоппы для обеспечения безопасности в информационных системах.

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

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

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

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

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

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

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

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

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

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

Х Построить новые линейные коды с параметрами лучшими чем известные.

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

Х Разработать систему многоуровневого и иерархического разграничения доступа к информации на основе системы вложенных (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. кафедры информационных систем и кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения Публикации. По теме диссертации опубликовано более печатных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе: 10 статей в журналах, включенных в Перечень ВАК, 1 авторское свидетельство СССР и 3 патента США.

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

1. Новые классы кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, среди которых получены новые коды с параметрами лучшими известных, 2. Новый класс кумулятивно-сепарабельных кодов Гоппы, в котором имеются коды с параметрами существенно улучшающими известные оценки для классических кодов Гоппы, 3. Взаимосвязи предложенных новых классов кодов Гоппы представленные в виде Ф цепейФ вложенных и эквивалентных кодов, 4. Новый класс оптимальных обобщенных (L, G) кодов в метрике взвешенного расстояния Хэмминга, 5. Алгоритм декодирования (L, G) кодов с исправлением числа ошибок, превышающего половину конструктивного расстояния, использующий модифицированный расширенный алгоритм Евклида, 6. "Локаторный"код, позволяющий представить все известные циклические коды, лежащие на границе Хартманна-Тзенга как обобщенные циклические (L, G)- коды, 7. Описание линейных кодов с неравной защитой символов как обобщенных (L, G)- кодов Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложения. Работа содержит 323 страницы машинописного текста, 12 рисунков и 38 таблиц. Список использованной литературы содержит 152 наименования.

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

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

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

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

n ai 0 mod G(x), x - i i=где G(x) - многочлен степени t с коэффициентами из поля GF(qm), называемый многочленом Гоппы, и элементы i образуют подмножество L = {1, 2,... n} GF(qm), называемое множеством нумераторов позиций кодового слова. Размерность k и минимальное расстояние d этих кодов удовлетворяют следующим неравенствам k n - mt, d t + 1.

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

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

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

В этом случае можно записать следующее сравнение n n ai + ei n ai ei = + E(x) mod G(x).

x - i i=1 x - i i=1 x - i i=Отсюда,очевидно, получим n ei E(x) mod G(x).

x - i i=В левой части сравнения рациональная дробь:

n ei (x) =.

x - i (x) i=deg G(x) Причем (x) = (x - i), т.е. deg (x) = wt(e) .

i:ei= (x) принято называть многочленом локаторов ошибок.

n (x) = ei (x - j), т.е. deg (x) deg (x) - 1, i=1 j=i ej= где (x) многочлен значений ошибок.

Очевидно, что для любого многочлена E(x) степени меньшей A(x) deg G(x) существует единственная несократимая дробь такая B(x) что deg G(x) deg A(x) < deg B(x) , A(x) E(x) mod G(x).

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

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

Теорема 1. Среди двух последовательных пар многочленов {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 предложен модифицированный расширенный алгоритм Евклида [39, 23, 38] для декодирования кодов Гоппы за границу, определяемую конструктивным расстоянием кода. Основная идея предлагаемого алгоритма состоит в аппроксимации (x) искомой дроби множеством подходящих дробей, полученных (x) в процессе реализации расширенного алгоритма Евклида. То есть, предлагается использовать представление многочлена локаторов ошибок как линейной комбинации многочленов Ui(x), полученных в процессе выполнения расширенного алгоритма Евклида:

R (x) = ii(x).

i=Аналогичным образом может быть представлен и многочлен значений ошибок R (x) = iPi(x).

i=Где многочлены i(x) и Pi(x) получаются из соответствующих Uj(x) и aj(x).

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

Теорема 2. Используя модифицированный расширенный алгоритм Евклида можно получить множество из m = 20 + 1 пар линейно независимых многочленов {Pi(x), i(x)}, i = 1,.., m таких что Pi(x) A(x)i(x) mod G(x).

t где deg Pi(x) < и .

Кроме того deg i(x) , deg G(x) = t и t = 2( - 0).

Будем считать, что deg A(x) , так как в противном случае не существует многочленов i(x) степень которых не превосходит величины T - .

Теорема 3. Пусть {i(x), Pi(x)} - множество из 20 + 1 пар многочленов, вычисленных с помощью модифицированного расширенного алгоритма Евклида по исходным многочленам A(x) и G(x). Любая пара многочленов {P (x), Q(x)} для которых выполняется сравнение Q(x) A(x)P (x) mod G(x), при deg Q(x) - 1, deg P (x) , t где , t = deg G(x) и t = 2 - 20 может быть представлена как линейная комбинация 20 + 1 пар многочленов {i(x), Pi(x)} в следующей форме 20+P (x) = ii(x), i=20+Q(x) = iPi(x).

i=В разделе 1.4 показано, что предложенный алгоритм может быть использован для декодирования циклических кодов Гоппы до границы, определяемой оценками Hartmann-Tzeng, Roos и Shaohua. Приведены конкретные примеры использования такого алгоритма для кодов на границе Hartmann-Tzeng и Shaohua. Рассмотрен пример декодирования за половину минимального расстояния [39, 23, 38] с использованием предложенного модифицированного расширенного алгоритма Евклида.

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

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

Х 1 = (L1, G1) с L1 = {GF (t2)\GF (t)} {0} и G1(x) = xt-1 + 1 ;

Х = (L, G1) с L = {L1\{0}};

1 1 Х 2 = (L2, G2) с L2 = {GF (t2)\GF (t)} и G2(x) = xt + x ;

Х 3 = (L3, G3) с L3 = {GF (t2)\{ : G3() = 0}} и G3(x) = xt + x + 1 ;

Х 4 = (L4, G4) с L4 = {GF (t2)\{ : G4() = 0}} и G4(x) = xt + xt-1 + 1 ;

Х = (L, G4) с L = {L4\{0}} ;

4 4 Х 5 = (L5, G5) с L5 = L и G5(x) = xt+1 + xt + x ;

Х 6 = (L6, G6) с L6 = {GF (t2)\{ : G6() = 0}} и G6(x) = xt+1 + 1 ;

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

Рис. 1: Цепь вложенных и эквивалентных недвоичных сепарабельных кодов c L GF (q2l) В разделе 2.2 приведены теоремы для минимального расстояния кодов из рассмотренных классов, при этом для некоторых классов доказано точное значение минимального расстояния.

Теорема 4. [8] Минимальное расстояние кода 1 равно его оценке, получаемой по степени многочлена Гоппы G1(x) = xt-1 + 1, то есть d1 = t.

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

То есть d6 = t + 2.

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

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

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

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

Х 0 = (L0, G0) с G0 = xt -1 + xt-1 + 1 и L0 = GF (t3) \ { :

G0() = 0};

- = (L, G0) с G0 = xt -1 + xt-1 + 1 и L = L0 \ {0};

0 0 Х 1 = (L1, G1) с G1 = xt + xt + x и L1 = GF (t3) \ { :

G1() = 0};

Х 2 = (L2, G2) с G2 = xt + xt + x + 1 и L2 = GF (t3) \ { :

G2() = 0};

2 2 Х 3 = (L3, G3) с G3 = xt + xt -1 + xt -t + 1 и L3 = GF (t3) \ { : G3() = 0};

2 2 - = (L, G3) с G3 = xt + xt -1 + xt -t + 1 и L = L3 \ {0};

3 3 2 2 Х 4 = (L4, G4) с G4 = xt +t+1 + xt +t + xt +1 + xt+1 и L4 = GF (t3) \ { : G4() = 0};

2 Х 5 = (L5, G5) с G5 = xt -1 + xt -t + 1 и L5 = GF (t3) \ { :

G5() = 0};

2 - = (L, G5) с G5 = xt -1 + xt -t + 1и L = L5 \ {0} ;

5 5 2 Х 6 = (L6, G6) с G6 = xt +t+xt +1+xt+1 и L6 = GF (t3)\{ :

G6() = 0};

Х 7 = (L7, G7) с G7 = xt +t+1 + 1 и L7 = GF (t3) \ GF (t3);

2 Х 8 = (L8, G8) с G8 = xt +t+1 + xt + xt + x + A, A GF (t) и L8 = GF (t3) \ { : G8() = 0};

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

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

k1 k1V er + 3l (2 2l + 2l-1 - 4) + l - 1, где k1V er = n-3l22l +3l - оценка, предложенная P.Veron. Построены примеры конкретных кодов, принадлежащих этим классам.

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

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

Х 1 = (L1, G1) с L1 = {GF (t2)\GF (t)} {0} и G1(x) = xt-1 + 1 ;

Х = (L, G1) с L = {L1\{0}} 1 1 Х 2 = (L2, G2) с L2 = {GF (t2)\GF (t)} и G2(x) = xt + x ;

Х 3 = (L3, G3) с L3 = {GF (t2)\{ : G3() = 0}} и G3(x) = xt + x + 1 ;

Х = (L, G4) с L = GF (t2) \ {{ : G4() = 0} {0}} 4 4 и G4(x) = xt + xt-1 + 1 ;

Х 5 = (L5, G5) с L5 = L и G5(x) = xt+1 + xt + x ;

Х 6 = (L6, G6) с L6 = {GF (t2) \ { : G6() = 0}} и G6(x) = xt+1 + 1 ;

где t = ql, q простое число. Предложена систематизации и определены взаимосвязи введенных классов комулятивносепарабельных кодов. Доказана возможность их описания в виде "цепи"вложенных и эквивалентных кодов, что в дальнейшем позволило получить улучшенные оценки на минимальное расстояние и размерность для всех предложенных классов. Найдено точРис. 3: Цепь вложенных и эквивалентных комулятивносепарабельных кодов с L GF (q2l) ное значение минимального расстояния для класса кодов (i), являющимся замыкающим для предложенного семейства классов комулятивно-сепарабельных кодов.

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

Получена улучшенная оценка размерности для класса кодов (i) (q-1)(q+3) k n - 2l((q - 1)(t + 1) - ).

Приведены улучшенные оценки для минимального расстояния и размерности всех предложенных классов комулятивносепарабельных кодов. Приведены таблицы с конкретными значениями параметров кодов из всех рассмотренных классов при q = 3, 5, 7, 9, среди которых имеются коды с параметрами лучшими известных.

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

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

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

n-gi(x) ai 0 mod G(x), fi(x) i=где НОД(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 (qm). G(x) - многочлен степени t с коэффициентами из GF (qm).

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

k n - t m, и d - наибольшее целое число, для которого выполняется d-t > rij + sil, j=для любых ij и il = ij, l, j = 0,..., n - 1.

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

l l d n = Iq(l) = (d)q, l d=1,d|l l ql-1 - ql-2 - (q - 1) (ql-e - 1 q - 1) + 1, k n qe - 1 e=ql - 1 d +.

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

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

Определение 7. Метрика взвешенного рассстояния Хэмминга dwH(a, b) между векторами a = (a1a2... an) и b = (b1b2... bn) определяется следующим образом n dwH(a, b) = wi d(ai, bi), i=где d(ai, bi) = 1 если ai = bi и d(ai, bi) = 0 если ai = bi.

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

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

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

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

В разделе 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) коды [11]. Вводится понятие ФлокаторногоФ кода, использование которого позволяет построить множество нумераторов для всех известных циклических кодов лежащих на границе Хартмана-Тзенга и тем самым описать их как циклические (L, G) коды.

Определение 9. Локаторным кодом для исходного циклического (n, k, d) кода с подмножеством нулей z и не нулей N в последовательности M будем называть циклический код над GF(qm) длины c взаимно простой с n, среди нулей которого имеется множество элементов:

v+j1, v+j2,..., v+jt-f где - корень c-ой степени из 1.

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

емма 10. Пусть 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, ) с корнями порождающего многочлена v+j, j N R, где - корень степени c из единицы и (c, n) = 1, то циклический код A имеет минимальное расстояние не меньшее d, где d оценивается в соответствии с неравенством :

t > (d - 2) + s, где s - 1.

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

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

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

b+i1+ci2, 1 i1 v < c, 0 i2 < , где - корень n-ой степени из 1 и (n, c) = 1, то циклический код A имеет минимальное расстояние по крайней мере d, где d-максимальное целое удовлетворяющее следующему неравенству:

c( + 1) - v > (d - 2)(c - v + 1) + (c - v), что эквивалентно c > (d - 2)(c - v + 1).

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

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

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

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

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

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

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

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

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

1. Введены новые классы классических кодов Гоппы с улучшенной оценкой размерности и минимального расстояния, среди кодов из этих классов получены новые коды с параметрами лучшеми известных, 2. Определено соотношение между новыми классами кодов и показано, что все они могут быть представлены общей Ф цепьюФ вложенных и эквивалентных кодов. Такое представление позволило доказать точное значение минимального расстояния и размерности предложенных классов кодов, 3. Введен класс кумулятивно-сепарабельных кодов Гоппы, показано, что среди кодов этого класса имеются коды с параметрами существенно улучшающими известные оценки для классических кодов Гоппы, 4. Выявлены взаимосвязи различных классов кодов Гоппы из предложенного класса кумулятивно-сепарабельных кодов, 5. Получен класс совершенных кодов в метрике взвешенного расстояния Хэмминга, 6. Введено понятие "локаторного"кода, использование которого позволило представить все известные циклические коды, лежащие на границе Хартманна-Тзенга как обобщенные циклические (L, G)- коды с соответствующим алгоритмом декодирования, 7. Предложен модифицированный расширенный алгоритм Евклида, позволяющий декодировать алгебраические коды за половину конструктивного расстояния, 8. Предложено описание линейных кодов с неравной защитой как обобщенных (L, G)- кодов, 9. Предложены варианты использования (L, G) кодов для защиты информации.

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

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

№ 3. С.109-112.

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

С.352.

3. Беззатеев С. В., Мирончиков Е.Т., Шехунова Н.А., Подкласс двоичных кодов Гоппы // Пробл. передачи инф. 1989. T.25. №.3. С.98-102.

4. Беззатеев С.В., Литвинов М.Ю., Трояновский Б.К., Использование помехоустойчивых кодов для шифрации видеоинформации // Информационноуправляющие системы 2004. № 5 C. 23-26.

5. Беззатеев С.В., Степанов М.В., Алгеброгеометрические коды на границе Грайсмера // Информационно-управляющие системы 2005. № 3 С.47-49.

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

№ 6 C.2-5.

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

29-8. 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.

9. Bezzateev S.V., Shekhunova N.A., A subclass of binary Goppa codes with improved estimation of the code dimension, //Designs, Codes and Cryptography 19V.14 P.23-38.

10. Bezzateev S., Shekhunova N., Chain of separable binary Goppa codes and their minimal distance // IEEE Transaction on Information Theory 2008. V.54 N. P.5773-5778.

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

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

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

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

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

С.16-18.

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

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

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

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

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

21. Беззатеев С.В., О декодировании троичного кода Голея, //Проблемы совершенствования устройств и методов приема, передачи и обработки информации Москва 1986 ч. С.192-195.

22. Беззатеев С.В., Шехунова Н.А., Семейство вложенных кодов Гоппы, //Тезисы докладов IX Всесоюзной конференции по теории кодирования и передачи информации,Одесса. 19 ч.1 С.82-84.

23. Беззатеев С.В. Декодирование кодов Гоппы за конструктивное расстояние // Техника средств связи, Общетехническая серия 1988. №.2 С. 3-18.

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

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

26. Bezzateev S.V., Shekhunova N.A., On the Subcodes of one>

27. Bezzateev S.V., Shekhunova N.A., Decoding beyond the design distance for binary cyclic codes, //Proceedings of ACCT-2, Leningrad, 1990, 28. Bezzateev 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.,>

30. Bezzateev S.V., Shekhunova N.A., On subcodes of one>

.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, 19 P.34-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.

P.377.

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>

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.18031807.

40. Bezzateev S.V., Shekhunova N.A., Design of Linear Unequal Error Protecting Codes as Generalized (L,G) Codes, //Proceedings of XII Integrational 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 non-binary cumulative Goppa codes, //The 9th International Conference on Finite Fields and their Applications,University College Dublin, July 13-17. 2009 P.7, ( 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 (Личное участие 25 % ) Формат бумаги 60 84 1/16. Бумага офсетная. Усл. печ. л. 2.

Тираж 100 экз. Зак. № Отпечатано в редакционно-издательском центре ГУАП 190000, Санкт-Петербург, Б. Морская ул.,    Авторефераты по всем темам  >>  Авторефераты по техническим специальностям