Построение защищенного видеоканала с использованием изоморфизма графов



Скачать 80.91 Kb.
Дата11.10.2012
Размер80.91 Kb.
ТипДокументы
ПОСТРОЕНИЕ ЗАЩИЩЕННОГО ВИДЕОКАНАЛА С ИСПОЛЬЗОВАНИЕМ ИЗОМОРФИЗМА ГРАФОВ

А.В. Пролубников, Р.Т. Файзуллин

Омский государственный университет
e-mail: prolubnikov@univer.omsk.su, faizulin@univer.omsk.su
Введение

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

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

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

,

который и поступает в канал связи. Приёмник восстанавливает исходный кадр видеоизображения с помощью функции дешифрования и того же секретного ключа gif" name="object12" align=absmiddle width=32 height=21>:

.

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

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


Шифр двойной перестановки и задача проверки изоморфизма графов

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

Построим по матрицу , а по – матрицу:

, .

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

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

Поскольку , то

,

где

,

поскольку


.

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

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

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

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

Описание криптосистемы

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

Режим выработки ключа. Находясь в режиме выработки ключа к шифру и при помощи протокола выработки общего секретного ключа Хэллмана-Диффи [3] получают некоторое число : . Абонент формирует некоторую случайную (или псевдослучайную) двойную перестановку пикселей изображения . Матрица перестановки вершин соответствующего графа – некоторая матрица перестановки , которая задает как матрицу перестановки строк пикселей , так и матрицу перестановки столбцов пикселей изображения . Двойная перестановка изображения отправляется абоненту . Абонент , также владея числом , обладая как , так и его двойной перестановкой, сопоставляет этим изображениям взвешенные графы, и, решая задачу проверки изоморфизма графов, также получает перестановку .

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

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

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

,

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

Выполнение приведенного выше неравенства обеспечивается также тем, что , а время работы таких алгоритмов проверки изоморфизма графов, как VF алгоритм, алгоритм Улльмана, алгоритм Nauty, для определения не превышает 0.01 c [4], если сигнальные изображения представлены числовыми матрицами размерности , поскольку графы, соответствующие сигнальным изображениям, заведомо изоморфны и являются графами с тривиальными группами автоморфизмов, а число их вершин не превышает 100. Это позволяет добиться устойчивой передачи видеоизображения при моделировании криптосистемы на компьютере Pentium II с тактовой частотой 500MHz.

Заключение

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

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

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

Список литературы

1. Володин A.A., Митько В.Г., Спинко Е.Н. Обработка видео в системах телевизионного наблюдения // Вопросы защиты информации. М.: 2002. С. 34-47.

2. Faizullin R., Prolubnikov A. An Algorithm of the Spectral Splitting For The Double Permutation Cipher // Pattern Recogniton and Image Analysis. MAIK, Nauka. Vol. 12. С. 365-375. No. 4, 2002.

3. Иванов М.А. Криптографические методы защиты информации в компьютерных системах и сетях. М.: КУДИЦ-ОБРАЗ, 2001, С. 365-375.

4. Foggia P., Sansone C., Vento M., A Database of Graphs for Isomorphism and Subgraph Isomorphism Benchmarking // Proc. of the Third IAPR TC-15 International Workshop on Graph Based Representations, Italy, 2001.

Похожие:

Построение защищенного видеоканала с использованием изоморфизма графов iconРешение для всех случаев задачи проверки изоморфизма графов, представленных в известных библиотеках тестовых задач
Об алгоритмах проверки изоморфизма графов, использующих полиномиально-вычислимые спектральные ин
Построение защищенного видеоканала с использованием изоморфизма графов iconПрименение различных инвариантов графов к проверке изоморфизма некоторых видов графов
Мельникова Е. А., Сайфуллина Е. Ф. Применение различных инвариантов графов к проверке изоморфизма некоторых видов графов. // Проблемы...
Построение защищенного видеоканала с использованием изоморфизма графов iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Построение защищенного видеоканала с использованием изоморфизма графов iconOracle Label Security позволяет контролировать доступ к каждой строке
Построение защищенного программного обеспечения задача комплексная и неординарная, при этом администрирование политики безопасности...
Построение защищенного видеоканала с использованием изоморфизма графов iconДуховно-физический изоморфизм
Духа и материи. Духовная доминанта изоморфизма представлена символикой библейской мифологии. Физика изоморфизма базируется на явлении...
Построение защищенного видеоканала с использованием изоморфизма графов iconДуховно-физический изоморфизм
Духа и материи. Духовная доминанта изоморфизма представлена символикой библейской мифологии. Физика изоморфизма базируется на явлении...
Построение защищенного видеоканала с использованием изоморфизма графов iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Построение защищенного видеоканала с использованием изоморфизма графов iconА. О. Пришляк Пусть g ориентированный граф вложенный в поверхность Ф, а G’ в Ф’. В настоящей работы решается задача
Вопрос о существовании такого гомеоморфизма равносилен вопросу о возможности продления изоморфизма графов до гомеоморфизма поверхностей....
Построение защищенного видеоканала с использованием изоморфизма графов iconПрограмма наименование дисциплины: Теория конечных графов
Основной целью освоения дисциплины является изучение классической теории конечных графов, а также применение методов теории конечных...
Построение защищенного видеоканала с использованием изоморфизма графов iconО модулярной проблеме изоморфизма для групп порядка
Пусть – конечная -группа, – поле из элементов, – групповая алгебра. Модулярная проблема изоморфизма групповых алгебр звучит следующим...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org