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

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

ВЕРШИНИН Игорь Сергеевич

МОДЕЛИРОВАНИЕ ДВУМЕРНО-АССОЦИАТИВНЫХ МЕХАНИЗМОВ МАСКИРОВАНИЯ СТИЛИЗОВАННЫХ БИНАРНЫХ ИЗОБРАЖЕНИЙ

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

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

SepLu.

Казань 2005

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

им. А.Н. Туполева

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

профессор Райхлин Вадим Абрамович

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

профессор Фурман Яков Абрамович

кандидат физико-математических наук Горбунов Николай Иванович

Ведущая организация:

НИИ математики и механики им. Н.Г. Чеботарева (г. Казань)

Защита состоится «25"» ¿киртл. 2005 г. в часов на заседании диссертационного совета Д 212.079.01

при Казанском государственном техническом университете им. А.Н. Туполева по адресу: 420111, г. Казань, ул. К. Маркса, 10

С диссертацией можно ознакомится в библиотеке Казанского государственного технического университета им. А.Н. Туполева

Автореферат разослан

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

П.Г. Данилаев

200^-4 о

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

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

Можно выделить две цели маскирования в данном случае:

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

2) противодействие несанкционированному распознаванию.

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

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

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

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

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

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

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

кирования стилизованных бинарных изображений.

ДОС. НАЦИОНАЛ*»«** БИБЛИОТЕКА

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

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

4. Адаптация развиваемого подхода для случая точечных объектов картографии с учетом проблематики геоинформационных систем (ГИС).

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

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

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

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

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

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

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

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

3. Выбор критерия эффективности и оценка эффективности развитой процедуры.

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

5 Оценка вычислительной сложности реализации механизмов маскирования.

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

Апробация результатов работы. Основные результаты работы докладывались и обсуждались на научно-технической конференции «IX Всероссийские Туполевские чтения студентов» (Казань, 2000г.); городском семинаре «Методы моделирования» (Казань, 2001-2004гг.); Республиканской научно-практической конференции «Интеллектуальные системы и информационные технологии» (Казань, 2001г.); XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 2002г.); V Международной научно-технической конференции «Новый информационные технологии и системы» (Пенза, 2002г.); 7-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (Санкт-Петербург, 2004г.); семинаре отдела автоматизации научных исследований СПИИРАН (Санкт-Петербург, 2004г.); секции НТС ФГУП «НИИ «Квант» (Москва, 2004г.).

Публикации. Основное содержание диссертации опубликовано в 10 работах, включая 6 статей, 3 тезиса докладов и 1 учебное пособие.

Структура и объем диссертации. Диссертационная работа состоит из введения, четырех глав и заключения. Она изложена на 113 страницах, содержит 48 рисунков и 9 таблиц. Библиографический список включает 40 наименований.

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

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

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

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

Рассматриваемая задача идентификации формулируется следующим образом. Для данного троичного эталона (троичной матрицы)

Х'=1х«|; х'ряб {0,1,-},Ч=1...ш',р=1...п,;1е {й}

(Я. - число типов объектов) найти координаты всех покрываемых им объектов двоичного изображения (булевой матрицы)

А=Цая|; але {0, 1}, 1 = 1...К, ] = 1...Ь; К* т', Ь >п'.

Запись х'рс, = (-) означает безразличное (замаскированное) значение соответствующего элемента эталона. Множество замаскированных элементов отображается единичными элементами матрицы масок

0,х'рч е{0,1}; .Ьх'яеН.

Троичный эталон представляется двумя бинарными матрицами: идеального эталона Х2 и маски М1.

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

Естественным требованием к маскированию объектов является взаимная непокрываемость любой пары троичных эталонов множества {X1}, 1е {1Д }, что диктуется требованием однозначности распознавания. Достаточное условие такой непокрываемости - различие хотя бы в одном значащем элементе х^ троичных матриц X'1 и Xй, Ц * 12.

Ограничимся рассмотрением случая, когда объекты изображения представлены в алфавите почтовых индексов (рис. 1). Формулируются следующие утверждения.

Утверждение 1.1. Задача маскирования в случае действия систематических помех в общем случае неразрешима.

Утверждение 1.2. Задача маскирования всегда разрешима, если систематические помехи не затрагивают узлы сетки, а именно сам узел плюс один бит на каждую линию совокупного контура (рис. 2).

При этом минимальные размеры эталонов должны быть не менее чем 5x9. Все остальные биты могут быть подвержены действию помех. Случай же действия помех в указанных местах (т.е. узлах) приводит к необходимости увеличения размеров объектов.

Утверждение 13. Задача маскирования принципиально неразрешима в случае действия стохастических помех.

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

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

Рис. 1

Рис.2

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

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

Формулируется АЛГОРИТМ маскирования, в основе работы которого лежит возможность ассоциации объектов по различию, т.е. достаточность сохранения ограниченного числа бит эталонов для их последующей однозначной идентификации.

АЛГОРИТМ сформулирован таким образом, чтобы обеспечить сохранение минимального количества бит (от 2 до 6), определяемых маской.

Элементы эталона X1, не подлежащие маскированию, определены единичными компонентами инверсной матрицы масок М1 = для этого эталона. Решение задачи маскирования в данном случае существенно многозначно. Один из вариантов решения среди многих других на множестве десятичных цифр в алфавите почтовых индексов показаны на рис. 3. Точками обозначены сохраняемые значения битов (размеры объектов 3x5).

