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

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

Смикун Петр Иванович

ИССЛЕДОВАНИЕ ВОПРОСОВ ПОСТРОЕНИЯ И РАЗРАБОТКА МАТРИЧНЫХ МНОГОФУНКЦИОНАЛЬНЫХ СИСТЕМ ОБНАРУЖЕНИЯ ОШИБОК И ЗАЩИТЫ ДАННЫХ

Специальность 05.13.18 - «Математическое моделирование, численные методы и комплексы программ»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 7 ШР 2011

Ульяновск - 2011

4840328

Работа выполнена на кафедре «Телекоммуникационные технологии и сети» в Государственном образовательном учреждении высшего профессионального образования Ульяновский государственный университет

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

Смагин Алексеи Аркадьевич

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

Кумунжиев Константин Васильевич

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

Ведущая организация: 24 Центральный научно-исследовательский институт Министерства обороны РФ, г. Санкт-Петербург, г. Петродворец

Защита состоится 30 марта 2011 года в 1300 часов на заседании диссертационного совета Д 212.278.02 при Ульяновском государственном университете по адресу: Набережная р. Свияги, 106, корпус 1, ауд. 703

С диссертацией можно ознакомиться в научной библиотеке Ульяновского государственного университета, с авторефератом на сайте ВУЗа www.uni.ulsu.ru.

Автореферат разослан « » февраля 2011 года.

Отзывы на автореферат просим присылать по адресу: 432000, г. Ульяновск, ул. Л. Толстого, д. 42, УлГУ, Управление научных исследований.

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

диссертационного совета / ' М.А. Волков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

1 Nikitin V., Yurkin D„ Chilamkurti N. The influence of the cryptographic protocols on the quality of the radio transmission . // Proc. of International Conference on Ultra Modern Telecommunications. - 1CUMT-2009, St.-Petersburg, Russia. P. 1-5.

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

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

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

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

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

2 Золотарев В.В., Овечкин Г.В.Помехоустойчивое кодирование.Методы и алгоритмы:справочник/ Пол рел.чл.-корр..Ю.Б.Зубарева.- М:Горячая линия.-телеком, 2004.

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

Объектом исследования является системы передачи данных по небезопасным каналам связи с ошибками.

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

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

Для достижения цели решаются следующие составные задачи:

1. Исследование возможностей построения матричных кодов, обнаруживающих ошибки в каналах связи.

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

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

4. Разработка матричных моделей контроля и криптографической защиты данных.

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

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

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

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

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

2. На основе метода матрично-алгоритмического кодирования разработаны модели схемных решений по обнаружению не менее двух ошибок в передаваемых данных и созданы условия для прогнозирования при их передаче по каналам связи с ошибками.

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

4. Предложен рекурсивный способ и алгоритм вычисления веса стандартного двоичного представления чисел без процедуры генерации кода за счет одной операции деления с остатком и порядка 1о^2 N сложений, обладающий простотой реализации и высокой скоростью.

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

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

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

1. Подход и модели матрично-алгоритмического кодирования/ декодирования в виде диаграмм преобразования кодов заданного ранга (веса).

2. Модели схемных решений по обнаружению ошибок на базе матрично-алгоритмического кодирования данных для каналов связи с ошибками без введения избыточности в передаваемый код.

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

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

4. Рекурсивный способ и алгоритм вычисления веса (ранга) стандартного двоичного представления чисел без процедуры генерации кода за счет одной операции деления с остатком и порядка 1од2 N сложений.

5. Комплекс программ моделирования и анализа характеристик систем, создаваемых на базе матрично-алгоритмического преобразования данных и предложенных моделей.

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

Внедрение результатов работы. Результаты, полученные в ходе выполнения диссертационной работы, приняты к использованию в проектных работах ФНПЦ ОАО «НПО «Марс», г. Ульяновск, ОАО «Интелтех», г. Санкт-Петербург, ЗАО «Центрпрограммсистем», г.Тверь.

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

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

1. Девятая международная научно-техническая конференция. Проблемы техники и технологий телекоммуникаций. ПТиТТ-2008 (Казань, 2008).

2. Шестая международная конференция «Оптические технологии в телекоммуникациях. ОТТ-2008 (Казань-2008).

3. Научные семинары факультета математики и информационных технологий Ульяновского государственного университета, (г. Ульяновск, 2007-2010гг.).

Публикации. По теме диссертации опубликовано 6 работ, в том числе 3 -в изданиях из перечня ВАК.

