Исследование и разработка универсального метода стегоанализа на основе использования NIST-тестов тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат наук Нгуен Зуи Кыонг

  • Нгуен Зуи Кыонг
  • кандидат науккандидат наук
  • 2020, ФГБОУ ВО «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича»
  • Специальность ВАК РФ05.13.19
  • Количество страниц 136
Нгуен Зуи Кыонг. Исследование и разработка универсального метода стегоанализа на основе использования NIST-тестов: дис. кандидат наук: 05.13.19 - Методы и системы защиты информации, информационная безопасность. ФГБОУ ВО «Санкт-Петербургский государственный университет телекоммуникаций им. проф. М.А. Бонч-Бруевича». 2020. 136 с.

Оглавление диссертации кандидат наук Нгуен Зуи Кыонг

ВВЕДЕНИЕ

ГЛАВА 1. СТЕГОСИСТЕМЫ И ОСНОВНЫЕ МЕТОДЫ ИХ ОБНАРУЖЕНИЯ

1.1. Основные понятия стеганографии и стегоанализа

1.2. Методы стеганографии и стегоанализа для цифровых изображений и видеосигналов стандарта MPEG-2

1.2.1. Стегосистема с вложением в наименьшие значащие биты с замещением

1.2.2. Стегосистема с вложением в наименьшие значащие биты с «согласованием» (СГ-±1НЗБ)

1.2.3. Матричное вложение

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

1.2.5. Проект HUGO

1.2.6. Описание стегосистемы для видеосигналов стандарта MPEG-2

1.2.7. Слепой стегоанализ

Выводы по главе

ГЛАВА 2. ОБНАРУЖЕНИЕ СТЕГОСИСТЕМ НА ОСНОВЕ ИСПОЛЬЗОВАНИЯ NIST-ТЕСТОВ НА ПСЕВДОСЛУЧАЙНОСТЬ

2.1. Описание стандарта «NIST-тесты»

2.2. Принцип обнаружения стегосистем на основе использования NIST-тестов

2.3. Экспериментальные результаты стегоанализа на основе использования NIST-тестов для СГ-НЗБ

2.4. Экспериментальные результаты стегоанализа на основе использования NIST-тестов для СГ-HUGO

2.5. Экспериментальные результаты стегоанализа на основе использования NIST-тестов для СГ-видео

2.6. Выводы по главе

ГЛАВА 3. ОЦЕНКА СТЕГОКЛЮЧЕЙ ДЛЯ СТЕГОСИСТЕМ, ИСПОЛЬЗУЮЩИХ СТОЙКОЕ ШИФРОВАНИЕ ВЛОЖЕННЫХ СООБЩЕНИЙ

3.1. Оценка стегоключей универсальным методом стегоанализа для стегосистемы с матричным вложением на кодах Хэмминга

3.2. Оценка стегоключей в стегосистеме HUGO

3.3. Выводы по главе

ГЛАВА 4. МОДИФИКАЦИЯ КРИПТОГРАММЫ ДЛЯ ЗАЩИТЫ СТЕГОСИС-ТЕМ ОТ АТАКИ ИХ ОБНАРУЖЕНИЯ, ИСПОЛЬЗУЮЩЕЙ NIST-ТЕСТЫ

4.1. Описание метода модификации криптограмм на основе использования алгоритма сжатия «Deflate»

4.2. Описание метода модификации криптограмм, основанного на использовании алгоритма декомпрессии арифметических кодов

4.3. Дополнительные экспериментальные исследования эффективности использование модификаций криптограммы

4.4. Выводы по главе

ЗАКЛЮЧЕНИЕ

СПИСОК СОКРАЩЕНИЙ И УСЛОВНЫХ ОБОЗНАЧЕНИЙ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ A. АКТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ

ПРИЛОЖЕНИЕ Б. ОПИСАНИЕ АЛГОРИТМОВ NIST-ТЕСТОВ

ПРИЛОЖЕНИЕ В. КРАТКОЕ ОПИСАНИЕ АЛГОРИТМА СЖАТИЯ «DEFLATE»

ПРИЛОЖЕНИЕ Д. РЕАЛИЗАЦИЯ АЛГОРИТМОВ ДИССЕРТАЦИИ В ВИДЕ КОДОВ ИСТОЧНИКА

ВВЕДЕНИЕ

Рекомендованный список диссертаций по специальности «Методы и системы защиты информации, информационная безопасность», 05.13.19 шифр ВАК

Введение диссертации (часть автореферата) на тему «Исследование и разработка универсального метода стегоанализа на основе использования NIST-тестов»

Актуальность темы исследования

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

Благодаря превосходству невидимых техник, стеганография стала полезным инструментом для организаций при обмене важной информацией в среде публичных СМИ (Средства Массовой Информации). Таким образом, стеганография развивается быстро и более изощренно с большим количеством работ, публикуемых ежегодно (не говоря уже о количестве работ, не опубликованных публично) в виде статистики в диаграмме на Рисунке 1.2 (см. Главу 1, стр. 15 в период с 2010 по 2019 год).

Стегоанализ (СГА) - это метод, противоположный стеганографии. Он предназначен для определения наличия дополнительного содержимого, возможно для нахождения его характеристик, а также для извлечения вложенной информации. Исследование стегоанализа в дополнение к изучению стеганографии также имеет два практических применения, а именно: во-первых, для эффективного обслуживания области информационной безопасности; во-вторых, для того, чтобы модернизировать и способствовать развитию технологии стеганографии.

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

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

Степень разработанности темы

Разработка приложений и академические исследования в области цифровой стеганографии и стегоанализа начались в основном в 1990-х годах и с тех пор неуклонно увеличиваются их количество, а также глубина [1].

Основоположниками в данной научной области можно назвать таких ученых, как J. Fridrich, G.J. Simmons, Phil Sallee, Yun-Qing Shi, Miroslav Goljan, F. Petitcolas, C.Cachin, Andrew D. Ker, Hyoung Joong Kim, В.И. Коржик, И. Н. Оков, Б.Я. Рябко, и др. Наиболее значимые работы, посвященные разработке стеганографии, принадлежат таким ученым как J. Fridrich [19, 31, 35, 43], C. Cachin [15], Phil Sallee [1, 55], Andrew D. Ker [14, 22], Коржик В. И. [13, 20, 30, 45], Оков И. Н. [34].

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

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

Стегосистемы для неподвижных изображений, а также видео формата MPEG-2.

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

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

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

Цели и задачи исследования

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

Для исследования возможности нового метода обнаружения СГ на основе использования МЗТ-тестов, а также возможности защиты СГ от такой атаки решается ряд частных задач:

1. Развить и исследовать универсальный метод обнаружения стегосистем на основе использования МЗТ-тестов, недавно предложенный на уровне гипотезы научным руководителем; оценить результаты обнаруживаемости стегосистем посредством экспериментального исследования для основных стегосистем, таких как стегосистемы с вложением в наименьшие значащие биты с замещением (СГ-НЗБ), и с согласованием (СГ-±1НЗБ), СГ-НЦОО, стегосистема для изображений при контурном вложении (СГ-К), видео-стегосистема (СГ-видео).

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

3. Исследовать методы модификации криптограмм для защиты от атаки обнаружения стегосистем, использующей МЗТ-тесты.

Научная новизна

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

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

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

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

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

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

1. Расширен класс алгоритмов обнаружения стегосистем в части исследования нового метода стегоанализа, основанного на использовании МЗТ-тестов.

2. Установлены основные ограничения применимости данного метода стегосистемами: СГ-НЗБ, СГ-±1НЗБ, СГ-К, СГ-НШО, и СГ-видео формата MPEG-2.

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

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

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

1. Материалы работы по методу обнаружения стегосистем с использованием NIST-тестов могут быть использованы как при разработке новых стегосистем, так и при построении системы DLP (Data Leakage Prevention).

2. Метод оценки стегоключей для СГ может применяться для поиска стегоключей всех СГ, при условии, что известен или найден алгоритм извлечения информации, что позволит извлекать вложенную информацию при возможности взлома шифра.

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

Практическая значимость основных результатов диссертации подтверждается актами о внедрении, полученными от организаций: СПбГУТ, СПбГУПТД, и акционерного общества «НАУЧНЫЕ ПРИБОРЫ» (Приложение A).

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