Рис.3

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

АЛГОРИТМ 1. /: = 0.

2.3анумеровать случайную перестановку букв множества О/ в натуральном порядке Э], Э2,... , Эа , образовав тем самым список С/ = (ЭД ] = 1,2, ...а.гдеа-число двоичных эталонов, для которых генерируется набор масок на /-уровне. Дополнить этот список пустым элементом Эа+|. Ни один элемент списка С/ изначально не отмечен.

3. 1: = 1.

4. ]: = I, г: = 1. Считать Э, первым элементом множества 0;+ь

5. Пока не встретится неотмеченный элемент списка С/, ]: = ] + 1. Если не пуст, идти к п. 6. Иначе - к п. 16.

6. Э, © Э} (побитно) А] (булева матрица).

7. Пока не встретится неотмеченный элемент списка С/, ] : = ] + 1. Если Э, не пуст, идти к п. 8. Иначе - к п. 13.

8. Э, © Э; (побитно) —> А2 (булева матрица).

9. А3: = А,.

10. А, & А2 (побитно)-> А|. Если А| *) 0), идти к п. 7. Иначе - к п. 11.

11. г: = г + 1. Считать ЭJ г-элементом множества 0/+|.

12. А|: = Аз. Переход к п. 7.

13. Случайным образом выбрать один из единичных элементов матрицы А,. Его координаты (p,q) определяют новый единичный элемент mw инверсной матрицы масок М для всех неотмеченных эталонов списка С;.

14. Отметить элементы списка С/, включенные во множество D(+).

15. /: = / + 1; D,: = D/+1, а : = г. Переход к п. 2.

16. Формирование инверсной маски для последнего неотмеченного элемента списка С/ считать законченным. Отметить этот элемент, аннулировав тем самым список С/ и множество Dm (сделав их пустыми).

17. /: = I - 1. Если 1 > 0, идти к п. 18. Иначе - к п. 19.

1В. Пока не встретится неотмеченный элемент списка Q , i : = i + 1. Переход к п. 4. 19. КОНЕЦ.

Работу алгоритма иллюстрирует рис. 4.

,9-

11

* м у ' п 19 f

1 3 5566 1 3 „ 14321

et i S S i I С) 1 Ц j

Э| Эг Э) э4 3f э» э? э» э» э» Рис.4

Переупорядочение элементов при переходе на вышестоящий уровень на рисунке не показано. Точками выделены элементы списков С/. Кружками - отметки этих элементов. Факт аннулирования списка обозначен петлей обратной связи для его последнего неотмеченного элемента. Цифры на стрелках проставлены в порядке наступления совокупных событий подъема - спуска между уровнями. Замечаем, например, что списки Ci и Q аннулировались по 4 раза, а списки Со и С3 - по одному.

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

Случайность сгенерированного набора масок при каждом применении АЛГОРИТМА обеспечивается произвольными перестановками порядка следования эталонов на разных этапах его работы и случайным выбором единиц на

формируемы* при этом булевых матрицах, т.е. случайным выбором значащих бит эталонов.

Формулируются и доказываются следующие утверждения, определяющие некоторые свойства АЛГОРИТМА. Эти утверждения используются при доказательстве теоремы маскирования 2.1.

Утверждение 1.4. Произвольная маска любого набора как результата работы АЛГОРИТМА либо уникальна (отвечает одному эталону), либо является общей для некоторой пары эталонов.

Утверждение 1.5. Для любого такого набора существует по крайней мере одна маска, общая для некоторой пары эталонов.

Утверждение 1.6. Пара троичных эталонов с общей инверсной матрицей масок дихотомизируется одной единицей этой маски.

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

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

Теорема 1.1. При хранении или передаче изображения в целом (без сжатия) задача маскирования по АЛГОРИТМУ для битовой сетки кадра в общем случае неразрешима.

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

Крупные объекты размерами (с'х<1') байт; с', <1* > 1, естественным образом разбиваются на элементарные фрагменты (1x1) байт. Это позволяет проводить распознавание в 2 этапа. Сначала распознаются отдельные фрагменты. Затем они "сцепляются" в соответствии с эталоном объекта. По условию мощность Г| множества типов элементарных фрагментов для всех объектов изображения 2<Т1<(3, где - число возможных двоичных представлений байта. Обозначив каждый тип фрагмента определенным символом, получим представление эталона объекта в виде матрицы принятых символов.

Теорема 1.2. Задача маскирования "неплотных" изображений, хранимых или передаваемых без сжатия, при использовании дополнительной байтовой

сетки кадра и мощности множества элементарных фрагментов по совокупности объектов г) < <2 принципиально разрешима в расширенном алфавите символов.

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

В качестве критерия эффективности выбирается

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

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

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

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

Формулируется и доказывается теорема маскирования, положенная в основу анализа стойкости.

Теорема 2.1. Если при генерации наборов масок использован АЛГОРИТМ, то для любой реализации множества рандомизированных объектов и любого вновь сгенерированного множества троичных эталонов этих объектов каждый рандомизированный объект покрывается одним и только одним эталоном. При этом один эталон может покрывать несколько объектов, а однозначная идентификация может быть как правильной, так и ошибочной.

