автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Кодовые конструкции на основе классических кодов Гоппы для обработки и передачи информации

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

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

4856436

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

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

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

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

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

О 3 мдр 2011

4856436

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

Официальные оппоненты: доктор технических наук, профессор

Зяблов Виктор Васильевич

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

Защита состоится Ь> , 2011 г. в 14.00 часов на засе-

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

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

Научный консультант Засл. деятель науки РФ,

доктор технических наук, профессор Крук Евгений Аврамович

Засл. деятель науки РФ,

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

Коржик Валерий Иванович

доктор физ.-мат.наук, профессор Соловьева Фаина Ивановна

Ученый секретарь

диссертационного совета

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

Осипов Л. А.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Развитие предложенной В.Д.Гоппой классификации (£, С) кодов,

6. Построение обобщений (Ь, (?) кодов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

6. Международных конференциях по алгебраической и комбинаторной теории кодирования (АССТ, 1988-2010)

7. Международных симпозиумах по теории информации (КИТ, 1995-2008);

8. Международном симпозиуме по конечным полям и их приложениям (Fq9, Дублин, 2009)

9. Международных Советско-Шведских симпозиумах по теории информации(1991-1995)

10. Международных симпозиумах по оптимальным кодам (Золотой берег, 2001; Варна, 2009)

а также на семинарах:

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

2. кафедры информационных систем и кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения

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

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

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

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

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

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

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

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

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

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

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

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

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

п 1

У^а,-= OmodGfa;),

f-f x-ai

где <?(ж) - многочлен степени I с коэффициентами из поля ОГ(дт), называемый многочленом Гоппы, и элементы щ образуют подмножество Ь = {а\,а2,---ап} ^ называемое множеством нумераторов позиций кодового слова.

Размерность к и минимальное расстояние <1 этих кодов удовлетворяют следующим неравенствам

Величину ¿а = t + 1 принято называть конструктивным расстоянием кода Гоппы. Отметим здесь, что для двоичного кода Гоппы, задаваемого сепарабельным многочленом С(х) степени конструктивное расстояние определяется величиной ¿с = 2£ + 1 . В.Д. Гоппой было доказано, что среди классических Г(Х, б) кодов существуют коды, лежащие на границе Варшамова-Гилберта, и указано на существование кодов с минимальным расстоянием отличным от конструктивного. Было так же показано, что именно среди этих кодов имеются коды, лежащие на границе Варшамова-Гилберта. Таким образом, актуальной является задача декодирования кодов Гоппы за границу, определяемую степенью многочлена Гоппы.

Пусть при передаче кодового слова а = (<21,(12 >... ,ап) , Г(£, С)- кода имел место вектор ошибки е = (еьег, • • •, еп) такой, что число его ненулевых компонент не превышает половину с^ С(х), т.е. половину конструктивного расстояния Г(£, в)- кода. В этом случае можно записать следующее сравнение

к > п — тЬ ,с1 > Ь + 1 .

У = V + у = Е(х) тоас(х).

' X — Щ х — «г X — Щ

г=1 г=1 г=1

Х - Oti

X — 0>{

Отсюда, очевидно, получим

п

В левой части сравнения — рациональная дробь:

п

Причем

4х) = П - '

г.егТ^О

и, следовательно,

Многочлен Л(х) принято называть многочленом локаторов ошибок .

п(х) = 2 64' П ~ ал) '

¿=1

е^О

то есть

degí)(я:) < degЛ(ar) - 1 ,

где Щх) — многочлен значений ошибок.

Очевидно, что для любого многочлена Е(х) степени меньшей degG(ж) существует единственная несократимая дробь такая что

degЛ(:r) < degB(x) <

^1 = Е(х)тос1С(х). В{х)

В разделе 1.2 описаны алгоритм Берлекэмпа - Мэсси и расширенный алгоритм Евклида, используемые для решении ключевого уравнения

ед

А(х)