Для решения поставленных задач использовались теоретические методы, основанные на разделах прикладной математики, таких как теория вероятности и математическая статистика, теория кодирования, а также методов компьютерного моделирования и программирования на языке Matlab, в том числе с использованием элементов искусственного интеллекта (метод опорных векторов (с обучением), известного как SVM (Support Vector Machine)).

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

1. Метод обнаружения стегосистем с использованием NIST-тестов и оценка его эффектности.

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

СГ как матричное вложение на кодах Хэмминга и вложением по алгоритму HUGO.

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

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

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

Результаты данной диссертационной работы были апробированы на российских и международных научных конференциях, в том числе: «2017 20-th Conference of Open Innovations Association (FRUCT 20)» (Санкт-Петербург, 2017) [2]; «Federated Conference on Computer Science and Information Systems 2018» (Poznan city - Poland, 2018) [3]; «2019 24-th Conference of Open Innovations Association (FRUCT 24)» (Москва, 2019) [4]; Международной научно-технической и научно-методической конференции «Актуальные проблемы инфотелекоммуникаций в науке и образовании» (АПИНО) (Санкт-Петербург, 2017, 2018, 2019, 2020).

Публикации

По теме диссертации было опубликовано 7 печатных работ. Из них 3 работы были опубликованы в журналах, входящих в перечень ВАК; 4 работы были опубликованы в издающих, включённых в системы цитирования.

Соответствие паспорту специальности.

Содержание исследования соответствуют следующим пунктам специальности 05.13.19 - «Методы и системы защиты информации, информационная безопасность»: п.3. Методы, модели и средства выявления, идентификации и классификации угроз нарушения информационной безопасности объектов различного вида и класса; п.5. Методы и средства (комплексы средств) информационного противодействия угрозам нарушения информационной безопасности в открытых компьютерных сетях, включая Интернет; п.10. Модели и методы оценки эффективности систем (комплексов) обеспечения информационной безопасности объектов защиты.

Личное участие соискателя

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

ГЛАВА 1.

СТЕГОСИСТЕМЫ И ОСНОВНЫЕ МЕТОДЫ ИХ ОБНАРУЖЕНИЯ

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

В криптографии сообщение преобразуется с помощью ключа шифрования. По типу ключа криптосистемы делятся на симметричные имеющие один и тот же ключ шифрования и дешифрования и несимметричные (в которых ключ шифрования отличается от секретного ключа дешифрования) [9], причём, только легальные пользователи имеют ключ дешифрования. Никто не может получить доступ к сообщению без использования такого ключа. Однако передача зашифрованного сообщения может легко вызвать подозрение, и зашифрованное сообщение, таким образом, станет предметом повышенного внимания. Чтобы преодолеть этот недостаток криптографических методов и были предложены методы стеганографии. Стеганография - такая технология, которая вкладывает секретные сообщения в «невинные» покрывающие объекты (изображение, аудио, видео, и др.). Таким образом, стеганография скрывает существование встроенных секретных данных, так что никто не может даже обнаружить факт их присутствия [10, 11].

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

1.1. Основные понятия стеганографии и стегоанализа

Стеганография - это греческое слово, означающее скрытное письмо. Слово «в1е§апов» означает «секрет», а «§гарИу» означает «запись». Термин «стеганография» стал использоваться с 16-го века после появления книги Тритемия «Стеганография» [12]. Но сегодня большинство людей передают данные в виде текста, изображений, видео и аудио при помощи сети Интернет.

Более того, стегосистемы предназначены для скрытного вложения секретной информации в «невинные» покрывающие объекты. В качестве ПО могут использоваться неподвижные, а также подвижные изображения (клипы и видеофайлы), звуковые (речевые и музыкальные) файлы, текстовые файлы, сканированные документы, программный код, сетевые протоколы и т.д. ПО до вложения и после вложения (СГ) предполагаются цифровыми, и поэтому будут рассматриваться только так называемую цифровую стеганографию [13].

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

На Рисунке 1.1 показаны основные компоненты стегосистемы, а также процесс вложения секретной информации в покрывающие объекты.

Рисунок 1.1 - Блок-схема стегосистемы

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

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

Стегоключ: Используется при вложении и извлечении информации.

Стеганография в широком смысле - это скрытие информации (IH -Information Hiding) или семейство методов, которые обеспечивают вложение некоторой дополнительной информации в ПО при условии того, что качество ПО поддерживается приемлемым. Опишем кратко две основные части скрытия информации: цифровая стеганография и цифровые водяные знаки (ЦВЗ) [13].

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

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

Цели применения стегосистем:

1. Альтернатива КГ при условии того, что она запрещена или ограничена в использовании.

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

3. Ретрансляция секретной информации через неавторизованных пользователей.

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

5. Отслеживание нелегальных распространителей некоторых сообщений.

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

Основная концепция при разработке СГ: Найти шумовые компоненты ПО и заменить их на зашифрованное секретное сообщение.

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

Безопасность стеганографической системы определяется количественно с учётом понятия относительной энтропии (или расстояния Кулъбака-Лейблера) между распределениями стегообъектов и покрывающих объектов, что дает границу для потенциальной способности обнаружения любого стегообъекта [13, 15].

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

Прошедшее десятилетие продолжает оставаться свидетелем роста научных публикаций в области СГ и СГА. На Рисунке 1.2 показано графическое представление этого явления. Технология, используемая в стеганографии, зависит от типа ПО. Наиболее распространенными вариантами таких объектов являются: изображение, аудио файлы, текстовые объекты, видеофайлы и сетевая стеганография [16, 17].

Рост публвкаций в стеганографии и ст er анализ а

S000 7000

в 6000

я

й

В 5000

I

4000 3000

И 2000 1000 о

2010 2011 2012 2013 2014 2015 2016 2017 2018 2019

■Год

Рисунок 1.2 - Рост исследований в области стеганографии и стегоанализа [Google Scholar]

Классификация стеганографии по виду покрывающего объекта

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

Рисунок 1.3 - Классификация стеганографии по виду покрывающего объекта

1) Лингвистическая стеганография

Лингвистическая стеганография (СГ-Л) связана с скрытием информации в тексте, представленном на любом естественном языке. Это означает, что содержание, грамматика, синтаксис и семантика должны быть сохранены полностью. Два основных типа СГ-Л, это: с синонимами и с редактированием [13].

2) Скрытие данных в изображениях

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

3) Аудио стеганография

Метод встраивания секретной информации в аудио файлы известен как аудио стеганография. Этот метод также имеет очень надежный характер, но с ограничением количества данных, которые можно вкладывать. Этот метод вкладывает данные в звуковые файлы WAV, AU, MP3, и т.д. Существуют разные

методы аудио стеганографии, в том числе: 1) кодирование НЗБ; 2) фазовое кодирование; 3) широкополосные сигналы, эхо сигналы и др. [18].

4) Видео стеганография

Видео-стеганографию можно рассматривать как расширение стеганографии для изображений. Фактически, видеопоток состоит из серии последовательных и одинаково распределенных во времени неподвижных изображений; иногда это сопровождается аудио. Поэтому многие методы стеганографии в изображениях применимы и в видео-стеганографии (например, [18]). Видео является очень перспективным типом покрывающих носителей, поскольку оно позволяет погружать большое количество секретных данных. Кроме того, видео -стеганография становится очень важной из-за частого использования и популярности видеофайлов, передаваемых через Интернет.

5) Сетевая стеганография

Сетевая стеганография основана на внедрении скрытной информации в различные интернет-протоколы, такие как TCP/IP (Transmission Control Protocol / Internet Protocol). Встраивание возможно на всех уровнях OSI (Open Systems Interconnection), как показано в следующей таблице. [13]

Таблица 1.1. Возможность встраивать информацию в подчиненные уровни OSI

Уровни эталонной сетевой модели 081 Способность к встраиванию

Прикладной уровень Использование обычной стеганографии

Уровень представления Встраивание в поля сообщений

Сеансовый уровень Мониторинг удаленных сайтов

Транспортный уровень Встраивание в неиспользуемые поля протоколов TCP

Сетевой уровень Встраивание в свободные поля IP-пакетов

Канальный уровень Встраивание в заголовки фреймов, использование CRC (Cyclic Redundancy Check Code)

