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

По результатам моделирования строятся соответствующие графики. Имея данные такого эксперимента, проведенного на реальной машине, можно проверить адекватность настройки модели и при необходимости провести корректировку заданных параметров. На графике (рис.6) в качестве примера приведены значения скорости и ускорения на месте человека-оператора при заданном возмущении значением в 500 Н, заданного при помощи источника случайного сигнала с нормальным распределением <^ап^т№тЬег».

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

Рис. 6. График результатов моделирования

Библиографический список

1. Гордеев Б. А. Системы виброзащиты с использованием инерционности и диссипации

реологических сред / Б. А. Гордеев, В. И. Ерофеев, А. В. Синёв, О.О. Мугин. - М.:ФИЗМАТЛИТ, 2004. -176 с.

2. Щербаков В. С., Корытов М. С., Руппель А. А. и др. Моделирование и визуализация движений механических систем в Matlab. Омск:СибАДИ, 2007. 84 с.

3. Баранов В. Н., Захаров Ю. Е, Электрогид-равлические и гидравлические вибрационные механизмы. - М.; Машиностроение, 1977. - 326 с.

4. Смоляницкий Э. А., Перлов А. С. К динамическому анализу рабочего оборудования гидравлического экскаватора. Труды ВНИИ-стройдормаш. - М., 1969, с. 20-27.

5. Галдин В. Н. Алгоритм и некоторые результаты расчета основных параметров рабочего органа для разрушения грунта // Вестник СибАДИ.

2011. № 2 (20). С. 55-59.

AUTOMATION SYSTEM MODELING OF VIBROPROTECTION DEVICES CONSTRUCTION MACHINERY

A. O. Lisin

The article considers the system of the automation of the simulation of vibration devices of construction machinery on the basis of the single bucket excavator. Provides a block diagram of the operation of the system. Considered are the methods used for the simulation of vibration devices.

Лисин Александр Олегович - Аспирант кафедры «АППиЭ» ФГБОУ ВПО «СибАДИ». E-mail -Lexlisin@gmail. com

УДК 004.056.55

АЛГОРИТМЫ ОБРАБОТКИ ИНФОРМАЦИИ ПРИ ПЕРЕДАЧЕ И ХРАНЕНИИ ДАННЫХ, ОСНОВАННЫЕ НА ПРОЦЕДУРЕ РАЗДЕЛЕНИИ СЕКРЕТА

В. В. Михеев, Д. А. Сагайдак, А. А. Свенч, Р. Р. Файзуллин

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

Ключевые слова: передача данных, разделение секрета, шифрование, центр обработки данных.

Введение

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

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

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

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

z1 = 0,а1 ..а{ z2 = 0,ам..а21 ...^п. Преобразуем это последовательность по правилу:

1 п -х. = z---^ z и после операции Ах,

п1=1

где А симметричная вырожденная матрица с ядром в виде вектора констант, получим вектор /. В простейшем случае, в качестве матрицы можно взять конечноразностный оператор, аппроксимирующий краевую задачу с периодическими краевыми условиями: d 2

У = /, у(0) = у( 1) . Обратное преобра-

виде:

dx2 зование

можно

записать

в

х = ^------—У] , где Л],У] это ненулевые

]=2 Л]

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

компонент вектора / (передавая по открытому каналу только абсолютные значения компонент), значимое число младших бит компо-

1 п

нент, или просто среднее значение —^ Z] .

п

]=1

Обратим внимание: 1) прямые и обратные операции преобразования данных можно распараллелить, причем самым эффективным способом: по вариантам, 2) можно не ограничиваться одним преобразованием Ах, а рассматривать «раунды», например, АВС..Ах, где каждая матрица отвечает своему вырожденному оператору. Отметим, что и ядра этих операторов могут быть не такими простыми как в рассмотренном выше случае.

Алгоритм, использующий разложение в тригонометрические ряды. Пусть известно, что для длины исходного блока данных N верно следующее предположение: 31 > 0: N < 21+1 • 1 Иными словами,