= Я(х)то(Ю(я)

и позволяющие исправлять число ошибок, определяемое величи-

ной

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

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

либо НОД(и{(х),а{{х)) = С, либо Н0Д(Щ+1 (х),(х)) = Д где С и £> - некоторые константы.

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

я

¿=1

Аналогичным образом может быть представлен и многочлен значений ошибок

л

1=1

где многочлены ДДх) и Рг(ж) получаются из соответствующих многочленов и ц(х).

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

Теорема 3. Используя модифицированный расширенный алгоритм Евклида, можно получить множество из т = 2то + 1

пар линейно независимых многочленов

{Pi(x), Дг(ж)}, i = 1, т

таких, что

Pi(x) = A(x)Ai(x) rnodG(:r) ,

где deg Pi(x) < т и т > [|J.

Кроме того degAi(x) < т, degG(x) — tut — 2(т - то). Будем считать, что deg А{х) > т, так как в противном случае не существует многочленов Ai(x), степень которых не превосходит величины Т — т.

Теорема 4. Пусть {Aj(a;), Pi(x)} - множество из 2tq + 1 пар многочленов, вычисленных с помощью модифицированного расширенного алгоритма Евклида по исходнъш многочленам А(х) и G(x). Любая пара многочленов {P(x),Q(x)}, для которых выполняется сравнение

Q{x) = А{х)Р{х) modG(x),

при

degQ(:c)<T-l , degР{х) < г,

где т > t = deg G(x) и t = 2т — 2tq может быть представлена как линейная комбинация 2tq + 1 пар многочленов {А^ж), Рг(х)} в следующей форме

2713 + 1

Р(х)= £ /3iAi(x), ¿=1 2т0+1

Q(x) = £ ßiPi(x).

¿=1

В разделе 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 С

• Tj = Г(£и G\) с h = {GF(t2)\GF(t)} U {0} и G1{x)=xt~l + 1 ;

. rî = r(LÎ,Gi)cLî = {L1\{0}};

. Г2 = r(L2,G2) с La = {GF(t2)\GF{t}} и G2{x) = хь + ж ;

. Г3 = T(L3, G3) с L3 = {GF{t2)\{a : G3(a) = 0}} и G3(x) = xx + x + 1 ;

• Г4 = T(L4,GA) с Ь4 = {GF(t2)\{a : G4(a) = 0}} и G4(x) = xt + xt~1 + 1 ;

. ra = r(L|,G4)cL| = {Z4\{0}};

• Г5 = Г(Ls, Gs) ci5 = i> G5(x) = xt+l + x* + x ;

• T6 = T{L6, G в) с U = {GF{t2)\{a : G6{a) = 0}} и G6(x) = xt+l + 1 ;

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

коды с длиной кода равной

Рис. 1: Цепь вложенных и эквивалентных недвоичных сепа-рабельных кодов с Ь С СТ7^2')

Теорема 5. [10] Минимальное расстояние кода Г1 равно его оценке, получаемой по степени многочлена Гоппы С\(х) = ж4-1 + 1, то есть (1\ =

Теорема 6. [10] Минимальное расстояние кода Гб равно его оценке, получаемой по степени многочлена Гоппы — + 1, то есть — Ь + 2.

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

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

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

В разделе 2.4 рассмотрены специальные классы двоичных се-парабельных кодов Гоппы с множеством локаторов позиций Ь с С^(2зг) [И].

. Г0 = Г(Ь0,Со) с в0 = х'2-1 + х4"1 + 1 и и = \ {а :

О0(а) = 0};

- Ц - Г(£5, <?0) с Со = х*2'1 + х4-1 + 1 и Ь% = Ь0 \ {0};

• Гх = Г^ьСх) с в! = х*2 + х1 + ж и Ьг = \ {а :

. Г2 = Г(12,С2) с С2 = х4* + х4 + х + 1 и Ь2 = СР(13) \ {а :

С2(«) = 0};

• Г3 = Г(Ь3, С3) с (?3 = я'* + х'2"1 + х4'"4 + 1 и Ьъ = С.Р(£3) \ {а : <?3(а) = 0};

- Г^ = С3) с С3 = х4' + ж42"1 + ж4'"4 + 1 и Ц = \ {0};

• Г4 = Т{Ь4, С4) с С4 = х*2+4+1 + х4'+4 + х4'+1 + х4+1 и и =

\ {а : С?4(а) = 0};

• Г5 = Г(15) С?б) с С5 = ж42"1 + ж42"4 + 1 и 1б = \ {« : <?5(а) = 0};

- Ц = Т(Ц, б?5) с С5 = х42-1 + х42-4 + 1и Ц = ЬВ\ {0} ;

• Г6 = Т(Ь6,в6) с Сб = х42+4+х42+1+х4+1 и и = : С6(а) = 0};