Физический уровень Использование конфликтных ситуаций: «0» - отправить пакет после некоторой задержки, «1» - отправить пакет сразу после конфликта

Возможность встраивания в заголовки TCP представлена на Рисунке 1.4.

Рисунок 1.4. Возможность встраивания в заголовки TCP

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

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

В настоящей диссертации, используется СГ с встраиванием информации только в цифровые изображения. Есть несколько веских причин для этого выбора [19]. Прежде всего, цифровые изображения являются наиболее распространенным типом объектов, для которых в настоящее время доступны стеганографические приложения. Кроме того, многие базовые принципы и методологии могут быть легко распространены с изображений на другие цифровые объекты, такие как видео и аудио. Также значительно проще объяснить воспринимаемое воздействие изменения изображения, а не аудиоклипа, просто потому, что изображения могут быть напечатаны на бумаге. И, наконец, по сравнению с другими цифровыми объектами, область стеганографии и стегоанализа изображений является самой

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

Основные методы стегоанализа

Стегоанализ является дополнительной задачей для стеганографии. Главная цель СГА - это обнаружить различие между ПО и стегообъектами с вероятностью по крайней мере лучшей, чем случайное угадывание [13, 19, 20], при этом, рассматривается стеганография на цифровых носителях, где ПО - это цифровые неподвижные или видеоизображения, или сигналы, такие как речь и музыка.

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

Все известные ранее стегосистемы сопровождались методами СГА. Одна из первых работ, посвященной СГА в более полной форме, была представлена в монографии I БпёпсЬ [19]. По этой монографии методы СГА можно разделить на две основные области: целевой СГА и слепой СГА.

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

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

1.2. Методы стеганографии и стегоанализа для цифровых изображений и

Похожие диссертационные работы по специальности «Методы и системы защиты информации, информационная безопасность», 05.13.19 шифр ВАК

Список литературы диссертационного исследования кандидат наук Нгуен Зуи Кыонг, 2020 год

СПИСОК ЛИТЕРАТУРЫ

1. Johnson N. F. Detection of hidden information, covert channels and information flows / N. F. Johnson, P. A. Sallee // Wiley Handbook of Science and Technology for Homeland Security. - 2008. - С. 1-37.

2. Valery Korzhik. Detection of stegosystems using block ciphers for encryption of the embedded messages / Valery Korzhik, Ivan Fedyanin, Nguyen Duy Cuong // 2017 20th Conference of Open Innovations Association (FRUCT). - IEEE, 2017. - С. 181186.

3. Korzhik V. [et al.] Secret Key Sharing Protocol Between Units Connected by Wireless MIMO Fading Channels / V. Korzhik, A. Gerasimovich, C. Nguyen, V. Starostin, V. Yakovlev, M. Kabardov, G. Morales-Luna //2018 Federated Conference on Computer Science and Information Systems (FedCSIS). - IEEE, 2018. - С. 569-576.

4. Valery Korzhik. Cipher Modification Against Steganalysis Based on NIST Tests / Valery Korzhik, Nguyen Duy Cuong, Guillermo Morales-Luna //2019 24th Conference of Open Innovations Association (FRUCT). - IEEE, 2019. - С. 179-186.

5. Коржик В. И. Оценка стегоключей для стегосистем, использующих стойкое шифрование вложенных сообщений / В. И. Коржик, З. К. Нгуен, А. К. Годлевский //Проблемы информационной безопасности. Компьютерные системы. - 2018. - №. 3. - С. 26-36. (из перечня ВАК)

6. Коржик В. И. Модификация шифров для защиты от атаки обнаружения стегосистем, использующей NIST-тесты / В. И. Коржик, З. К. Нгуен, К. А. Ахрамеева //Проблемы информационной безопасности. Компьютерные системы. -2020. - №. 1. - C. 33-43. (из перечня ВАК)

7. Ахрамеева К. А. Обнаружение видео стегосистем универсальным методом, основанным на использовании NIST-тестов / К. А. Ахрамеева, В. И. Коржик, З. К. Нгуен // Труды учебных заведений связи. - 2020. - Т. 6. - №. 1. - C. 70-76. (из перечня ВАК)

8. Valéry Korzhik. Side Attacks on Stegosystems Executing Message Encryption Previous to Embedding / Valery Korzhik, Cuong Nguyen, Ivan Fedyanin, Guillermo Morales-Luna // Journal of Information Hiding and Multimedia Signal Processing. -2020. - Т. 11. - №. 1. - С. 44-57.

9. Коржик В. И. Основы криптографии / В. И. Коржик, Яковлев В.А. - СПб, ИЦ Интермедия. - СПб., 2016. - 295 с.

10. Provos N. Hide and seek: An introduction to steganography / N. Provos, P. Honeyman // IEEE security & privacy. - 2003. - Т. 1. - №. 3. - С. 32-44.

11. Piper F. Basic principles of cryptography / F. Piper // IEE Colloquium on Public Uses of Cryptography. - IET, 1996. - С. 2/1-2/3.

12. de Leeuw K. M. M. The history of information security: a comprehensive handbook / K. M. M. de Leeuw, J. Bergstra. - Elsevier, 2007. - 887 с.

13. Коржик В. И. Цифровая стеганография и цифровые водяные знаки. Часть 1. Цифровая стеганография / В.И. Коржик, К.А. Небаева, Е.Ю. Герлинг, П.С. Догиль, И.А. Федянин. - СПбГУТ. - СПб., 2016. - 226 с.

14. Ker A. D. [et al.] Moving steganography and steganalysis from the laboratory into the real world //Proceedings of the first ACM workshop on Information hiding and multimedia security. - ACM, 2013. - С. 45-58.

15. Cachin C. An information-theoretic model for steganography / C. Cachin // Information and Computation. - 2004. - Т. 192. - №. 1. - С. 41-56.

16. Johnson N. F. Steganalysis: The investigation of hidden information / N. F. Johnson, S. Jajodia // 1998 IEEE Information Technology Conference, Information Environment for the Future (Cat. No. 98EX228). - IEEE, 1998. - С. 113-116.

17. Bandyopadhyay S. K. [et al.] A tutorial review on steganography // International conference on contemporary computing. - 2008. - Т. 101. - С. 105-114.

18. Mahajan S. A Review of Methods and Approach for Secure Stegnography / S. Mahajan, A. Singh //International Journal of Advanced Research in Computer Science and Software Engineering. - 2012. - Т. 2. - №. 10. - С. 67-70.

19. Fridrich J. Steganography in digital media: principles, algorithms, and applications / J. Fridrich. - Cambridge University Press, 2009. - 427 c.

20. Korzhik V. [et al.] Steganalysis based on statistical properties of the encrypted messages // International Conference on Mathematical Methods, Models, and Architectures for Computer Network Security. - Springer, Cham, 2017. - C. 288-298.

21. Dumitrescu S. Detection of LSB steganography via sample pair analysis / X. Wu, Z. Wang //International Workshop on Information Hiding. - Springer, Berlin, Heidelberg, 2002. - C. 355-372.

22. Ker A. D. Steganalysis of LSB matching in grayscale images / A. D. Ker // IEEE signal processing letters. - 2005. - T. 12. - №. 6. - C. 441-444.

23. Canny J. A computational approach to edge detection / J. Canny // IEEE Transactions on pattern analysis and machine intelligence. - 1986. - №. 6. - C. 679-698.

24. Kanopoulos N. Design of an image edge detection filter using the Sobel operator / N. Kanopoulos, N. Vasanthavada, Baker // IEEE Journal of solid-state circuits. - 1988. - T. 23. - №. 2. - C. 358-367.

25. Seif A. A hardware architecture of Prewitt edge detection / A. Seif, M. M. Salut, M. N. Marsono // 2010 IEEE Conference on Sustainable Utilization and Development in Engineering and Technology. - IEEE, 2010. - C. 99-101.

26. Afsari F. Interval-valued intuitionistic fuzzy generators: Application to edge detection / F. Afsari, E. Eslami, P. Eslami // Journal of Intelligent & Fuzzy Systems. -2014. - T. 27. - №. 3. - C. 1309-1324.

27. Dadgostar H. Image steganography based on interval-valued intuitionistic fuzzy edge detection and modified LSB / H. Dadgostar, F. Afsari //Journal of information security and applications. - 2016. - T. 30. - C. 94-104.