Анализ стойкости проводится в 2 этапа.

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

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

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

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

Пусть А. = 3, объекты представлены цифрами 1,2 и 3, размеры эталонов и масок 3x5 бит, истинное сообщение отвечает перестановке (1, 2, 3). На рис. 5,а,б показаны два рассмотренных варианта маскирования объектов в сообще-

нии (сохраняемые биты выделены знаком .) и по три исхода рандомизации -(1), (2) и (3) для каждого варианта. Найденные путем полного перебора ключей числа однозначных идентификаций всевозможных перестановок для указанных случаев приведены в табл. 1. Максимум идентификаций для каждого случая выделен знаком О.

<1

(1) (1)

а 1 1 Ш1 о Ш > о 5 0 0 > и 0 I ! V

1 с 1 0 0 0 1 1 1' и 0 '> ■-> 1 0 I 1 0

0 1 1 1 0 0 0 1 1 0 Е 1 1 011 С Щ»

1 0 0 1 С-- 1 0 1 Л о Е : 001 <1 1 О

0 0 о 1 Ш : 1 г! 1 1 ) ; 1

(2) (1)

63 1 0 Ш1 о Шо о 0 1 0 1 1 -. 1 1

1 0 ) 0 0 1 0 1 1 з 1 <% о 0 0 1 1 !

О 1 1 ООО 0 1 0 0 0 0 1 01 1 Шо

1 I 0 0 1 1 1 1 0 о И 0 1 шо 0 1 1

0 0 0 о 1 Ш 1 00 0 1 0 1 1 1 ! 0 1

(3) <3>

0 1 0 Шо 1 Шо о 0 ) 1 0 1 1 0 с- 1

1 1 1 С 1 и 0 1 1 У 0 1 1 и V 1 >

0 0 1 ООО 0 I 0 II 0 и 101 : ШУ

0 1 0 ООО 0 0 1 ; Ш 0 о Шо 0 0)

0 0 0 о 1 Щ о 1 © : 1 1 1 0 0 0 1 1

Рис.5

Табл. 1

Идентифицируемые Число ключей однозначных идентификаций

перестановки Рис. 5,а Рис. 5,6

(1) (2) (3) (1) (2) (3)

0,2,3) Ф 4 2 4

(1,3,2) 1 — 3 2 б —

(2,1,3) 2 3 5 (10) 1 1

(2,3,1) — 2 («) 1 <9)

(3,1,2) — — 8 1

(3,2,1) — 4 2 — 8 3

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

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

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

Сделанный вывод безотносителен к оценке сложности полного перебора ключей. Но эта оценка важна для дальнейшего. Полный перебор проблематичен. Число вариантов ключей при X = 10 и шхп = 3x5 составляет примерно 3-Ю12. Для mxn = 8x8 эта оценка возрастает до 1015. При этом реализация 105 попыток распознавания на ЭВМ класса Pentium IV по специальной программе занимает в среднем 0,5 часа. Проведение 1015 опытов потребует более 0,5 миллиона лет непрерывной работы компьютера.

2. Анализ стойкости к несанкционированному распознаванию рандомизированных по маске сцен.

- Случай единообразной рандомизации

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

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

- Случай пошаговой рандомизации

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

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

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

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

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

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

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

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

48 49 50 51 52 53 54

** I < >__

» -ч ч. 1 )

56 ,4 А ;

^ ^ ею ____

г" О +

Г ^ « )

в д

V I

55 л»

* А

V

о ^ л о \

„ / Л" „

' V / ^ |

41

4 Г 1

54 /

»у

Рис. 6

Исходное изображение представляется в сжатом виде. При этом множество тематических карт-кластеров задается следующим образом. Имя карты

< ИМЯ_ТЕМЫ > <ГЛОБАЛЬНЫЕ_КООРДИНАТЫ_КАДРА>, где кадр - участок определенных размеров на некоторой карте местности. Тематическая карта формируется как отношение с кортежами:

<ИМЯ_ОБЪЕКТА> <ЛОКАЛЬНЫЕ_КООРДИНАТЫ_ОБЪЕКТА>.

По условию мощности множеств имен и градаций значений координат не превышают величины Г, что допускает единообразное кодирование имен и координат словом длины к > 1оёгГ в алфавите почтовых индексов (у £ 10) при сохранении семантических особенностей кодов разных уровней.

Любая из 10 букв этого алфавита представлена двоичными матрицами эталона и маски размерами тхп бит, п=2т-1. По известным отношениям генерируется множество зашифрованных тематических карт. Совокупность карт и эталонов составляет графическую базу данных. Роль базы знаний - секретного ключа выполняет соответствующий набор масок. Знание ключа необходимо для идентификации карт и дешифрации их содержимого.

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

Л2.?Ч5.6/.В,9Д

Алгоритм кластеризации:

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

2. Выбираем размеры кластера (карты) 4ХТ1 (1 < £ < ¡тх, 1 < Л < .ь«) для размещения подтаблиц фрагментов исходного текста, где .¡„в* - размеры страницы. Принципы формирования кластеров поясняют п. 3,4.

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

Символ (0,0)

Здесь (0, 0) - локальные координаты выделенного объекта в данном кластере.