. г7 - г(¿7, <?7)с = + 1 и 17 = \

• Г8 = Г(18, вв) с в8 = х42+4+1 + х42 + х4 + х + А, А 6 и Ь8 = (З^3) \ {а : <38(а) = 0};

где í = 2г. Приведены улучшенные оценки на размерность этих классов кодов и показана их взаимосвязь в виде "цепи кодов" . Для класса кодов Г^^Са) с многочленом С] (х), представляю-

Рис. 2: Цепь вложенных и эквивалентных двоичных сепара-бельных кодов с L С GF(231)

щим собой функцию следа элемента ß £ GF(t3), получена улучшенная по сравнению с предложенной P.Veron в 1998 году оценка размерности кода :

ki > An/er + 3/ • (2 • 2' + 2Í_1 - 4) + / - 1 ,

где fei Ver = n —3£-22' + 3/ - оценка, предложенная P.Veron. Построены примеры конкретных кодов, принадлежащих этим классам. Показано, что некоторые из них лежат на границе Грайсмера, и доказано существование алгебро-геометрических кодов Гоппы рода 1 , лежащих на границе Грайсмера [5]. Используя предложенные классы кодов, удалось построить более пятидесяти конкретных кодов с параметрами, лучшими среди известных.

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

. Г® = Г(Ь1(С«) с Li = {GF(t2)\GF(t)} U {0} и G\(x) = х1"1 + 1 ;

. г1® = г(ьъа®)с11 = {ь1\{0}}

• Г? = Гс ¿2 = И в2(х) =Х* + Х-,

• Г? = Г^з.С^) с £3 = {С^(*2)\{а : С3(а) = 0}} и въ(х) =х* + х+ 1 ;

. = Т(Ь1, С?) с Ь% = С^2) \ {{а : С4(а) = 0} 1){0}} и С4(®) = яг* + ж4"1 + 1 ;

• Г^ = Т(Ь5, С^) с ¿5 - Ц и С5(х) = + х* + х ; . Г« = Г(Х6, С«) с = \ {а : 0&(а) = 0}} и

<36(яг) = + 1 ;

где 4 = д — простое число . Кумулятивно-сепарабельный код Г^ получается из исходного кода Г3- повышением кратности используемого многочлена Гоппы, то есть г) — (0-/(х))г.

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

Теорема 7. Минимальное расстояние кода Г® при 1 < г < д — 1 в точности равно г (4 + 1) + 1.

Получена улучшенная оценка размерности для класса кодов к > П - 21{{ч - 1)(г +1) - ,

Рис. 3; Цепь вложенных и эквивалентных кумулятивно-сепарабельных кодов с Ь С

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

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

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

Обобщенный (I, (3) код состоит из всех д-ичных векторов а = (ао, а\,..., ап_1), для которых выполняется сравнение:

i=о

где HOA(/¿(x),/j(a;)) = 1 для всех г ф j, sí = deg^¿(a;) < deg/i(x) = гч и Н0ДЫз).Л(®)) - 1, HOA(G(®)Jf(x)) = 1 для всех г = 0,...,п — 1,и коэффициенты многочленовgi(x), fi{x) лежат в поле GF(qm). G(x) - многочлен степени t с коэффициентами из GF{qm).

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

к >п — t ■ т,

и d - наибольшее целое число , для которого выполняется

d-2

"tu

í>Erb+s 1

для любых гз и ц ф г^-, ^ = 0,..., п — 1 .

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

1 1