28. Kadhim I. J. [et al.] Comprehensive survey of image steganography: Techniques, Evaluations, and trends in future research //Neurocomputing. - 2019. - T. 335. - C. 299-326.

29. Pevny T. Using high-dimensional image models to perform highly undetectable steganography / T. Pevny, T. Filler, P. Bas // International Workshop on Information Hiding. - Springer, Berlin, Heidelberg, 2010. - С. 161-177.

30. Korzhik V. Using the generalised Viterbi algorithm to achieve a highly effective stegosystem for images / V. Korzhik, G. Morales-Luna, I. Fedyanin // 2015 Federated Conference on Computer Science and Information Systems (FedCSIS). -IEEE, 2015. - С. 855-860.

31. Pevny T. Steganalysis by subtractive pixel adjacency matrix / T. Pevny, P. Bas, J. Fridrich //IEEE Transactions on information Forensics and Security. - 2010. - Т. 5. -№. 2. - С. 215-224.

32. Korzhik V. A generalization of Viterbi algorithm on the case of channel model described by additive Markov channel / V. Korzhik // Proc. of IV Intern'l Symp on Information Theory, Part II. - 1984. - С. 109-111.

33. Korzhik V. I. Optimal Decoding of Convolutional Codes in Channels with Additive Markov Noise / V. I. Korzhik, Y. P. Lopato // Problemy Peredachi Informatsii. - 1987. - Т. 23. - №. 4. - С. 35-40.

34. Грибунин В. Г. Цифровая стеганография / В. Г. Грибунин, И. Н. Оков, И. В. Туринцев. - М.:СОЛОН-Пресс, 2016. - 262 с.

35. Pevny T. Towards multi-class blind steganalyzer for JPEG images / T. Pevny, J. Fridrich // International Workshop on Digital Watermarking. - Springer, Berlin, Heidelberg, 2005. - С. 39-53.

36. Воронцов, К. В. Лекции по методу опорных векторов: [электронный ресурс] / К. В. Воронцов - 2007. - 18 с. - Режим доступа: http://www.ccas.ru/voron/download/SVM.pdf (Дата обращения 01.01.2020).

37. Bassham III L. E. [et al.] Sp 800-22 rev. 1a. a statistical test suite for random and pseudorandom number generators for cryptographic applications. - 2010. - 131 с.

38. Marsaglia G. The Marsaglia random number CDROM including the DIEHARD battery of tests of randomness /. - 1996. - Режим доступа: http: //stat.fsu.edu/pub/diehard.

39. L'Ecuyer P. TestU01: AC library for empirical testing of random number generators / P. L'Ecuyer, R. Simard // ACM Transactions on Mathematical Software (TOMS). - 2007. - Т. 33. - №. 4. - С. 22.

40. Walker J. ENT: a pseudorandom number sequence test program / J. Walker. -01 января 2020 [Электронный ресурс] Режим доступа: http s: //www.fourmilab .ch/random/.

41. Caelli, W. [et al.] Crypt X Package Documentation, Information Security Research Centre and School of Mathematics, Queensland University of Technology (1992), Crypt-X: http:// www.isrc.qut.edu. au/resource/cryptx/

42. Schneier B. The GOST encryption algorithm / B. Schneier // DR DOBBS JOURNAL. - 1995. - Т. 20. - №. 1. - С. 123-124.

43. Fridrich J. [et al.] Forensic steganalysis: determining the stego key in spatial domain steganography // Security, Steganography, and Watermarking of Multimedia Contents VII. - International Society for Optics and Photonics, 2005. - Т. 5681. - С. 631642.

44. Hsu, C. A Practical Guide to Support Vector Classification / C. Hsu, C. Chang, C. Lin Department of Computer Science and Information Engineering, National Taiwan University, Taiwan, 2010. -2010. - С. 1-16.

45. Korzhik V. Steganographic applications of the nearest-neighbor approach to Kullback-Leibler divergence estimation / V. Korzhik, I. Fedyanin // 2015 Third International Conference on Digital Information, Networking, and Wireless Communications (DINWC). - IEEE, 2015. - С. 133-138.

46. Bas P. "Break our steganographic system": the ins and outs of organizing BOSS / P. Bas, T. Filler, T. Pevny // International workshop on information hiding. - Springer, Berlin, Heidelberg, 2011. - С. 59-70.

47. Menezes A. J. Handbook of applied cryptography / A. J. Menezes, P. C. V. Oorschot, S. A. Vanstone // CRC, West Palm Beach, FL, USA. - 1997. - 746 с.

48. Fontaine C. How Reed-Solomon codes can improve steganographic schemes / C. Fontaine, F. Galand // EURASIP Journal on Information Security. - 2009. - Т. 2009. - №. 1. - С. 274-285.

49. Schonfeld D. Embedding with syndrome coding based on BCH codes / D. Schonfeld, A. Winker // ACH. — Geneva, 2006. — С. 214-221.

50. Syndrome-Trellis Codes Toolbox. - 01 января 2020 [Электронный ресурс] Режим доступа: http : //dde.binghamton.edu/download/syndrome/

51. Oswal S. [et al.] Deflate Compression Algorithm // International Journal of Engineering Research and General Science. - 2016. - Т. 4. - №. 1. - C. 430-436.

52. Marton K. On the interpretation of results from the NIST statistical test suite / K. Marton, A. Suciu //Science and Technology. - 2015. - Т. 18. - №. 1. - С. 18-32.

53. K. Sayood. Introduction to data compression/ Morgan Kaufmann. - Newnes, 2012. - 740 с.

54. DDE Laboratory in the Binghamton University, BOSSBASE 1.01, [Электронный ресурс] Режим доступа: http : //dde.binghamton.edu

55. Sallee P. Model-based steganography //International workshop on digital watermarking. - Springer, Berlin, Heidelberg, 2003. - С. 154-167.

56. Hamano K. Correction of overlapping template matching test included in NIST randomness test suite / K. Hamano, T. Kaneko //IEICE transactions on fundamentals of electronics, communications and computer sciences. - 2007. - Т. 90. - №. 9. - С. 17881792.

57. Salomon D. Data Compression - The Complete Reference - 4th edition / D. Salomon. - Spinger-Verlag, 2007. - 1092 с.

58. Langdon G. A note on the Ziv-Lempel model for compressing individual sequences (Corresp.) / G. Langdon //IEEE Transactions on Information Theory. - 1983. - T. 29. - №. 2. - C. 284-287.

59. Deutsch P. RFC1951: DEFLATE compressed data format specification version 1.3. - 1996. - 17 c.

60. Park B. [et al.] Data extraction from damage compressed file for computer forensic purposes //International Journal of Hybrid Information Technology. - 2008. - T. 1. - №. 4. - C. 89-102.

61. Deutsch P. Zlib compressed data format specification version 3.3 / P. Deutsch, J. L. Gailly. - RFC 1950, May, 1996. - 10 c.

ПРИЛОЖЕНИЕ A. АКТЫ О ВНЕДРЕНИИ РЕЗУЛЬТАТОВ ДИССЕРТАЦИОННОЙ РАБОТЫ

федеральное агентство связи

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

(спбгут)

Нгуен Зуи Кои га на тему: «Исследование и разработка универсального метода стегоанализа на основе

использования NIST тестов»

Настоящий Акт составлен в том, что, что программа универсального метода стегоанализа на основе использования N1ST как результат диссертационной работы, Нгуен Зуи Конга, была использована в учебном пособии "Основы стеганографии", а также при разработке лабораторной работы "'Обнаружение +-1 НЗБ стегосистем методом универсального стегоанализа".

Результат используются кафедрой Защищенных систем связи Федерального государственного бюджетного образовательного учреждения высшего образования «Санкт-Петербургский государственный университет телекоммуникаций им, проф. М.А. Бонч-Бруевича» в учебном процессе на старших курсах обучения бакалавров по направлению подготовки 10.03.01 «Информационная безопасность» по дисциплинам «Основы стеганографии» (рабочая программа дисциплины, регистрационный № 18.05/1278-Д) и «Безопасность беспроводных локальных сетей» (рабочая программа дисциплины, регистрационный № 16.05/230-Д) при чтении курсов лекций, проведении практических занятий и лабораторных работ.

Комиссия считает, что внедрение указанных научных результатов Нгуен Зуи Конга в образовательный процесс СПбГУТ позволило повысить качество подготовки бакалавров по направлению подготовки 10.03.01 «Информационная