Личный вклад автора. Постановка задачи исследований осуществлена совместно с научным руководителем. Все основные установленные в диссертации результаты получены соискателем самостоятельно.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка используемой литературы из 114 наименований и одного приложения. Основной текст диссертации изложен на 154 страницы и содержит 47 рисунков и 9 таблиц.

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

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

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

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

Предложен быстрый способ декодирования данных на основе матрицы интервалов с возможными модификациями, разработан и исследован алгоритм кодирования/декодирования текста, приведены примеры. Сделан вывод о недостаточности возможностей матрично-координатного кодирования для выполнения поставленных в диссертационной работе задач.

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

Предложено использовать для матрично-алгоритмического кодирования модифицированную матрицу биномиальных коэффициентов Паскаля, приведенную к левой нижнетреугольной матрице, обладающей свойствами сжатия данных, помехоустойчивого кодирования и криптографической защиты (впервые эти свойства были указаны Ю.Ю. Терентьевой; криптографические аспекты кода матрицы рассматривались В.В. Капитанчуком).

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

блока. Согласно данному методу любое неотрицательное целое число может быть представлено двоичным кодом заданного веса (в работе назван рангом кода, а метод, в котором он использован - методом матрично-рангового кодирования (метод МРК)).

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

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

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

Пусть А = ||а^|| — треугольная матрица I х где сг,7 = 1, 2, 3, ..., N — целые неотрицательные числа, взятые из натурального ряда для / </, а^ = 0 при } > ('. Схема кодирования числа N задаётся уравнением

/ — число бит в кодовой последовательности,

/ — некоторое условие, связанное со значениями матричного числа ац и некоторого числа Д.

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

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

где

1, при / = Кие О, при / = [а1эе

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

Осуществление выбора перехода от одного матричного числа к другому на к-и шаге происходит по следующей схеме (рис. 1).

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

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

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

В столбце, индекс которого определяется значением ранга, находится интервал между двумя соседними матричными числами, в который попадает кодируемое (исходное) число. Нижняя граница интервала и является точкой старта (начало пути). Формируемый путь имеет начало и конец. Начало пути связано с входом в матрицу и определяется значением требуемого ранга Я и исходным числом УУИСХ — по этим значениям

(1-2,;-2) (I-2.7-1) (1-2,])

Рис. 1. Модель пошагового перехода

Я. №исх

Рис. 2. Диаграмма формирования пути в матричном поле чисел

определяются матричные координаты (¿,/)точки старта. Путь включает в себя отдельные шаги, число которых равно длине формируемого двоичного кода. Время кодирования определяется как

Т= ^рч + + 'вф,

где £рч - время разбиения числа на пары; - время выделения одноразрядных 10-х чисел; Свф - время вычисления по формуле.

Рассмотрим пример кодирования десятичного числа N=43. Зададим ранг /?=4 (рис. 3). Матричное число 35, расположенное на пересечении 8-ой строки и 4-го столбца матрицы представляет собой начало пути (точку старта). Движение по числовому полю матрицы определяется применением правила (р. Направление движения «вверх-прямо» порождает нулевое значение разряда двоичного кода; движение «вверх-влево» - соответственно «1». По завершении процесса кодирования двоичный код числа 43 имеет вид - 10011010 (154|0).

1

2 0

3 й 1 0

4 3 Ф 1 0

5 4 6 1 0

6 5 10 5 1 0

7 6 15 й 15 6 1 0

8 7 21 35 © 21 7 1 0

9 8 28 56 о 56 28 8 1 0

10 9 36 84 126 126 84 36 9 1 0

1 2 3 4 5 6 7 8 9 10

Рис. 3. Процесс образования дерева кода числа N=43 при ранге К=4

На рис. 4 показана диаграмма матрично-алгоритмического декодирования двоичного кода, которая обладает наглядностью и фиксирует все действия на пути декодирования. Процесс декодирования двоичного числа состоит в определении координат (г, /) на матричном поле соответствующих позициям единиц в полученном коде. Так как координата г" при кодировании меняется

инкремеитивно , то она имеет «натуральную нумерацию» битов кода с крайнего правого разряда . Вторая координата определяется следующим образом:

КО = * - /СО). при Х{ = 1; у СО = 0 при %1 = 0.

Здесь используются следующие обозначения: у(1) - номер разряда кода с единичным значением; У(0) - номер разряда кода с нулевым значением; /(0) -число «встретившихся» нулевых значений разрядов кода, считая с первой правой позиции; «+» - знак сложения. По координатам г, / из матричного поля чисел выбирается соответствующее матричное число Т{1, у). Следует учитывать, что матричное число с координатами (¿, 0) отсутствует в матрице и «выбираемое» по этим координатам число приравнивается нулю.

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

Время дешифрования прямо пропорционально К и равно весу кода, умноженному на время вычисленияу(1) плюс время, необходимое для выполнения И сложений

*дш = я' Й(С0,) +

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

у = (п - 1) х _

Максимальная длина матричного кода

п = 1оя2 Са, где д =

Максимально представимое число

шах М{ = шах С^ Д .

Диапазон представления кодируемых чисел

с^ <м< с^.

Количество кодируемых чисел длиной Ь с рангом Я

к = с?:;.

Скорость кода

р, - К^-'Л

Сквозная нумерация координаты I

Матричные числа

Определение номера координаты у

Код числа

I = п-1

I = п-2

п п-1 п-2 2 1

1 = 2

I =1

^Т^— + -^т^- + ~(^Ш— + —+ Р У •

Рис. 4. Диаграмма матрично-алгоритмического декодирования

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

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

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

А = too-«hl.

где q0 — количество замен 1 —>0, а цх — количество замен 0—+1.

С целью установления соответствия между указанными выше рангами предложен рекурсивный алгоритм определения значения ранга стандартного двоичного представления входного числа N минуя процедуру генерации кода (перевод 10-+2). Вычисления проводятся по рекурсивной формуле R^Ffx), где функция F(x) определяется следующим образом:

F(0) = 0

FC 1) - 1

Нумеруются все возможные двоичные последовательности длины L при помощи перевода в десятичный код с использованием стандартной процедуры. Пусть i -десятичное число, полученное в результате операции декодирования, Rt - ранг /-го блока длины L. Определим рекурсивную функцию F(x) следующим образом:

F(0) = 0,F(1) = 1 ,F{x) = / ([да]) + F(x - 2^*1).

Тогда ранг /-го блока длины L может быть вычислен при помощи построенной функции:

Ri = FCO-

Число шагов рекурсии для определения веса десятичного числа 7Vравно

Т = entier (log N).

Получена формула вероятности необнаруженной ошибки, которая происходит в случае искажения ранга:

R-1

Р*.О. = X Р°(1 - ^"-"PiV ~ Pi)"-1'" ■

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

к

рсю^Ф'а-р)*4, [=1

где р1 - вероятность не повторения кодов; к - число кодов матричных чисел заданного ранга.

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

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

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

Далее во второй главе рассмотрен предложенный алгоритм построения блоковых кодов на основе метода МРК. Способ построения блоковых кодов позволяет обнаруживать ошибки при передаче блоков по параллельным несимметричным каналам связи с ошибками словами постоянной длины и с одинаковым рангом. Последние служат предпосылкой обнаружения ошибок.

Структура кода МРК такова, что он всегда начинается с 1 в старшем бите и, а в самое начало кода — бит с номером п+1 — добавляется 0. В этом случае длина сообщения равна Ь+1 бит.

Для исправления ошибок предлагается процедура построения двух динамических векторов V и которые отвечают за корректность п и п+1 битов. Эти значения сдвигаются по блоку и набирается статистика нарушений по всем ¿+1 элементам сообщения. При достаточно большом количестве передач (увеличении объёма передаваемых данных) векторы V (0—»1) и IV (1 —>0) будут давать вероятностные оценки зашумлённости канала (т. е. проводить диагностику), а также исправлять ошибки.

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

В схемы обнаружения и исправления ошибок заложены ранговый и двухбитовый контроль кода МРК, передаваемого по каналу связи с ошибками. Проанализированы параллельный и последовательный способы обнаружения и исправления ошибок при двухбитовом и объединенном контроле.

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

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

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

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

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

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

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

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

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

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

п К!(п-Я)!'

с помощью которой и секретного ключа К определяется подключ к'

к' - К mod Cg,

где п - длина ключа К, R - заданный ранг кода, при этом подключ к' задает количество циклов матричного кодирования.

Формально циклическое матричное кодирование может быть представлено следующим образом.

Пусть т, п и q — натуральные числа, причём т — длина раундового ключа, п — длина блока шифра, q — количество раундов, тогда К — {0, 1}'", N = {О, 1}", С = {0, 1}" — множества соответственно раундовых ключей, блоков данных (или открытых текстов) и блоков шифртекстов, и пусть также

у: U х К -* U,

\|) - функция МРК со свойством обратимости: для любых и, v 6 U и к € К, если и Ф v, го у(и, к) Ф y(v, к). Это свойство характеризует функцию как у ': U х К—* U, у~'(н, к) = v, если y(v, к) = и.

Зададим функцию Ф: X х fC N, положив Ф(хь кь ..., kr) = N, где N вычисляется итеративно как iV = ur, и; v i = 1,2, ...,ги щ, - х. Функция

Ф является функцией r-раундового шифрования, А, — раундовым ключом /-го раунда.

Функция обладает свойством обратимости:

Ф[хьк1.....к,) = N=> Ф~'(Л/, к,.....кг)

Ф'НЫь ки ..., кг) = 1/о, им = ki), i = r,r-1,..., 1; ur = у.

Таким образом, множества К, X, Y и функция Ф~' образуют г-раундовый итеративный блочный шифр

Ф = (х, N, К, ф,

в котором ф — есть функция раундового шифрования.

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

1

Результаты экспериментальных исследований приведены на рис. 5а.

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

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

На рис. 56 приведен график, характеризующий лавинный эффект для перестановочного шифратора. Следует отметить, что наибольшее значение лавинного эффекта обеспечивается при числе раундов примерно равном половине длины входного вектора. Отсюда необходимое число раундов является ограниченной величиной и лавинный эффект не зависит от увеличения их количества после указанного выше предела.

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

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

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

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

Матричный шифр

100%

40%

а)

0 1 2 3 4 5 6 Раунд кодирования

Перестановочный шифр

70%

0 1 2 3 4 5 Раунд кодирования

Рис. 5 Графики, характеризующие лавинные эффекты

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

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

На рисунке 7 под В° понимается количество циклов, которые формируются для матричного и перестановочного шифраторов по значению

подключа К. Для оценки времени шифрования с помощью композиционного шифра Г необходимо учесть кроме времени самого матричного кодирования tk, время на раундовые перестановки £рП! число цикл-раундов, количество больших циклов С. Отсюда

Т = % + 1рп) * 1/2 ■ С,

