автореферат диссертации по радиотехнике и связи, 05.12.04, диссертация на тему:Модификации алгоритма Мак-Элис для повышения показателей качества радиосистем передачи информации

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

Фам Суан Нгиа ~«^„с* ^ х 2

МОДИФИКАЦИДХЛГОРИТМА МАК-ЭЛИС ДЛЯ ПОВЫШЕНИЯ ПОКАЗАТЕЛЕЙ КАЧЕСТВА РАДИОСИСТЕМ ПЕРЕДАЧИ ИНФОРМАЦИИ

Специальность: 05.12.04 -«Радиотехника, в том числе системы и устройства телевидения»

АВТОРЕФЕРАТ

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

Рязань 2007

003062712

Работа выполнена в ГОУВПО «Рязанский государственный радиотехнический

университет»

Научный руководитель - Заслуженный работник высшей школы РФ,

доктор технических наук, профессор Кириллов Сергей Николаевич

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

Паршин Юрий Николаевич

- Кандидат технических наук, доцент Бурнашев Рустам Умндович

Ведущая организация - ФГУП ОКБ «Спектр» (г.Рязань)

Защита состоится 23 мая 2007 г. в 12 часов на заседании диссертационного совета Д 212211.04 в Рязанском государственном радиотехническом университете по адресу 390005, г. Рязань, ул Гагарина, д. 59/1.

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

Автореферат разослан «¡Т » апрели 2007г

Ученый секретарь диссертационного совета кандидат технических наук "7??// д Г Борисов

ОБЩАЯ ХАРАКТЕРИСТИКА ДИССЕРТАЦИОННОЙ РАБОТЫ

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

Кроме того, эти системы должны выполнять поставленные задачи в условиях действия различного вида помех

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

Значительный вклад в области повышения помехоустойчивости передаваемой информации внесли такие учёные как Котельников В А , Злотник Б. M , Кларк Д. Ж., Кейн Д Ж, Питерсон У , Уэлдон Э , Месси Б Дж, Кассами Т., Токура H, Морелос-Сарагоса Р, Золотарёв В. В., Самсонов Б , Плохое Е M, и др.

Другим важным требованием к системам передачи информации является обеспечение скрытности, которая характеризуется способностью системы противостоять мерам, направленным на раскрытие содержания информации. Обеспечение скрытности передаваемой информации включает комплекс мер затрудняющих: обнаружение сигнала, определение структуры обнаруженного сигнала (на основе определения ряда его параметров) и раскрытие смысла содержащегося в передаваемой информации. Одним из методов, часто использующимся для повышения скрытности информации, является применение кодирования Повышением скрытности передаваемой информации занимались Шеннон К., Тузов Г И, Сивов В А., Брюс Щнайер, Саломаа А , Алферов А П., Зубов А Ю, Нечаев В И, Молдовян H А, Молдовян А А, Венбо Мао и др.

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

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

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

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

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

Поставленная в работе цель включает решение следующих задач

- анализ устойчивости алгоритма Мак-Элис в случае действия комплекса помех, при использовании различных линейных кодов (например, коды Хэмминга, Боуза - Чоудхури - Хоквингема, Рида-Соломона, Гоппы, самоортогональных кодов (СОК), произведение кодов, турбо кодов),

- модификации алгоритма Мак-Элис в интересах повышения скрытности, скорости и помехоустойчивости передачи информации,

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

- исследования применения модификаций алгоритма Мак-Элис для электронной цифровой подписи (ЭЦП) в радиосистемах передачи информации,

- анализ реализации модификаций алгоритма Мак-Элис при использовании программированных логических интегральных систем (ПЛИС) в высокоскоростных системах передачи информации

Методы проведения исследований В работе использовались методы статистической радиотехники, математической статистки, численные методы вычислительной математики Данные теоретические методы сочетались с экспериментальными исследованиями на основе имитационного моделирования

Научная новизна В рамках данной работы были получены следующие новые научные результаты

1 Оценена устойчивость алгоритма Мак-Элис при действии комплекса широкополосной, узкополосной, структурной и импульсной помех в

случае использования кодов Хэмминга, Боуза - Чоудхури -Хоквингема, Рида-Соломона, Гоппы, произведение кодов, СОК, турбо кодов с различными кодовыми скоростями и определена самая опасная помеха

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

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

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

5 Показана возможность применения алгоритма Мак-Элис для ЭЦП, а также в радиосистемах передачи информации

Практическая ценность.

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

Основные положения, выносимые на защиту:

1 Модифицированный алгоритм Мак-Элис, основанный на добавлении информации в вектор ошибки и изменении исходной информации путем использования матрицы хеширования, обеспечивающей информационную скрытность до 1,37.1016 при использовании кода Гоппы (1024, 524)

2.Модифицированный алгоритм Мак-Элис основанный на добавлении информации в вектор ошибок, позволяющий повысить кодовую скорость на -60%

3 Модифицированный алгоритм Мак-Элис основанный на использовании параллельных кодов, позволяющий повысить информационную скрытность в 1014 раз (при длине кодового слова и=7) по сравнению с исходным алгоритмом

4 Модифицированный алгоритм Мак-Элис, основанный на применении произведения кодов, обеспечивающий информационную скрытность более 1,37.1016 и число исправляемых ошибок до 91 бит при использовании произведения кода Х(15,11)БЧХ(1024,728)

5.Модифицированный алгоритм Мак-Элис с преобразованием исходной информации путем сжатия и использования вектора ошибок, позволяющий получить информационную скрытность АГ=1,3 7 1016 в случае использования кода Гоппы (1024,524), а также повысить кодовую скорость до 0,95

Апробация работы Результаты работы докладывались на следующих научно-технических конференциях

1 52-я Студенческая Научно-Техническая Конференция 2005, Рязань

2 Всероссийская научно-практическая конференция студентов, молодых учёных и специалистов "Новые информационные технологии в научных исследования и в образовании" 2005, Рязань

3 Всероссийская научно-практическая конференция "Сети и системы связи", 2005 Рязань

4 Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникации» 2005, Рязань

5 Международная молодежная научная конференция, посвященная 1000 летию города Казани "Туполевские чтения" 2005, Казань

6 Всероссийская научно-практическая конференция студентов, молодых учёных и специалистов "Новые информационные технологии в научных исследования и в образовании" 2006, Рязань.

7 Всероссийская научно-практическая конференция "Сети и системы связи", 2006. Рязань

8 Всероссийская научно-практическая конференция студентов, молодых учёных и специалистов "Новые информационные технологии в научных исследования и в образовании" 2007, Рязань.

9 Всероссийская научно-практическая конференция "Сети и системы связи", 2007 Рязань

Публикации. По теме диссертации опубликовано 13 работ Из них 3 статьи в журналах, рекомендованных ВАК РФ для кандидатских диссертаций, 1 статья в межвузовских сборниках, 9 тезисов докладов

Структура и объём работы Диссертационная работа состоит из введения, трех глав, заключение, списка литературы из 119 наименований и 3 Приложений Диссертация содержит 168 стр, в том числе 132 стр основного текста, 12 таблиц и 92 рисунка

СОДЕРЖАНИЕ ДИССЕРТАЦИОННОЙ РАБОТЫ

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

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

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

Параметрами алгоритма Мак - Элис являются целые числа к, nut, где к -длина информационного сообщения, п - длина кодового слова, t -

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

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

- случайно выбрать двоичную невырожденную матрицу S^v,

- случайно выбрать подстановочную матрицу Рпт,

- вычислить произведение матриц Gp=SGP

