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

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

ТИТОВ Алексей Иванович

РАЗРАБОТКА ЭВОЛЮЦИОННЫХ МЕТОДОВ И АЛГОРИТМОВ КОДИРОВАНИЯ-ДЕКОДИРОВАНИЯ ДАННЫХ В КОМПЬЮТЕРНЫХ

СИСТЕМАХ

Специальность 05.13.17 - Теоретические основы информатики

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

* ТК 2013

Белгород 2013

005543132

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

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

доктор технических наук, профессор, заслуженный деятель науки Российской Федерации

Официальные оппоненты: Еременко Владимир Тарасович,

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

Чижов Илья Игоревич,

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

Ведущая организация: Федеральное государственное бюджетное

образовательное учреждение высшего профессионального образования «Юго-Западный государственный университет» (г. Курск)

Защита состоится 25 декабря 2013 года в 14 часов 00 минут на заседании диссертационного совета Д 212.015.10 на базе ФГАОУ ВО «Белгородский государственный национальный исследовательский университет», по адресу: 308015 г. Белгород, ул. Победы, 85, корп. 15, ауд. 3-8.

С диссертацией можно ознакомиться в научной библиотеке ФГАОУ ВО «Белгородский государственный национальный исследовательский университет», по адресу: 308015 г. Белгород, ул. Победы, 85.

Автореферат разослан «25» ноября 2013 г.

Ученый секретарь диссертационного совета кандидат технических наук, старший научный сотрудник

Белов С.П.

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

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

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

В настоящее время особое внимание отводится секретному кодированию информации для обеспечения безопасности баз данных, хранимых на серверах. Вопросам секретного кодирования посвящены многочисленные публикации в России и за рубежом. Значительный вклад в развитие теории секретного кодирования внесли К. Шенон, А. Тьюринг, Б. Шнайер, Венбо Мао, С. Баричев, В. Герасименко и другие.

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

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

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

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

использование этого представления в разработке эволюционных алгоритмов кодирования-декодирования данных.

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

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

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

3) исследовать зависимость стойкости секретного кода от способа разбиения кодированных данных на группы с вложенными подгруппами;

4) разработать эволюционные методы секретного кодирования данных с использованием генетических алгоритмов, основанных на предложенной математической модели;

5) разработать комплексы программ реализации алгоритмов в компьютерных системах различной архитектуры;

6) разработать метод экспериментальной оценки стойкости кода к несанкционированному декодированию.

Объект исследования: алфавитно-цифровая информация, хранимая в базах данных на серверах компьютерных систем.

Предмет исследования: методы кодирования информации в виде данных компьютерных систем.

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

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

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

2. Математическая модель секретного кодирования на основе преобразований в линейном векторном пространстве.

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

4. Методика сравнительной оценки стойкости кодов.

Практическая значимость работы.

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

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

• Использование разработанного программного обеспечения в филиале Федерального казенного учреждения «Налог-Сервис» ФНС России в

Белгородской области и в ЗАО «БОШЕ» (г. Старый Оскол) (подтверждено актами, приведенными в прил. 3);

• использование разработанных методов секретного кодирования в учебном процессе Губкинского филиала БГТУ им. В.Г. Шухова, в курсе «Защита компьютерной информации» по направлению подготовки бакалавров по специализации 230100.62 - информатика и вычислительная техника.

Область исследования. Содержание диссертации соответствует паспорту специальности 05.13.17 - Теоретические основы информатики по следующим областям исследований:

п.З. Исследование методов и разработка средств кодирования информации в виде данных. Принципы создания языков описания данных, языков манипулирования данными, языков запросов. Разработка и исследование моделей данных и новых принципов их проектирования;

п. 13. Применение бионических принципов, методов и моделей в информационных технологиях;

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

Связь с научными и инновационными программами. В рамках работы получен грант имени «Владимира Раевского» номинации Зворыкинский проект в рамках форума «Нежеголь-2011» за разработку метода секретного кодирования данных для защиты баз данных интернет-издательства «Я — в науке».

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

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

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

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

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

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

Апробация результатов диссертационного исследования.

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

управление и информатика», г. Белгород (2012 г.); «Информационные технологии в науке, образовании и производстве», г. Орел (2012 г.); Второй Международной научно-технической конференции «Компьютерные науки и технологии», г. Белгород (2011 г.); 11-й Международной научно-технической конференции «Проблемы информатики и моделирования», Харьков-Ялта (2011 г.).

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

Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, библиографического списка (106 наименований) и 7 приложений. Работа изложена на 120 страницах, иллюстрируется 45 рисунками.

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

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

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

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

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

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

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

/1 0 ... Оч

Х = (Х1Х2...Хп)1°,1 , ? =*•*, (1)

\0 0 •■■ V

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

Двоичный код У=( У] У2... УП)^Х=(Х1Х2...ХП) в двоичном алфавите образуется перестановкой компонент двоичного вектора X. Предложено, управляя матрицей Е, путем вращения единичных двоичных векторов формировать матрицу перестановок. Так как вращение Е должно приводить к аддитивной группе, элементы которой являются также единичными векторами, то минимальный угол поворота Д(2 определяется исходя из умножения Е на 2±], знак определяется направлением вращения - в сторону значения единичного вектора 2° или в сторону значения единичного двоичного вектора 2" (п - длина двоичного вектора).

