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

005013061

Сизов Владимир Петрович

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

АЛГОРИТМ ЗАЩИТЫ ИНФОРМАЦИИ НА ОСНОВЕ ТРИГОНОМЕТРИЧЕСКИХ ФУНКЦИЙ

05.13.19 - Методы и системы защиты информации, информационная безопасность

2 9 мдр 2012

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

Уфа-2012

005013061

Работа выполнена на кафедре автоматики и телемеханики ФГБОУ ВПО «Пермский национальный исследовательский политехнический университет»

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

ЮЖАКОВ Александр Анатольевич, Пермский национальный исследовательский политехнический университет, кафедра автоматики и телемеханики

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

МАШКИНА Ирина Владимировна,

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

доктор технических наук, СКИБА Владимир Юрьевич, Главный научно-информационный вычислительный центр ФТС России

Ведущее предприятие ФГБОУ ВПО «Казанский национальный

исследовательский технический университет им. А.Н. Туполева-КАИ»

Защита состоится Г? а^улётЛ!/ 2012 г. в (О часов на заседании диссертационного совета Д 212.288.07 при Уфимском государственном авиационном техническом университете по адресу: 450000, г. Уфа, ул. К. Маркса, 12 С диссертацией можно ознакомиться в библиотеке университета

Автореферат разослан «_//_» 2012 г.

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

С.С. Валеев

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

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

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

Объект исследования

Методы защиты и повышения достоверности информации в системах автоматизации испытаний.

Предмет исследования

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

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

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

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

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

- разработка и исследование функциональных моделей шифраторов и кодеров;

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

- исследование характеристик предложенного алгоритма кодирования.

Методы исследования

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

Основные научные результаты, полученные автором и выносимые на защиту:

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

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

- функциональные модели шифраторов и кодеров;

- алгоритм кодирования на основе тригонометрических функций;

- характеристики предложенного алгоритма кодирования.

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

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

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

риодом гаммирования, необратимостью и минимальной задержкой времени сигнала;

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

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

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

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

Научно-практические результаты работы были использованы в учебном процессе по специальным дисциплинам специальностей 220201 «Управление и информатика в технических системах» и 210400 «Телекоммуникации» Пермского государственного технического университета.

Апробация работы

Основные положения диссертации докладывались и обсуждались на международных и всероссийских научно-технических конференциях:

- У1 конференция «Информационная Безопасность регионов России» (Санкт-Петербург, октябрь, 2008 г.);

- международная научная конференция «Рускрипто 2005» (Москва, 2005 г.); «Рускрипто 2009» (Москва, 2009 г.).

Публикации

Основные положения и результаты опубликованы в 7 печатных работах, в том числе 3 работы в изданиях из перечня ВАК; патент РФ на изобретение №23311116, от 10.08.2008 г. и Свидетельство о государственной регистрации программы ЭВМ №2010610256 от 11.01.2010 г.

Структура и объём диссертации: работа состоит из введения, 5 глав, заключения, и содержит 114 страниц машинописного текста, 19 рисунков, 9 таблиц, список литературы из 87 наименований.

Содержание работы

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

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

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

Рассматривается архитектура одного из применяемых протоколов LAN (Local AreaNetworks)nepefla4H информации по открытым сетям LON Work.

Большинство способов кодирования данных, практически используемых в настоящее время, при передаче информации в системах «реального» времени обладают лишь вычислительной стойкостью, т.е. коды могут быть вскрыты путем перебора, причем отсутствие более быстрых алгоритмов вскрытия строго не доказано. Реально можно говорить о следующем. Шифр считается стойким, если для него неизвестны алгоритмы взлома, существенно более эффективные, чем прямой перебор ключей. В случае если у вас имеется ГПСЧ работающий на основании секретного ключа. Вы можете передавать информацию по открытым каналам САИ, предварительно передав секретный ключ по закрытому каналу. В этом случае, вам необходимо иметь абсолютно надёжный ГПСЧ. Рассматривается вопрос избыточности передаваемой информации и избыточность информации конкретно в сетях САИ. Возможности предварительного

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

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

Предложен новый алгоритм кодирования, основанный на использовании периодических функций типа у = cos х и уравнения "волны", т.е. у = cos(x + Дх).

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

Пример реализации способа: по координатной оси X расставляются символы из открытого текста в случайном порядке с использованием всех возможных символов. Каждому символу соответствует свой порядковый номер от 1 до 256 согласно таблице Unicode. Всего используется в компьютере 256 символов. По оси Г расставляем символы, используемые в шифротексте в случайном порядке с использованием всех возможных символов. Им так же присваиваются порядковые номера, например, от 1 до 256. Три линейные функции 1,2,3 описываются как: Y2> Yy.

где Х - порядковый номер символа из открытого теста (знак из исходного текста); 1 - любое число, например 0; 2 е (-со,+оо) (начальная фаза колебаний функции); ТУ' - номер по счету шифруемого символа из открытого текста (1, 2,

Yx = X + 256 • [cos(z+tf • Дх)]+256, Y2 = X + 256-[cos{z+N-hx)\ У3 = X + 256 • [cos(z+JV • Дх)] - 256.

(1) (2) (3)

3, ..., я); Дх - любое число, например, 32; &% е (-со,+со) (это число определяет скорость перемещения функции из стороны в сторону и её направление).

Зашифруем открытый текст, состоящий из букв А. ААААА - открытый

текст.

В данном примере секретными является числа Ar и Z. Все остальные параметры не являются секретом. Кроме того, количество секретных параметров можно сделать бесконечное множество. В нашем примере, секретные параметр ры это: порядок расстановки символов по осям X и Y, Дх - приращение функции, Z - начальная фаза колебаний функции. Будем считать, что порядок расстановки знаков по осям Xu Yодинаковый. Например, знак А занимает промежуток (0-1) по осиХ, знак Б - (1-2); В - (2-3) ... Я - (255-256) (в рассмотренном примере пронумерован русский алфавит А-1, Б-2, В-3 и т.д.). То же самое реализовано на оси Y. Отсюда получим функцию шифрования (рисунок).

Порядок работы алгоритма. Шифруем первый знак открытого текста. Имея три формулы, подставляем значение 0,5 - середину промежутка (0-1) -буква А. Для буквы Б это значение соответствует 1,5, для В соответственно 2,5 для Я-255,5

Пусть: (для удобства) Z = 0; N = 1 (т.к. шифруется первый по счету знак из открытого текста, потом 2, 3,4, 5); Ас = 32 (близко по кратности числу л).

Выполняем операцию кодирования по формулам (1)-(3) и получаем: ^ = 0,5 + 256 ■ [cos(0 +1 • 32)] + 256 = 437,6; Y2 = 0,5 + 256 ■ [cos(0 +1 ■ 32)] = 217,6; У3 = 0,5 + 256 • [cos(0 +1 • 32)] - 256 = -38,39.

Из трех значений Уь Y2, 73 выбираем Y2, так как оно попало в промежуток от 0 до 256, и округляем значение Y2 до большего целого У2= 218.

Выполняя аналогичные процедуры получаем второй, третий, четвертый и пятый знаки шифротекста: второй знак - 113 (N= 2), третий знак - 230 (Л' = 3), четвертый знак - 99 (Л' = 4), пятый знак - 16 (N= 5).

В итоге из числового ряда 0,5; 0,5; 0,5; 0,5; 0,5 - открытого текста А А AAA получили числовой ряд 218; 113; 230; 99; 16 - шифротекст. Необходимо отметить, цифры 218; 113; 230; 99; 16 получены путём округления иррациональных чисел.

Для расшифровки применяют те же самые формулы (1)—(3).

Из каждого полученного значения 218; 113; 230; 99; 16 вычитаем 0,5. Это делается для того, чтобы в формулы подставлялись значения из середины отрезка, которому принадлежит данный знак. Т.е. в формулы (1Н3) п0 факту подставляются значения 217,5; 112,5; 229,5; 98,5; 15,5. Тогда на первом шаге.

Хх =217,5-256- [«»(0 +1 • 32] - 256 = -255,6;

=217,5-256 • [соэ(0 +1 • 32] = 0,4;

=217,5-256- [соз(0 +1 • 32] + 256 = 265,4.

Х- 0,4. А нам известно, что значение А е {0, 1}.

Подставляя следующие значения получаем остальные значения: 0,3; 0,7; 0,6; 0,56; все эти значения попали в промежуток (0-1) соответственно получили текст ААААА.

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

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

«волны» типа у = cos (х + + Ах). Особенность периодической функции состоит в том, что, во-первых, её период выражен иррациональным числом, а, во-вторых, значение функции имеет бесконечное количество значений xt то есть при

л 7 л 13л

у = 0,5 переменная х принимает значения —; — и т.д., до бесконечности,

как положительных, так и отрицательных значений.

Необходимо иметь в виду, что при использовании вычисляемого (бесконечного и непериодического) значения числа л период гаммирования функции шифрования бесконечен. Это доказывается следующим образом. Если взять элементарную периодическую функцию с уравнением волны типа _y = cos(x+Дг), то период функции равен 2л, а период гаммирования равен к, раз при условии Ах ■ щ - 2л • п2, где и, и и2 - целые числа, не равные между собой. Это возможно только в том случае, если Ах кратно 2л. Внутри современного процессора не существует числа л. Всякий раз это значение вычисляется по определенному алгоритму. Зная, например, ряд функции cos:

,4 6 2л / \ 1 z z z , z cos(z) = l--+---+......±-,

2! 4! 6! 2 n\

n

и принимая для упрощения z = —, тогда в этом случае ряд равен нулю:

,4 _2я Л < -Z z Z , Z 0 = 1--+---+......± —.

2! 4! 6! 2п\

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

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

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

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

Одна из основных задач, возникающих при использовании «физических» генераторов - преобразование порождаемым ими последовательностей в абсолютно случайные с различными функциями распределения. В основу предлагаемого алгоритма кодирования положено тригонометрическое функциональное преобразование типа у = cos(jc). Рассматривается влияние энтропии источника на предложенное алгоритмическое преобразование. Производится сравнение генераторов случайных чисел (ГСЧ), работа которых построена на физических явлениях и работа программных генераторов псевдослучайных чисел (ГПСЧ). Рассматривается вероятность появления битовых сочетаний в различных типах генераторов случайных чисел. Рассматривается эффективная нумерация множеств, нумерация сочетаний.

Фон Нейман (John von Neumann) впервые рассмотрел эту задачу и предложил первый алгоритм для ее решения. Для его описания введем следующие обозначения: дан бернуллиевский источник, порождающий символы из алфавита {0, 1} с вероятностями 1 -р и р соответственно, 0 <р < 1, причем р может быть неизвестно. Требуется преобразовать (или закодировать) порождаемую источником последовательность в такую, где вероятности появления нуля и единицы равны, т.е. в абсолютно случайную.

Фон Нейман предложил следующий метод: исходная последовательность разбивается на блоки (слова) длины 2, которые кодируются по следующему правилу:

00 —»А, 01 —> 0, 10 1, 11 А, (4)

где А обозначает пустое слово.

Пример 3.1. Пусть исходная последовательность и = 1101110110. Разделим ее на блоки по два бита: м = 11,01,11,01,10. Затем применяем отображение (4) и получаем полностью случайную последовательность z = А, 0, А, 0, 1 = 001. Таким образом, мы "извлекли" 3 равновероятных и независимых бита из 10-битовой исходной последовательности.

Из приведенного примера виден и недостаток метода, задаваемого правилом (4) - результирующая последовательность намного короче исходной. Точнее, легко видеть, что из t исходных символов получается последовательность из tp (1-р) независимых символов. Например, если р близко к 1/2, то из t символов в среднем получается г/4.

Элайес (Peter Elias) предложил метод преобразования, более экономно расходующий символы исходной последовательности, что достигается за счет перехода к кодированию блоков длины п,п> 2 (при п = 2 методы Элайеса и фон Неймана совпадают). Для количественной оценки эффективности метода Элайес ввел величину п„, определяемую как отношение среднего значения длины получаемого кодового слова к длине блока п. Он показал, что естественной верхней границей для величины п„ является энтропия источника h(p), которая, напомним, определяется равенством

%) = 0?logp + (l-i>)log(l -р)).

Идея метода Элайеса состоит в следующем. Исходная последовательность разбивается на блоки длины п бит. В каждом блоке подсчитывается количество единиц (обозначим это число через щ\ тогда количество нулей будет щ = п - п\). Затем рассматривается все множество S сочетаний из щ единиц и щ нулей. Заметим, что все последовательности в этом множестве равновероятны (их вероятности равны/?"'( 1 -р)"°). Все множество сочетаний разбивается в ряд непересекающихся подмножеств, мощность которых равна степени двух, причем используются максимально возможные степени.

Например, если во множестве 10 элементов, то оно разбивается на два подмножества мощности 8 и 2. Далее находится номер блока в подмножестве, в которое он входит. Этот номер, записанный в виде двоичного числа, выдается на выход. Если в подмножестве оказался только один элемент, то на выход вы-

дается пустое слово А. Более детально идея метода будет проиллюстрирована с помощью примера.

Пример 3.2. Пусть порождается та же исходная последовательность, что и в примере 3.1, и = 1101110110. Разделим ее на два блока по 5 бит: и = 11011,10110.

Рассмотрим первый блок и{ = 11011. Для этого блока и0 = 1 и и, = 4. Рассмотрим теперь упорядоченное множество всех сочетаний, состоящих из, одного нуля и четырех единиц (табл. 1). Всего таких сочетаний 5, по этому имеем два подмножества и с числом элементов соответственно 4 и 1. Видно, что И) входит в 50 под номером 2 = (10)2. Таким образом, на выходе получаем слово И'(М]) = (10)2.

Таблица 1 - Множество равновероятных последовательностей

Последовательность Номер в Б \1>

01111 000 00

10111 001 01

11011 010 10

11101 011 11

11110 100 -

Теперь выполним преобразование для второго блока последовательности и - 10110. Для этого блока п0 = 2,п\ = 3. Рассмотрим упорядоченное множество всех последовательностей, состоящих из двух нулей и трех единиц (табл. 1). Всего таких последовательностей — = 10, поэтому имеем два подмножества

213!

5о и с числом элементов соответственно 8 и 2. Видно, что и2 входит под номером 6 = (110)2 в . Таким образом, на выходе получаем слово н(т2 ) = (1Ю)2.

В теореме 4.2 (глава 4) будет показано, что средняя длина каждого слова №(«,) превышает пЫр) - 21о%{п + 1). Отсюда получаем нижнюю границу для т]„, ; Щр) -21оё(и +1) = 21оё(л +1)

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

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