4. Повторяем п. 3 Оши^ти) раз на множестве неотмеченных строк. При этом всякий раз устанавливаем принадлежность вновь выделенной строки к одному из ранее введенных кластеров и преобразуем координаты (из глобальных по тексту в локальные по кластеру). Если такового кластера не оказывается, инициируем новый кластер. И так далее, пока не будут исчерпаны все записи исходной таблицы.

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

5. Стилизуем используемые символы как бинарные изображения в виде двоичных матриц - эталонов размерами шхп, п = 2т - 1 (используется алфавит почтовых символов).

6. Случайным образом по АЛГОРИТМУ генерируем набор масок для множества используемых символов.

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

Отнесение некоторого объекта к тому или иному случайно формируемому кластеру связано с упорадоченным (по времени образования кластера) пе-

ребором и рядом проверок. Это определяет своеобразие реализации принципа "рассеивания " - первого-основополагающего принципа шифрации.

АЛГОРИТМ маскирования оставляет в каждой цифре от 2 до 6 значащих элементов. При этом множества таких элементов случайно распределены по совокупному контуру всех символов. Соответственно "плавают" координаты ран-домизируемых элементов в каждой матрице, а число таких элементов и потенциальная стойкость маскирования растут с увеличением ш. Так реализуется "перемешивание " - второй основополагающий принцип шифрации.

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

Полагая число градаций (значений кодов) объектов и их координат Г = Vе, для разных у и к получаем ряд значений Г = (2 - 10), 16,25,27,32,36, 49, 64, 81,100, 125, 128,216,243,256,343,512,625,729,1000,... Этот ряд нерегулярен. Число же градаций объектов Го« - некоторый элемент натурального ряда 2 , 3,..., 1000,... Поэтому для достижения совершенной секретности по Шеннону в общем случае необходимо вводить пустые объекты. Обозначим через 5 степень неоднозначности их кодирования. Тогда число типов непустых объектов Гов = Т ~ 8. Код конкретного пустого объекта должен выбираться случайно на множестве из б вариантов. Эти объекты определенным образом вводятся по всей картографируемой местности и могут присутствовать в любом кластере.

Рассмотрим некоторую карту местности (рис. 7). На рисунке: У и X -максимальные значения координат (у и х) картографируемого массива, е - заданная погрешность определения координат объектов. Соответственно шаг локальной координатной сетки равен 2е. Согласно показанному ряду градаций координат для Г = ук, обеспечиваемых к-разрядным кодом с основанием у, выбираем подходящее значение Г (вместе с у и к) из условия равенства числа градаций в локальной и глобальной областях. Полагая X = У = А, получаем линейный размер кластера (длину стороны квадрата) С = (2 е) Необходимым условием представления координаты объекта суммой

КООРДИНАТА (х либо у) = ГЛОБ. КООРД. + ЛОК. КООРД. является Л1 Гх,у5 С. Соответственно

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

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

Локальная координатная Картографируемая Объекты

Рис.7

В п. 3.4 проводится анализ стойкости замаскированных данных к различного рода атакам. Рассматриваются следующие типы атак:

1) атака с позиций точного знания некоторых объектов и их координат;

2) атака на передаваемую или хранимую ГАММУ;

3) атака на предмет частичной дешифрации;

4) специфичная атака на предмет отсутствия некоторого объекта на картографированной местности в целом.

5) атака дезинформации направленным действием помех.

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

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

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

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

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

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

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

Удовлетворительный результат (по временному признаку, компьютер Pentium IV) был получен для размеров матриц, оснований и разрядностей, указанных в таблице 2.

Табл. 2

шхп = 20x39

к у = 2 Число ключей: 92 у = 3 Число ключей: 9288 у = 4 Число ключей: 1368180

к = 2 7,08 с 18,226 с 9 мин

к = 3 26,558 d 2,05 мин 1 час 47,64 мин

к = 4 1,9 мин 47,92 мин —

к = 5 37 мин — —

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

Г = 16 (24 или 42), 27 (З3), 32 (25), 64 (43), 81 (З4).

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

Утверждение 4.1. Если число ключей при данном основании у и размерах эталонов шхп меньше числа градаций Г = у*, то критерий К. Шеннона принципиально невыполним.

Существенным недостатком метода в случае малых оснований является потеря стойкости, если противник обладает точными знаниями о некоторых объектах и их координатах. Поэтому целесообразен переход к большим основаниям (у = 10).

Гипотеза. Подходящая рандомизация для обеспечения безусловной стойкости в случае больших оснований (у = 10) всегда существует.

Это утверждение экстраполируется из описанных выше результатов для у = 2 - 4. Принципиальная достижимость нахождения такой рандомизации за ограниченное время при наличии достаточных вычислительных ресурсов постулируется на основании проведенных исследований оценки сложности маскирования в процессе узкого поиска (см. далее) и связывается с увеличением размеров матриц двоичных эталонов и масок. Решению этой задачи может помочь использование параллельных вычислительных систем.

Для у = 10 (т.е. используется полный алфавит почтовых индексов) для числа градаций до 100 выбирается разрядность к = 2; более 100 - к = 3.

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

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

1. Случайным образом определить количество V внедряемых пустых объектов (от 1 до 1000).

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