Произвольный угол поворота С =]Д(2 где А(} = —.

А так как длина единичного двоичного вектора e¡ остается неизменной, то вращение Е представляется как

Р1=соз±1фУтос1п. (2)

Матрица перестановок может формироваться не только поворотом на один и тот же угол (3 всех единичных векторов с,, но и попарным вращением отдельных векторов е] и еш в противоположных направлениях, что представляется в виде

(соя 7 ) е1) той п (сов-' ) ег) той п, / = т — I > 0,1, т = 1, п .

^ (3)

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

Матрица Е может быть представлена клеточной матрицей с элементами Е1, \ = 1,к, каждый из которых представляет число в системе счисления 2Э. Каждый элемент Е1 представляет подгруппу Е, к которой применимы преобразования (2), (3), формирующие матрицы перестановок каждой подгруппы. А так как может выполняться вращение группы Е и вращение вложенных в нее подгрупп, то вращение группы с вложенными подгруппами представляется в виде

Из = (4)

Р4 = Р10')(Р2а т)Е% (5)

Р5 = Р2 (7, т)^ (/)£')<

Рб = Р2(г1,т1)(Р2(г2,т2)яО,

(7)

где j,k - углы поворота при соответствующих вращениях;

_ пары вращающихся единичных векторов в соответствующих

вращениях.

Использование (4), (5), (6), (7) выполняется только при разделении Е минимум на две подгруппы с числом двоичных элементов в каждой: п>25, 8>2.

При клеточном представлении Е каждый из клеточных элементов может задавать отдельное слово X, представляемое в виде (1), которое принимает вид

/1 0 ... Оч

Х = (Х1Х2...Хк) Р . 1 .. ? ]=*(Е*Д),Д = 1, (8)

\0 0 ••• 1/

где X - число в системе счисления с основанием М, X1 - символы допустимые в этой системе счисления; Е*Я — матрица перестановок размером к*к. Как и при двоичном исходном векторе, управление матрицей Е позволяет в соответствии с (2), (3) использовать вращение группы X с вложенными подгруппами X1,1 = 1, к, формируя матрицу перестановок в виде (4), (5), (6), (7).

Так как перестановки определяются вращением матрицы Е, то допустимо каждый компонент X1 представить клеточной матрицей с компонентами X} размером к;*к; и считать, что X представляется числом разрядностью Р= к;*к. Это приводит (8) к представлению в виде

/1 0 ... 0

у_ (у1 у1 у1 у2у2 у2 у/сук ук \ / 0 1 0

Л — ^Л1Л2 ... Лк1Л1Л2 —Лк1 ...Л1Л2 ■■• лк1) I ; •.. :

\0 0 - 1

где группа Е из единичных векторов теперь представляется матрицей размером кк^кк]. К матрице Е применимы все введенные ранее вращения (2), (3), (4), (5), (6), (7). Это позволяет производить не только перестановки, но и делать замены по задаваемой подгруппе элементов с изменением количества элементов в подгруппе. Представляя X} вложением подгруппы, получаем множество перестановок и замен, которые целесообразно ограничить. При использовании подгруппы, задаваемой основанием системы счисления 2я, величину Б определим из 1т;п=28, где 1тш представляет максимальное целое в разрядной сетке компьютера и соответствует двум словам двоичного алфавита. Это принципиальное отличие в представлении процесса кодирования от существующих, так как преобразованию подвергаются два слова, одно их которых может являться ключом, который в процессе кодирования также изменяется. В процессе кодирования данных не только ключ используется в преобразовании исходного слова, но и слово используется в преобразовании ключа.

Следует отметить, что после выполнения перестановок и замены, полученное слово X = (Y^Y-} ... Y^Y^Y^ ... Y^ ... Y^Yf ... y£ ) переводится в систему с основанием 2s и представляется вектором

Y^Y'Y2... YVX=(X'X2. (Ю)

К сформированному вращением вектору Y могут быть добавлены с использованием арифметического и логического сложений некоторые числа А], А2. При использовании результата перестановок в виде (10) А[ представляется клеточной матрицей с элементами А1Ь А12, ...,Aik, в то время как двоичный вектор А2 = А2 суммируется в подгруппах с двоичным представлением чисел.

В подгруппе с двоичным кодированием один шаг преобразования кода X в секретный код Y представляется в виде:

r = X(Fi(Fj+pA1©rA2)), (11)

где F;, Fj соответствует операциям вращения в (4), (5), (6), (7).

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

Y(t) = Y(t - l)(F,(t)(F,(t) + pAi ф rA2)) , (12)

где Fj(t), Fj(t) определяется выражениями (4), (5), (6),(7), использующими на t-ом шаге кодирования; Y(t-l) определяется этими же выражениями на предыдущем шаге кодирования, F;(0), Fj(0) определяется выражением (11), р,г = {0,1}, Ai=const, в частном случае 0, А2 — случайная величина.

Из существования обратных, по отношению к прямым (2), (3), преобразований вытекает существование обратных преобразований по отношению к прямым (4), (5), (6), (7). Это позволяет математическую модель декодирования секретных данных представить в виде

Y(T - 1) = Y(T)(F"1 (Т)(F"1 (Т) - рАг ® rA2)) (13)

T=N, N-1,...,0, Y(T)=Y(t=N) в (12).

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

Для четырехразрядного кода строится матрица Н, которая объединяется с Е. Элементы этой матрицы определяются через элементы матрицы Е на основе кратности корректируемой ошибки, а число дополнительно вводимых элементов определяется требуемым расстоянием Хэмминга. И для четырехразрядного кода при коррекции однократной ошибки прямоугольная матрица Н имеет размер 4*3, а прямоугольная матрица, полученная объединением Е и Н, имеет размер 4*7. А так как в предложенной модели кодирования исходный вектор m может быть разбит на подгруппы длиной 4 бита, то случайным образом задается подгруппа и