Санкт-Петербург

УТВЕРЖДАЮ

Первый проректор - проректор по учебной работеj * .

об использовании результатов диссертационной работы а^»; защищенных систем связи СПб ГУТ им. проф. М.А. Бон

смгмшст

минобрнауки россии

федеральное государственное бюджетное oöpajui>iiie.u.noe учреждение высшего образования «санкт-петербургский государственный университет промышленных технологий и дизайна» (спбгуптд)

В. Мирена* v.l., д. 18. Санкт-Пстсрб>рг, 191186 Тел. («J2> 315-75-25 Факс (812) 571-95-84 Е-niail: rcctortfsutd та h;tp:/mvvv aild.ru ОКПО 02068605". ОГРН 1027809192102. ИНШСПП 7808042283'784001001

/$РЗ\Л£Ш> Ц. Jf 0j--$j/c\S-J/

УТВЕРЖДАЮ

Проректор по научной работе СПбГУПТД д.т.н., проф. MaKapoj

m'h-'ips

2020г.

на№

ог

АКТ

о внедрении научных результатов диссертационной работы аспиранта кафедры защищенных систем связи СПб ГУТ им. проф. М.А. Ьонч-Бруевича Нгуен Зуи Конга на тему: «Исследование и разработка универсального метода стегоанализа на основе

использования NIST тестов»

Комиссия в составе: зам. зав. кафедрой интеллектуальных систем и защиты информации (ИСЗИ) к.т.н. доц. Вагнер В.И., к.т.н., ст. преп. Штеренберг С.И., составила настоящий акт о том, что научные результаты, Нгуен Зуи Конга, полученные им в ходе диссертационного исследования на тему «Исследование и разработка универсального метода стегоанализа на основе использования NIST гестов», используются на кафедре ИСЗИ СПбГУПТД при подготовке лекционно-практических занятий, а именно:

1. Универсальный метод стегоанализа на основе использования NIST тестов для направления подготовки бакалавров 10.03.01 - «Информационная безопасность» по дисциплине «Комплексная защита информации на предприятии».

2. Оценка стегоключей с использованием универсального метода стегоанализа для направления подготовки бакалавров 10.03.01 -«Информационная безопасность» по дисциплине «Комплексная защита информации на предприятии».

3. Преобразоапнис криптограмм для защиты от обнаружения стсгосистсм универсальным методом для направления подготовки бакалавров 10.03.01 -«Информационная безопасность» по дисциплине «Комплексная защита информации на предприятии».

Комиссия считает, что внедрение указанных научных результатов Нгуен Зуи Конга в образовательный процесс СПбГУПТД позволило повысить качество подготовки бакалавров по направлению подготовки бакалавров 10.03.01 Информационная безопасность.

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

Председатель комиссии:

зам. зав. кафедрой Интеллектуальных систем и защиты

информации, к.т.н., доцент

Вагнер Виктория Игоревна

Члены комиссии:

ст. преп.

Интеллектуальных систем и защиты информации, к.т.н.

Штеренберг Станислав Игоревич

AJUpUXtMOl С6Ц6С7ВС

НАУЧНЫЕ ПРИБОРЫ

УТВЕРЖДАЮ

о внедрении научных результатов диссертационной работы аспирата кафедры защищенных систем связи СПб ГУТ им. проф. МЛ. Бонч-Г>руеиича Нгуен Зуи Кыонга на тему:

«Исследование и разработка универсального метода стегоаналта на основе нспольижания NISItcctob»

Комиссия в составе: заместителя технического директора к.т.н. Изотова Б.В.. ведущею инженера к.ф.-м.н. Павлова В.А., ведущего специалиста Леонова A.B. составила настоящий акт том, что следующие результаты диссер1ациошюй работы. Нгуен Зуи Кыонга. а именно:

Универсальный метод стегоанализа на основе использования NFST тестов был использован в НИР «Исследование методов построения стсгосистем с возможностью их извлечения из твердых носителей».

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

Председатель комиссии: Ь.В. Изотов

Члены комиссии: В.А. Павлов

А. В. Леонов

ПРИЛОЖЕНИЕ Б. ОПИСАНИЕ АЛГОРИТМОВ М8Т-ТЕСТОВ

Доступные теоретические исследования, относящиеся ко многим статистическим параметрам битовых последовательностей в предположении случайности, являются вычислительной основой для оценки изменения Хи-квадрата . Исходя из общих теоретических соображений, совокупности 15 тестов можно разделить на четыре категории, а именно: частотные тесты (тесты: 1

- 4), тесты на повторяющиеся шаблоны (тесты: 5 и 6), тесты в соответствие с шаблонами (тесты: 7 - 12) и тесты, основанные на случайном блуждании (тесты 13

- 15). Алгоритмы тестов 1, 3, 6, 9, 13 и 15 действительно рассматривают всю битовую последовательность вместе для вычисления изменения /2 и вычисляют Р — значение на основе функции ошибки, за исключением 13-го теста, для которого используется функция Гаусса. Алгоритмы тестов 2 и 7 разделяют всю битовую последовательность на N блоков и вычисляют Р — значение на основе Гамма-функции, используя N в качестве степеней свободы. Алгоритмы тестов 4, 5, 8 и 10 разделяют всю битовую последовательность на N блоков, а также рассматривают + 1) классы, полученные из соответствующих теоретических исследований, и вычисляют Р — значение на основе Гамма-функции, используя К в качестве степеней свободы вместо N. Алгоритмы тестов 11, 12 и 14, без разделения битовой последовательности на блоки, представляют (^ + 1) классы, полученные из соответствующих теоретических исследований, и вычисляют Р — значение на основе Гамма-функции с К степенями свободы.

Б.1. Тест 1: Частотный побитовый тест

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

Направление расчета:

(1) Каждый бит 0 и 1 в строке представлен -1 и 1 соответственно с использованием математического соотношения ^ = — 1, где ^ представляет новое значение бита в ¡-й позиции.

(2) Сумма Хь представляет собой 5П, а 5оЬ5 = |5П|/^п. И х = 5оЬ5/72.

(3) Р — значение = 1 — ег/(х), где ег^х) - дополнительная функция ошибок [37].

Б.2. Тест 2: Частотный блочный тест

Цель этого теста состоит в том, чтобы определить, равна ли частота единиц в М-битном блоке приблизительно М/2, как и следовало ожидать в предположении случайности.

Направление расчета:

(1) Разбить входную последовательность на N = блоков.

непересекающихся

(2) Если пропорция 1 в каждом блоке составляет примерно 1, п-битовая последовательность может быть названа случайной.

(3) Пропорция пI единиц в каждом блоке определяется как п^ = ¿25=1 £а-1)м+] где 1 < I < N.

(4) Хи-квадрат = 4М — 1)2; а = ± и х =

(5) Р — значение = 1 - Г(а, х) / Г(а, го), где Г - гамма-функция.

Б.3. Тест 3: Тест на последовательность одинаковых битов

В этом тесте цель состоит в том, чтобы увидеть, находится ли частоты серий 1 и 0 различной длины находиться в пределах случайности.

Направление расчета:

(1) ^(оЬя) = г(&) + 1 где г(^) = 0 если £л = £л+1; иначе г(&) = 1.

(2) х = |Кп(оЬ5) - 2пгс(1 - гс)|/[2гс(1 - я)72п].

(3) Р — значение = 1 — ег/(х).

Б.4. Тест 4: Тест на самую длинную последовательность единиц в блоке

Цель этого теста состоит в том, чтобы определить, соответствует ли длина самого длинного прогона единиц в тестируемой последовательности длине самого длинного прогона, ожидаемой в случайной последовательности.

Направление расчета:

непересекающихся

(1) Разбить входную последовательность на N = блоков.

(2) Рассматривая все блоки, V; представляет сумму всех частот самых длинных серий конкретных 1, появляющихся в каждом блоке.

(3) Для вычисления V; подразделяется на (^ + 1) классы с 0 < I < Среди п, М, N и К предлагается эмпирическое соотношение, представленное ниже.

Минимальное п Минимальное М К Минимальное N

128 8 3 16

6272 128 5 49

750000 104 6 75