Открытым ключом является пара (Gp t), закрытым - тройка (S,G,P). Алгоритм Мак - Эллис показан на рисунке 1, где блок формирования к, п, t, е, S, P,G -формирует все необходимые параметры алгоритма, блоки Si1, Fx, С1 -вычисляет обратные матрицы, необходимые для декодирования, блок ИИ -источник информации, представляет собой генератор случайных чисел Данный блок генерирует псевдослучайную последовательность импульсов с амплитудой [0,1] заданной длины к, блок Кодер осуществляет кодирование по алгоритму Мак - Элис, блок М - манипулирует по фазе кодовую последовательность, блок Канал представляет собой модель канала связи с аддитивным белым гауссовым шумом (АБГШ), блок комплекса помех КП в зависимости от выбранных типов исследуемых помех формирует модели этих помех, блок Декодер -осуществляет декодирование по алгоритму Мак - Эллис, блок >< -подсчитывает BER среднюю вероятность ошибки на бит - вероятность превышения числом ошибочно принятых символов заданного значения

Рисунок 1

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

- представить Мв виде двоичного вектора и длины к,

- выбрать случайный бинарный вектор ошибок е длины п, содержащий не более г ошибок,

- вычислить бинарный вектор у = иСр + е и передать его абоненту В Здесь, расчеты выполнены по модулю 2.

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

Корректность приведенного алгоритма подтверждает следующее выражение

у1=уР-'=СиОр+е)Р',=

(иБОР + е)Рл = + еР~], где еГ1 - вектор, содержащий не более г единиц Поэтому алгоритм декодирования кода с порождающей матрицей б декодируету в вектор

1!\ = т

Полученные в первой главе результаты показали, что наиболее высокая помехоустойчивость наблюдается при использовании турбо кодов в алгоритме кодирования информации Мак-Элис Например, при действии широкополосной помехи, для достижения средней вероятности ошибки Ре=МУ*, в случае использование турбо кода, имеющего скорость кодирования г=1/2 необходимо отношение сигнал - шум ^„,=2,8 дБ, а при применении произведения кода с внешним кодом Х(15,11) и внутренним БЧХ(127, 92) со скоростью кодирования г = 0,53 - <?ш= 5,6 дБ В случае использования самоортогонального кода СОК (162, 81) (г = 0,5) с многопороговым декодером - <7Ш=6,7 дБ, а при применении кода БЧХ и Хэмминга со скоростью 1/2 отношение сигнал-шум цш больше, чем 6 дБ

СОК при использовании порогового или многопорогового декодирования (МПД) обладает выигрышем во времени кодирования и декодирования по сравнению с других представленными кодами, в частности на два - три порядка по сравнению с турбо кодами, которые требуют самое большое время декодирования

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

При действии широкополосной помехи устойчивость произведения кодов ПК Х(31,26)БЧХ(63,51) ухудшается на 0,7 дБ по сравнению с кодом СОК (567, 378) с МПД, имеющим кодовую скорость гМ),67, при вероятности ошибки на бит Ре~\(У6 В случае сравнения с СОК(162, 81) (г =0,5) при действии узкополосной, структурной, так и импульсной помехи преимущество в помехоустойчивости достигает 13 раз

Наиболее опасной является импульсная помеха для всех кодов, использованных в качестве линейных или комбинированных кодов алгоритма Мак-Эллис Например, при действии узкополосной, структурной и импульсной помех с отношением сигнал-помеха цу=цс~ци=15 дБ и при наличии широкополосного шума из канала с ^щ=2,5 дБ, в случае использования турбо кода, получаются вероятности ошибки Реу= 7 10"4, Рес= 10'3 и Реи= 3,2*10"3 соответственно

Во второй главе показаны предложенные в работе варианты повышения эффективности алгоритма Мак-Элис

На рисунке 2 приведена блок-схема кодирования алгоритма на основе изменения длины исходной последовательности при использовании матрицы И(„хк), имеющей размер п"к, в вектор ошибок е В этом алгоритме, входная информация т состоит из исходной информации т{ и модифицированной

информации вектора ошибки т2 = еИ.

Кодовое слово с вычисляется по формуле

с = тОр+е (3)

Рисунок 2

Тогда информационная скрытность К вычисляется по формуле

К = Скп!С1< (4)

Использование данного алгоритма позволит противостоять атакам, основанным на определении позиций единиц в векторе ошибок е, что значительно повышает информационную скрытность Например, при применении кода Гоппы (1024, 524) в качестве линейного кода с использованием этого алгоритма, информационная скрытность достигает -1,37 1016 Кроме того, данный алгоритм позволит расширить пространство закрытых ключей на 2п*к раз по сравнению с исходной схемой Например, применение кода БЧХ (15, 7) в качестве линейного кода в матрице й(15,7) изменяет вектор е(1х15) в последовательность длиной к=7, что повышает пространство закрытых ключей на 2105 раз

Однако, исследование вышепредложенного алгоритма показало, что его помехоустойчивость и скорость передачи информации аналогичны исходному алгоритму Мак-Элис

На рисунке 3 показана модификация алгоритма Мак-Элис на основе повышения кодовой скорости

Рисунок 3

Работа данного алгоритма изложена ниже Предположим, что входная информация т состоящая из ™|(1>к) и т2( 1х,), а также квадратная матрица используется изменения позиций бит информационной последовательности т2 Тогда кодовое слово можно записать в виде

двух частей в интересах

е = с + т]Ор, (5)

где е = %(т2Б2). Причем длина л информационной части т2 должна удовлетворять формуле (4)

Функция g выполняет преобразование т3 в вектор ошибок е, который имеет длину п и вес г

При декодировании кодового слова с, блок информации т\ получен использованием известного декодирования, а блок информации вычисляет по формуле

где е~с + т{}р, - обратная матрица#обратная функцияg

Добавление информации в вектор ошибки е позволяет не только повысить скорость, но и увеличить скрытность передаваемой информации по сравнению с исходной схемой Например, при использовании кода Гоппы (1024, 524) (добавленное число бит л = 264), скорость возрастает с 0,5 до 0,79, а при использовании кода Гоппы (1024, 654) (л = 225) в качестве линейного кода скорость возрастает с 0,63 до 0,87 Заметим, что в случае когда злоумышленник декодировал кодовое слово с (из канала), он не сможет получить полную информацию, потому что, информационная часть (-60% передаваемой информации) присутствует в векторе е При использовании матрицы 52 повышается информационную скрытность части т2 (нал1 раз), так

же увеличится пространство закрытых ключей (на Кч(т2)= 0 29* 2,2 ) Например, при использовании кода БЧХ (1023,513) в качестве линейного кода алгоритма

Мак-Элис, следует, что л = 313 и Кч(тг)= 0.29х 23'3 Анализ данного алгоритма показал, что его помехоустойчивость аналогична исходной схеме, кроме того при этом наблюдается низкая информационная скрытность под действием атаки, основанной на определении позиций единиц в векторе ошибок

На рисунке 4 показан алгоритм, основанный на совмещении требований повышения кодовой скорости и скрытности передачи информации Здесь двоичная матрица И имеет размер п*к Тогда кодовое слово можно записать как