можно найти машинное слово длины I бит, такое, что любую пару таких слов в исходном блоке данных можно индексировать константой, умещающейся в такое слово. Например, для любого блока данных, размер которого не превосходит 32Гб, могут быть использованы слова длиной 32 бита. Далее под машинным словом будем понимать слово длины I бит. Далее рассмотрим преобразование исходного блока данных: для каждой пары машинных слов №2^21+1) проинтерпретируем их как целые числа без знаков (х, у) - согласно кодировке целых чисел, принятой в используемой архитектуре ЭВМ. Эти числа можно в свою очередь интерпретировать как точку в пространстве R2 Получившийся в результате

. N

набор точек длины Ь = — затем необходимо

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

У У

условие: Ут, п : т < п >—^ Здесь и

хт хп

далее предполагается, что все х, отличны от нуля. Для того, чтобы это условие гарантированно соблюдалось, ко всем значениям х, прибавляется 1. Отметим, что преобразование сортировки точек необратимо без сохранения прямой или обратной перестановки. К полученному набору упорядоченных точек (хт, ут) далее применяется алгоритм, строящий ломаную линию G:

1. Положить начальную точку G: д0 := (0, 0). Назначить ее опорной точкой (хд, уд).

2. Взять следующую точку из набора (хт,

уш).

3. Добавить к G точку дт := (хд+хт, уд+ут). Назначить ее опорной: (хд, уд) := дт.

4. Если в исходном наборе еще остались необработанные точки, вернуться к шагу 2.

Полученная ломаная линия G выпукла и монотонна. Если выделить линию тренда Т, проходящую через точки д0 и дь то ломаная G' = G - Т может быть приближена некоторой периодической функцией ^х). Такая функция, как правило, может быть хорошо аппроксимирована рядом Фурье по синусам с количеством коэффициентов, намного меньшим, чем L. [5] Описанное преобразование является обратимым, и может быть использовано в качестве метода асимметричного разделения секрета: в этом случае «большая» часть секрета представляет собой совокупность перестановки, полученной на шаге сортировки, и значений х, которые необходимы для определения координат точек для восстановления. Размер этой части в совокупности будет совпадать со значением N. «Меньшая» часть секрета представляет собой данные о линии тренда (длина и угловой коэффициент) и набор коэффициентов Фурье, который может быть ограничен сверху, как логарифм от исходного объема данных. Можно показать, что задача восстановления ломаной, даже при известном значении касательной в крайней правой точке неопределенна. Обратим внимание также на то, что рассмотренное преобразование может быть использовано для сжатия информации.

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

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

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

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

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

битовых векторов А1,..., Ап, размерности которых равны ^1,...,Ып и дисперсии

распределены равномерно в достаточно большом интервале.

В этом случае возникает проблема экономичной записи данных, которая в настоящее время решается различными способами: шардингом [1], т.е. грубым физическим разде-

лением данных по различным носителям данных, введением различных типов данных, наподобие CHAR и VARCHAR, разделением данных маркерами. Но если Mt варьируются

от 103 до 1010, а n изменяется, то отведение равных областей памяти для каждого исключительно неэффективно, а разделение данных специальной строкой бит (маркером) неэффективно по времени поиска этого маркера, и нет никакой гарантии, что выбранная в качестве маркера строка не встречается ни в одном из Aj.

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

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

Первые l бит заполним нулями, где l -это длина записи числа п, далее идёт сама запись числа n , например, пусть даны n = 3 битовых векторов, тогда запись числа n в двоичной системе счисления равна 11, тогда l = 00. Тогда на первом этапе получается следующая числовая последовательность: 0011. Далее, mt бит заполняются нулями, где

mt - это число бит необходимых для записи длины вектора At в двоичной системе счисления. Например, в предыдущем примере n = 3 , следовательно, имеется три битовых вектора A1, A2, A3, пусть A1 = 111011, A2 = 10111, A3 = 101, тогда размерности этих битовых последовательностей равны M1 = 6, M2 = 5 , M3 = 3 соответственно, а