здесь tpn = 1ХП * к', где - время одной блочной перестановки,

С -к'тпосИ/2.

Рис. 7 Структурная схема композиционного шифрования/дешифрования.

Вероятность появления некоторого шифркода для рассматриваемого циклического композиционного шифра для одного большого цикла составит

2П(1+2) \0gCn

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

кодируемого числа (входного двоичного вектора). Количество больших циклов лежит в пределах половины длины входного вектора (1/2) поэтому значение подключа к' должно быть приведено к этому интервалу к' = к mod 1/2, это же значение определяет число циклов раундового шифрования.

Ниже представлена одна из таблиц (табл.1), полученных в ходе проводимых экспериментов.

Таблица 1

Номер большого цикла 1 2 3 4 5 6

Число изменений в шифркоде б 6 8 9 10 12

Длина входа 10 13 15 18 19 23

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

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

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

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

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

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

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

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

Разработан комплекс программ системы моделирования, включающий в

себя:

- программу определения ранга веса десятичного числа без перевода его в двоичный код;

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

- программу шифрования с помощью различных перестановок и матрично-рангового кодирования;

- программу позволяющую исследовать стойкость с помощью лавинного эффекта;

- программу двухуровневого композиционного шифрования текстовых данных.

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

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

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

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

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

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

2. На основе метода матрично-алгоритмического кодирования разработаны модели схемных решений по обнаружению не менее двух ошибок в передаваемых данных и созданы условия для прогнозирования при их передаче по каналам связи с ошибками.

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