изменяемый в ней бит. Изменяемый бит определяет двоичный вектор, который в коде, полученном на Т,+]-м шаге декодирования, должен быть изменен в соответствии с (11) на Т;-м шаге декодирования.

Метод кодирования данных с использованием предложенной математической модели требует расширения кодируемых данных X посредством дополнительных данных У. Таким образом, что:

г=ХиУ, ХПУ = 0. (14)

При этом длина слова Ь2=ЬХ+ЬУ+ЬХ, где Ьх - длина слова X; Ьу -длина слова У; Ьх — длина дополнения, выбранного из условия

Ь2=2п, п>2. (15)

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

Использование (4), (5), (6), (7) для формирования перестановок при формировании закрытого кода в соответствии с (12) и порядка применения операторов определяет эволюционные методы кодирования данных; так, при приоритете оператора, заключенного в скобки в преобразовании (5) и кодировании в соответствии с (12), метод кодирования состоит в следующем:

1) считать кодируемое сообщение;

2) в соответствии с (14), (15) получить код длины Ь2;

3) в полученном коде задать число рядом стоящих разрядов, которые будут одновременно участвовать в обмене, число этих разрядов выбирается из 2к, к = 1,2,3,

4) задать пары, участвующие в перестановках;

5) задать моменты, при которых вводится арифметическое или логическое сложение;

6) выполнить преобразования, заданные оператором Б(]);

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

пар;

8) в случае несоответствия момента окончания преобразования повторить, начиная с п. 4;

9) изменить по заданному закону число разрядов, участвующих в перестановках;

10) если не все заданные состояния разрядов в перестановках выполнены, вернуться к п. 3;

11) задать последовательность значений углов поворота;

12) выполнить преобразование, задаваемое значением j в

13) если не вся последовательность принимаемых j значений выбрана, вернуться к п. 11;

14) выдать закрытые значения кодируемых слов X.

В соответствии с описанным методом кодирования на рис. 1 приведен алгоритм секретного кодирования данных в системе счисления с основанием 2. ...........................

( Начало !

V__________________________________..У

Считать кодируемое сообщение |

Сформировать код длины1г

---Ч................................._..... Произвести разбиение на } входящий код 2" блоков

Задать пары участвующие в перестановках

......................

Задать моменты ввода арифметического и логического сложения р,г

1

Выполнить преобразование, сформировать новые пары

----- Достигнуто"""'...... заданное число """—перестановок._____•—"

Изменить число разрядов участвующих в перестановке

_ ....." Все заданные ------ с^" перестановки выполнены

_

Задать последовательность углов поворота

Выполнить преобразование заданное значением \

.....' Все —..... —повороты — выполнены ____________

Формирование закрытого кода

( Конец ч)

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

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

При кодировании чисел, представленных двоичным кодом, размер рекомендуется выбирать равным 32*64, что соответствует 32 словам по 64 бита. Каждое из слов разбивается на две части А и В по 32 бита. После этого в соответствии с выбранным Б; организуется перестановка между А и В по 16 бит, затем по 8 , по 4, по 2 и по 1 биту.

После этого перестановка организуется в А и В. На задаваемом шаге выполнения перестановок вводится случайное изменение в А и В. Если генератором случайных чисел в А выбран КА-й группе РА, то в группе В выбирается Кв и г в по некоторому ззкону, например!

Кв=(Кд+2) mod 4; РВ=(РА+19) mod 32 После случайного изменения кода в соответствии с (12) на шаге, задаваемом в закрытом ключе, ключ расширяется введением полей КА и РА, и выполняется преобразование в соответствии с (12) при р=г=0. Преобразования продолжаются до заданного шага, также задаваемого в закрытом ключе. Результатом этих преобразований является формирование секретного кода, состоящего из количества символов, содержащихся в 64-битном слове. При необходимости могут быть увеличены количество слов и их длина. Предложенные методы секретного кодирования двоичных данных обеспечивают повышенную стойкость кода по сравнению с известными алгоритмами, так как даже при наличии множества соответствующих закрытых и открытых текстов выявление зависимостей в них невозможно из за применения генератора случайных чисел.

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

Блочное кодирование основано на представлении блока в виде (8) с элементами X', представленными в системе счисления 2s. При заданной длине Lz=Lx=Ly определяется значение S. Как и при двоичном кодировании, Lz разбивается на две группы, и по тем же правилам, что и для двоичных кодов, организуется перестановка в группах А и В слов в системе счисления с основанием 2s. В отличие от перестановок в двоичной системе счисления обмен организуется при фиксированной длине группы из К разрядов слова в системе счисления 2s. После выполнения перестановок увеличивается в два раза количество слов с уменьшенной в 2 раза их размерности, и, как и ранее, в соответствии с выбранным преобразованием Fb организуется обмен группами между А и В. Данный обмен завершается при достижении в подгруппе длины, соответствующей 32 словам разрядностью 64 бита, либо 64 словам разрядностью 128 бит. Далее, в каждой из таких подгрупп организуется процесс преобразования битовых данных в закрытый код в соответствии с ранее приведенным методом. В закрытом ключе хранится то же, что и при кодировании двоичных данных. Логическое сложение или другая заданная операция используется только при достижении S наперед заданного значения. Процесс декодирования осуществляется выполнением в обратном порядке тех же операций с использованием обратного преобразования (13) и содержимого закрытого ключа.

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