m1 = 000, m2 = 000, m3 = 00 . Тем самым,

на втором этапе получится следующая последовательность: 0001100001010011. Третьим этапом формирования последовательности является последовательная запись самих

векторов A1, A2, A3. Например, для приведённых выше примеров, получится следующая исходная последовательность: 0011000110000101001111101110111101.

Обратим внимание на то, что зная диапазон возможных изменений At можно записывать At в mt + dt позициях, предваряя или

дополняя нулями значащие цифры At. Это

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

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

Пусть имеется поток видеоинформации, передаваемый по каналам связи, осуществляется разбиение данного видеопотока на фреймы. Производится построчное чтение пикселей фрейма, затем, для каждого пикселя строки находятся его значения в формате RGB (red, green, blue) в двоичной системе счисления (размерностью 24 бита, т.е. по 8 бит для каждого цвета) и записываются последовательно друг за другом в одну строку, создавая последовательность, состоящую из нулей и единиц. Каждая такая достаточно длинная последовательность строки прочитанных пикселей разбивается на n битовых

векторов A1, A2,..., An, разных размерностей M1,...,Mn. Затем все полученные строки, состоящие из префикса и зашифрованных или преобразованных A1, A2v, An ^ C1,--, Cn (без изменения длин записи), объединяются в одну битовую сроку. Очевидно, что, не зная префиксов, определение границ разделения сводится к переборной задаче.

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

Пусть имеется поток определенного («телевизионного») формата 720х576 пикселей 25 кадров в секунду в формате RGB (в дальнейшем будет осуществляться преобразование видеопотоков стандартных форматов: 720х576, 640х480, 352х288 (CIF - Common Interchenge Format), 176х144 (QCIF -Quartered Common Interchenge Format)), т.е. размерность изображения является известной и выбирается из одного из стандартов. Здесь осуществляются аналогичные действия: осуществляется разбиения видеопотока на фреймы, для каждого пикселя фрейма находятся его значения в формате RGB (red, green, blue) в двоичной системе счисления и записываются последовательно друг за другом (изображение считывается построчно слева направо), затем полученная битовая последовательность (битовая последова-

тельность состоит из последовательно записанных друг за другом значения пикселей строк в двоичной системе счисления) разбивается на n случайных битовых векторов разной размерности. Формируется префикс с указанием, на сколько n частей разбита последовательность и с указанием длин каждых полученных векторов A1, A2,..., An.

В качестве генератора случайных чисел в программе, реализующей описываемый метод (произвольно генерируются размерности векторов A1,A2,...,An размером от 500 до 1000

бит), используется генератор псевдослучайных чисел RandomRange(), встроенный в среду программирования Borland (C++, Delphi) и удовлетворяющий набору тестов определённому стандартом FIPS 140-1 (Federal Information Processing Standards) [3].

Над полученными битовыми векторами A1, A2,..., An, осуществляются следующие

операции X1 = A1, X2 = A2 + A3,...,

X , = A , + A (где «+» - побитовое сложе-

n— 1 n— 1 n v m

ние по модулю 2), полученные битовые векторы X1, X2,...,Xn, записываются последовательно друг за другом и дописываются к сформированному выше префиксу.

Так же возможно, что для получения битовых векторов X1,X2,...,Xn, вместо операции «+» - побитовое сложение по модулю 2, описанной выше, можно воспользоваться одним из режимов шифрования (метод применения блочного шифра, позволяющий преобразовать последовательность блоков открытых данных в последовательность блоков зашифрованных данных), таких как CBC (Cipher Block Chaining), CFB (режим гаммирования с обратной связью, Cipher Feedback).

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

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

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

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

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

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

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

А2 + А3 = Х 2

Ап-1 + Ап = Хп-1

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

Описанный метод не требует значительных вычислительных ресурсов и способен осуществлять преобразование данных «на лету».

Заключение

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

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

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