Поток информации используемый в САИ обладает очень низкой энтропией. Кодировать такой поток с высокой достоверностью очень сложно. Высоким качеством достоверности обладает предложенный алгоритм.

В четвертой главе предлагаемый алгоритм кодирования проходит различные тесты на качество кодирования в сравнении с существующими алгоритмами и совершенно случайным набором знаков сгенерированным ГСЧ. Было показано, что код Вернама совершенно секретен. Мы видели, что в этом коде длина ключа равна длине сообщения и ключ используется всего один раз. Если же использовать короткий многоразовый ключ (что актуально для большинства практических приложений), то какой наилучший результат стойкости кода можно достичь?

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

Пример 4.1. Предположим, что «Источник» спрятал важные документы в ячейке камеры хранения, снабженной пятидекадным кодовым замком. Теперь он хотел бы сообщить «Приёмнику» комбинацию цифр, открывающую ячейку. Он -«Источник» решил использовать аналог кода Цезаря, адаптированный к алфавиту, состоящему из десятичных цифр:

с = (т + к) modlO,

где т - символ сообщения; к - секретный ключ; т, к 6 {0, 1,9}; с - получаемый символ закодированного текста.

Допустим, «Источник» послал «Приёмнику» закодированный текст 26047. «Злоумышленник» пытается раскодировать его, последовательно перебирая все возможные ключи. Результаты ее попыток сведены в табл. 2.