Расширение родительской популяции соответствует изменению количества групп N длиной 25 при изменениях Б. При 8=тах, задается количество групп N1. Определяется длина кода в системе счисления 2я, которая задается 1г = Ы125. Далее меняется Б в соответствии с 82=81-1 и N в соответствии с Ы2=2Ы1. Введение логического сложения со случайным значением выполняется при достижении 8 заданного значения и соответствует операции мутации. Реализованы генетические алгоритмы при использовании в кодировании ключа У в соответствии с (11). Эволюционный метод при реализации генетическим алгоритмом представлен блок-схемой приведенной на рис. 2.

; Начало )

Генерация родительских

популяций

.........................................._.......*..................................................

Разделение популяции на пары

Образование потомков »

.......—"Выполнить"-.....

случайное изменение ' '......потомках,,-------------

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

Задать новую популяцию

............~..... Выполнено ...........

^заданное число формирований" --.„. поколении

? Формирование закрытого кода

1 Конец )

Рис. 2. Блок-схема генетического алгоритма кодирования данных

В соответствии с алгоритмом в генетическом алгоритме нужно выполнить:

1) генерирование исходной популяции, представляемой разбиением на подгруппы исходного кода;

2) задание пар в словах А, В, участвующих в обмене;

3) выполнение обмена между А и В;

4) проверка условия «Задано в ключе случайное изменение», если да, то п. 5, иначе п. 6;

5) случайно изменить биты в А или В либо в А и В;

6) потомков полученных в результате обмена принять за новую популяцию;

7) проверить условие «Соответствует ли число поколений заданному числу в ключе», если нет, то вернуться к п. 2;

8) завершить формирование секретного кода.

Один из раундов работы генетического алгоритма представлен на рис. 3.

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

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

Вычисление начального смещения ключа кодирования (рис. 4).

кеу1еп§<М а

КЛЮЧ ключ КЛЮЧ ключ ключ ключ ключ ключ

Открытый файл

—---tail

filelength

Рис. 4. Вычисление смещения ключа кодирования

Д= filelength mod keylength, где filelength - количество байт в открытом файле, keylength - количество байт в ключе кодирования, А - величина смещения ключа кодирования, tail -байты ключа кодирования, переходящие на следующий уровень.

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

keyi+keyiength = keyj{<p} tail;, i < Д (14)

keyi+keyiength = keyj{<p} кеу(_д, i > Д'

где ксу, - ¡-тый байт ключа кодирования, 1аП; - ¡-тый байт, перешедший на следующий уровень расширения; Д - величина смещения ключа кодирования; {<р} - заданная операция по заданному модулю. Для расширения ключа второго уровня и последующих разработаем общую математическую модель:

кеу(п)1+Дп = кеу(п - 1)1{<р} ъШр 1 < Дп_! (15)

кеу(п)^Дп = кеу(п - 1),{ф} кеу(п),, 1 > Дп_!' где п - номер уровня расширения; кеу(п), - ¡-тьгй байт ключа кодирования на уровне расширения п, - ьтый байт, перешедший на следующий уровень расширения; Дп - величина смещения ключа кодирования уровня п; {ф} -заданная операция по заданному модулю.

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

Блок-схема алгоритма, реализующего метод расширения ключа,

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

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

Примеры использования генетического алгоритма кодирования-декодирования данных с заданным количеством селекций, в ходе которых не выполняется мутация, приведены на рис. 6 (кодирование) и на рис. 7 (декодирование).

А,° А/ В,0 Ва-

1000 1101 1011 0110

В2° ¥ А2° В,0

1000 оно С2° 1101 1011

А,1 А,1 л'

1000 0110 1101 1011

-V / В,1 г А,1 В21

1101 1000 С.1 0101 1011

А,2 А,2 л

1000 0011 1000 0101

Рис. 6. Работа генетического алгоритма кодирования данных

Кодирование данных:

1) считываем первый и второй биты закрытого ключа. В зависимости от значений закрепляем блоки данных: «О» закрепляем первый блок слова, «1» закрепляем второй блок слова. Здесь первый бит информации отвечает за первое слово, второй бит - за второе слово. Оставшиеся блоки записываем из первого слова в третью позицию, из второго слова - в четвёртую;

2) делаем скрещивание С1ФС2, записываем результат в Б,;

3) считываем третий бит закрытого ключа, если:

«О» считываем С] после точки кроссовера, С2 — до точки кроссовера; «1» считываем С1 до точки кроссовера, С2 - после точки кроссовера; записываем результат в Б2;

4) если количество поколений не удовлетворяет критерию, то повторить шаг 1-3, при этом ключ кодирования двигается дальше.

Ключ кодирования: 011100. Входные слова: первое слово (10001101), второе слово (10110110).

Количество поколений для достижения стойкости: 2.

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

А,0 А2° В° В 2°

1000 ООН 1000 0101

У2° ^ Х,° / / Х2°

1101 1000 Сг° 0101 1011

V В;1

0101 1101 1000 1011

"г X!1 X*1 ,

1000 0110 С21 1101 1011

Л2 ><

1000 1101 1011 0110

Рис. 7. Работа генетического алгоритма декодирования данных

Декодирование:

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

Если бит имеет значение «О», то В]0 - во второй блок слова С|(У2), а В2° - в первый блок слова С2(Х|);