4. Предложен рекурсивный способ и алгоритм вычисления стандартного двоичного представления чисел без процедуры генерации кода за счет одной операции деления с остатком и порядка 1о§2 N сложений, обладающий простотой реализации и высокой скоростью.

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

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

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

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

В изданиях из перечня ВАК:

]. Смагин A.A., Смикун П.И., Терентьева Ю.Ю. Алгоритм помехоустойчивой передачи потока данных. // Известия Самарского научного центра РАН. Специальный выпуск. Четверть века изысканий и экспериментов по созданию уникальных технологий и материалов для авиаракётостроения. УНТЦ-ФГУП ВИАМ - Самара. Изд-во Самарского научного центра РАН, 2008. -ТА, №3. С.96-99.

2. Смагин A.A., Смикун П.И. О возможности совмещения функций шифрования и контроля ошибок в системе кодирования. // Автоматизация процессов управления. Ульяновск. ФНПЦ ОАО «НПО Марс», 2010,- №3 (17).- С. 18-22.

3. Смагин A.A., Смикун П.И., Терентьева Ю.Ю. Об одном способе построения блоковых кодов. // Известия Самарского научного центра РАН. Специальный выпуск. Четверть века изысканий и экспериментов по созданию уникальных технологий и материалов для авиаракетостроения. УНТЦ-ФГУП ВИАМ -Самара. Изд-во Самарского научного центра РАН, 2008. -Т.4, №3. - С.99-102.