с = (|я,+Л(е1)Х?|,+е, (7)

где вектор е\ рассчитывается по формуле

а вектор ошибки е по формуле

е = (9)

где Р2- подстановочная матрица с размером «хи, 52- двоичная невырожденная матрица, имеющая лхл, функция g выполняет преобразование двоичной

последовательности т^т^ с длиной л и любым весом в вектор ошибок е, который имеет длину п и вес г

Атгорктм Мак Элис

Рисунок 4

Анализ блок-схемы на рисунке 4 показал, что при использовании данного алгоритма затруднено обнаружение информации, передаваемой в векторе е Поэтому можно защитить передаваемую информацию от атак, основанных на повторной передаче информации, при использовании кода Гоппы (1024, 524), при этом информационная скрытность достигает £~1,37.10!б Кроме того, скорость передаваемой информации, благодаря добавлению информации в вектор ошибок, значительно повышается (с 0,5 до 0,79 при использовании кода Гоппы (1024, 524)) В случае применения кода БЧХ (1023, 523) скорость передачи г увеличивается с 0,51 до 0,84 (добавленное количество бит л=305), а при использовании кода БЧХ (1023, 618), г увеличивается с 0,6 до 0,85 (л=257). Применение двоичной невырожденной матрицы 52 и подстановочной матрицы Р2, позволит дополнительно повысить пространство закрытого ключа на Дкш=0 29x2^«' Например, при использовании кода БЧХ (1023, 513), когда л =

313, и=1023, следует АКц1 = 0,29.23"21023'.

На рисунке 5 приведена блок-схема алгоритма Мак-Элис, использующего параллельные коды Предлагается блок-схема алгоритма, содержащая две ветви, структура каждой аналогична исходному алгоритму с закрытыми -(ЯьСьЛ), (52, в2, Р2) и открытыми ключами (/,, вр1 = ^О^Л), ('ъ 6р2= Информация на выходе источника состоит из двух частей Входная информация

для каждой ветви представляется строками матриц и т2(Пхк2)

Кодирование в каждой ветви выполняет по строкам матриц т\ и т2 Блоки Мх и М2 объединяют кодовые слова, поступающие из соответствующей ветви, в последовательность длиной п{п2, в чем и состоит особенность данного алгоритма

Gpj -S-СЬР

Рисунок 5

Выходная последовательность кодера имеет длину 2п\пг Декодирование основано на разделении кодовой последовательности на две подпоследовательности длиной щпг, декодирование которых осуществляется на основе исходного алгоритма

Из анализа блок-схемы алгоритма (рисунок 5) следует, что объединение двух кодовых последовательностей значительно повышает скрытность передаваемой информации При таком объединении информационная скрытность повышается на min( 2"'"2, С"'"^) по сравнению с исходной схемой

Например, при использовании в данном алгоритме двух кодов с длиной кодового слова п = 1, выигрыш составит порядка ~5Х1014 Из анализа данного алгоритма следует, что хотя кодовое слово, имеет не большую длину или не большой размер открытого и закрытого ключа, но при этом обеспечивается высокая скрытность

На рисунке 6 предложен вариант реализации алгоритма Мак-Элис на основе произведения кодов

Принцип работы данного алгоритма аналогичен исходному алгоритму Однако, различием между этими алгоритмами является замена простого линейного кода на произведение кодов Принцип работы и структурная схема алгоритма Мак-Элис при использовании произведения кодов аналогичны исходному алгоритму (рисунок 1)

На рисунке 6, вектор ошибок также содержит часть входной информации При кодировании необходимо использовать функцию g и матрицу h Аналогично первому алгоритму, представленному на рисунке 2, матрица h позволяется изменять вектор ошибок с длиной п и весом t в последовательность /и4 с длиной к и любым весом В данном алгоритме характеристики функции g, аналогичны алгоритму, представленному на рисунке 3 Функция g осуществляет преобразование информационной части т2 с длиной л и любым весом в вектор ошибок

Кодирование и декодирование, при использовании данного способа повышения эффективности системы кодирования, осуществляется аналогично исходному алгоритму Мак-Элис

Рисунок 6

При этом открытый ключ вычисляется по следующим формулам

Ор=80*Р, (10)

Г=(£/,</2-1)/2, (11)

где О* = 6Т, Рх С2; С{ - порождающая матрица внешнего кода, С2 - порождающая матрица внутреннего кода, Р\ - матрица перемежителя, с1{ - минимальное кодовое расстояние внешнего кода; 4 - минимальное кодовое расстояние внутреннего кода. Закрытым ключом является сочетание пяти матриц (З^г^РьСУ)

информационная скрытность АГ данной модификации алгоритма Мак-Элис определяется по формуле (4)

Выражение (11) показывает, что исправляющая способность алгоритма представленного на рисунке 6 значительно повышается по сравнению с алгоритмом на основе простых линейных кодов Использование произведения кодов в алгоритме Мак-Элис обеспечивает выигрыш в информационной скрытности, а так же помехоустойчивости системы передачи информации Кроме того, при добавлении информации в вектор ошибок можно повысить кодовую скорость на 60% по сравнению с исходной схемой

Результаты сравнения информационной скрытности и количества исправляемых ошибок в случае использования кода Гоппы (1024, 524), кода БЧХ (1023, 523) и произведения кода с внешним кодом Хэмминга (15, 11) и внутренним БЧХ (1023, 728) в качестве линейного в алгоритме Мак-Элис представлены в таблице 1

Другой вариант, позволяющий повысить эффективность алгоритма Мак-Элис, реализуется на основе применения метода сжатия информации Блок-

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

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

Таблица 1-Результаты сравнения кода Гоппы (1024, 524), кода БЧХ (1023, 523) и ПК Х(15,П)БЧХ(1023, 728) ___

Параметр Гоппа (1024, 512) БЧХ (1023,523) ПК Х(15,11)БЧХ(1023, 728)

Кодовая скорость 0,5 0,51 0,52

Информационная скрытность 1,37хЮ'6 6,27*1017 >6,27* 10'7

Количество исправляемых ошибок 50 57 91

Например, для кода БЧХ(31,21) требуется к=21, со средним коэффициентом уменьшения длины последовательности на 20%, п2=26 следует ЛМО7

Кодирование

Рисунок 7

Эффективность алгоритма Мак-Элис повысится, если совместить данный алгоритм с алгоритмом на основе добавления информации в вектор ошибок (рисунок 3), в этом случае кодовая скорость вычислят по формуле

г = (п2 +л)/п, (12)

где п2 - длина исходной последовательности (т^, л - длина добавленной информации (/и2), п - длина кодового слова В этом случае кодовая скорость может быть близка к 0,95 Например, при использовании кода БЧХ (31,21,2), как выше определено п2=26 ил=3 (по формуле (12)), следует г=(26+3)/31-0,93

В третьей главе рассмотрены вопросы использования модифицированных алгоритмов Мак-Элис для электронной цифровой подписи (ЭЦП), а также вопросы практической реализации алгоритма Мак-Элис на ПЛИС в высокоскоростных системах передачи информации

Блок-схема радиосистемы передачи информации, применяющая алгоритм Мак-Элис, представлена на рисунке 8 показано, что благодаря замене алгоритмов шифрования и канального кодирования на алгоритм Мак-Элис в 9 раз сократится время обработки сигнала в устройстве Однако, при применении этого алгоритма для передачи закрытых ключей определенное количество исправляемых ошибок линейного кода используется для создания открытого ключа, поэтому помехоустойчивость системы передачи информации уменьшается

Рисунок 8

Полученные результаты третьей главе показали, что--в случае использования исходного алгоритма Мак-Элис не требуется передача секретного алгоритма (или ключа), при этом данный алгоритм обладает преимуществом по скрытности информации (-1050) Кроме того, использование модифицированного алгоритма Мак-Элис позволяет повысить в два раза информационную скрытность системы ЭЦП по сравнению с применением исходной схемы

-достижение заданной помехоустойчивости и скрытности передачи информации в алгоритме Мак-Элис увеличивает сложность устройства и приводит к потерям в отношении сигнал-шум Эти потери значительно зависят от используемого кода в системе Например, для достижения средней вероятности на бит Ре — 10"5, при использовании кода СОК(567, 378) с МПД в качестве линейного кода потери в отношении сигнал-шум (Aqm) равны ЗдБ, что повышает информационную скрытность (К) на -2x104 а при применении произведения кода ПК БЧХ(63, 51)Х(31,26) - Aqm=l дБ и К=2*104 -показано, что количество вычисленных операций в известной схеме системы передачи информации, применяющей RSA и канального кодирования Гоппы (1024,524), в 9 раз выше, чем при использовании алгоритма Мак-Элис Возможна реализация алгоритма Мак-Элис на ПЛИС XC4VSX55 (семейства Virtex-4), при скорости передачи информации в кодере 250 Мбит/с

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

1 Показано, что наиболее высокая помехоустойчивость наблюдается при использовании турбо кодов в алгоритме кодирования информации Мак-Элис Например, при действии широкополосной помехи, для достижения средней вероятности ошибки Ре= 10"4, в случае использование турбо кода, имеющего скорость кодирования г=1/2 необходимо <?w=2,8 дБ, а при применении произведения кода с внешним кодом Х(15,11) и внутренним БЧХ(127, 92) со кодовой скоростью г = 0,53 - qut= 5,6 дБ В случае использования кода СОК (162, 81) (г = 0,5) с многопороговым декодером - дш=6,7 дБ, а при применении

кода БЧХ и Хэмминга со скоростью г~1/2 отношение сигнал-шум qui больше, чем 6 дБ

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

3. Показано, что наиболее опасной является импульсная помеха для всех кодов, использованных в качестве линейных или комбинированных в алгоритма Мак-Эллис Например, при действии узкополосной, структурной и импульсной помех с отношением сигнал-помеха qy=qc~qи =15 дБ и при наличии широкополосного шума из канала с qM=2,5 дБ, в случае использования турбо кода, получаются вероятности ошибки Реу= 7 10"4, Рес= 10"3 и Реи= 3,2><10"3 соответственно

4 Показано, что изменение исходной последовательности с использованием функции хеширования в одну сторону, позволяет повысить информационную скрытность до ~1,37 1016 при применении кода Гоппы (1024, 524) в качестве линейного кода в алгоритме Мак-Элис Предложено для повышения информационной скрытности использовать матрицу (И) с размером (п*к) вместо функции хеширования h(e), что расширило пространство закрытых ключей на 2105 раз по сравнению с исходной схемой при к-1, «=15

5 Предложена модификация алгоритма Мак-Элис при добавлении информации в вектор ошибок, позволяющая повысить кодовую скорость на -60% при этом наблюдается низкая информационная скрытность действием атаки, основанной на определении позиции единиц в векторе ошибок

6 Предложена модификация алгоритма Мак-Элис с преобразованием исходной информации путем сжатия и использования вектора ошибок, позволяющая получить выигрыш в скрытности A~l,37 1016 в случае использования кода Гоппы (1024,524), а также повысить кодовую скорость до 0,95

7.Показана возможность применения алгоритма Мак-Элис для ЭЦП при этом не требуется передача секретного алгоритма (или ключа), а скрытность информации повышается в -10 0 и в два раза возрастает информационную скрытность системы ЭЦП по сравнению с применением исходной схемы

8 Доказано, что реализация алгоритма Мак-Элис требует в 9 рад меньше вычисленных операций, чем алгоритма RSA и помехоустойчивого кода Гоппы (1024, 524) в системе передачи информации при тех же параметрах

9 Показана возможность реализации алгоритма Мак-Элис на ПЛИС XC4VSX55 (семейства Virtex-4), при скорости передачи информации 250 Мбит/с

Список публикаций 1 Крысяев Д Е, Фам С H Анализ помехоустойчивости алгоритма кодирования информации Мак-Элис // ВНТК «Новые информационные технологии в научных исследования и в образовании» Тезисы докладов 2005 С 41

2 Крысяев Д Е , Фам С.Н Исследование влияния комплекса помех на алгоритм кодирования информации Мак-Элис // Всероссийский научно-практический семинар. Сети и системы связи Тезисы докладов 2005 С 281.

3. Крысяев Д Е , Фам С.Н Исследование влияния комплекса помех на алгоритм кодирования информации Мс-ЕНесе // СНТК-52 Рязанская государственная радиотехническая академия. Тезисы докладов 2005. С 4.

4. Крысяев Д Е, Фам С Н Исследование помехоустойчивости системы кодирования Мак-Элис // Вестник РГРТА 2005 №15. С 112-116

5 Крысяев ДЕ., Фам СН Исследование помехоустойчивости алгоритма кодирования информации Мак-Элис при воздействии комплекса помех // «Туполевские чтения» Тезисы докладов 2005 С. 84-85

6. Крысяев Д Е., Фам С.Н. Исследование помехоустойчивости системы передачи информации на основе алгоритма Мак-Элис при использовании кода Рида-Соломона // «Биомедицинские технологии и радиотехника». Рязань 2005 С 140145.

7 Кириллов С Н., Крысяев Д.Е, Фам С Н. Исследование помехоустойчивости алгоритма Мак-Элис на основе кода Гоппы и порогового декодирования блокового самоортогонального кода // 14-ая МНТК «Проблемы передачи и обработки информации в сетях и системах телекоммуникации» Тезисы доклада Рязань 2005. С.62-63

8 Крысяев Д.Е., Фам С Н Исследование помехоустойчивости алгоритма Мак-Элис на основе каскадного кодирования // ВНТК «Новые информационные технологии в тучных исследования и в образовании». Тезисы докладов 2006. С. 130-131

9. Крысяев Д.Е., Фам С Н Исследование помехозащищенности алгоритма Мак -Элис на основе произведения кодов // Всероссийская научно-практическая конференция Сети, системы связи и телекоммуникации. Тезисы докладов 2006 С 154-155

10 Кириллов С.Н, Крысяев Д Е, Фам С Н Способы повышения эффективности системы кодирования информации Мак-Элис // Вестник РГРТУ 2006 №19 С. 35-39

11 Фам Суан Нгиа Анализ применения алгоритма Мак-Элис для электронной цифровой подписи // Вестник РГРТУ 2007. №20. С 41-45.

12 Фам С Н. Повышение эффективности алгоритма Мак-Элис на основе сжатия информации // ВНТК «Новые информационные технологии в научных исследованиях и в образовании». Тезисы докладов 2007. С. 17.

13. Фам Суан Нгиа. Исследование помехозащищенности алгоритма Мак-Элис на основе турбо кодов // Всероссийская научно-практическая конференция Сети, системы связи и телекоммуникации Тезисы докладов 2007 С 150-151

Фам Суан Нгиа

Модификации алгоритма Мак-элис для повышения показателей качества радиосистем передачи информации

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

Отпечатано в ГНУ ВНИМС, Рязань, Щорса 38/11 Формат бумаги 60x84 1/16 Печатных листов 1 Заказ № 25 Тираж 100 экз

16 апреля 2007г

ВВЕДЕНИЕ.

1 АНАЛИЗ УСТОЙЧИВОСТИ АЛГОРИТМА КОДИРОВАНИЯ ИНФОРМАЦИИ МАК - ЭЛИС К ДЕЙСТВИЮ КОМПЛЕКСА ПОМЕХ.

1.1 ВВОДНЫЕ ЗАМЕЧАНИЯ.

1.2 ОПИСАНИЕ АЛГОРИТМА МАК - ЭЛИС.

1.3 МЕШАЮЩИЕ ВЛИЯНИЯ В КАНАЛАХ ПЕРЕДАЧИ ИНФОРМАЦИИ.

1.4 ИССЛЕДОВАНИЕ ПОМЕХОУСТОЙЧИВОСТИ АЛГОРИТМА КОДИРОВАНИЯ ИНФОРМАЦИИ МАК - ЭЛИС.

1.4.1 Характеристики комплекса помех.

1.4.2 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Хэмминга.

1.4.3 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Боуза - Чоудхури - Хоквингема.

1.4.4 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Рида - Соломона.

1.4.5 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении кодов Гоппы.

1.4.6 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении метода порогового и многопорогового декодирования.

1.4.7 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении произведения кодов.

1.4.8 Результаты экспериментальных исследований помехоустойчивости алгоритма Мак - Элис при применении турбо кодов.

1.5 ВЫВОДЫ.

2 МОДИФИКАЦИИ АЛГОРИТМА МАК - ЭЛИС ДЛЯ ПОВЫШЕНИЯ ИНФОРМАЦИОННОЙ СКРЫТНОСТИ И КОДОВОЙ СКОРОСТИ.

2.1 ВВОДНЫЕ ЗАМЕЧАНИЯ.

2.1.1 Особенности алгоритмов шифрования.

2.1.2 Алгоритмы защиты информации с открытым ключом.

2.1.3 Шифросистемы алгоритма с открытым ключом.

2.2 ВАРИАНТЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ АЛГОРИТМА

МАК-ЭЛИС.

2.2.1 Алгоритм на основе изменения входной информации кодера.

2.2.2 Алгоритм повышения кодовой скорости.

2.2.3 Алгоритм основанный на совмещении требований повышения кодовой скорости и информационной скрытности.

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

2.2.5 Алгоритм на основе использования произведения кодов.

2.2.6 Алгоритм Мак-Элис при использовании сжатия информации.

2.2.7 Сравнение эффективности вариантов модификаций алгоритма Мак - Элис.

2.3 ВЫВОДЫ.

3 ПРАКТИЧЕСКИЕ АСПЕКТЫ РЕАЛИЗАЦИИ АЛГОРИТМА

МАК-ЭЛИС.

3.1 ВВОДНЫЕ ЗАМЕЧАНИЯ.

3.2 ПРИМЕНЕНИЕ АЛГОРИТМА МАК-ЭЛИС ДЛЯ ЭЛЕКТРОННОЙ ЦИФРОВОЙ ПОДПИСИ.

3.2.1 Понятие электронной цифровой подписи.

3.2.2 Анализ применения алгоритма Мак-Элис для электронной цифровой подписи.

3.3 АНАЛИЗ ФАКТОРОВ ВЛИЯЮЩИХ НА ПРАКТИЧЕСКУЮ РЕАЛИЗАЦИЮ АЛГОРИТМА МАК-ЭЛИС.

3.3.1 Факторы обеспечения заданной скорости передачи информации.

3.3.2 Факторы обеспечения заданной помехоустойчивости и скрытности передачи информации.

3.3.3 Анализ вычислительных затрат на реализацию алгоритма Мак-Элис.1.

3.4 АНАЛИЗ РЕАЛИЗАЦИИ АЛГОРИТМА МАК - ЭЛИС НА ПРОГРАММИРУЕМЫХ ЛОГИЧЕСКИХ

ИНТЕГРАЛЬНЫХ СХЕМАХ.

3.4.1 Обоснование реализации алгоритма Мак-Элис на программируемых логических интегральных системах.

3.4.2 Особенности структуры программируемых логических интегральных схем.

3.4.3 Анализ реализации алгоритма Мак-Элис на программируемых логических интегральных схемах.

3.5 ВЫВОДЫ.

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

Кроме того, эти системы должны выполнять поставленные задачи в условиях действия различного вида помех [1].

Одним из решений данной задачи является использование помехоустойчивого кодирования в системах передачи информации. Целесообразность кодирования информации впервые была показана в работе Шеннона К. [2], где было доказано, что если скорость создания сообщений источником не превосходит некоторой величины, называемой пропускной способностью канала, то при правильно выбранных методах кодирования и декодирования можно вести передачу по каналу с шумом со сколь угодно малой вероятностью ошибки. Основные задачи помехоустойчивого кодирования связаны с построением кодов с высокой корректирующей способностью и разработке высокоэффективных, практически реализуемых алгоритмов их декодирования [3. 6].

Значительный вклад в области повышения помехоустойчивости передаваемой информации внесли такие учёные как Котельников В. А., Злотник Б. М., Кларк Д. Ж., Кейн Д. Ж., Питерсон У., Уэлдон Э., Месси Б. Дж., Кассами Т., Токура Н., Морелос-Сарагоса Р., Золотарёв В. В., Самсонов Б., Плохов Е. М., Вегтои С., С1ау1еих А., ТЫШи^БЫта и.др. [1,4. 12].

Другим важным требованием к системам передачи информации является обеспечение скрытности, которая характеризуется способностью системы противостоять мерам, направленным на раскрытие содержания информации. Обеспечение скрытности передаваемой информации включает комплекс мер затрудняющих: обнаружение сигнала, определение структуры обнаруженного сигнала (на основе определения ряда его параметров) и раскрытие смысла содержащегося в передаваемой информации [3, 13, 14]. Одним из методов, часто использующимся для повышения скрытности информации, является применение кодирования. Повышением скрытности передаваемой информации занимались Шеннон К., Тузов Г. И., Сивов В. А., Брюс Щнайер, Саломаа А., Алферов А. П., Зубов А. Ю., Нечаев В.И, Молдовян Н. А, Молдовян А. А, Венбо Мао [2, 3, 15.20] и.др.

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

В отличие от этих систем алгоритм Мак-Элис, основанный на использовании линейных кодов, позволяет одновременно обеспечивать заданную помехоустойчивость и скрытность передаваемой информации [15. 17, 21.24]. Однако, данный алгоритм обладает такими недостатками, как низкая кодовая скорость, большая длина кодового слова, значительный размер закрытого и открытого ключа. Для широкого использования данного алгоритма, необходимо устранить вышеперечисленные недостатки.

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

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

Поставленная в работе цель включает решение следующих задач:

- анализ устойчивости алгоритма Мак-Элис в случае действия комплекса помех, при использовании различных линейных кодов (например, коды Хэмминга, Боуза - Чоудхури - Хоквингема, Рида-Соломона, Гоппы, саммоортогональных кодов (СОК), произведение кодов, турбо кодов);

- модификации алгоритма Мак-Элис в интересах повышения скрытности, скорости и помехоустойчивости передачи информации;

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

- исследования применения модификаций алгоритма Мак-Элис для электронной цифровой подписи (ЭЦП), в радиосистемах передачи информации;

- анализ реализации модификаций алгоритма Мак-Элис при использовании программированных логических интегральных систем (ПЛИС) в высокоскоростных системах передачи информации.

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

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

1. Оценена устойчивость алгоритма Мак-Элис при действии комплекса широкополосной, узкополосной, структурной и импульсной помех в случае использования кодов Хэмминга, Боуза - Чоудхури - Хоквингема, Рида-Соломона, Гоппы, произведение кодов, СОК, турбо кодов с различными кодовыми скоростями и определена самая опасная помеха.

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

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

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

5. Показана возможность применения алгоритма Мак-Элис для ЭЦП, а также в радиосистемах передачи информации.

Практическая ценность.

Представленные в работе модифицированные алгоритмы Мак-Элис, имеют высокую помехоустойчивость, скрытность передачи информации и кодовую скорость, что позволяет их использовать для ЭЦП и в различных радиосистемах передачи информации. Модифицированные алгоритмы Мак-Элис применяющие комбинированные коды и обладающие высокой способностью исправлять ошибки, могут использовать в системах передачи данных, требующих высокую помехоустойчивость. Результаты диссертационной работы нашли применения в сетях передачи данных в ОАО «Телекоммуникационной компании Ринфотелс», а также в ГОУ ВПО «Рязанский государственный радиотехнический университет».

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

1. Модифицированный алгоритм Мак-Элис, основанный на добавлении информации в вектор ошибки и изменении исходной информации путем использования матрицы хеширования, обеспечивающей информационную скрытность до 1,37.1016 при использовании кода Гоппы (1024, 524).

2. Модифицированный алгоритм Мак-Элис основанный на добавлении информации в вектор ошибок, позволяющий повысить кодовую скорость на -60%.

3. Модифицированный алгоритм Мак-Элис основанный на применении параллельных кодов, позволяющий повысить информационную скрытность в 10,4раз (при длине кодового слова п=1) по сравнению с исходным алгоритмом.

4. Модифицированный алгоритм Мак-Элис, основанный на использовании произведения кодов, обеспечивающий информационную скрытность более 1,37.1016 и число исправляемых ошибок до 91 бит при использовании произведения кодов Х(15,11)БЧХ( 1024,728).

5. Модифицированный алгоритм Мак-Элис с преобразованием исходной информации путем сжатия и использования вектора ошибок, позволяющий получить информационную скрытность до ЛМ,37.1016 в случае использования кода Гоппы (1024,524), а также повысить кодовую скорость до 0,95.

Апробация работы. Результаты работы докладывались на следующих научно-технических конференциях:

1. 52-я Студенческая Научно-Техническая Конференция. 2005, Рязань.

2. Всероссийская научно-практическая конференция студентов, молодых учёных и специалистов "Новые информационные технологии в научных исследования и в образовании". 2005, Рязань.

3. Всероссийская научно-практическая конференция "Сети и системы связи", 2005. Рязань.

4. Международная научно-техническая конференция «Проблемы передачи и обработки информации в сетях и системах телекоммуникации». 2005, Рязань.

5. Международная молодежная научная конференция, посвященная 1000 летию города Казани "Туполевские чтения". 2005, Казань.

6. Всероссийская научно-практическая конференция студентов, молодых учёных и специалистов "Новые информационные технологии в научных исследования и в образовании". 2006, Рязань.

7. Всероссийская научно-практическая конференция "Сети и системы связи", 2006. Рязань.

8. Всероссийская научно-практическая конференция студентов, молодых учёных и специалистов "Новые информационные технологии в научных исследования и в образовании". 2007, Рязань.

9. Всероссийская научно-практическая конференция "Сети и системы связи", 2007. Рязань.

Публикации. По теме диссертации опубликовано 13 работ. Из них 3 статьи в журналах рекомендованных ВАК РФ для кандидатских диссертаций, 1 статья в межвузовском сборнике, 9 тезисов докладов.

Структура и объём работы. Диссертационная работа состоит из введения, трех глав, заключение, списка литературы из 120 наименований и 3 Приложений. Диссертация содержит 168 стр., в том числе 132 стр. основного текста, 12 таблиц и 92 рисунка.

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

1. Показано, что наиболее высокая помехоустойчивость наблюдается при использовании турбо кодов в алгоритме кодирования информации Мак-Элис. Например, при действии широкополосной помехи, для достижения средней вероятности ошибки Ре=10"4, в случае использование турбо кода, имеющего скорость кодирования г=1/2 необходимо яш=2,8 дБ, а при применении произведения кода с внешним кодом Х(15,11) и внутренним БЧХ(127, 92) с кодовую скоростью г = 0,53 - яш= 5,6 дБ. В случае использования кода СОК (162, 81) (г = 0,5) с многопороговым декодером -Ящ=6,7 дБ, а при применении кода БЧХ и Хэмминга со скоростью х~\И отношение сигнал-шум больше, чем 6 дБ.

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

3. Показано, что наиболее опасной является импульсная помеха для всех кодов, использованных в качестве линейных или комбинированных в алгоритма Мак-Эллис. Например, при действии узкополосной, структурной и импульсной помех с отношением сигнал-помеха =15 дБ и при наличии широкополосного шума из канала с <2^=2,5 дБ, в случае использования турбо кода, получаются вероятности ошибки Реу= 7.10'4, Рес= 10"3 и Реи= 3,2x10'3 соответственно.

4. Показано, что изменение исходной последовательности с использованием функции хеширования в одну сторону, позволяет повысить информационной скрытности до -1,37.1016 при применении кода Гоппы (1024, 524) в качестве линейного кода в алгоритме Мак-Элис. Предложено для повышения информационной скрытности использовать матрицу с размером {п*к) вместо функции хеширования к(ё), что расширило пространство закрытых ключей на 2105 раз по сравнению с исходной схемой при к=1, «=15.

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

6. Предложена модификация алгоритма Мак-Элис с преобразованием исходной информации путем сжатия и использования вектора ошибок, позволяющая получить информационную скрытность до АТ~1,37.1016 в случае использования кода Гоппы (1024, 524), а также повысить кодовую скорость до 0,95.

7. Показана возможность применения алгоритма Мак-Элис для ЭЦП при этом не требуется передача секретного алгоритма (или ключа), а скрытность информации повышается в ~Ю50 и в два раза возрастает информационную скрытность системы ЭЦП по сравнению с применением исходной схемы.

8. Доказано, что реализация алгоритма Мак-Элис требует в 9 рад меньше вычисленных операций, чем алгоритма RSA и помехоустойчивого кода Гоппы (1024, 524) в системе передачи информации при тех же параметрах.

9. Показана возможность реализации алгоритма Мак-Элис на ПЛИС XC4VSX55 (семейства Virtex-4), при скорости передачи информации 250 Мбит/с.

ЗАКЛЮЧЕНИЕ

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

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

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

В третьей главе рассмотрены вопросы использования модифицированных алгоритмов Мак-Элис для ЭЦП, а также вопросы практической реализации алгоритма Мак-Элис на ПЛИС в высокоскоростных системах передачи информации.

1. Котельников В. А. Теория потенциальной помехоустойчивости. М.Л.: 1956.150 с.

2. Shannon С. Е. Communication Theory of Secrecy Systems // Bell Systems Technical Journal. 1949. V.28. P. С 656-751.

3. Тузов Г. И., Сивов В. А., Прытков В. И., Урядников Ю. Ф., Дергачев Ю. А., Сулиманов А. А. Помехозащищенность радиосистем со сложными сигналами. М.: Радио и связь, 1985. 264 с.

4. Злотник Б.М. Помехосутойчивые коды в системах связи. М.: Радио и связь. 1989. 229 с.

5. Кларк Дж., мл., Кейн Дж.Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1987. 392 с.

6. Питерсон У. Уэлдон Э. Коды, исправляющие ошибки / Пер. с англ.; под ред. Р.П, Добрушина и С.И. Самойленко. М.: Мир. 1976, 594 с.

7. Месси Дж. Пороговое декодирование // Пер. с англ, под ред. Э.Л. БлохаМ.: Мир, 1966. 208 с.

8. Кассами Т., Токура Н., Ивадари Е., Инагаки.Я. Теория кодирования. М:. 1978. 578с.

9. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М:.Техносфера, 2005. 319 с. Ю.Золотарёв В. В., Овечкин Г. В. Помехоустойчивое кодирование. М: Горячая линия- Телеком, 2004. 126 с.

10. П.Самсонов Б.Б., Плохов Е.М., Филоненков А.И., Кречет Т.В. Теория информации и кодирование. Ростов-на-Дону "Феникс" 2002.-288с.

11. Berrou С., Glavieux A., Thitumajshima P. Near Shannon Limit Error-correcting Coding and Decoding: Turbo code//in Proc. Of the Intern. Conf.on Commun. (Geneva, Switzerland). 1993. May. P 1064-1070.

12. M. В. Максимов, M. П. Бобнев, Б. X. Кривицкий и др. Защита от радиопомех. М.: «Сов. радио», 1976. 496 с.

13. Свистов В. М. Радиолокационные сигналы и их обработка. М.: «Сов. радио», 1977.448 с.

14. Брюс Шнайер. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. 2002. 850 с.

15. Саломаа. А. Криптография с открытым ключом. М.: Мир, 1995. 320 с.

16. Алферов А.П., Зубов А.Ю., Кузьмин А.С., Черемушкин А.В.Основы криптографии. М: 2001. 480 с.

17. Нечаев В.И.Элементы криптографии (Основы теории защиты информации). М.:Высш. шк, 1999.109 с.

18. Молдовян Н. А, Молдовян А. А. Введение в криптосистемы с открытым ключом. Санкт-Петербург, 2005. 286 с.

19. Венбо Мао. Современная криптография теория и практика. Москва. Санкт-Петербург. Киев, 2005. 763 с.

20. Hung Min Sun. Enhancing the security of the McEliece Public-key Cryptosystem.Journal of information science and engineering 16. 2000. С 799812.

21. M.C. Lin and Т. C. Fu. Information rate of McEliece's public key cryptosystem. Electronics letters, Vol. 26, No.l, 1990, pp. 16-18.

22. C. S. Park. Improving code rate of Mc-Eliece's public key cryptosystem. Electronics letters, Vol. 25, No. 21, 1989, pp. 1466-1467.

23. Johan van Tilburg. On the Public-key Cryptosystem. Springer-Verlag, 1998. CI 19 -131.

24. Rodger E. Ziemer, Rodger L. Peterson. Introduction to digital communication.-Pretice Hall, 2000. 905 c.

25. Борисов B.A., Калмыков B.B., Ковальчук Я. М., Себекин Ю. Н., Сенин А. И., Федоров И. Б. , Цикин И. А. Радиотехнические системы передачи информации. М.: Радио и связь, 1990. 304 с.

26. Пенин П. И. Системы передачи цифровой информации. М., «Сов. радио», 1976.368 с.

27. Иванов В. И., Гордиенко В. Н., Попов Г. Н., Аснин JI. Б., Репин В. Н., Тверецкий М. С., Заславский К. Е., Исаев Р. И. Цифровые и аналоговые системы передачи. М.: Горячая линия, 2003. 232 с.

28. Золотарев В. В. Методы помехоустойчивого кодирования для каналов сослучайными ошибками // Радиоэлектроника, 2000. №12. С. 47 51.

29. Золотарёв В.В.,Зубарев Ю.Б., Жуков С.Е., Строков В.В., Овечкин Г.В.,

30. Многопороговые декодеры для высокоскоростных спутниковых каналовсвязи новые перспективы // Электросвязь. N2, 2005. С10-13.

31. Каганов В.И Радиотехнические цепи и сигналы. М: Издательский центр «Академия», 2003. 224 с.

32. Левин J1. С., Плоткин М. А. Цифровые системы передачи информации. М.: Радио и связь, 1982. 216 с.

33. Бельфер P.A. Анализ систем связи в аспекте пртектирования информационной безопасности // Электросвязь, № 3,2004. С22-24.

34. Зверев Б.В., Зелевич Е.П. Анализ видов несанкционированного доступа и методы защиты услуг связи // Электросвязь, № 12,2000. С9-11.

35. Осмоловский С. А. Сравнительный анализ некоторых свойств стохастических кодов и кодов Рида Соломона // Электросвязь, № 1, 1991. С31-33.

36. Калинцев Ю.К. Обеспечение безопасности информации в современных сетях электросвязи // Электросвязь, № 12, 2000. С6-8.

37. Бельфер P.A. Классификация угроз информационной безопасности сетей связи всс России (ISDN, IN, UMTS) и методы их количественной оценки // ЭЛЕКТРОСВЯЗЬ, № 7, 2002. С14 18.

38. Галкина В. И., Захарчено И. И. Радиотехнические системы в ракетной технике. М:.1974. 369с.

39. Калинцев Ю.К. Обеспечение безопасности информации в современных сетях электросвязи // Электросвязь, № 12,2000. С6-8.42.3айдлер Е. Системы передачи дискретной информации. Издательство "Связь" М:.1977. 52с.

40. Кириллов.С.Н., Малинин Д.Ю. Повышение эффективности методов защиты речевой информации в радиоканалах.// Электросвязь. 2000. №б. С38-40.

41. Кириллов.С.Н., Малинин Д.Ю. Повышение эффективности методов защиты информации // Новые информационные технологии в научных исследованиях в образовании Тезисы докладов. Рязань 1999. С37.

42. Крысяев Д.Е., Фам С.Н. Анализ помехоустойчивости алгоритма кодирования информации Мак-Элис // ВНТК «Новые информационные технологии в научных исследования и в образовании». Тезисы докладов 2005. С. 41.

43. Крысяев Д.Е., Фам С.Н. Исследование влияния комплекса помех на алгоритм кодирования информации Мак-Элис // Всероссийский научно-практический семинар. Сети и системы связи. Тезисы докладов 2005. С. 281.

44. Крысяев Д.Е., Фам С.Н. Исследование влияния комплекса помех на алгоритм кодирования информации Мс-ЕНесе // СНТК-52. Рязанская государственная радиотехническая академия. Тезисы докладов 2005. С. 4.

45. Крысяев Д.Е., Фам С.Н. Исследование помехоустойчивости системы кодирования Мак-Элис // Вестник РГРТА. Статья 2005 №15. С.112-116.

46. Крысяев Д.Е., Фам С.Н. Исследование помехоустойчивости алгоритма кодирования информации Мак-Элис при воздействии комплекса помех // «Туполевские чтения». Тезисы докладов 2005. С. 84-85.

47. Крысяев Д.Е., Фам С.Н. Исследование помехоустойчивости системы передачи информации на основе алгоритма Мак-Элис при использовании кода Рида-Соломона // «Биомедицинские технологии и радиотехника». Рязань 2005.С.140-145.

48. Крысяев Д.Е., Фам С.Н. Исследование помехоустойчивости алгоритма Мак-Элис на основе каскадного кодирования // ВНТК «Новые информационные технологии в научных исследования и в образовании». Тезисы докладов 2006.С. 130-131.

49. Крысяев Д.Е., Фам С.Н. Исследование помехозащищенности алгоритма Мак -Элис на основе произведения кодов // Всероссийская научно-практическая конференция. Сети, системы связи и телекоммуникации . Тезисы докладов 2006. С. 154 155.

50. Кириллов С.Н., Крысяев Д.Е., Фам С.Н. Способы повышения эффективности системы кодирования информации Мак-Элис // Вестник РГРТУ. Статья 2006. №19. С35-39.

51. Фам Суан Нгиа. Анализ применения алгоритма Мак-Элис для электронной цифровой подписи // Вестник РГРТУ 2007. №20. С41-45.

52. Фам С.Н. Анализ применения алгоритма Мак-Элис на основе сжатия информации // ВНТК «Новые информационные технологии в научных исследованиях и в образовании». Тезисы докладов 2007. С. 17.

53. Фам С.Н. Исследование помехозащищенности алгоритма Мак -Элис на основе турбо кодов // Всероссийская научно-практическая конференция. Сети, системы связи и телекоммуникации . Тезисы докладов 2007. С. 150 — 151.

54. Дстахов A.M. Аудит безопасности информационных систем // Защита информации конфидент. 2003. Nfi2. С 90-96.

55. Быков C.B. Особенности защиты цифровой интеллектуальной собственности // Защита информации конфидент. 2001. Nfi3. С 50-55.

56. Владимиров Д.Н., Яковлев М.А. Обеспечение информационной безопасности в системе SAP R/3 // Защита информации конфидент. 2003. №4. С 24-27.

57. Жуков О. Д. Модулярные вычисления в системах защиты информации //Информационные технологии. 2002. №l. С26-29.

58. Защита речевой информации: Технические средства и услуги: Камалог.// Защита информации. Конфидент. 2001. N4. С. 81-99.

59. Ильин В.Е., и др. Анализ проблемы адаптивной защиты ИВС в условиях информационного противоборства // Защита информации. Конфидент. 2002. N4-5. С 99-107.

60. Каливалов А.Ж. Принцип скрытия структуры запроса для обеспечения защиты баз данных // Защита информации. Конфидент. 2003. N4. С. 30-33.

61. Кастерскш К. Примы защиты исходных текстов и двоичного кода // Открытые системы СУБД. 2001. N7-8. С40-44.

62. Панасенко С.П. Электронная цифровая подпись // Мир ПК. 2002. N3. С.78-83.

63. Реброб А.И. Защита программ и баз данных // Защита информации. Конфидент.- 2001. N3. С 44-49.

64. Сивенцев А. Оценка и сопоставление угроз информации и мер защиты от них.// Connect/-Mnp связи. 2001. N7. С102 104.

65. Хорев A.A., Макаров Ю.К. Методы защиты речевой информации и оценки их эффективности // Защита информации. Конфидент.- 2001. N4 С. 22-33.

66. Андрианов В.В. Технология защиты в принципах организации информационных систем // Защита информации. Конфидент. 1998. №3. С. 23-31.

67. Амаров М. Защита сообщений электронной почты // Мир П.К. 1996. №-1. С.93-96.

68. Колесников A.A., Щекотихин В.В. Защита речевой информации от утечки по техническим каналам // Конфидент. 1999.№4-5. С.63-67.

69. Малюк A.A. Безопасность информационных технологий/ /Мифи.- 1998. №з.с.5-13.

70. Раевский А., Груздев С. Проблема защиты данных // Защита информации. .Конфидент. 1997. N5. С. 55-58.

71. Касперскии К. Приемы защиты исходных текстов и двоичного кода // Открытые системы СУБД. 2001. N7-8. С40-43.

72. Гекин К. Криптозащита текстов файлов // Мир П.К. 2001. N5. С. 48-55.

73. Анин Б.О. Шифровании и дешифровании // Защита информации. Конфидент. 1997. Nûl. С.71-79.

74. Вайнер П.С. Применение машин с ассоциативным поиском для информации и атаки на DES // Защита информации. Конфидент. 1996. №б. С.80-85.

75. Вовченко В.В. Организация защиты речевой информации на объекте // Защита информации. Конфидент. 1998. №б. С.49-57.

76. Баронии С.П., Синдедерю. Б. О помехоустойчивости и пропускной способности цифровых корреляционных процессоров в системах подвижной радиосвязи с кодовым разделением каналов // Радиотехника и электроника, 2001. N3. С. 339-345.

77. Гутин B.C., Станкевич Ю.А. Цифровые методы передачи информации в спутниковых радиолиниях // Изв. Ленингр. Электротехн. Ин-та.1986. Вып 370. С. 50-56.

78. Дорофеев В.М., Злотникова Е. А., Паянская M.J1. Взаимные помехи в цифровых системах спутниковой связи // Электросвязь. 1998. №б. С. 31-36.

79. Дорофеев В.М. Влияние кратковременных помех на параметры цифровых систем спутниковой связи // Труды, 1992. С. 21.

80. Дорофеев В.М., Кустуев А.И. Цифровая спутниковая связь: Обзор //Электросвязь. 1988-N25. С.22-25.

81. Драгун JI.A., Курицын С.А. Модель дискретного спутникового канала связи // ТР.НИИР. 1986. №l. С29-34.

82. Кантор Л.Я. Передача сигналов в цифровых спутниковых системах связи // Электросвязь, 1988. №5. СЗ-6.

83. Бесковная С. В., и др. Анализ пропускной способности каналов связи многофункциональных информационно- управляющих комплексов // Изв. Вузов. Электроника. 2000. №3. 76-79.

84. Гвоздев В. И; Шестопалов В. Ю. Многоходовые линии передачи для цифровых каналов связи // Зарубеж. Радиоэлектроника. 1988. №12. С. 49-58.

85. Коржик В.И., Яковлев В.А. Пропуская способность канала связи со случайным внутренним кодированием // Пробл передачи информ. 1992. Выпн28. С.24-34.

86. Макаров С.Б., Цикин И. А., Ядыкин В. К. Метод оценки эффективности использования полосы частоты канала передачи // Радиотехника. 1991. N"10. С. 93-97.

87. Мишин Е., Брауде Ю. Золотарев, Гудзера В., СоколоВ. Как защитить каналы связи //Мир связи. 1998. Т10. С.102-103.

88. Сендерский В.А., Строков В. В. Предельная помехоустойчивость двоичного канала без памяти при оптимальном приеме // Электросвязь. 1990. №7. С.13-14.

89. Аладин И. М. и др. Спектральная эффективность радиоканалов при передаче дискретных сообщений // Мобильные системы. 2002. N1. С. 24-29.

90. Аль Хенин М. Ф. Модель дискретного канала радиосвязи // Известия вузов. Радиоэлектроника. 1997. №10. С. 73-76.

91. Коричнев Л.П. Статистические процедуры последовательного анализа состояния дискретных каналов связи // Электросвязь. 1992. №4. С. 6-7.

92. Баушев С. В., Зайцев И. Е. Критерий кодирования сообщений однократного источника // Зарубежная радиоэлектроника. 2002. N2. С. 64-70.

93. Дмитриев А. А., и др. Кодирование информации на основе динамического хаоса // Зарубежние. Радиоэлектроника. 2000. №2. С. 27-33.

94. Геер А. Э. Блоково самоортогональные сверточные коды с малой избыточностью // Известия вузов. Радиоэлектроника. 1997. №12. С. 22-30.

95. Давыдов А. А. Построение линейных покрывающих кодов // Пробл передачи информ.- 1990. Т26, Вып 4. С. 38-45.

96. Использование кода Рида Соломона для повышения надежности расшифровки кодированных сообщений // Экспресс - Информация. Сер. НКК. 1991. №35. С. 22.

97. Кокошкин И. В. Метод статистического перекодирования ИКМ сигнала //Вестн. Связи. 1992. №8. С.31-33.

98. Опаринский П. П. О помехозащищенности блоковых кодов// Вопросы радиоэлектроники. Сер. ОВР. 1990. Выш 14. С. 105.

99. Ю8.Васильченко Ю. А., Правда В. И. Оценка качества канала связи для сетей с асинхронной пакетной передачей данных. // Изв. вузов. Радиоэлектроника. 2002. N2. С. 49 55.

100. Вершинин В. А. Повышение помехоустойчивости передачи при восстановлении группового сигнала // Изв. Вузов. Радиоэлектроника. 1991. Т34,№4. С. 92-93.

101. Кириллов В. И. Помехозащищенность линейного регенератора цифровой системы передачи с решающей обратной связью // Радиоэлектроника. 1996. №2. С. 36-41.

102. Альцев А. Д., Чуднов А. М. Синтез дискретных помехозащищенных сигналов методами теории игр // Изв вузов. Радиоэлектроника. 1989. N-7. С. 59-61.

103. Прилекпский П. П. Радиолиния с повышенной помехозащищенностью // Теория и техника радиосвязи: Науч.- техн. Сб. Воронеж, 1995. Вып.1. С. 5159.

104. Ерош. И. Л. «Игры в прятки» с перехватчиком сообщений // Информационно-управляющие системы, №2, 2004. С. 45-49.115. http://www.mtdbest.iki.rssi.ru

105. Ашихмин А. С. Цифровая схемотехника. Современный подход. М.: 2007. 287с.117.www.flis.ru118. www.texas-instruments.com119. www.Xilinx.com

106. Зотов В. Ю. Проектирование цифровых устройств на основе ПЛИС фирмы XILINX в САПР WedPACK ISE. Москва Горячая линия Телеком. 2003. 623с.