Если бит имеет значение «1», то В10 - в первый блок слова С[(У[), а В2° - во второй блок слова С2(Х2);

2) в зависимости от значения считанного бита ключа на предыдущем шаге проводим восстановление предка по генотипу потомков.

Если «О», то У,=(А,0®Х,); Х2=(А2°фУ2). Если «1», то У2=(А2°фХ2); Х|=(А,°фУ|).

3) считываем следующие два бита ключа, в зависимости от их значений меняем блоки местами (табл. 1).

Таблица 1.

Значение бит ключа

Значение бит ключа Запись блоков информации

00 А,=У, а2=х, В,=У2 В2—Х2

01 А,=У, а2=х, В,=х2 В2=У2

10 А,=Х, А2=У, В,=у2 в2=х2

11 А,=Х, А2=У, В1=Х2 В2=у2

4) Если количество поколений не удовлетворяет критерию, то повторить шаг 1-3, при этом ключ кодирования двигается дальше.

Ключ кодирования: 011100.

Входные закрытые слова: первое слово (10000011),

второе слово (10000101).

Количество поколений для достижения стойкости: 2.

Предложены рекомендации для разработчиков алгоритмов кодирования на базе эволюционного метода, в которых отмечено, что работа ведется с неравномерными двоичными кодами, то есть размер одного блока данных находится в отрезке от 8 до 65518 бит. Минимальный размер 8 бит связан с современными реалиями архитектуры вычислительной техники (стандарт хранения 1 байт = 8 бит). Так же стоит обратить внимание на то, что при кодировании 8 бит информации с применением технологии контрольных бит добавляется 4 бита дополнительной информации (позиции контрольных бит 1, 2, 4, 8 соответственно). Это составляет 50% от размера исходных данных. В то же время при кодировании 65518 бит добавляется 17 бит дополнительной информации, что составляет 0,02595% от исходного содержания сообщения. По среднестатистическим данным, размер добавочной информации составляет 0,0916..0,0488% от первоначального размера кодируемой информации.

Верхний предел размера блока данных выбран из расчета, что для хранения и обработки в оперативной памяти ЭВМ для каждого блока выделяется участок в восемь раз больше размера исходных данных (при максимальном размере блоков данных 128 килобайт).

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

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

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

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

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

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

Начало

Копируем открытый файл ! Кодируем исходный открытый файл I

Изменяем 1 бит в копии oi ирыгого файла Кодируем копию открытого файла

Проводим амапиз двух закрытых файлов на

Размеры .......—.

файлов соответствуют filesizel ____________________

эксперимент считать недействительным

Есть — различия в частототных "" характеристиках

Г

Разница в 1 бит

! подсчитать количество байт i с раз/) «чны ми ча с юшыми xapa»f©p»ci иками

t

п..

эксперимент считать недействительным

Кодирование эквивалентное

Вычислить GAC

; Конец j

Рис. 8. Блок-схема алгоритма проведения эксперимента

Для DES у—16, для ГОСТ28147-89 у=16, для разработанного ПО кодирования-декодирования данных эволюционным методом критерий GAC не имеет точного значения, так как мутация может внести изменения в двоичный вектор, а может оставить существующий вектор без изменений (селекция не мутировавшего потомка), в общем случае у=256*В1С=256*0.5=128.

Первое изменение файла на 1 бит дало разницу в 182 байтах, второе изменение файла на 1 байт дало разницу в 201 байте.

Полученный критерий BIC лавинного эффекта для ПО кодирования эволюционным методом на основе предложенной математической модели имеет значение 0,4879120=0,5, что подтверждает равновероятность влияния бит входного файла на любой бит выходного в рамках кодируемого блока. Критерий GAC лавинного эффекта гораздо выше, чем у существующих алгоритмов секретного кодирования, и в частных случаях превышает математически рассчитанное значение у=256*В1С=256*0.5=128.

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

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

1. Обосновано использование бионических принципов в кодировании данных с целью обеспечения их секретности.

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

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

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

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

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

7. Разработана методика вычислительного эксперимента по оценке стойкости различных алгоритмов.

8. Установлено повышение стойкости разработанных алгоритмов по сравнению с DES и ГОСТ 28147-89 в 8 раз.

ОСНОВНЫЕ ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи в рецензируемых журналах из перечня ВАК

Титов А.И. Анализ алгоритмов шифрования, применяемых для предотвращения утечки информации с web-сервера / А.И. Титов, Н.И. Корсунов // Информационные системы и технологии, - 2010, -№ 6(62) ноябрь-декабрь, - С. 142-146.

Титов А.И. Метод расширения ключа для кодирования информации, передаваемой по каналу связи/ А.И. Титов, Н.И. Корсунов, Муромцев В.В. // Научные ведомости БелГУ,-2010,-№19(90), вып. 16/1,-С. 157-160.

Титов А.И. Модифицированный алгоритм шифрования данных/ А.И. Титов, Н.И. Корсунов //Информационные системы и технологии, - 2011, -№2 (64), - С.89-95.

Титов А.И. Повышение эффективности защиты информации модификацией шифра Вижинера/ А.И. Титов, Н.И. Корсунов //Научные ведомости БелГУ Серия: История Политология Экономика Информатика, -2010,-№7(78), вып. 14/1,-С. 171-175.

Титов А.И. Модифицированный блочно-итерационный метод шифрования и дешифрования данных / А.И. Титов, Н.И. Корсунов // Информационные системы и технологии, - 2012, - № 1(69) январь-февраль, -С. 107-114.