3. Проверить выбранные координаты на совпадение с координатами существенных объектов и ранее введенных пустых объектов. Если координаты совпали, выбрать иные координаты.

4. Повторить пп. 2,3 V раз.

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

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

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

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

Оценка сложности метода проводилась экспериментально. Рассматривается случай полного осневания (у = 10). Дополнительные ограничения: к = 3, буквы любого кодового слова попарно различны (Гт^ = 720).

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

Обозначим: К = ABC - шифрограмма как упорядоченная последовательность трех рандомизированных символов; А, В, С - двоичные матрицы |аД |bj.,|, |cj;

{D, Е, F) - подмножество эталонов в алфавите почтовых индексов (D, Е, F е {0,9}), всевозможные перестановки которых являются предметом распознавания в К.

Введем понятие к-подмножеств указателей нулей усеченных масок на {А, В, С} ({D, Е, F}). Эти указатели представлены векторами (записями)

<K,/,(j,i),R>,K = 0,1,2.....

0-подмножество является пустым. Значение 1 = 0 отмечает общий дихотомапь-ный бит на {А, В, С} ({D, Е, F}). Указатель матриц R = ABC (DEF) при / = 0. Если же /=1,2,..., то R = AB(DE) v AC(DF) v BC(EF). Множество допустимых наборов масок для данных К и DEF представляется полной совокупностью соответствующих к-подмножеств.

Полная задача, решаемая рассматриваемым далее АЛГОРИТМОМ 2, состоит в следующем. Путем узкого поиска на множествах {А, В, С} и {D, Е, F} выявить перестановки на {D, Е, F}, которые шифрограмма К заведомо не представляет. Это должно означать отсутствие на тематической карте соответствующего объекта или координаты. И так - для любых неповторяющихся "троек" почтовых символов. Пусть DEF - одна из таких перестановок. Тогда будем писать К v» DEF. Результат К -> DEF как итог узкого поиска мало информативен, ибо требует проверки перебором на полном множестве ключей.

Утверждение 4.3. Если К v» DEF, то соответствующий объект или координата на тематической карте отсутствует.

Соответственно критерием выбора подходящей рандомизации является выполнение условия К -» DEF для любого упорядочения из трех символов. При этом согласно проведенным исследованиям частота импликаций тех или иных кандидатов на распознавание роли не играет.

АЛГОРИТМ 2

1. Сформировать множества координат

Ü. >}ав, {j, i}ас, ti, Ubc; ti, >}de, ti, í}df, ti, í}ef дихотомальных бит всех пар двоичных матриц отдельно из {А, В, С} и {D, Е, F}. Соответственно ограничить области поиска:

TAB={j, 1}авп ti, 'Ье; TAC={j, í}ac<^ {j, «}of; TBC={j, i}BCn {j, i}EF. Элементы множеств ТАв, TAc, Твс имплицировать в записи

</,(j,i),R>,/=l,2,...,

одноименных таблиц, атрибут (j, i) которых определяет координаты нулей в соответствующих парах допустимых масок.

2. Сформировать множества координат

{j. í}abc ; (j, iJobF

дихотомальных бит троек ABC и DEF в целом. Ввести еще одно ограничение:

Sabc = {j, ¡}abc ^ {j. '}def-Построить одноименную таблицу указателей

{к ДО, i), R}, / = О,

где к - номер записи, a (j, i) показывает нули в полной тройке допустимых масок.

3. Сформировать к-подмножества указателей в составе одной из записей таблицы Sabc (заголовка) и соответствующей этой записи полной таблицы -Tab, Tac или Твс- Заголовок вместе с любой записью присоединенной таблицы определяют некоторый допустимый набор масок.

4. На найденном таким образом множестве допустимых наборов масок провести сравнения на равенство размаскированных бит шифрограммы и распознаваемого кодового слова (отмеченных нулевыми значениями бит матриц масок). Отрицательный результат всех сравнений интерпретировать как К •>*> DEF. Иначе (хотя бы один положительный результат) К —> DEF.

Сложность маскирования оценивалась экспериментально (компьютер Pentium IV) следующим образом.

1. По АЛГОРИТМУ генерировались случайные маски.

2. Последовательно для каждого из 720 возможных кодов проводилась рандомизация (генерировалась шифрограмма).

3. По АЛГОРИТМУ 2 для любой шифрограммы выявлялось множество кандидатов на истинное сообщение. Если их число оказывалось меньше 720, проводилась новая рандомизация, и процесс повторялся до тех пор, пока число распознаваний не становилось равным 720.

При m = 10 и 8 поиск нужной рандомизации потребовал в среднем 3 и 13 часов на 720 кодовых слов.

Утверждение 4.4. В случае m > 8 для любого допустимого ключа, сформированного АЛГОРИТМОМ, и любого кодового слова длины к = 3 в алфавите почтовых индексов существует рандомизация такая, что при узком поиске рассматриваемый метод маскирования удовлетворяет критерию К. Шеннона. Временные затраты на ее нахождение уменьшаются с ростом т.

Найденная оценка сложности: к = 3, m > 8,п > 15.

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

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

Особенностью ГИС является возможность разделения информации об объектах на тематические слои в соответствии с предметной областью.

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

Подсистема защиты данных разработана для ГИС Мар1п1Ъ и состоит из следующих модулей:

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

2. Модуль шифрации объектов выбранного слоя

3. Модуль генерации масок (ключа)

4. Модуль рандомизации

5. Модуль дешифрации

6 Модуль полного или частичного отображения (восстановления) объектов тематического слоя.

Модуль селекции и кластеризации проводит выборку тематического слоя и преобразование полученной информации к виду "объекты-координаты". Модуль шифрации предназначен для шифрования полученных в результате работы предыдущего модуля кластеров. Для получения ключа (набора масок) осуществляется вызов модуля генерации масок, который реализует АЛГОРИТМ маскирования. Модуль рандомизации осуществляет рандомизацию замаскированных бит эталонов. Модуль дешифрации предназначен для дешифрирования зашифрованной базы данных. Модуль отображения объектов проводит обратное преобразование локальных координат объектов по кластеру в глобальные и отображение расшифрованного тематического слоя на карте местности. В заключении сформулированы основные результаты диссертации.

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

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

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

- основной АЛГОРИТМ маскирования;

- способ рандомизации.

3. Проанализирована разрешимость задачи маскирования по основному АЛГОРИТМУ. Установлено, что для битовой сетки кадра эта задача практически неразрешима. Ее решение следует искать на пути использования дополнительной байтовой сетки.

4. Сформулирована и доказана теорема маскирования, которая положена в основу анализа стойкости предлагаемого метода.

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

уровня стойкости) и получены оценки эффективности с позиций принятой трактовки.