Таблица 2 - Раскодировка сообщения 26047 путем перебора ключей

к m к m

1 15936 6 60841

2 04825 7 59370

3 93714 8 48269

4 82603 9 37158

5 71592 0 26047

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

Причина невскрываемости кода состоит в том, что «язык» кодового замка не содержит избыточности. Даже простой код, примененный к сообщениям этого языка, становится не вскрываемым.

Определение 4.1. Код называется строго идеальным, если

Щх,х2...х,\у = Н(к\у) = mm(H(xtx2..,xt ),#(£)}. (5)

При условии, что если энтропия ключа меньше энтропии сообщения источника, то (5) упрощается и

H{xtx2...Xl\y = H{k\y) = H{k) (6)

при всех достаточно больших значениях энтропии. Так как рассматриваем случай, когда длина сообщения велика, то в качестве определения строго идеального кода будем использовать (6).

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

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

Таблица 3 - Качество кодирования

Сравниваемые параметры Общеизвестный способ. DES Предлагаемый способ Идеальное распределение

Тип закодированного текста. 6 Мб текста состоящих из начального байта при побитовом разложении 0. 6 Мб текста состоящих из начального байта при побитовом разложении 0. «Одноразовый блокнот» или код Вернама.

Закон распределения. (Спектр) Нормальный. Равномерный. Равномерный.

Количество сочетаний знаков встречаемых в кодировке. 25188 65536 65536

Колич. повторений встречающихся в тексте. 2-106; 2-85; 2-96;

Увеличение объема закодированного текста. На 8 байт На 2 байта Нет увеличения

Время кодирования. 6 минут 20 секунд 25 секунд

Общее количество 0 и 1 в кодировке. 1 -25349346; 0-25232158; расхождение - 0.231682%. 1 -25159905; 0- 25171743; расхождение - 0.023520%. I -25168277; 0-25163435; расхождение - 0.009620%.

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

В главе приведены результаты практической реализации предложенных в предыдущих главах алгоритмов кодирования, включенных в состав САИ, реализованной с использованием программно-технических средств на базе протокола связи Ь(Ж Система внедрена в опытную эксплуатацию на НПО «Искра» г. Пермь и прошла метрологическую аттестацию, подтвердившую высокие показатели надежности и достоверности обработки информации САИ.

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

Результаты опытной эксплуатации позволяют отметить следующее:

1. Большой объем кодируемой информации.

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

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

4. Заложенный в архитектуру САИ блочно-модульный принцип реализации обеспечивает использование более сложных и перспективных алгоритмов обработки.

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

6. Реализованный алгоритм кодирования информации в пакетах LON повышает надёжность и достоверность передаваемой информации за счёт применения разработанного подхода. Что позволило повысить эффективность применения САИ за счет сокращения времени проведения экспериментальных исследований объектов и снижения затрат, необходимых для проведения испытаний. Исключена возможность подмены информации передаваемой по открытым каналам, что снижает экономические потери от недостоверности передаваемой информации.

В заключении сформулированы основные результаты работы.

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

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

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

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

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

3. Разработаны и исследованы функциональные модели кодеров.

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

5. Исследованы характеристики предложенного алгоритма кодирования.

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

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

1. Сизов В.П. Метод шифрования // Электроника-1999, - № 6, С. 12.

2. Сизов В.П. Новый алгоритм шифрования // Вопросы защиты информации. -2008. -№ 2. С. 4-11.

3. Капгер И.В., Сизов В.П., Южаков A.A. Реализация криптографического преобразования сообщений, передаваемых в промышленных сетях LON // Вопросы защиты информации, № 1 (88), 2010. - С. 28-43.

4. Устройство для шифрования В.П. Сизова; пат. 2006102776 Рос. Федерация / Сизов В.П. №23311116, получен 10.08.2008.

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

5. Сизов В.П. Поточный алгоритм шифрования И Информационная безопасность регионов России: материалы VI конф., С-Петербург, октябрь 2008 г. -С-Пб.,2008.-С. 36-38.

6. Капгер И.В. Сизов В.П. Южаков A.A. Применение криптографических алгоритмов в сетях LON / Системы мониторинга и управления: сб. науч. тр. / Перм. гос. техн. ун-т. - Пермь, 2009. - С. 14-26

7. Капгер И.В., Сизов В.П., Южаков A.A. Реализация криптографического преобразования сообщений, передаваемых в промышленных сетях LON, по алгоритму шифрования Сизова В.П. Свидетельство о государственной регистрации программы ЭВМ № 2010610256,11.01.2010.

Подписано в печать 06.03.2012. Формат 60x90/16. Усл. печ. л. 1,0. Тираж 100 экз. Заказ № 330/2012

Издательство Пермского национального исследовательского

политехнического университета 614990, г. Пермь, Комсомольский пр., 29, к.113 тел. (342) 219-80-33

61 12-5/273/

Пермский национальный исследовательский политехнический университет

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

СИЗОВ Владимир Петрович

АЛГОРИТМ ЗАЩИТЫ ИНФОРМАЦИИ НА ОСНОВЕ ТРИГОНОМЕТРИЧЕСКИХ ФУНКЦИЙ

Специальность 05.13.19 - Методы и системы защиты информации, информационная безопасность

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

Научный руководитель д.т.н., профессор Южаков A.A.

Пермь - 2012

СОДЕРЖАНИЕ

Введение..................................................................... 6

1, Анализ способов повышения достоверности информационного обеспечения систем автоматизации испытаний...................... 15

1.1. Особенности современных систем автоматизации испытаний .................................................................................... 15

1.2. Способы повышения достоверности информации

в системах автоматизации испытаний..................................................

1.3. Основы теории кодирования для построения невскрывае-

мых и защищенных систем...................................................... 22

1.3.1, Основные понятия и определения 22

1.3.2, Расстояние единственности кода............................... 27

1.3.3, Соотношение избыточностей по входу и выходу 33

1.4. Основные подходы к построению способа эффективного специального кодирования............................36

1.4.1.Быстрое кодирование с использованием генератора случайных чисел....................................................................................................39

1.4.2.Качественные показатели идеального генератора случайных чисел......................................................................................................................................................40

1.4.2.1. Детерминированные ГГТСЧ.................................................... 41

1.4.2.2.ГПСЧ с источником энтропии................................. 42

1.4.2.3.ГПСЧ в системах кодирования................................ 45

1.4.2.4. Аппаратные ГПСЧ............................................... 45

1.5. Выводы..............................................................................................................................................46

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

функций.............................................................................................. 48

2.1. Метод тригонометрического кодирования....................................................48

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

2.3. Реализация метода кодирования уровня FAN САИ для систем «реального» времени........................................................................................................63

2.4.Вывод ы....................................................................................................................................65

3 Построение эффективного генератора случайных чисел..............68

3.1. Задачи, возникающие при использовании физических генераторов случайных чисел..................................................................................................................68

3.2.Эффективная нумерация множеств..............................................................74

3.2.1 Постановка задачи....................................................................................................74

3.2.2.Нумерация сочетаний............................................................................................79

3.3. Эффективная генерация произвольно распределенных случайных величин........................................................................................................................................86

3.3.1. Постановка задачи....................................................................................................86

3.3.2.Быстрая генерация случайных величин................................................88

3.3.3.Генерация случайных величин на основе тригонометрический функций..........................................................................................................................................89

3.4. Выводы....................................................................................................................................92

4, Анализ характеристик метода кодирования для повышения

достоверности информации........................................................................................................................................94

4.1. Основные определения и постановка задачи анализа..................94

4.2. Оценка метода кодирования на базе тригонометрических функций............................................................................................................................................................96

4.2.1, Требования к алгоритмам кодирования в САИ............................97

4.2.2, Тесты для проверки генераторов случайных и псевдослучайных чисел................................................................................................................................................98

4.2.2.1, Тест «Регистровый сдвиг»............................................................................99

4.2.2.2,Тест «Разброс символов»..............................................................................99

4.2.2.3.Тест «Статистика сочетаний байтов в кодировке»................100

4.2.2.4.Способ оценивания по закону распределения

символов..........................................................................................................................................................105

4.2.2.5.Способ оценивания по количеству сочетаний знаков .... 108

4.2.2.6.Прочие характеристики..................................................................................111

4.3. Выводы....................................................................................................................................112

5. Разработка и реализация алгоритма кодирования в составе системы автоматизации испытаний......................................................................................113

5.1. Описание аппаратурного и программного обеспечения системы автоматизации испытаний..................................................................................................113

5.1.1. Характеристика объекта автоматизации..............................................113

5.1.2. Назначение системы................................................................................................114

5.1.3. Структура системы................................................................................................115

5.1.4. Функционирование системы........................................................................117

5.1.5. Результаты опытной эксплуатации САИ..........................................118

5.2.Анализ производительности LON-системы..........................................120

5.2.1.Измерение производительности систем коммуникации ... 121

5.2.2. Оценка разработанных алгоритмов кодирования информации в сетях LON САИ..................................................................................................................126

5.3. Выводы....................................................................................................................................130

6. Заключение..............................................................................................................................132

Литература......................................................................................................................................134

Приложение А Листинг программы расчета спектра распределения символов....................................................................................................................................142

Приложение Б Листинг программы расчета распределения сочетания знаков......................................................................................................................................146

Приложение В Листинг программы расчета числа повторений

сочетаний знаков......................................................................................................................................149

Приложение Г Листинг программы расчета числа «нулей» и

«единиц» в кодированном тексте..........................................................................................151

Приложение Д Акт о внедрении результатов НИОКР «Разработка алгоритмов кодирования информации в составе аппаратно-программного обеспечения системы автоматизации испытаний авиационных изделий»................................................................. 151

Приложение Е Перечень параметров САИ........................ 152

Приложение Ж Листинг алгоритма программы метода повышения достоверности информации для LON................................. 153

Приложение И Результаты тестирования шифрования по ГОСТ

..................................................................................................................................................................155

Приложение К Результаты тестирования кодирования по предложенному алгоритму............................................................................................................156

ВВЕДЕНИЕ

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

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

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

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

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

САИ является, безусловно, актуальной.

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

- достоверность сообщений в смысле отсутствия ложных сведений и данных;

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

(бита, цифры, буквы, слова).

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

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

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

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

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

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

Основы теории безусловной стойкости способов кодирования были изложены в работе К.Шеннона [12].

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

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

на символ сообщения [12].

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

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

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

Значительный вклад в развитие эффективных алгоритмов кодирования информации внесли работы Э. М. Габидулина, Б. Я. Рябко, В. М. Сидельникова и целого ряда других отечественных ученых. Вопросы безусловной стойкости кодов были впервые рассмотрены К.Шенноном, а затем в работах Р. Альсведе (Ahlswede,R.), Дж. Л. Месси (Massey,J.L.), Б.Я.Рябко, Ю. М. Штарькова и др. Омофонными кодами занимались такие исследователи как К. Гюнтер (Gunther, Ch.), К. Гирман (Gehrmann, Ch.), Дж. Л.Месси, В. Пенцхорн (Penzhorn,W.), В. К. да PoKa(daRocha,V.C.), Б. Я. Рябко и др. Извлечение случайности и генерация случайных величин рассматривались в многочисленных работах, среди которых отметим работы Дж. Абрахаме (Abrahams,J.), П. Элайе-ca(Elias,P.), Д. КнутаиА. Яо (Knuth,D., Yao,A.), Н.Нисана и Д. Цуккермана (Nisan, N., Zuckerman,D.), Ж. Р. Роше (Roche,J.R.), Б.Я.Рябко, Т. С. Ханаи М.

Хоши (Han, T.S., Hoshi,M.). Многочисленные работы посвящены методам универсального, нумерационного и адаптивного кодирования источников.

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

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

Важное место при разработке эффект