Титов А.И. Эволюционные методы кодирования данных, пример работы алгоритмов кодирования декодирования/ А.И. Титов, Н.И. Корсунов, К.И. Логачев //Научные ведомости БелГУ, Серия: История Политология Экономика Информатика,-2012,-№ 1(120), вып. 14/1,-С. 122-126.

Титов А.И. Обеспечение скрытности кодирования данных помехоустойчивыми кодами/ А.И. Титов, Н.И. Корсунов //Научные ведомости БелГУ, Серия: История Политология Экономика Информатика, -2013,-№8(151), вып. 14/1,-С. 112-117.

Титов А.И. Защита информации баз данных, хранящихся на удаленных серверах / А.И. Титов, Н.И. Корсунов //Журнал Вопросы радиоэлектроники, -2012, с. 180-186.

Титов А.И. Эволюционное кодирование данных / А.И. Титов //Журнал Вопросы радиоэлектроники, - 2013, с. 93-96.

Публикации в сборниках трудов научных конференций

Титов А.И. Модифицированный алгоритм скрытного кодирования данных / А.И. Титов, Н.И. Корсунов // КНиТ - 2011 : труды Второй Международной научно-технической конференции, 3-7 октября 2011. -Белгород: Изд-во НИУ БелГУ, 2011.

Титов А.И. Применение генетических алгоритмов в эволюционном методе кодирования (шифрования) данных /А.И. Титов // Сборник трудов международной молодежной конференции. Прикладная математика, управление и информатика, - 2012, - С.598-601.

Титов А.И. Эволюционный подход к скрытному кодированию хранимых данных/ Н.И. Корсунов, А.И. Титов // Тезисы одиннадцатой Международной научно-технической конференции «Проблемы информатики и моделирования», 26-30 сентября 2011. —Харьков: Цифрапринт, 2011.

Программы для ЭВМ

Свидетельство о государственной регистрации для программы для ЭВМ № 2010617605 «Программная система шифрования-дешифрования данных для хранения данных на стороннем Web-cepBepe», авторы: Корсунов Н.И., Титов А.И., 11 ноября 2010 г.

Свидетельство о государственной регистрации для программы для ЭВМ № 2011611604 «Блочно-итерационный алгоритм шифрования-дешифрования данных», авторы: Титов А.И., Корсунов Н.И., 17 февраля 2011 г.

Свидетельство о государственной регистрации для программы для ЭВМ № 2012619873 «Программный комплекс эволюционного кодирования-декодирования данных», авторы: Титов А.И., Корсунов Н.И., 31 октября 2012 г.

Титов А.И. Эволюционные методы кодирования данных, пример работы алгоритмов кодирования декодирования/ А.И. Титов, Н.И. Корсунов, К.И. Логачев //Научные ведомости БелГУ, Серия: История Политология Экономика Информатика,-2012,-№ 1(120), вып. 14/1,-С. 122-126.

Титов А.И. Обеспечение скрытности кодирования данных помехоустойчивыми кодами/ А.И. Титов, Н.И. Корсунов //Научные ведомости БелГУ, Серия: История Политология Экономика Информатика, -2013, - № 8 (151), вып. 14/1,-С. 112-117.

Титов А.И. Защита информации баз данных, хранящихся на удаленных серверах / А.И. Титов, Н.И. Корсунов //Журнал Вопросы радиоэлектроники, -2012, с. 180-186.

Титов А.И. Эволюционное кодирование данных / А.И. Титов //Журнал Вопросы радиоэлектроники, - 2013, с. 93-96.

Публикации в сборниках трудов научных конференций

Титов А.И. Модифицированный алгоритм скрытного кодирования данных / А.И. Титов, Н.И. Корсунов // КНиТ - 2011 : труды Второй Международной научно-технической конференции, 3-7 октября 2011. -Белгород: Изд-во НИУ БелГУ, 2011.

Титов А.И. Применение генетических алгоритмов в эволюционном методе кодирования (шифрования) данных /А.И. Титов // Сборник трудов международной молодежной конференции. Прикладная математика, управление и информатика, - 2012, - С.598-601.

Титов А.И. Эволюционный подход к скрытному кодированию хранимых данных/ Н.И. Корсунов, А.И. Титов // Тезисы одиннадцатой Международной научно-технической конференции «Проблемы информатики и моделирования», 26-30 сентября 2011. - Харьков: Цифрапринт, 2011.

Программы для ЭВМ

Свидетельство о государственной регистрации для программы для ЭВМ № 2010617605 «Программная система шифрования-дешифрования данных для хранения данных на стороннем Web-сервере», авторы: Корсунов Н.И., Титов А.И., 11 ноября 2010 г.

Свидетельство о государственной регистрации для программы для ЭВМ № 2011611604 «Блочно-итерационный алгоритм шифрования-дешифрования данных», авторы: Титов А.И., Корсунов Н.И., 17 февраля 2011 г.

Свидетельство о государственной регистрации для программы для ЭВМ № 2012619873 «Программный комплекс эволюционного кодирования-декодирования данных», авторы: Титов А.И., Корсунов Н.И., 31 октября 2012 г.

Подписано в печать 21.11.2013. Гарнитура Times New Roman Формат 60x84/16.Усл. п. л. 1,0. Тираж 100 экз. Заказ 473. Оригинал-макет подготовлен и тиражирован в ИД «Белгород» НИУ «БелГУ» 308015, г. Белгород, ул. Победы, д. 85.

БЕЛГОРОДСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

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

04201453262 Титов Алексей Иванович

РАЗРАБОТКА ЭВОЛЮЦИОННЫХ МЕТОДОВ И АЛГОРИТМОВ КОДИРОВАНИЯ-ДЕКОДИРОВАНИЯ ДАННЫХ В КОМПЬЮТЕРНЫХ

СИСТЕМАХ

по специальности 05.13.17 - Теоретические основы информатики

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

Научный руководитель д.т.н., заслуженный деятель науки РФ профессор, Корсунов Н.И.

Белгород -2013

ОГЛАВЛЕНИИ

ВВЕДЕНИЕ 5

Перечень сокращений 10

ГЛАВА 1. АНАЛИТИЧЕСКИЙ ОБЗОР. ПРОБЛЕМЫ И ЗАДАЧИ 10 ИССЛЕДОВАНИЯ

1.1. Применение секретного кодирования для защиты информации 11

1.2. Состояние исследований и разработок алгоритмов секретного 13 кодирования

1.2.1. Симметричные алгоритмы секретного кодирования. Упрощенная 14 модель

1.2.2. Поточное и блочное секретное кодирование 16

1.2.3. Поточное секретное кодирование. Алгоритмы А5, RC4, Lili-128.. 19

1.2.4. Блочное секретное кодирование. Сеть Фейстеля 24

1.2.6. Блочное симметричное секретное кодирование. DES 26

1.2.7. Блочное симметричное секретное кодирование. ГОСТ 28147-89 28 . 1.2.8. Блочное симметричное секретное кодирование. Rijndael 30

1.2.9. Асимметричный кодирование 33

1.3. Результаты главы 34 ГЛАВА 2. РАЗРАБОТКА МАТЕМАТИЧЕСКОЙ МОДЕЛИ 34 КОДИРОВАНИЯ-ДЕКОДИРОВАНИЯ С ПОВЫШЕНИЕМ СТОЙКОСТИ К НЕСАНКЦИОНИРОВАННОМУ ДЕКОДИРОВАНИЮ

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

2.1.1. Применение методов помехоустойчивого кодирования в 36 формировании секретного кода

2.1.2. Введение оператора вращения при представлении кодируемых 38 данных помехоустойчивым кодом

2.2. Математическая модель секретного кодирования данных 40 2.2.1. Представление вращения порождающей матрицы исходного кода 40

при формировании секретного кода

2.2.2. Метод определения угла поворота порождающей матрицы 42

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

2.3. Метод расширения ключа при кодировании данных 53

2.4. Применение математ^еежш'жщели для секретного кодирования 55 текстовых сообщений

2.4.1. Разделение топологической структуры «Сообщение» на элементы 55

2.4.2. Секретное кодирование по средствам вращения группы слов 57

2.4.3. Секретное кодирование по средствам вращения букв слов 59

2.5. Доказательство повышения стойкости к несанкционированному 60 декодированию метода эволюционного кодирования данных

2.5.1. Критерии лавинного эффекта 61

2.5.2. Сравнительный анализ математической модели и стойкости 62 предложенного метода секретного кодирования и ГОСТ28147-89

2.6. Секретное кодирование с использованием генетических операторов 65

2.7. Результаты главы 66 3. РАЗРАБОТКА МЕТОДА ЭВОЛЮЦИОННОГО КОДИРОВАНИЯ- 67 ДЕКОДИРОВАНИЯ ДАННЫХ

3.1. Предъявляемые требования к методу секретного кодирования 67 данных с повышенной стойкостью к несанкционированному декодированию

3.2. Генетический операторы в формировании секретного кода 70

3.2.1 Применение операции кроссовера генетического алгоритма для 75 формирования секретного кода и восстановления исходных данных

3.2.2 Применение операции мутации генетического алгоритма для 82 формирования секретного кода

3.3. Алгоритм расширения ключа 87

3.4. Генетические алгоритмы в эволюционном методе кодирования 88

данных

3.5 Перспектива использования эволюционного кодирования данных в 98 системах обработки и передачи информации

3.6 Результаты главы 98 4. ПРОГРАММНАЯ РЕАЛИЗАЦИЯ ГЕНЕТИЧЕСКОГО АЛГОРИТМА 99 И ВЫЧИСЛИТЕЛЬНЫЙ ЭКПЕРИМЕНТ

4.1. Программная реализация секретного кодирования

4.2. Программная реализация секретного кодирования для Web-серверов ^9

4.3. Программная реализация эволюционного метода кодирования- 102 декодирования данных на CPU

4.4. Программная реализация эволюционного метода кодирования- 105 декодирования данных с использованием GPU

4.5. Вычислительный эксперимент 107

4.6. Результаты главы 117 ЗАКЛЮЧЕНИЕ 118 СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 119 Приложение А. Список работ опубликованных по теме диссертации 130 Приложение Б. Листинг программного обеспечения «Taina» 131 Приложение В. Листинг программного обеспечения для частотного 147 анализаи «Comparer»

Приложение Г. Таблицы результатов экспериментов 150

Приложение Д. Листинг основного модуля программного обеспечения 165 для хранения закрытых файлов на удаленномшеЬ-сервере

Приложение Е. Листинг основных функций программного обеспечения 169 кодирования данных средствами CUDA

Приложение Ж. Копии свидетельств о государственной регистрации 174 программ для ЭВМ

Приложение 3 177

ВВЕДЕНИЕ

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

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