В других изданиях:

4. Смагин A.A., Смикун П.И., Терентьева Ю.Ю. Обеспечение помехоустойчивости при кодировании матрично-ранговым методом. Труды девятой международной научно-технической конференции «Проблемы техники и технологий телекоммуникаций» - ПТиТТ-2008. Казань, - 2008. С.30-33.

5 Смагин A.A., Липатова C.B., Смикун П.И., Мельниченко A.C. Методика построения специализированных АС на базе SOA. // Автоматизация процессов управления -. Ульяновск: ФНПЦ ОАО «НПО Марс», 2009,-№3 (17).-С.44-51.

6 Смагин A.A., Смикун П.И. Моделирование процесса передачи данных на основе синхронизации передающего и приемного устройств. // Автоматизация процессов управления. Ульяновск: ФНПЦ ОАО «НПО Марс», 2009, - №3 (17).- С. 14-18.

Подписано в печать 25.02.2011. Формат 60x84/16. Усл. печ. л. 1,0. Бумага книжно-журнальная. Тираж 100 экз. Заказ № 16 !$0

Отпечатано с оригинал-макета в Издательском центре Ульяновского государственного университета 432000, г. Ульяновск, ул. Л. Толстого, 42

Введение

1. Анализ и проектирование матричных систем преобразования кодов

1.1 Разработка подхода к алгоритмическому кодированию в числовом 11 поле матрицы

1.1.1 Анализ систем матричного кодирования и их применение

1.1.2 Кодирование текста с использованием специальной матрицы А

1.1.3 Кодирование биграмм текста с использованием 26 модифицированной матрицы В

1.2 Графо-матричный подход к кодированию целых чисел

1.3 Разработка алгоритма матричного кодирования на основе 37 модифицированной матрицы паскаля

1.4 Организация декодирования матричных кодов

1.5 Обеспечение биективности матричного кодирования

1.6 Выводы

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

2.2 Обнаружение и исправление ошибок

2.3 Использование блоковых кодов

2.4 Разработка схем контроля и исправления ошибок матрично- 71 ранговым кодированием

2.5 Выводы

3. Разработка систем шифрозащиты на основе матричного преобразования данных

3.1 Задачи построения скоростных шифров

3.2. Исследование шифрующих свойств циклического матричного 83 кодирования

3.3. Разработка схем и алгоритма шифрования и дешифрования на базе 95 управляемых перестановок и преобразования данных

3.4 Организация построения композиционного блочного шифра на 108 основе матричного кодера и управляемых перестановок

3.5 Выводы

4. Моделирование матричных систем кодирования/декодирования и 119 шифрования/дешифрования

4.1 Модель совмещения функций контроля ошибок и шифрования по 119 зашумленному каналу связи

4.2 Разработка и реализация двухуровневого композиционного 126 матричного шифрования текста

4.3 Моделирование матричной системы кодирования/декодирования и 137 шифрования/дешифрования

4.4 Выводы

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

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

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

Пропускная способность открытого канала зависит от скоростей работы шифратора, узла избыточного помехоустойчивого кодирования и от их соотношения [86]. Изыскание дополнительных возможностей повышения общей скорости этих операций может быть достигнуто несколькими путями: подбором методов кодирования и шифрования, обеспечивающих этот эффект, оптимальной организацией сочетания процедур избыточного кодирования и шифрования передаваемых данных (последовательность действий: «что раньше -что позже»?), а также рассмотрением возможностей совмещения этих операций в одном методе кодирования входных данных. Последний путь подразумевает, что методы кодирования должны обладать свойством многофункциональности [73]. Сочетание двух подходов в одном методе обеспечения целостности может дать существенный выигрыш в быстродействии: вместо двух последовательных процедур шифрования и помехоустойчивого кодирования вводится одна, которая реализует сразу обе функции.

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

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

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

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

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

Объектом исследования является системы передачи данных по небезопасным каналам связи с ошибками.

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

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

Для достижения цели решаются следующие составные задачи:

1. Исследование возможностей построения матричных кодов, обнаруживающих ошибки в каналах связи.

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

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

4. Разработка матричных моделей контроля и криптографической защиты данных.

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

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

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

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

2. На основе метода матрично-алгоритмического кодирования разработаны модели схемных решений по обнаружению не менее двух ошибок в передаваемых данных и созданы условия для прогнозирования при их передаче по каналам связи с ошибками.

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

4. Предложен рекурсивный способ и алгоритм вычисления веса стандартного двоичного представления чисел без процедуры генерации кода за счет одной операции деления с остатком и порядка 1о§2 N сложений, обладающий простотой реализации и высокой скоростью.

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

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

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

1. Подход и модели матрично-алгоритмического кодирования/ декодирования в виде диаграмм преобразования кодов заданного ранга (веса).

2. Модели схемных решений по обнаружению ошибок на базе матрично-алгоритмического кодирования данных для каналов связи с ошибками без введения избыточности в передаваемый код.

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

4. Рекурсивный способ и алгоритм вычисления веса (ранга) стандартного двоичного представления чисел без процедуры генерации кода за счет одной операции деления с остатком и порядка log2 N сложений.

5. Комплекс программ моделирования и анализа характеристик систем, создаваемых на базе матрично-алгоритмического преобразования данных и предложенных моделей.

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

Внедрение результатов работы. Результаты, полученные в ходе выполнения диссертационной работы, приняты к использованию в проектных работах ФНПЦ ОАО «НПО «Марс», г. Ульяновск, ОАО «Интелтех», г. Санкт-Петербург, ЗАО «Центрпрограммсистем», г.Тверь .

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

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

1. Девятая международная научно-техническая конференция. Проблемы техники и технологий телекоммуникаций. ПТиТТ-2008 (Казань, 2008).

2. Шестая международная конференция «Оптические технологии в телекоммуникациях. ОТТ-2008 (Казань-2008).

3. Научные семинары факультета математики и информационных технологий Ульяновского государственного университета, (г. Ульяновск, 2007-2010гг.).

142 4.4 Выводы

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

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

3. Разработана программная система моделирования, включающая в себя:

- программу определения ранга веса десятичного числа без перевода его в двоичный код;

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

- программу шифрования с помощью различных перестановок и мат-рично-алгоритмического кодирования;

- программу, позволяющую исследовать стойкость с помощью лавинного эффекта;

- программу двухуровневого композиционного шифрования текстовых данных.

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

143

Заключение

Исследования, проведенные в диссертационной работе, позволили сделать следующее заключение:

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

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

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

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

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

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

1. Айвазян CA., Буштабер В.М., Енюков И.С, Мешалкин Л.Д. Прикладная статистика: классификация и снижение размерности. М.: Финансы и статистика, 1989. 607 с.

2. Акимов O.E. Дискретная математика: логика, группы, графы. М.: Лаборатория Базовых Знаний, 2001. 352 с.

3. Альсведе Р., Бассалыго Л.А., Пинскер М.С. Двоичные коды, исправляющие локализованные ошибки и дефекты // Проблемы передачи информации, 1994.- 30, №2.- С. 10-13.

4. Алексеев Л. Е. Молдовян A.A. Молдовян H.A. Алгоритмы защиты информации с СЗИ НСД «СПЕКТР-Z» // Вопросы защиты информации. -2000. №3. - С. 63-68.

5. Анин Б.Ю. Защита компьютерной информации. СПб.: БХВ - Санкт-Петербург, 2000, 384 с. ил.

6. Аршинов М.Н., Садовский Л. Е. Коды и математика. М.: Наука. 1983.

7. Балашов Е.П., Негода В.Н., Пузанков Д.В., Смагин A.A., Смолов В.Б. Информационные системы: табличная обработка информации. Л., 1985, 184с.

8. Байков В.Д., Смолов В.Д. Специализированные процессоры: итерационные алгоритмы и структуры. М., 1985, 288 с.

9. Баричев С.Г. и др. «Основы современной криптографии». М.: «Горячая линия — Телеком», 2001.

10. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971.477 с.

11. Белкин А.Р., Левин М.Ш. Принятие решений: комбинаторные модели аппроксимации информации. М.: Наука, 1990. 160 с.

12. Биркгоф Г., Барти Т. Современная прикладная алгебра. М.: Мир, 1976. 243 с.

13. Блейхут Р. Теория и практика кодов, контролирующие ошибки.- М: Мир, 1986.- 576 с.