(4) у0 - это количество блоков, где «1» - самый длинный цикл из одних или все нули в блоке, - это количество блоков, где «11» - самый длинный цикл из одних, у2 - то же самое для «111», поэтому и так далее. Для К = 3, у3 - это количество блоков, в которых самые длинные серии из одних равны «1111» или более.

(5) Учитывая случайность, теоретически изучены вероятности появления самых длинных одних серий для М = 8 & К = 3, М = 128 & К = 5,М = 512 & К = 5, М = 1000 & К = 5 и М = 10000 & К = 6. Репрезентативный набор одного из таких значений для М = 8 и К = 3 приведен ниже:

4 класса Вероятность

V0 < '1' 0,2148

M = 8 & K = 3 v1 = '11' 0,3672

V2 = '111' 0,2305

V3 > '1111' 0,1875

(6) Вероятности появления самых длинных серий из 5 и более настолько малы, что они объединяются в v3.

(7) Можно отметить, что для М = 128 и К = 5 шесть классов помечены как v0 <'1111',^ ='11111', v2 ='111111', v3 ='1111111', v4 ='11111111' и v5 > '111111111'. Другой кластер классов, например М = 512 & К = 5, М = 1000 & К = 5 и М = 10000 & К = 6, имеют соответствующие классы с вероятностями. Все связанные данные скомпилированы в NIST-документе.

(8) Можно отметить, что £f=0 = N, а сумма вероятностей для конкретной (М, К) группы равна единице.

(9) Хи-квадрат = £f=o ^р2; а = \ и х = /2/2.

(10) Р — значение = 1 - г (а, х) / г (а, го).

Б.5. Тест 5: Тест рангов бинарных матриц

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

Направление расчета:

(1) Каждый блок представлен матрицей из М строк и Q столбцов, так что N = [n/MQJ. Обычно и М, и Q принимаются за 32.

(2) Есть много теоретических исследований, связанных с рангом квадратной двоичной матрицы порядка М > 10. Из исследования вероятности даны следующим образом: = П5=1[1 — 2-] = 0,5 • 0,75 • 0,875 • ... = 0,2888... ;

= 2РМ = 0,5776 ... ; Рм_2 = 4Рм/9 = 0,1284 ... и все остальные вероятности очень малы (< 0,005).

(3) ^ = количество подматриц, имеющих полный ранг М.

(4) = количество подматриц с рангом (М — 1).

(5) = N — ^ — = Количество субматриц с рангом (М — 2) и менее.

(7) Для а = 1, г (а, х) = [1 - ехр(—х)] и г (а, го) = 1.

(8) Р — значение = 1 - г (а,х) / г (а, го) = ехр(—х).

Б.6. Тест 6: Спектральный тест

Целью теста является выполнение дискретного преобразования Фурье (Discrete Fourier Transform - DFT) каждой битовой последовательности и определение их пиковой высоты. Учитывая случайность, можно найти пороговое значение высоты пика (T). Если максимум 5% высоты пика больше, чем T, последовательность можно назвать случайной.

Справочная информация в отношении случайности:

(1) DFT создает последовательность комплексных переменных для представления периодических компонентов разных частот. Компонент DFT j-го бита задается как /у = Efc=1 xfce2n:i(k-1);/n, где xfc - это k-й бит, закодированный в форме -1 и +1.

(2) Из-за симметрии преобразования действительного в комплексное значение рассматриваются только значения j от 0 до (п/2 — 1) вместо п.

Направление расчета:

(1) Каждый бит 0 и 1 в n-битовой последовательности представлен -1 и 1 соответственно с использованием соотношения Xt = 2£j — 1, где Xt представляет новое значение бита £j в i-й позиции, 1 < i < п.

(2) Пороговое значение высоты пика (Г) рассчитывается по соотношению

(6) Ж2 = ££„-2^^; а = К/2 и ж = х2/2.

(3) Мо = ожидаемое теоретическое (95%) число пиков в предположении случайности = 0,95 • п/2.

(4) Следуя приведенному выше выражению, величина (М) /у рассчитывается для 0<у <(-—1).

(5) ^ = количество пиков в М, которые меньше, чем Г.

(6) й = ; * = М

(7) Р — значение = 1 - ег/ (х).

Б.7. Тест 7: Тест на совпадение неперекрывающихся шаблонов

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

Справочная информация в отношении случайности:

(1) Для случайных последовательностей предполагается, что центральная предельная теорема применима.

(2) Среднее (ц) и дисперсия (а2) рассчитываются на основе

М-ш+1

приблизительного нормального распределения, определяемого как ц = ——— и

а2 = — 2^-1), где т - фиксированная длина непериодического шаблона, появляющегося М раз.

Направление расчета:

(1) п-битовая последовательность делится на N неперекрывающихся блоков, каждый из которых состоит из М-битов, где N = [п/М]. Неиспользованные биты отбрасываются.

(2) Среднее значение ц и дисперсия а2 рассчитываются по приведенному выше выражению.

(3) И^ = Количество раз, когда указанный шаблон был найден в ]-м блоке. Поиск соответствия продолжается для всех блоков с 1 < у < N.

(4) = £=1^-^; а = N/2 и х = г72.

(5) Р — значение = 1 - г (а,х) / г (а, го).

Б.8. Тест 8: Тест на совпадение перекрывающихся шаблонов

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

Справочная информация в отношении случайности:

(1) Для вычисления теоретических вероятностей (^), соответствующих

„ - (М-ш+1) - .

классам V;, значения к и п рассчитываются как Я = ——— и ^ = Я /2, где т -фиксированная длина непериодического шаблона, а М - битовый размер блока.

(2) Шесть классов (V;), I = 0,1,.. ,5 рассматриваются, и степени свободы

(3) Значения кип необходимы для вычисления всех значений ^. В предположении случайности теоретические значения вероятности ^, доступные в литературе [56]: я0 = 0,324652; = 0,182617; = 0,142670; % = 0,106645;

= 0,077147; = 0,166269.

Направление расчета:

(0) Задано несколько замечаний: п > 106; т = 9 или 10; N > . 5 •

47 тт(Я[)

п > М^; Я « 2; К « 2Я; т« /о^2М; указанные значения ^ приведены исключительно для К = 5.

(1) п-битовая строка делится на N блоков, каждый из которых состоит из М-битов, так что N = [п/М]. Лишние биты отбрасываются.

(2) Счетчик перекрытия т-битового окна выполняется для всех N блоков, и массив классов V; соответственно заполняется.

(3) Г2 = а = К/2 и ж = X2/2.

(4) Р — значение = 1 - г (а, х) / г (а, го).

Б.9. Тест 9: Универсальный статистический тест Маурера

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

Справочная информация в отношении случайности:

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

К как, = — Р), где с и р - соответствующие индексы текущего и

предыдущего появления одного и того же шаблона. На основе стандартного нормального распределения плотности ожидаемое значение теоретической тестовой статистики £(/д) определяется как, £(/д) = 2-1 ^¿=1(1 — 2-1у-1

Отдельное выражение для дисперсии (¿) также дается. Дисперсия связана с

s variance (L) „

теоретическим стандартным отклонением (а) как, о = с I---, где с = 0,7 —

M+^ + H)3-^.

L v L 15

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

шаблонные блоки разных размеров. Таблица соответствия для ¿ в диапазоне от 6 до 16 приведена ниже,

¿ £(/п) G ¿ £(/n) G

6 5,2177052 2,954 12 11,168765 3,401

7 6,1962507 3,125 13 12,168070 3,410

8 7,1836656 3,238 14 13,167693 3,416

9 7,1836656 3,238 15 13,167693 3,416

10 7,1836656 3,238 16 13,167693 3,416

11 10,170032 3,384

Направление расчета:

(1) Создается таблица с возможным значением ¿-бита, где отмечается последнее появление номера блока каждого ¿-бита. В тестовом сегменте К проверяется каждый блок и вычисляется расстояние между текущим блоком и блоком, в котором последний раз встречается тот же ¿-битовый блок. Предыдущий номер блока заменяется текущим номером блока.

(2) Функция тестовой статистики (/^) рассчитывается на основе следующего выражения: = ¿о^гО — ?)), где 7} - табличная запись, соответствующая десятичному представлению содержимого /-го Ь-битового блока.

(3) Предыдущая запись таблицы 7} заменяется текущим номером /-го блока.