В настоящее время, особое внимание отводится секретному

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

хранимых на серверах. Вопросам секретного кодирования посвящены

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

развитие теории секретного кодирования внесли: К. Шенон, А. Тьюринг, Б.

Шнайер, Венбо Мао, С. Баричев, В. Герасименко и другие.

Однако в их работах, как правило, делается упор на построение

симметричных и ассиметричных кодов на базе моделей в виде цифровых

автоматов. Несмотря на существенные успехи в создании секретных кодов и

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

кодирования не обеспечивают стойкость кода к несанкционированному

декодированияю, если известны пары открытых и закрытых текстов.

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

повышения стойкости кода является метод неэквивалентного кодирования,

при котором одному символу алфавита X соответствует несколько символов

алфавита У. Существующие методы симметричного кодирования данных без

5

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

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

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

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

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

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

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

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

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

6. разработать метод экспериментальной оценки стойкости кода к несанкционированному декодированию.

Объект исследования: алфавитно-цифровая информация, хранимая в базах данных на серверах компьютерных систем.

Предмет исследования: методы кодирования информации в виде данных компьютерных систем.

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

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

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

2. математическая модель секретного кодирования на основе преобразований в линейном векторном пространстве;

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

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

• обеспечение повышения стойкости к несанкционированному

декодияованию пазоаботанных эволюционных алгооитмов по ^ ^ 1 11 1 1

сравнению с известными алгоритмами;

• реализация генетических алгоритмов программными средствами в вычислительных системах различной архитектуры;

• использование разработанного программного обеспечения в филиале Федерального казенного учреждения «Налог-Сервис» ФНС России в

Белгородской области и в ЗАО «БОШЕ» г. Старый Оскол (подтверждены актами, приведенными в прил .3);

• использование разработанных методов секретного кодирования в учебном процессе Губкинского филиала БГТУ им. В.Г. Шухова в курсе «Защита компьютерной информации» по направлению подготовки бакалавров 230100.62 - информатика и вычислительная техника. Область исследования. Содержание диссертации соответствует паспорту специальности 05.13.17 «Теоретические основы информатики» по следующим областям исследований:

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

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

Связь с научными и инновационными программами. В рамках работы получен грант имени «Владимира Раевского» номинации «Зворыкинский проект» в рамках форума «Нежеголь-2011» за разработку метода секретного кодирования данных для защиты баз данных интернет-издательства «Я в науке».

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

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

2. эволюционный метод и генетические алгоритмы секретного кодирования данных и их программная реализация в компьютерных системах;

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

работоспособности разработанных методов и алгоритмов.

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

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

Апробация результатов диссертационного исследования. Результаты работы докладывались и обсуждались на следующих научно-технических конференциях: Международная молодежная конференция «Прикладная математика, управление и информатика», г. Губкин (2012 г.); Международная молодежная конференция «Прикладная математика, управление и информатика», г. Белгород (2012 г.); Информационные технологии в науке, образовании и производстве, г. Орел (2012 г.); Вторая Международная научно-техническая конференция «Компьютерные науки и технологии», г. Белгород (2011 г.); 11-ая Международной научно-технической конференции «Проблемы информатики и моделирования» Харьков-Ялта (2011 г.).

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

Объем и структура работы. Диссертационная работа состоит из введения, 4 глав, заключения, списка литературы (106 наименований) и 7 приложений. Основной текст содержит 120 страниц, иллюстрируется 45 рисунками.

Перечень сокращений

АСУ - автоматизированная система управления; ЭЦП - электронная цифровая подпись; PCJ10C- регистр сдвига с линейной обратной связью; ПСП - псевдослучайная последовательность;

ECB - режим кодирования «Электронная кодовая книга»(Electronic Code Book);

СВС - режим кодирования «Сцепление блоков шифра» (CipherBlockChaining);

OFB- режим кодирования «Обратная связь по выходу» (OutputFeed- Васк); CFB- режим кодирования «Обратная связь по шифротексту» (CipherFeedback);

1. АНАЛИТИЧЕСКИЙ ОБЗОР. ПРОБЛЕМЫ И ЗАДАЧИ

ИССЛЕДОВАНИЯ

Широкое применение компьютерной техники и технологий, используемых человеком в повседневной работе для обработки и хранения данных, привело к обострению проблемы секретного кодирования информации для ограничения несанкционированного доступа, так как несанкционированное чтение или фальсификация информации злоумышленником может нанести серьезный урон обладателю. Секретное кодирование информации в компьютерных системах имеет ряд специфических особенностей, обусловленных тем, что информация не является жестко связанной с носителем, она может легко и быстро копироваться, а также передаваться по каналам связи. В практике часто применяется использование удаленных серверов для хранения информации, к которой необходим доступ из любой точки мира (24 часа в сутки). Известно большое количество угроз информации, которые могут быть реализованы как со стороны внешних, так и внутренних нарушителей [21].

1.1. Применение секретного кодирования для защиты информации

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

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

Решение проблемы защиты информации, циркулирующей в

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

разрабатывать на базе использования программных методов. При этом

важным является применение стойких к несанкционированному доступу

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

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

программному обеспечению и может использовать ее для генерации

закрытых сообщений из желаемых открытых. Гибким и эффективным

средством гарантирования конфиденциальности, целостности и подлинности

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

преобразования, также называемые шифрованием). Использование методов

11

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

Для современных систем секретного кодирования информации сформулированы следующие общепринятые требования [21]:

• закрытый файл должен поддавать