6. Установлена доказуемая стойкость метода при достаточном числе типов объектов и соответствующих размерах эталонов Выявлены случаи перехода от доказуемой стойкости к безусловной (с позиций принятой трактовки критерия К. Шеннона).

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

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

9. Разработан исследовательский Пакет прикладных программ защиты данных ГИС.

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

1. Вершинин И.С., Глебов Е.Е. Алгоритмы сжатия и маскирования стилизованных двоичных изображений при их хранении или передаче //IX Всероссийские Туполевские чтения студентов: Научно-техническая конференция, Казань, 25-26 октября 2000 года: Тезисы докладов. Том II. Казань: Изд-во Казан, гос. техн. ун-та, 2000. С. 22.

2. Райхлин В.А., Вершинин И.С., Глебов Е.Е. К решению задачи маскирования стилизованных двоичных изображений //Вестник КГТУ им. А.Н. Туполева. 2001. №1. С. 42-47.

3. Вершинин И.С. Генерация рандомизированных бинарных изображений //Интеллектуальные системы и информационные технологии: Труды республиканской научно-практической конференции 30 октября — 1 ноября 2001 г. Казань: Отечество, 2001. С. 54-56.

4. Райхлин В.А., Вершинин И.С. О стойкости шифра защиты данных GIS //Новые информационные технологии и системы: Труды V Международной научно-технической конференции - Пенза, ПГУ, 2002. С. 17-19.

5. Райхлин В.А., Вершинин И.С. Элементы криптоанализа двумерного картографического шифра //Вестник КГТУ им. А.Н. Туполева. 2002. №4. С. 48-54.

6. Райхлин В.А., Вершинин И.С., Глебов Е.Е. Практикум по параллельным системам: Учебное пособие. Казань: Изд-во Казан, гос. техн. ун-та, 2003. 74 с.

7. Райхлин В.А., Вершинин И.С. К оценке сложности двумерного картографического шифра //Вестник КГТУ им. А.Н. Туполева. 2003. №4. С. 50-54.

8. Райхлин В.А., Морозов A.B., Вершинин И.С., Абрамов Е.В. Интеллектуальные модели синтеза //Труды конференций IEEE AIS'03, CAD-2003. - М.: Физматлит, 2003. Т.2. С.158-171.

9. Вершинин И.С. Двумерно-ассоциативный механизм защиты бинарных объектов картографии //Эволюционное моделирование /Под ред. В.А. Райхли-на. Труды Казанского городского семинара "Методы моделирования". Вып. 2 -Казань: Изд-во "ФЭН" ("Наука"), 2004. С. 74-89.

10. Vershinin I.S. Data protection of GIS //7th International Conference on Pattern Recognition and Image Analysis: New Information Technologies (PRIA-7-2004). St. Petersburg, October 18-23,2004. Conference Proceedings (Vol. l-III), Volume II., St. Petersburg, SPbETU 2004. P. 556-558.

Формат 60x84 1/6. Бумага офсетная. Печать офсетная. Печ. л. 1,25. Усл. печ. л. 1,16. Усл. кр.-отт. 1,21. Уч.-изд. л. 1,04. Тираж 100. Заказ Е4.

Типография Издательства Казанского государственного технического университета 420111, Казань, К. Маркса, 10

0511- 05./3

РНБ Русский фонд

2005-4 40935

•л"*"

V

I t « * ' ( Í !

1136

ВВЕДЕНИЕ

Глава 1. Распознавание стилизованных бинарных изображений в условиях помех

1.1. Рассматриваемая задача распознавания и подходы к ее решению

1.2. Проблема маскирования и основной алгоритм

1.3. Свойства алгоритма маскирования

1.4. Разрешимость проблемы маскирования

1.5. Выводы

Глава 2. Маскирование как средство противодействия несанкционированному распознаванию