(4) Стандартное отклонение (а) рассчитывается на основе выражения, приведенного выше, и соответствующего значения дисперсии, приведенного в таблице выше.

(5) х = /п-Д/п) и Р —значение = 1 - ег/(х).

V2CT

Б.10. Тест 10: Тест на линейную сложность

Основное внимание в этом тесте уделяется длине регистра сдвига с линейной обратной связью (LFSR - Linear Feedback Shift Register). Цель этого теста -определить, является ли последовательность достаточно сложной, чтобы ее можно

было считать случайной. Случайные последовательности характеризуются более длинными LFSR. Слишком короткая ЬББК подразумевает неслучайность

Справочная информация в отношении случайности:

(1) Длинная п- битовая последовательность делится на N блоков, каждый из которых состоит из М бит.

(2) Учитывая случайность, средняя длина ЬББК (ц) М-битовой строки

М . 2

определяется как [ = — +----.

(3) Статистическое отклонение (7^) ЬББК длины (¿^) определяется как 7^ =

(4) В зависимости от значений 7^, N блоков делятся на 7 фиксированных групп ), где 0 < I < 6, исходя из следующих соображений:

< —2,5),^(—2,5 < —1,5),Р2(—1,5 < < —0,5), р3(—0,5 < < +0,5), у4(+0,5 < < +1,5),У5(+1,5 < 7^ < +2,5)

(5) Теоретические вероятности (^) каждой из 7 групп, указанных выше, получены из стандартной литературы как я0 = 0,010417, = 0,03125, =0,125, % = 0,5, = 0,25, = 0,0625, я6 = 0,020833.

Направление расчета:

(1) ц рассчитывается для значения М.

(2) 7^ рассчитывается для каждого из N блоков. В зависимости от значения 7^ соответствующий массив ^ увеличивается. Можно отметить, что £|=0 ^ = N.

(3) Если бы не было группы; Т был бы в одной группе. Создание 7 групп предоставляет Т выбор дополнительных 6 групп - следовательно, степени свободы

равны 6.

(4) Ж^^о^™2; а = К/2 и * = Х2/2.

(5) Р — значение = 1 - г (а, х) / г (а, го).

Б.11. Тест 11: Тест на периодичность

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

Справочная информация в отношении случайности:

(1) Пусть V; представляет счетчики частоты для 0 < I < (2т — 1), где I обозначает десятичное значение конкретного т-разрядного шаблона.

(2) Статистика пси-квадрата (^), аналогичная Хи-квадрату (/2),

I ? 1 1 л N9 1 1 ?

определяется выражением ^ = —¿2=0 Л^ — ^ш)2 = —¿2=0 1 ^¿2 — п.

(3) Статистика Хи-квадрат (/2) в данном случае Л^ш = — ^т-1

Л^т-1 = ^т-1 — ^ш-2

= — А^ш-1 = — 2^-1 + ^ш-2

(4) Здесь Л^ - это распределение /2 с ^ = 2т-1 степенями свободы, а Л2^ - другое распределение Л2^ с = 2т-2 степеней свободы.

(5) Два распределения Хи-квадрат (/2) в сочетании с двумя степенями свободы дают два значения Р.

(6) Значение т обычно мало и т < [/о^2(п)] — 2.

Направление расчета:

(1) Для т-битовой шаблона V; считается 0 < I < (2т - 1); вычисляется с Лт = п/2™.

(2) Для (т — 1)-битового шаблона V; считается 0 < I < (2т-1 - 1);

вычисляется с Лт-1 = п/2т-1.

(3) Для (т — 2)-битового шаблона V; считается 0 < I < (2т-2 - 1); ^ш-2 вычисляется с Лт-2 = п/2т-2.

(4) На основе ^ и вычисляется Д^, а на основе ^, и вычисляется Д2^ш.

К 1

(5) Тогда а1 = и Р —значение1 = 1 - г (а1,^1) / Г (а1,го).

К 1

(6) Тогда ^2=у и Х2=-Д2^™, Р — значение2 = 1 - г («2,^2) / г («2,™).

Б.12. Тест 12: Тест приблизительной энтропии

Цель теста - сравнить частоту перекрывающихся блоков двух последовательных / смежных длин (т и (т + 1)) с ожидаемым результатом для случайной последовательности.

Справочная информация в отношении случайности:

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

(2) Пусть V; представляет перекрывающиеся подсчеты частоты конкретного т-разрядного шаблона для ¿, варьирующегося 0 < I < 2т, где I обозначает десятичное значение конкретного ^-разрядного шаблона.

(3) СГ = ^/п, щ = СГ и 0т = £2=Го-1 ^

(4) Для подсчета (т + 1)-битовых шаблонов сопоставления первые т битов добавляются в конец данной «-битовой строки.

(5) Точно так же ^ представляет перекрывающиеся счетчики частоты конкретного (т + 1)-битового шаблона для 0 < I < 2т+-, здесь I обозначает десятичное значение конкретного (т + 1)-битового шаблона.

(6) с™+- = Vi = с™+- и 0т+- = .

(7) Лр£п(т) = 0т — 0т+-, Лр£п(т) - значение сравнения между энтропиями т и (т + 1) -битных шаблонов.

(8) Количество степеней свободы К = 2т и /2 = 2п[1п 2 — ЛрЕп(т)].

Направление расчета:

(1) Для подсчета т-битовых шаблонов сопоставления ^ подсчитывается перекрывающимся образом через добавленную (п + т — 1)-битовую последовательность для всех возможных т-битовых шаблонов, I варьируется

0 < I < 2т — 1.

(2) На основе 2т типов V; вычисляются значения С™, ^ и 0т.

(3) Опять же, для подсчета (т + 1)-битовых шаблонов сопоставления ^ подсчитывается перекрывающимся образом по всей добавленной (п + т)-битовой последовательности для всех возможных (т + 1)-битовых шаблонов, где 0 < I < 2т — 1.

(4) На основе 2т + 1 типов V; вычисляются значения С/п+1, ^ и 0т+1.

(5) X2 = 2п[1п 2 — ЛрЕп(т) ] где ЛрЕп(т) = 0т — 0т+1.

(6) а = ^/2 и х = /2/2.

(7) Р — значение = 1 - г (а, х) / г (а, го). Б.13. Тест 13: Тест кумулятивных сумм

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

Справочная информация в отношении случайности:

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

определяемой как Ф(г) = е-"2/2йи.

Направление расчета:

(1) Во всей n-битовой последовательности 0 равны -1, как это делается в тесте 1. Совокупные суммы скорректированных (-1, +1) цифр Xt последовательности получаются как St = 5j-x + Xt с i = 1 до п и S0 = 0. Совокупные суммы могут рассматриваться как случайное блуждание.

(2) Максимальная величина (z) кумулятивных сумм St рассчитывается как z = max |5/1. Если велико, битовая последовательность считается неслучайной.

1<t<n vn ' J

(3) Накопленные суммы могут быть получены в прямом направлении, то есть от начала до конца (обозначается как режим 0), а также в обратном порядке, то есть от конца к началу (обозначается как режим 1). Для каждого из двух случаев отмечены два значения z.

(4) Значение P вычисляется с использованием следующего уравнения, включающего функцию нормального распределения (Ф).

Р - значение = 1 - [Ф(^) - Ф(^)] [Ф(^) - Ф(^)]

^fc = (-^+1)/4L v Vn J к Vn Ji ^ = 3)/4L v Vn J K Vn Ji

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

Б.14. Тест 14: Тест на произвольные отклонения

Цель этого теста состоит в том, чтобы определить, отклоняется ли число посещений определенного состояния в цикле от того, что можно ожидать для случайной последовательности. Этот тест представляет собой серию из восьми тестов (и выводов), по одному тесту и выводу для каждого из состояний: -4, -3, -2, -1 и +1, +2, +3, +4.

Справочная информация в отношении случайности:

(1) ^^(s) определяется как теоретическая вероятность к числа посещений состояния s. Выражения rcfc(s) для к = 0,1,2,3,4, и 5 выводятся теоретически. Здесь степени свободы К = 5.

(2) Вероятность 0 числа посещений состояния б: ^(я) = 1 — —.

1 1