Их работа требует как передачи больших объемов данных, так и быстрой и безопасной их обработки, в том числе и связанной с решением систем нелинейных уравнений [7], [8], [9].

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

Библиографический список

1. Rahul Roy (July 28, 2008). Shard - A Data-

base Design [Электронный ресурс]. -Режим доступа: http://technoroy.blogspot.com/2008/07/ shard-

database-design.html, свободный (дата обращения 29.04.2012).

2. Elias P. Universal codeword sets and representations of the integers // IEEE Transactions on Information Theory, 1975, vol. IT-21, № 2. P. 194-203.

3. Federal Information Processing Standards Publication. FIPS PUB 140-1. Security Requirements for Cryptographic Modules. - U.S. Department of commerce / National institute of standards and technology, 1994. - 53 с.

4. Файзуллин Р. Т., Файзуллин И. Р., Данилова О. Т. Алгоритмы разделения секрета с использованием принципиально малой части в качестве ключа// Вестник Тюменского государственного университета. - Тюмень: ГОУ ВПО ТюмГУ, 2011. -вып. 7. - С.175 -179.

5. Корытова М. В., Файзуллин Р. Т. Криптостеганографический алгоритм на основе применения тригонометрических рядов с неубывающими коэффициентами// Известия Челябинского науч. центра вып. 3 (20), 2003.

6. Файзуллин Р.Т., Сагайдак Д.А. Приложение алгоритма префиксного кодирования массива данных в схеме разделения секрета// Доклады Томского государственного университета систем управления и радиоэлектроники. -1(25), -часть 2, -

2012, С. 136-140.

7. Файзуллин Р. Т., “О решении нелинейных алгебраических систем гидравлики”, Сиб. журн. ин-дустр. матем., 2:2, 1999.

8. Мызников А. М., Файзуллин Р. Т. Уточнение коэффициентов сопротивления в сложных гид-

равлических сетях по результатам ограниченного числа измерений, Теплофизика и аэромехани ка. -Новосибирск: ИТФ СО РАН, 2005. -т.12, №2. -С.483-486

9. Файзуллин Р. Т., Шалай В. В. Вычислительные системы расчета и оптимизации технологических режимов нефтепроводов и тепловых сетей крупных городов, Открытое образование. - № 2. 2011. с.248-251.

DATA PROCESSING ALGORITHMS BASED

ON SECRET SHARING APPLIED TO THE

TRANSMISSION AND STORAGE OF THE INFORMATION

V. V. Mikheev, D. A. Sagaidak,

A. A. Svench, R. R. Faizullin

Article is devoted to consideration of several ways of efficient algorithms building for data splitting (secret sharing) at the data processing centers which may be applied to enhance speed of transfer, processing, security and also stability for the attacks. The example of secret sharing for the video information transfer is used to illustrate one of the algorithms.

Михеев Виталий Викторович - Кандидат физико-математических наук, доцент ФГБОУ ВПО «ОмГТУ», каф. «КЗИ». Основные направления научной деятельности Интегрирование дифференциальных уравнений теоретической физики, Квантовая статистическая механика, Теория групп и алгебр Ли. Общее количество опубликованных работ: 20. vvm125l@mail.ru

Сагайдак Дмитрий Анатольевич - Аспирант ФГБОУ ВПО «ОмГТУ». Основные направления научной деятельности Криптографические методы защиты информации. Схемы разделения секрета. Программирование и компьютерное моделирование. Общее количество опубликованных работ: 4. e-mail: sagaydak.dmitriy@gmail.com

Свенч А. А. - Аспирант ФГБОУ ВПО «ОмГТУ».

Файзуллин Рамиль Рашитович - Кандидат физико-математических наук ФГБОУ ВПО «ОмГТУ», каф. «КЗИ». Основные направления научной деятельности Геометрия и ана-лиз.Математическое программирование. Теория оптимизации. Моделирование. Общее количество опубликованных работ: 8. e-mail: strannik11@list.ru