2.1. Теорема маскирования

2.2. Адаптация критерия Шеннона применительно к поиску подходящей рандомизации

2.3. Несанкционированное распознавание упорядоченного множества рандомизированных по маске объектов

2.4. Несанкционированное распознавание рандомизированных по маске сцен

2.5. Выводы

Глава 3. Маскирование точечных объектов картографии

3.1. Необходимые сведения из картографии

3.2. Рассматриваемые структуры данных и вопросы кодирования

3.3. Сравнение маскирования с известными алгоритмами шифрования

3.4. Анализ стойкости замаскированных данных к несанкционированному распознаванию и активному противодействию

3.5. Выводы

Глава 4. Анализ сложности маскирования

4.1. Предельная задача оценки сложности и ее принципиальная разрешимость

4.2. Необходимость снижения требований к уровню стойкости и критерий рандомизации

4.3. Найденная оценка

4.4. Связь с проблематикой ГИС

4.5. Исследовательский Пакет прикладных программ

В диссертации исследуется вопрос о позитивности маскирования (целесообразность использования и достижимые результаты) при распознавании стилизованных бинарных изображений в терминах "объекты-координаты" (анализ сцен). Маскирование является непременным атрибутом ассоциативной обработки при решении арифметико-логических и символьных задач [33]. В этих случаях на каждом шаге всегда обрабатывается лишь одна информационная единица (бит либо байт) любой записи. Все другие исключаются из рассмотрения (маскируются). Но роль маскирования в процессе распознавания до сих пор была далеко не очевидной.

Можно выделить две цели маскирования в данном случае:

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

2) противодействие несанкционированному распознаванию.

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

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

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

Актуальность.

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

Современные симметричные одноключевые системы базируются на принципах, изложенных в работе К. Шеннона "Теория связи в секретных системах" [6]. К ним относятся криптоалгоритмы DES, IDEA, ГОСТ 2814789 и пр. Такие шифры являются универсальными и могут применяться в любой сфере человеческой деятельности, требующей криптографической защиты, тем более что при решении проблем криптографии в настоящее время наиболее часто используется принцип применения известных, исследованных с точки зрения криптографической стойкости, алгоритмов.

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

Цель.

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

Задачи.

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

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

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

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

4. Адаптация развиваемого подхода для случая точечных объектов картографии с учетом проблематики ГИС.

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

Научная новизна работы.

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

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

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

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

Результаты диссертации использованы в ГУП "Татинвестграждан-проект" (г. Казань) и в учебном процессе кафедры Компьютерных систем и информационной безопасности КГТУ им. А.Н. Туполева (КАИ).

Апробация результатов работы.

Основные результаты работы докладывались и обсуждались на научно-технической конференции «IX Всероссийские Туполевские чтения студентов» (Казань, 2000г.); городском семинаре «Методы моделирования» (Казань, 2001-2004гг.); Республиканской научно-практической конференции «Интеллектуальные системы и информационные технологии» (Казань, 2001г.); XIII Международной конференции «Проблемы теоретической кибернетики» (Казань, 2002г.); V Международной научно-технической конференции «Новые информационные технологии и системы» (Пенза, 2002г.); 7-ой Международной конференции «Распознавание образов и анализ изображений: новые информационные технологии» (Санкт-Петербург, 2004г.); семинаре отдела автоматизации научных исследований СПИИРАН

Санкт-Петербург, 2004г.); секции НТС ФГУП «НИИ «Квант» (Москва, 2004г.).

На защиту выносятся следующие положения:

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

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

3. Выбор критерия эффективности и оценка эффективности развитой процедуры.

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

5. Оценка вычислительной сложности реализации механизмов маскирования.

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

Публикации.

Основное содержание диссертации опубликовано в 10 работах, включая 6 статей [8, 22, 34-36, 40], 3 тезиса докладов [37-39] и 1 учебное пособие [5].

Структура и объем работы.

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

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

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

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

- основной АЛГОРИТМ маскирования;

- способ рандомизации.

3. Проанализирована разрешимость задачи маскирования по основному АЛГОРИТМУ. Установлено, что для битовой сетки кадра эта задача практически неразрешима. Ее решение следует искать на пути использования дополнительной байтовой сетки.

4. Сформулирована и доказана теорема маскирования, которая положена в основу анализа стойкости предлагаемого метода.

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

6. Установлена доказуемая стойкость метода при достаточном числе типов объектов и соответствующих размерах эталонов. Выявлены случаи перехода от доказуемой стойкости к безусловной (с позиций принятой трактовки критерия К. Шеннона).

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

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

9. Разработан исследовательский Пакет прикладных программ защиты данных ГИС.

ЗАКЛЮЧЕНИЕ

1. Райхлин В.А. Асинхронные цифровые схемы и модульные структуры. - Казань: КАИ им. А.Н. Туполева, 1980. 102 с.

2. Райхлин В.А. Операционные логико-запоминающие среды. Вопросы применения и синтеза //Автоматика и телемеханика. 1983. № 11. С. 161171.

3. Райхлин В.А. Об использовании аппарата двумерного ассоциативного поиска в процессе распознавания //Проблемно-ориентированные средства повышения эффективности вычислительных систем. — Казань: КАИ им. А.Н. Туполева. 1991. С.38-54.