п = 1д(о = у 2 »

¿=1,(111

1

2 ¿-е

е=2

^ ,1 (7^1)7 7'

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

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

Определение 8. Взвешенное расстояние Хэмминга (1гил(а,Ь) между векторами а = (0102...ап) и Ъ = (Ъ\Ь2..-Ьп) определяется следующим образом

п

(а, = Фг А) , i=l

где <1(щ, Ь{) = 1 если аг- ф и с1(а¿, Ь¿) = 0 если сц =

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

Теорема 9. Двоичные обобщенные (£,(?) коды, задаваемые неприводимым многочленом С?(ж) степени т с коэффициентами из и множеством нумераторов позиций

I иг (х) J г=1,...,п,;У=1,...,г

где и^\х)- неприводимый многочлен степени ] с коэффициентами из б77'(2"г) и С(х) ф и\Т\х) при всех г, лежат на границе Хэмминга, то есть, являются совершенными кодами во взвешенной метрике Хэмминга.

Т

где п — ^ nj - длина кода, к - размерность кода, - число ¿=1

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

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

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

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

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

Пусть исходный (п, к, (Г) циклический код А имеет множество корней порождающего многочлена Е = {а11,а12,.. . а'"-*},« € При этом часть из этих корней являются элементами последовательности М = аь+1,аь+2, а6+3,..., аь+{_1}. Будем считать, что в последовательности М имеется / нулей исходного кода: {&ь+1:'}з=1,/, где г3 принимает значения из множества {0,... — 1}.Обозначим Z = {¿1,12,- - ■ > V) подмножество индексов, определяющих такие нули кода.

Множество элементов с М определяет подмноже-

ство ненулей исходного кода. Обозначим соответствующее подмножество индексов как N = {л,• • • Ль-}}-

Определение 10. Локаторным кодом для исходного циклического (га, к, <1) кода с подмножеством нулей Z и не нулей N в последовательности М будем называть циклический код длины

с , НОД(с,п) = 1, среди пулей которого имеется множество элементов ... , ¡3- корень с-ой степени из 1.

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

Лемма 11. Пусть аь+н, аШ2,..., аь+Ь'; где 0 < ц < г2 < ... < ij < £ являются нулями исходного циклического (п,к,(1) кода А.

Обозначим Л набор из ] чисел {¿х, г'г, • • •, г./} и N71 - набор из Ь-з чисел {{1,2,...,Ц \Щ.

Если существуют циклический локаторный код (с, к, А) , корнями порождающего многочлена которого являются все

где (3 - корень степени с из единицы и (с,п) = 1, то циклический код А имеет минимальное расстояние не меньшее й, где <1 оценивается в соответствии с неравенством :

Ь > (<2 - 2) • Д + я, где в < Д - 1.

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

/Зп, где 1 < ¿1 < V < с и /3- корень степени с из единицы.

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

а6+г1+с!2 д <гх<г;<с,0<г2<5, где а- корень п-ой степени из 1 и (п,с) = 1,

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

с(5 + 1)-у>{й~ 2) (с - и + 1) + (с - и), 25

что эквивалентно

сб > (<*-2)(с-и + 1) •

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

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

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

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

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

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

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

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

Основные результаты работы

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

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

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

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

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

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

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

7. Предложены варианты использования (Ь, С) кодов для защиты информации .

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

(статьи 1-12 - опубликованы в изданиях, включенных в Перечень ВАК)

1. Беззатеев C.B., Алгоритм декодирования кода Голея (24,12,8) // Пробл. передачи информ. — 1986. — Т.22. — № 3. — С.109-112.

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

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

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

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

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

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

8. Беззатеев С.В., Коды Гоппы в протоколах анонимного запроса к данным, // Информационно-управляющие системы — 2010.— № 6 — С.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 — 1998

— V.14 — P.23-38.

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

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

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

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

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

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

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

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

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

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

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

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

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

28. Bezzateev S.V., Shekhunova N.A. , Multilevel Cryptosystem Based on Embedded Goppa Codes, // Proceedings 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 Inform,ation 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 Swedish-Russian 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 quasi-cyclic codes // Proceedings of ACCT-4, Sozopol, Bulgaria,—1996 - P.34-36

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 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.1803-1807.

40. Bezzateev 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 1&-22 - 2009 - P.ll-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 , (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. A.c. 1339901 СССР МКИ Н 03 М 13/02. Устройство для декодирования двоичного циклического кода. Веззатеев С.В., Мирончиков Е.Т., Шехунова H.A. — Опубл. 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 Kyung-hee, Krouk E., Linsky E.—lss. 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 Tae-chul, Lee Kyung-hee, Krouk E.—lss. 02.06.05 (Личное участие 25 % )

Формат бумаги 60 х 84 1/16. Бумага офсетная. Усл. печ. л. 2. Тираж 100 экз. Зак. № ЭД

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

Введение

1. Классические коды Гоппы

1.1 Определение.

1.2 Декодирование кодов Гоппы.

1.2.1 Алгоритм Берлекэмпа-Мэсси.

1.2.2 Расширенный алгоритм Евклида.

1.3 Модифицированный расширенный алгоритм Евклида и его свойства.

1.3.1 Числовые примеры для модифицированного расширенного алгоритма Евклида.

1.4 Декодирование кодов Гоппы за половину конструктивного расстояния.

1.4.1 Примеры использования модифицированного расширенного алгоритма Евклида.

1.4.2 Совершенные коды в классе классических кодов Гоппы и их декодирование.

1.5 Выводы по разделу.

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

2.1 Специальные классы q -ичных сепарабельных кодов Гоппы с множеством нумераторов Ь С

2.1.1 Свойства кодов Г], и

2.1.2 Соотношение кодов Г2 и Ц

2.1.3 Эквивалентность кодов Гз и Г2.

2.1.4 Свойства кода Г4.

2.1.5 Свойства кода Г5.

2.1.6 Свойства кода Гб.

Список таблиц

1.1 Наборы корней для декодирования циклических кодов на границе Шаохуа.

2.1 Параметры q- ичных сепарабельных кодов с L С GF(q21), образующих цепь.

2.2 Цепь троичных сепарабельных кодов с L С GF(З4)

2.3 Цепь троичных сепарабельных кодов с L С GF{З6)

2.4 Цепь пятиричных сепарабельных кодов с £ С GF(52).

2.5 Цепь пятиричных сепарабельных кодов с L С GF(54).

2.6 Цепь семиричных сепарабельных кодов с L С GF(72).

2.7 Параметры двоичных сепарабельных кодов, образующих цепь

2.8 Квазициклические коды Гоппы.

2.9 Нелинейные коды, построенные из кода (239, 123, 35) с применением конструкции (S,li,w)

2.10 Параметры кодов из рассматриваемого подкласса при I =

2.11 Размерность и минимальное расстояние T(L, xhGs(x)) -кодов для I = 3 , G(3h){x) = (я64 + ж63 + я56 + 1) • xh.

2.12 Размерность и минимальное расстояние T(L,xhGs(x)) -кодов для I = 4 , G{3h\x) = (х256 + х255 + ж240 + 1) • xh.

2.13 Весовой спектр некоторых кодов из представленного семейства Gf\x) = xh • О64 + я63 + ж56 + 1), L С GF{29).

2.14 Параметры кодов из рассматриваемого класса Г7 при I — 3,

2.15 Размерность и минимальное расстояние Г(£/7, G^) -кодов , п= 439, G(7h\x) = (яг + 1)Л(а;2в+23+1 + 1) и L7 = GF(29) \ GF{23)

2.16 Параметры кодов Г8.

2.17 Размерность и минимальное расстояние T(L,p(x)h • G$(x))-кодов, п — 455. "Здесь р(х) = х2 + х + 1 -неприводимый многочлен над GF{29)

3.1 Кумулятивно-сепарабельные коды.

3.2 Последовательность вложенных троичных кодов, полученных из кода гР(Ь6, О®), 43) = (х" - I)3.

3.3 Параметры кумулятивно-сепарабельных кодов Г^ = (.тг+1 -+1)«, £ = <}.

3.4 Параметры кумулятивно-сепарабельных кодов Г^ — {хь~1 +

1)«, 1 =

3.5 Размерности кумулятивно-сепарабельных кодов в зависимости от степени кумулятивности 1 < г < д — 1 для д = 3,/ = 2и£ =

3.6 Размерности кумулятивно-сепарабельных кодов в зависимости от степени кумулятивности 1 < г < q—l для q ~ 3,1 = 3 иt =

3.7 Размерности кумулятивно-сепарабельных кодов в зависимости от степени кумулятивности 1 — 1 для д = 5,1 = 2и1 —

3.8 Размерности кумулятивно-сепарабельных кодов в зависимости от степени кумулятивности 1 < г < д — 1 для д = 7, ¿ = 2и£ =

4.1 Параметры обобщенных недвоичных (£, (3) кодов с улучшенными оценками.

4.2 Семейство вложенных обобщенных недвоичных (Ь, С) кодов с улучшенными оценками.

4.3 Двоичный (4/1,5/2,5, 3) обобщенный (£,<?) код.

4.4 Двоичный (16/1,119/2,127,3) обобщенный (£, С) код.

4.5 Двоичный (16/1,120/2,120, 5) обобщенный (Ь, в) код.

4.6 Двоичный (8/1, 28/2,168/3,186,5) обобщенный (£, в) код

4.7 Все известные в настоящее время совершенные двоичные линейные коды во взвешенной метрике Хэмминга с длиной менее 1500, описываемые как обобщенные (Д (7) коды.

4.8 Таблица обобщенных (Д 6?)-кодов.

4.9 Таблица обобщенных (Д С)-кодов (Продолжение).

5.1 Распределение идентификаторов для схемы, представленной на рисунке 5.1.

5.2 Множество ключей необходимых для хранения для системы, представленной на рисунке 5.1.

5.3 Набор, ключей необходимых для хранения для рисунка 5.5 в схемах Akl-Taylor и Harn-Lin.

5.4 Набор, открытых и секретных ключей для рисунка 5.6.

5.5 Алгоритмы распределения ключей в многоуровневых и иерархических системах.

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

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

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

Коды Гоппы были описаны В.Д.Гоппой в 1970 году [30] и названы им (£, О) кодами. В дальнейшем эти коды получили также название классических кодов Гоппы. Ф.Дж.Мак-Вильямс и Н.Дж.А. Слоэн [41] называют их самым интересным объектом алгебраической теории кодирования. Р.Лидл и Г.Нидеррайтер [40] позиционируют эти коды как самое удачное обобщение знаменитых БЧХ - кодов. С момента опубликования первых работ В.Д. Гоппы [30,31] (Ь, (?) - коды привлекли к себе внимание как математиков, так и разработчиков систем и сетей передачи и обработки данных.

Конструкция, предложенная В.Д.Гоппой, оказалась плодотворной для дальнейших исследований: математики стали развивать ее по пути дальнейшей алгебраизации, и здесь были предложены алгебро-геометрические коды [28,33,34,146], а разработчики технических приложений направили свои усилия на обобщение результатов в рамках принятого аппарата, поиск конкретных классов классических кодов Гоппы [118,119], улучшение оценок их параметров [43,138,149-151] , а также построение эффективных алгоритмов декодирования [122,128,144].

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

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

1. Улучшение оценок параметров кодов, так как в общем случае оценка для размерности (L, G) кодов оказывалась хуже чем известные оценки,

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

3. Построение конкретных классов кодов с параметрами, соответствующими улучшенным оценкам,

4. Разработка алгоритмов реализующих декодирование (Д С) кодов с исправлением числа ошибок, превышающем половину конструктивного расстояния кода,

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

6. Развитие предложенной В.Д. Гоппой классификации (Ь, С?) кодов,

7. Построение обобщений кодов, предложенных В.Д.Гоппой ,

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5. Международных конференциях по алгебраической и комбинаторной теории кодирования (АССТ, 1988-2010);

6. Международных симпозиумах по теории информации (1Э1Т, 1995-2008);

7. Международном симпозиуме по конечным полям и их приложениям ^9, Дублин, 2009);

8. Международных Советско-Шведских симпозиумах по теории информации(1991-1995);

9. Международных симпозиумах по оптимальным кодам (Золотой берег, 2001; Варна, 2009), а также на семинарах:

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

2. кафедры информационных систем и кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения.

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

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

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

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

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

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

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

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

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

Во второй главе рассмотрены новые классы сепарабельных кодов Гоппы с множествами нумераторов позиций Ь С СР(с{21) и Ь С СР(д31). Показана взаимосвязь полученных классов и построены улучшенные оценки для минимального расстояния и размерности новых классов кодов. Построены примеры конкретных кодов, принадлежащих этим классам и являющихся лучшими известными на настоящий момент. Показано, что предложенные сепарабель-ные коды являются квазициклическими. Приведены параметры конкретных квазициклических кодов, имеющих лучшие на настоящий момент параметры.

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

В четвертой главе рассматриваются обобщенные (Ь, (7) коды, дается их определение и оценки для минимального расстояния и избыточности. Приводится новый подкласс обобщенных (£, С?) кодов с улучшенной оценкой на размерность кода. Определяются коды во взвешенной метрике Хэмминга и предлагается новый класс совершенных кодов в этой метрике. Рассматриваются обобщенные (£, (2) коды суффиксной конструкции и доказывается возможность описания известных ранее (2,1) и (£ + 1.1) кодов с неравной защитой символов как обобщенных (X, С) кодов при специальном задании множества нумераторов позиций. Приводятся алгоритмы декодирования для таких кодов. Рассматриваются обобщенные циклические (Д С) коды. Вводится понятие "локаторного" кода, использование которого позволяет построить множество нумераторов для известных циклических кодов лежащих на границе Хартмана-Тзенга и тем самым описать их как циклические (Ь, О) коды. Тем самым доказывается, что известное ранее ограничение класса циклических кодов Гоппы лишь классом примитивных БЧХ кодов может быть существенно откорректировано и многие циклические коды, минимальное расстояние которых превышает оценку БЧХ могут быть описаны как (Ь, (?) коды Приводится алгоритм декодирования обобщенных (£-, С) кодов.

В пятой главе рассмотрены практические применения (Ь, О) кодов в системах защиты информации. Предложена система многоуровневого и иерархического разграничения доступа, использующая классы вложенных кодов Гоппы. Рассмотрен вариант выбора ключей для пользователей, находящихся на разных уровнях системы разграничения доступа и определены свойства такой системы. Предложена система разделения секрета, использующая обобщенные (X, С?) коды с множеством нумераторов позиций, содержащим рациональные функции со знаменателями различных степеней. Использование таких классов кодов позволило предложить весовую схему разделения секрета. Рассмотрен протокол анонимности запросов и продемонстрирована возможность использования в нем (Ь, С) кодов. Рассмотрена модифицированная схема Рао-Нам для маскирования видеоизображения.

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

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

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

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

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

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

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

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

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

7. Предложены варианты использования (Ь, (2) кодов для защиты информации.

Заключение

В данной диссертационной работе рассмотрены кодовые конструкции на основе классических кодов Гоппы. Предложены новые классы (Ь, С?) кодов, имеющие улучшенные значения минимального расстояния и размерности. Проанализирована взаимосвязь различных классов сепарабельных кодов Гоппы и доказано что предложенные новые классы кодов образуют "цепь" вложенных и эквивалентных кодов. Для некоторых из введенных классов кодов удалось найти точное значение для минимального расстояния и размерности кода. Среди кодов из предложенных новых классов найдены лучшие известные на настоящий момент линейные коды. Показано, что многие из предложенных новых классов являются квазициклическими кодами. Наличие у предложенных классов такого свойства позволяет упростить алгоритмы кодирования/декодирования.

Предложен алгоритм декодирования позволяющий более эффективно использовать реальную корректирующую способность (Ьу С?) кодов, декодируя их за половину конструктивного расстояния. Рассмотрены обобщенные(Ь, С?) коды и показано что используя введенное в диссертационной работе понятие "локаторного" кода можно описать все известные в настоящее время циклические коды, лежащие на границе Хартмана-Тзенга как циклические обобщенные (Ь, С) коды, множество нумераторов позиций которых определяется найденным "локаторным кодом".

Использование обобщенных (I/, (2) с множествами нумераторов Ь, состоящим из рациональных функций, знаменатели которых имеют различные степени позволило построить совершенные двоичные линейные коды во взвешенной метрике Хэмминга. Построены таблицы всех известных в настоящее время совершенных двоичных линейных кодов во взвешенной метрике Хэмминга с длиной менее 1500. Показано, что такие коды могут быть использованы для повышения помехозащищенности в каналах с неравномерным распределением ошибок, а также для исправления ошибок заданной конфигурации, например в логических схемах. Использование обобщенных^, С) кодов суф-фиксной конструкции позволило описать коды с неравной защитой символов как (Ь, 6?) коды и предложить для них соответствующий алгоритм декодирования.

Кроме очевидного использования предложенных классов (Ь, 6?) кодов в системах передачи информации для повышения помехозащищенности, рассмотрены варианты использования таких кодов в системах информационной безопасности. Предложена схема использования классов вложенных (Ь, С) кодов в системах многоуровневого и иерархического разграничения доступа. Для обобщенных (Ь, О) кодов рассмотрена схема взвешенного распределения секрета для коалиции пользователей. Показана возможность использования специальным образом выбранных кодов Гоппы для реализации протоколов анонимных запросов к записям в базах данных.

1. Tables of nonlinear binary block codes by Litsyn,Rains, and Sloane, http://www.research.att.com/ njas/codes/And/

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

3. Беззатеев C.B. ,Мирончиков Е.Т., Шехупова, H.A., Оценка Хартмана -конструктивна,// Тезисы докладов VIII Симнозгьума по проблемам избыточности в информационных системах, Ленинград,—1983.— С.80-82.

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

5. Беззатеев C.B., Мирончиков Е.Т., Шехунова H.A., Использование (L, G) кодов в информационных системах коллективного пользования /¡Тезисы докладов XV военной научно-технической конференции, Киев. -1984. 4.2. - С.307

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

7. Беззатеев C.B., Алгоритм декодирования кода Голея (24,12,8) // Про-бл. передачи ииформ. 1986. - Т.22. — № 3. — С.109-112.

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

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

10. Беззатеев C.B. , Шехунова H.A., Декодирование циклических кодов выше конструктивного расстояния , //Помехоустойчивость и эффективность систем передачи информации, Тезисы докладов, Одесса.— 1986—с.55-56.

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

12. Беззатеев C.B., Шехунова H.A., О конструктивном расстоянии лучшего известного (55,16,19) кода Гоппы // Пробл. передачи информ. —1987. Т.23. — №- 4. - С.352.

13. Беззатеев C.B. , Шехунова H.A., Семейство вложенных кодов Гоппы, // Тезисы докладов IX Всесоюзной конференции по теории кодирования и передачи информации ,Одесса , — 1988,— ч.1 — С.82-84 .

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

15. Беззатеев C.B. , Шехунова H.A., О параметрах одного подкласса неприводимых кодов Гоппы, Тезисы докладов X Симпозиума по проблемам избыточности в информационных системах, Ленинград,— 1989 -4.1 С. 11-13 .

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

17. Беззатеев C.B. , Шехунова Н.А.,Кодовые методы защиты информации, IIтезисы докладов VI общероссийской научно-технической конференции "Методы и технические средства обеспечения безопасности информации" , Санкт-Петербург,— 1997.

18. Беззатеев C.B., Литвинов М.Ю., Трояновский Б.К., Использование помехоустойчивых кодов для шифрации видеоинформации // Информационно-управляющие системы — 2004. — № 5(30). — С. 2326.

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

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

21. Беззатеев C.B., Шехунова H.A., Специальные классы кодов Гоппы с улучшенными оценками параметров // Пробл. передачи инф. — 2010.— Т.46. т. - С. 29-50.

22. Беззатеев C.B., Коды Гоппы в протоколах анонимного запроса к данным, Информационно-управляющие системы, — 2010. — № 6. — С.86-87.

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

24. Бояринов И.М., Об одной конструкции линейных кодов с неравной защитой информационных символов // Проблемы передачи информации- Т. 16 m — С.103-107.

25. Бояринов И. М., Комбинированные методы декодирования линейных кодов с неравной защитой информационных символов // Пробл. передачи инф. 1983. - Т. 19. - №.1 - Р.17-35.

26. Влэдуц Г., Кацман Г.Л., Цфасман М.А. , Модулярные кривые и коды с полиномиальной сложностью построения. // Проблемы передает информации—1984.— Т.20 —№1 —С.47-55.29.