14. Боровиков В.П., Боровиков И.П. STATISTICA. Статистический анализ и обработка данных в среде Windows. М.: Инф. издат. дом «Филинъ», 1997, 608 с.

15. Бородин Л.Ф. Эквидистантные и другие оптимальные и близкие к оптимальным коды. // Радиотехника и электроника, 1960, т.5, вып.6. С. 1527.

16. Брассар Ж. Современная криптология. М.: Полимед, 1999.

17. Веников В.А. Теория подобия и моделирование. М.: Высшая школа, 1973.- 235 с.

18. Гайдышев И. Анализ и обработка данных: специальный справочник. СПб.: Питер, 2001. 752 с.

19. Галлагер Р. Теория информации и надежная связь. М.: Наука, 1974. с. 458.

20. Горин А.К., Поляков Г.А. Сравнительная оценка эффективности методов сжатия данных// Вопросы прикл. матем. и матем. моделир. / Днеп-ропетр. Держав, ун-т.- Днепропетровск, 1997.- С.36-38.

21. ГОСТ 28147-89. Системы обработки информации. Защита криптографическая. Алгоритм криптографического преобразования. М. Госстандарт СССР, 1989.

22. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. Пер. с англ. М.: Мир, 1998. 703 с.

23. Гуц Н.Д., Еремеев М.А., Молдовян A.A. Алгоритм формирования расширенного ключа на основе блоков управляемых перестановок // Вопросы защиты информации. 2001. - № 3. - С. 41-46.

24. Гуц Н.Д., Молдовян A.A., Молдовян H.A. Гибкие аппаратно-ориентированные шифры на базе управляемых сумматоров // Вопросы защиты информации. 2000. - № 1. - С. 8-15.

25. Гуц Н.Д., Изотов Б.В., Молдовян A.A., Молдовян H.A. Итеративный способ блочного шифрования. Патент РФ №2172075. МПК 7 Н 04 L 9/00,- Бюл. №22 от 10.08.2001.

26. Гуц Н.Д., Молдовян A.A., Молдовян H.A. Обоснование полноцикловых перестановок битов переноса в управляемых сумматорах гибких шифров. // Вопросы зашиты информации. 2000. - № 2. - С. 23-28.

27. Гуц Н.Д., Молдовян A.A., Молдовян H.A. Построение управляемых блоков перестановок с заданными свойствами // Вопросы защиты информации. 1999. -№4. - С. 39-49.

28. Гуц Н.Д., Изотов Б.В., Молдовян A.A., Молдовян H.A. Проектирование двухместных управляемых операций для скоростных гибких криптосистем. // Безопасность информационных технологий. 2001. -№2. - С. 1423.

29. Гуц Н.Д., Изотов Б.В., Молдовян H.A. Скоростной алгоритм шифрования SPECTR-H64. // Безопасность информационных технологий. -2000.-№ 4.- С. 37-50.

30. Гуц Н.Д., Изотов Б.В., Молдовян H.A. Управляемые перестановки с симметричной структурой в блочных шифрах // Вопросы защиты информации. 2000.-№ 4. - С. 57-65.

31. Джонсон Н., Лион Ф. Статистика и планирование эксперимента в технике и науке. Методы обработки данных. Пер. с англ. М.: Мир, 1980. 610с.

32. Домашев A.B., Грунтович М.М., Попов В.О., Правиков Д.И., Прокофьев И.В., Щербаков А.Ю. Программирование алгоритмов защиты информации. М.: «Нолидж», 2002. -416 с.

33. Зубов А.Ю. Криптографические методы защиты информации. Совершенные шифры: Учебное пособие // А.Ю. Зубов.-М.: Гелиос АРВ, 2005 -192 с.

34. Капитанчук В.В. Перспективы разработки скоростных блочных шифров //Сборник тезисов материалов конференции УлГУ «Практика и перспективы применения ИЛИ (CALS) технологий в производстве », г. Ульяновск, 9-10 сентября 2004 г. С. 123-125.

35. Капитанчук В.В. Шифраторы для защиты информации // Научно-технический сборник. Ульяновск: УВВТУ, 2005. -№ 37. С. 107 - 116.

36. Кнут Д.Э. Искусство программирования, том 1. Основные алгоритмы. Пер. с англ. М.: Издат. дом «Вильяме», 2000. 720 с.

37. Кнут Д.Э. Искусство программирования, том 2. Получисленные алгоритмы. Пер. с англ. М: Издат. дом «Вильяме», 2000. 832 с.