4. Райхлин В.А. Анализ производительности процессорных матриц при распознавании двоичных образов //Автометрия. 1996. № 5. С.97-103.

5. Райхлин В.А., Вершинин И.С., Глебов Е.Е. Практикум по параллельным системам: Учебное пособие. Казань: Изд-во Казан, гос. техн. ун-та, 2003. 74 с.

6. Shannon С.Е. Communication Theory of Secrecy Systems. //Bell System Technical Journal. V. 28. 1949. №4. P. 656-715.

7. Ростовцев А.Г., Михайлова H.B. Методы криптоанализа классических шифров. М.: Наука. 1995. 208 с.

8. Райхлин В.А., Вершинин И.С., Глебов Е.Е. К решению задачи маскирования стилизованных двоичных изображений //Вестник КГТУ им. А.Н. Туполева. 2001. №1. С. 42-47.

9. Каев А. Системы координат в картографии и геодезии Интернет-адрес: http://www.firststeps.ru/gis/geodez/r.php?3

10. Ю.Дьяков Б.Н. Геодезия. Общий курс. Интернет-адрес:http://www.ssga.ru/metodich/geodesyep/index.html

11. П.Ключевский Б. Криптографические алгоритмы Интернет-адрес: http://ns.ssl.stu.neva.ru/psw/crypto/Kluchev21.html

12. Винокуров А. Шифрование и шифры Интернет-адрес:http://www.enlight.ru/ib/tech/crypto/part3.htm

13. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си М.: Издательство ТРИУМФ, 2002. 816 с.

14. М.Жельников В. Криптография от папируса до компьютера. М.: ABF, 1997. 336 с.

15. Молдовян А.А., Молдовян Н.А., Советов Б.Я. Криптография СПб.: Лань. 2000. 224 с.

16. Молдовян А.А., Молдовян Н.А., Гуц Н.Д., Изотов Б.В. Криптография: скоростные шифры. СПб.: БХВ-Петербург. 2002. 496 с.

17. Винокуров А. Архитектура блочных шифров Интернет-адрес: http://alexeenko.prima.susu.ас.ru/cryptography/ib/p art4.php

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

19. Осмоловский C.A. Стохастические методы защиты информации М.: Радио и связь. 2003. 320 с.

20. Райхлин В.А., Вершинин И.С. Элементы криптоанализа двумерного картографического шифра //Вестник КГТУ им. А.Н. Туполева. 2002. №4. С. 48-54.

21. Зубов А.Ю. Совершенные шифры Интернет-адрес:http://www.cryptography.ru/db/msg.html?mid=l169432& uri=introduction.html

22. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999. 320 с.

23. Основы геоинформатики и ГИС-технологий Интернет-адрес:http://cnit.pgu.serpukhov.su/win/SEMINAR/PREZ/SldOO 1 .htm

24. Лебедев В.Б., Беркович E.B. Анализ информационных ресурсов при проектировании ГИС /Новые информационные технологии и системы: Труды V Международной научно-технической конференции Пенза, ПГУ, 2002. С. 19-22.

25. ДеМерс М.Н. Географические информационные системы. Основы. М: Изд-во Дата+. 1999. 489 с.

26. Картография. Пособие. Интернет-адрес:http://kartograff.hi.ru/polka/kniga/index.php

27. Сережников C.B. Геоинформационные системы что это? - М., НТФ "Трисофт", 1997. 327 с.

28. MapInfo Professional. Руководство пользователя. Maplnfo Corporation Troy, New York. Перевод Журавлев В.И, Колотов А.Ю., Николаев В.А., 2000г. 708 с.

29. MapBasic. Среда разработки. Руководство пользователя. Maplnfo Corporation Troy, New York. Перевод Журавлев В.И, Колотов А.Ю., Николаев В.А., 2000г. 619 с.

30. MapInfo Professional v6.0 Tutorial. Электронный учебник.

31. Райхлин В.А., Борисов А.Н. Основы организации микропроцессорных систем. Казань: Изд-во Казан, гос. техн. ун-та, 1998. 300 с.

32. Райхлин В.А., Вершинин И.С. К оценке сложности двумерного картографического шифра //Вестник КГТУ им. А.Н. Туполева. 2003. №4. С. 50-54.

33. Райхлин В.А., Морозов А.В., Вершинин И.С., Абрамов Е.В. Интеллектуальные модели синтеза //Труды конференций IEEE AIS'03, CAD-2003. М.: Физматлит, 2003. Т.2. С.158-171.

34. Вершинин И.С. Двумерно-ассоциативный механизм защиты бинарных объектов картографии //Эволюционное моделирование /Под ред. В.А. Райхлина. Труды Казанского городского семинара "Методы моделирования". Вып. 2 Казань: Изд-во "ФЭН" ("Наука"), 2004. С. 7489.

35. Вершинин И.С. Генерация рандомизированных бинарных изображений //Интеллектуальные системы и информационные технологии: Труды республиканской научно-практической конференции 30 октября 1 ноября 2001 г. Казань: Отечество, 2001. С. 54-56.

36. Райхлин В.А., Вершинин И.С. О стойкости шифра защиты данных GIS //Новые информационные технологии и системы: Труды V Международной научно-технической конференции Пенза, ПТУ, 2002. С. 17-19.