(3) Вероятность к числа посещений состояния s: ^(я) = —(1 ; к=1, 2, 3, и 4.

11

(4) Вероятность 5 или более посещений состояния б: ^(я) = — (1 ——-)4. Направление расчета:

(1) Во всей п-битовой последовательности 0 равны -1, как это делается в тесте 1. Совокупные суммы скорректированных (-1, +1) цифр ^ последовательности получаются как = + Х^ с i = 1 до п и 5о = 0, а также 5п+1 = 0.

(2) Если кумулятивные суммы пересекают ноль / (исключая 5о = 0) раз, / называется числом циклов с учетом точки пересечения нуля в 5п+1.

(3) Если / < тах(0,005 • V™, 500), последовательность считается неслучайной. Последовательность в один миллион бит считается неслучайной, если / меньше 500.

(4) ^(я) = частота ^-кратных визитов в состояние х во время / экскурсий. Ради вычисления можно рассмотреть, vfc(s) = Если число посещений

состояния б во время ]-й экскурсии точно равно то р^(^) = 1, иначе р^(^) = 0.

(5) Для у^я) с к > 5 данные счета заносятся в у5(я).

(6) Для каждого состояния статистика Хи-квадрат вычисляется как

? _ V5 С^ОЬ/"^^)2 Х =£к = 0 /**(*) .

(7) а = ^/2 и х = /2/2.

(8) Р — значение = 1 - г (&,х) / г (а, го).

(9) Есть восемь состояний - следовательно, будет восемь Р — значений, соответствующих каждому состоянию.

Б.15. Тест 15: Другой тест на произвольные отклонения

Целью данного теста является выявление отклонений от ожидаемого количества посещений различных состояний при случайном блуждании. Этот тест на самом деле представляет собой серию из восемнадцати тестов, один тест и заключение для каждого из состояний: -9, -8, ..., -1 и +1, +2, ..., +9.

Справочная информация в отношении случайности:

Статистическая вариация о = (4|я| — 2) в отношении случайного блуждания для посещения различных состояний.

Направление расчета:

(1) Во всей п-битовой последовательности все 0 равны -1, как это делается в тесте 1. Совокупные суммы скорректированных (-1, +1) цифр ^ последовательности получаются как = + ^, когда 2 < I < п и 5о = 51 = 0.

(2) Если кумулятивные суммы пересекают ноль / (исключая 5о = 0) раз, / называется числом циклов с учетом точки пересечения нуля в 5п+1.

(3) Если / < шах (0,005 • 7^, 500), последовательность считается неслучайной. Последовательность в один миллион бит считается неслучайной, если J меньше 500.

(4) ^(б) определяется как общее количество посещений состояния б во всех / циклах.

(5) ^ =

(6) Р — значение = 1 - ег/ (х).

Существует восемнадцать состояний - следовательно, рассчитываются восемнадцать Р — значений, соответствующих каждому состоянию.

ПРИЛОЖЕНИЕ В. КРАТКОЕ ОПИСАНИЕ АЛГОРИТМА СЖАТИЯ «DEFLATE»

Алгоритм сжатия «Deflate» [57] основан на использования алгоритма сжатия LZ77 [58] в сочетании с кодом Хаффмана. Принцип сжатия по алгоритму LZ77 состоит в том, что использовать часть ранее увиденного входного потока в качестве словаря.

Сжатый набор данных состоит из последовательности блоков, соответствующих последовательным блокам входных данных. Размеры блоков являются произвольными, за исключением того, что несжимаемые блоки ограничены 65535 байтами. Каждый блок сжимается с использованием комбинации алгоритма LZ77 и кодирования Хаффмана. Деревья кодирования Хаффмана для каждого блока не зависят от деревьев предыдущих или последующих блоков; алгоритм LZ77 может использовать ссылку на дублированную строку, встречающуюся в предыдущей части блока, до 32K входных байтов ранее. Каждый блок состоит из двух частей: пары деревьев кодирования Хаффмана и части сжатых данных.

Сжатые данные состоят из серии элементов двух типов: байтовые литералы (из строки, которые не были обнаружены как дублированные в предыдущих 32K входных байтах), и указатели на дублированные строки, где указатель представлен в виде пары (длина, расстояние).

Представление, используемое в формате «Deflate», ограничивает расстояния до 32 Кбайт и длины до 258 Байт, но не ограничивает размер блока, за исключением несжимаемых блоков. Каждый тип значения (литералы, расстояния и длины) в сжатых данных представлен с использованием кода Хаффмана, с использованием одного дерева кодирования для литералов и длин и отдельного дерева кодирования для расстояний. Деревья кодирования для каждого блока отображаются в компактной форме непосредственно перед сжатыми данными для этого блока.

Типы режимов сжатия по алгоритму «Deflate»

В алгоритме сжатия «Deflate» есть 3 режима сжатия данных.

+ Первый режим «Режим 1» не сжимает данные.

+ Второй режим «Режим 2» сжимает данные с использованием LZ77 и фиксированного кодирования Хаффмана в соответствии с фиксированной таблицей в алгоритме сжатия.

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

Режим 1 Режим 2 Режим 3

3 бита заголовка: 000 или 100 3 бита заголовка: 001 или 101 3 бита заголовка: 010 или 110

Данные (до 65635 байт) Буквенные / длина префиксных кодов и расстояния префиксных кодов Таблица информации

Сжатые данные (закодированные с двумя таблицами префиксов)

ЬБК (без знаковые 16-битные числа) байты данных Конец блока (Код 256) Конец блока (Код 256)

Кодер сравнивает длины для каждого режима сжатия, а затем сжимает данные, выбирая самую короткую длину сжатых данных [59]. Упрощенный алгоритм сжатия «Deflate» показан на Рисунке В.1. [60] (третий блок называется процедурой выбора, в этом блоке кодер сравнивает 3 длины для 3режимов (режим 1, режим 2 и режим 3), затем выбирается один режим с наименьшей длиной.)

Рисунок В.1 - Упрощенный алгоритм «Deflate» [60]

Чтобы декомпрессировать данные (алгоритм «Inflate»), распознается формат сжатых данных может быть распознан. Блок в режиме 1 состоит из заголовка (как указано выше) и раздела необработанных сжатых данных. В режиме 2, блок состоит из заголовка и части необработанных сжатых данных. А в режиме 3, блок состоит из заголовка, таблицы Хаффмана и блока необработанных сжатых данных [61].

Завершение последовательности в каждом блоке фиксировано одним заголовком или кодом (Код 256). Эти фиксированные под последовательности представлены в выходной двоичной последовательности компрессора «Deflate». Но отметим, что длины сжатых блоков различны. Длина сжатого блока рассчитывается по текущему заполнению буфера символов (по умолчанию 16383 символа, один символ в этом случае - либо один литерал, либо одно совпадение любой длины). Таким образом, аналитик не знает правильного положения фиксированных под последовательностей, и они могут совпадать с реальными данными.

ПРИЛОЖЕНИЕ Д. РЕАЛИЗАЦИЯ АЛГОРИТМОВ ДИССЕРТАЦИИ

В ВИДЕ КОДОВ ИСТОЧНИКА

Д1. Функция извлечения на основе матричного вложения в виде кодов источника

function [arr] = Extract Matrix embedding binary sequence(rgb,p) [width height] = size(rgb); arr=[]; if p==1 matrix = mod(rgb,2);

arr = reshape(matrix,[1 width*height]); else

H=genarating matrixH(p); k=2Ap-1; a = zeros(1,k); count=0; for i=1:width for j=1:height

count=count+1; a(count)=mod(rgb(i,j),2); if count==k count=0;

M=(mod(H*a',2)); arr=[arr M(:)'];

end

end

end

end

>->

о

function [genarating matrix] = genarating matrixH(p) row=p; col=2Ap-1; H = []; for i=1:col H=[H i];

end

H = H';

H = dec2bin(H,p); genarating matrix = H'; end

Д2. Функция извлечения на основе алгоритма HUGO в виде кодов источника

function [arr] = Extract HUGO binary sequence(rgb,p,q)

% This function was copyrighted by Tomas Filler (tomas.filler@binghamton.edu) [width height] = size(rgb); arr=[];

H hat = [p q];

size hat = length(H hat);

matrix = mod(rgb,2);

CO = reshape(matrix,[1 width*height]);

l=length(CO);

m = floor(l/size hat);

code= create code from submatrix(H hat, m); arr =calc syndrome(code,CO)'; end

%

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