38. Кнут Д.Э. Искусство программирования, том 3. Сортировка и поиск. Пер. с англ. М.: Издательский дом «Вильяме»", 2000. 832 с.

39. Колмогоров А.Н. Теория информации и теория алгоритмов. М.: Наука, 1987, 303с.

40. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. М.: МЦНМО, 2000. 960 с.

41. Кричевский Р.Е. Связь между избыточностью кодирования и достоверностью сведений об источнике // Проблемы передачи информации, 1968, 4, 3.- С.48-57.

42. Кричевский Р.Е. Сжатие и поиск информации.- М.: Радио и связь. 1989.168 с.

43. Кугураков B.C. Оценки избыточности кодов с мажоритарным и перестановочным декодированием // Дисс. на соиск. уч. степ, к.ф.-м.н./ М., 1981.

44. Кулаичев А.П. Компьютерный контроль процессов и анализ сигналов.-М.: Информатика и компьютеры, 1999.- 330 с.

45. Мастрюков Д. Алгоритмы сжатия информации. Часть 1. Сжатие по Хаффмену//Монитор. .1993, №8.- С. 14-24.

46. Мастрюков Д. Алгоритмы сжатия информации. Часть 2. Арифметическое кодирование// Монитор, 1994, №1.- С.20-26.

47. Мастрюков Д. Алгоритмы сжатия информации. Часть 3. Алгоритмы группы LII Монитор, 1994, №2.- С. 10-18.

48. Молдовян A.A., Молдовян H.A., Вероятностные механизмы в недетерминированных блочных шифрах // Безопасность информационных технологий. М.: МИФИ, 1997, №3.- С.58-61

49. Молдовян H.A. Скоростные блочные шифры. С.-Пб., Изд-во СПбГУ, 1998.-230 с.

50. Молдовян H.A. Проблематика и методы криптографии. С.-Пб., Изд-во СПбГУ, 1998.-212 с

51. Молдовян A.A., Молдовян H.A., Псевдовероятностные скоростные блочные шифры для программной реализации // Кибернетика и системный анализ. Киев, 1997, №4.- С. 133-141

52. Молдовян H.A., Молдовян A.A., Еремеев М.А. Криптография: от примитивов к синтезу алгоритмов. - СПб.: БХВ-Петербург, 2004.- 448 с.

53. Молдовян A.A., Молдовян H.A. Метод скоростного преобразования для защиты информации в АСУ // Автоматика и телемеханика. 2000. - №4. -С. 151-165.

54. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки.- М.: Мир, 1976.594 с

55. Сагалович Ю.Л. Алгебра, коды, диагностика.- М.: Мир, 1993.- 364 с.

56. Смагин A.A., Капитанчук В.В. Разработка двухуровневого композиционного шифра // Ученые записки Ульяновского государственного университета. Серия «Информационные технологии». Ульяновск, 2005. -№ 2. - С. 46-52.

57. И.Л. Ерош, В.В. Скуратов. Адресная передача сообщений с использованием матриц над полем GF(2) / Проблемы информационной безопасности. Компьютерные системы. 2004, №1, с. 72-78.

58. Смагин A.A., Смикун П.И. О возможности совмещения функций шифрования и контроля ошибок в системе кодирования. // АПУ. Ульяновск. ФНПЦ ОАО «НПО Марс», 2010, №3 (17), стр. 18-22.

59. Смагин A.A., Липатова С.В., Смикун П.И., Мельниченко A.C. Методика построения специализированных АС на базе SOA. // АПУ. Ульяновск.

60. ФНПЦ ОАО «НПО Марс», 2009, №3 (17), стр.44-51.

61. Смагин A.A., Смикун П.И. Моделирование процесса передачи данных на основе синхронизации передающего и приемного устройств. // АПУ. Ульяновск. ФНПЦ ОАО «НПО Марс», 2009, №3 (17), стр. 14-18.

62. Смагин A.A., Терентьева Ю.Ю, Капитанчук В.В., Метод построения криптографического примитива. // Международная конференция «Информационные технологии и безопасность» (ИТБ-2004). Украина, Крым, Партенит, 22-26 июня 2004г. С. 101 110.

63. Соколов A.B., Степанюк О.М. Защита от компьютерного терроризма. Справочное пособие. БХВ-Петербург, Арлит, 2002. 496 с.

64. Тараканов В.Е. Комбинаторные задачи и (0,1) матрицы. М., Наука, 1985.

65. Терентьева Ю.Ю. О некоторых областях применения метода матрично68