Стеганография

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 02:12, 18 мая 2017.


Стеганография (от греч. στεγανοσ — скрытый и греч. γραφω — пишу, буквально «тайнопись») — наука о защите информации путем сокрытия факта передачи сообщения.

Общие сведения

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

В прошлом веке широко использовались так называемые симпатические чернила, невидимые при обычных условиях. Скрытое сообщение размещали в определенные буквы невинных словосочетаний, передавали при помощи внесения в текст незначительных стилистических, орфографических или пунктуационных погрешностей. С изобретением фотографии появилась технология микрофотоснимков, успешно применяемая Германией во время мировых войн. Крапление карт шулерами – это тоже пример стеганографии. Скрытие информации перечисленными методами возможно лишь благодаря тому, что противнику неизвестен метод скрытия. Между тем, еще в 1883 году Кирхгофф писал о том, что система защиты информации должна обеспечивать свои функции даже при полной информированности противника о ее структуре и алгоритмах функционирования. Вся секретность системы защиты передаваемых сведений основана на ключе, т.е. на предварительно (как правило) разделенном между адресатами фрагменте информации. Несмотря на то, что этот принцип известен уже более 100 лет, сейчас встречаются разработки, пренебрегающие им. Конечно, они не могут применяться в серьезных целях. Развитие средств вычислительной техники в последнее десятилетие дало новый толчок для развития компьютерной стеганографии. Появилось много новых областей применения. Сообщения встраивают теперь в цифровые данные, как правило, имеющие аналоговую природу. Это – речь, аудиозаписи, изображения, видео. Известны также предложения по встраиванию информации в текстовые файлы и в исполняемые файлы программ.

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

Цифровая стеганография

Рис. 1. Классификация цифровой стеганографии

Цифровая стеганография включает в себя следующие направления:

  • встраивание информации с целью ее скрытой передачи;
  • встраивание цифровых водяных знаков (ЦВЗ) (watermarking);
  • встраивание идентификационных номеров (fingerprinting);
  • встраивание заголовков (captioning).

Цифровые водяные знаки

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

Название этот метод получил от всем известного способа защиты ценных бумаг, в том числе и денег, от подделки. В отличие от обычных водяных знаков ЦВЗ могут быть не только видимыми, но и (как правило) невидимыми. Невидимые ЦВЗ анализируются специальным декодером, который выносит решение об их корректности. ЦВЗ могут содержать некоторый аутентичный код, информацию о собственнике, либо какую-нибудь управляющую информацию. Наиболее подходящими объектами защиты при помощи ЦВЗ являются неподвижные изображения, файлы аудио- и видеоданных. Технология встраивания идентификационных номеров производителей имеет много общего с технологией ЦВЗ. Отличие заключается в том, что в первом случае каждая защищенная копия имеет свой уникальный встраиваемый номер (отсюда и название fingerprinting – дословно «отпечатки пальцев»). Этот идентификационный номер позволяет производителю отслеживать дальнейшую судьбу своего детища: не занялся ли кто-нибудь из покупателей незаконным тиражированием. Если да, то «отпечатки пальцев» быстро укажут на виновного.

Рис. 2. Стегосистема ЦВЗ

Стегосиcтема ЦВЗ содержит следующие ключевые узлы:

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

Данные, содержащие скрытое сообщение, могут подвергаться преднамеренным атакам или случайным помехам. В стегосистеме происходит объединение двух типов информации так, чтобы они могли быть различимы двумя принципиально разными детекторами. В качестве одного из детекторов выступает система выделения ЦВЗ, в качестве другого – человек. Для того, чтобы повысить устойчивость ЦВЗ к искажениям нередко выполняют его помехоустойчивое кодирование, либо применяют широкополосные сигналы. Первоначальную обработку скрытого сообщения выполняет прекодер. В качестве важнейшей предварительной обработки ЦВЗ (а также и контейнера) назовем вычисление его обобщенного преобразования Фурье. Это позволяет осуществить встраивание ЦВЗ в спектральной области, что значительно повышает его устойчивость к искажениям. Предварительная обработка часто выполняется с использованием ключа для повышения секретности встраивания. Далее ЦВЗ «вкладывается» в контейнер, например, путем модификации младших значащих бит коэффициентов. Этот процесс возможен благодаря особенностям системы восприятия человека. Хорошо известно, что изображения обладают большой психовизуальной избыточностью. Глаз человека подобен низкочастотному фильтру, пропускающему мелкие детали. Особенно незаметны искажения в высокочастотной области изображений. В большинстве стегосистем для внедрения и выделения ЦВЗ используется ключ. Ключ может быть предназначен для узкого круга лиц или же быть общедоступным. Например, ключ должен содержаться во всех DVD-плеерах, чтобы они могли прочесть содержащиеся на дисках ЦВЗ. Иногда по аналогии с криптографией стегосистемы делят на два класса: с открытым ключом и с секретным ключом. В стегодетекторе происходит обнаружение ЦВЗ в (возможно измененном) защищенном ЦВЗ изображении. Это изменение может быть обусловлено влиянием ошибок в канале связи, операций обработки сигнала, преднамеренных атак нарушителей. Тогда задача обнаружения и выделения стегосообщения является классической для теории связи. Однако такой подход не учитывает двух факторов: неслучайного характера сигнала контейнера и требований по сохранению его качества. Эти моменты не встречаются в известной теории обнаружения и выделения сигналов на фоне аддитивного шума. Их учет позволит построить более эффективные стегосистемы.

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

Контейнер

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

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

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

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

ЦВЗ могут быть трех типов: робастные, хрупкие и полухрупкие. Под робастностью понимается устойчивость ЦВЗ к различного рода воздействиям на стего. Робастным ЦВЗ посвящено большинство исследований. Хрупкие ЦВЗ разрушаются при незначительной модификации заполненного контейнера. Они применяются для аутентификации сигналов. Отличие от средств электронной цифровой подписи заключается в том, что хрупкие ЦВЗ все же допускают некоторую модификацию контента. Это важно для защиты мультимедийной информации, так как законный пользователь может, например, пожелать сжать изображение. Другое отличие заключается в том, что хрупкие ЦВЗ должны не только отразить факт модификации контейнера, но также вид и местоположение этого изменения. Полухрупкие ЦВЗ устойчивы по отношению к одним воздействиям и неустойчивы по отношению к другим. Вообще говоря, все ЦВЗ могут быть отнесены к этому типу. Однако полухрупкие ЦВЗ специально проектируются так, чтобы быть неустойчивыми по отношению к определенного рода операциям. Например, они могут позволять выполнять сжатие изображения, но запрещать вырезку из него или вставку в него фрагмента.

Требования при проектировании стегосистем

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

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

Требования к ЦВЗ

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

Математическая модель стегосистемы

Стегосистема может быть рассмотрена как система связи, в которой передается шифрованное изображение, которое далее будет называться цифровой водяной знак – ЦВЗ. Алгоритм встраивания ЦВЗ состоит из трех основных этапов:

  1. генерация ЦВЗ;
  2. встраивание ЦВЗ в кодере;
  3. обнаружение ЦВЗ в детекторе.

Этап 1 - Генерация ЦВЗ

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

где - представители соответствующих множеств.

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

то есть ЦВЗ зависит от свойств контейнера. Функция реализуется при помощи криптографически безопасного генератора псевдослучайной последовательности с в качестве начального значения.

Для повышения робастности ЦВЗ могут применяться помехоустойчивые коды, например, коды БЧХ, сверхточные коды. В ряде публикаций отмечены хорошие результаты, достигаемые при встраивании ЦВЗ в области вейвлет-преобразования с использованием турбо-кодов. Отсчеты ЦВЗ принимают обычно значения из множества {-1, 1}, при этом для отображения {0, 1} → {-1, 1} может применяться двоичная относительная фазовая модуляция (BPSK).

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

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

Этап 2 - Встраивание ЦВЗ в кодере

Процесс встраивания ЦВЗ в исходное изображение может быть описан как суперпозиция двух сигналов:

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

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

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

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

  1. Дополнительная информация отсутствует (переключатели разомкнуты) — «классические» стегосистемы. В ранних работах по стеганографии считалось, что информация о канале недоступна кодеру. Обнаружение ЦВЗ осуществлялось путем вычисления коэффициента корреляции между принятым стего и вычисленным по ключу ЦВЗ. Если коэффициент превышал некоторый порог, выносилось решение о присутствии ЦВЗ. Известно, что корреляционный приемник оптимален лишь в случае аддитивной гауссовой помехи. При других атаках (например, геометрических искажениях) эти стегосистемы не дают результатов.
  2. Информация о канале известна только кодеру (A замкнут, B разомкнут). Особенностью схемы является то, что, будучи слепой, она имеет ту же теоретическую пропускную способность, что и схема с наличием исходного контейнера в декодере. К недостаткам стегосистем 2 класса можно отнести высокую сложность кодера (необходимость построения кодовой книги для каждого изображения), а также отсутствие адаптации схемы к возможным атакам. В последнее время предложен ряд практических подходов, преодолевающих эти недостатки. В частности, для снижения сложности кодера предлагается использовать структурированные кодовые книги, а декодер рассчитывать на случай наихудшей атаки.
  3. Дополнительная информация известна только декодеру (A разомкнут, B замкнут). В этих схемах декодер строится с учетом возможных атак. В результате получаются робастные к геометрическим атакам системы. Одним из методов достижения этой цели является использование так называемого опорного ЦВЗ (аналог пилот-сигнала в радиосвязи). Опорный ЦВЗ — небольшое число бит, внедряемых в инвариантные к преобразованиям коэффициенты сигнала. Например, можно выполнить встраивание в амплитудные коэффициенты преобразования Фурье, которые инвариантны к аффинным преобразованиям. Тогда опорный ЦВЗ «покажет», какое преобразование выполнил со стего атакующий. Другим назначением пилотного ЦВЗ является борьба с замираниями по аналогии с радиосвязью. Замираниями в данном случае можно считать изменение значений отсчетов сигнала при встраивании данных, атаках, добавлении негауссовского шума и т.д. В радиосвязи для борьбы с замираниями используется метод разнесенного приема (по частоте, времени, пространству, коду). В стеганографии же используется разнесение ЦВЗ по пространству контейнера. Пилотный ЦВЗ генерируется в декодере на основе ключа.
  4. Дополнительная информация известна и в кодере и в декодере (оба ключа замкнуты). По всей видимости, все перспективные стегосистемы должны строиться по этому принципу. Оптимальность этой схемы достигается путем согласования кодера с сигналом-контейнером, а также адаптивным управлением декодером в условиях наблюдения канала атак.

Этап 3 - Обнаружение ЦВЗ в детекторе

Также как в радиосвязи наиболее важным устройством является приемник, в системе маскирования главным является детектор. В зависимости от типа он может выдавать двоичные либо М-ичные решения о наличии/отсутствии ЦВЗ (в случае детектора с мягкими решениями). Рассмотрим случай «жесткого» детектора, моделирующий экспертизу. Обозначим операцию детектирования через . Тогда

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

Рис. 4. Корреляционный приемник

Пусть у половины пикселей изображения значение яркости увеличено на 1, а у остальных — осталось неизменным, либо уменьшено на 1. Тогда , где . Коррелятор детектора вычисляет величину . Так как W может принимать значения ±1 , то будет весьма мало, a будет всегда положительно. Поэтому будет очень близко к . Тогда можно воспользоваться результатами теории связи и записать вероятность неверного обнаружения стего как дополнительную (комплементарную) функцию ошибок от корня квадратного из отношения («энергии сигнала») к дисперсии значений пикселей яркости («энергия шума»). Для случая «мягкого» детектора и закрытой системы маскирования имеются две основные меры подобия

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

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

Примеры стегоалгоритмов

Далее дано краткое описание следующих стегоалгоритмов:

  • алгоритм Куттера;
  • алгоритм Patchwork.


Алгоритм внедрения

Если 24-битное изображение имеет RGB-кодировку, то встраивание выполняется в канал синего цвета, так как к синему цвету система человеческого зрения наименее чувствительна. Рассмотрим алгоритм передачи одного бита секретной информации. Пусть – встраиваемый бит, – контейнер, - позиция, в которой выполняется вложение. Секретный бит встраивается в канал синего цвета путем модификации яркости:

где - константа, определяющая энергию встраиваемого сигнала.

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

Алгоритм извлечения

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

Оценка получается в виде:

где – число пикселей сверху (снизу, слева, справа) от оцениваемого пикселя ().

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

Алгоритм Patchwork

Алгоритм внедрения ЦВЗ

В основе алгоритма Patchwork лежит статистический подход. Patchwork внедряет в исходное изображение определенную статистику, которая имеет гауссовское распределение. Вначале псевдослучайным образом на основе ключа выбираются два пикселя изображения (А и В). Затем значение яркости синей цветовой компоненты одного из них увеличивается на значение , а значение яркости синей цветовой компоненты другого – уменьшается на . Далее этот процесс повторяется раз. Настолько уникальная статистика указывает присутствие или отсутствие подписи. Patchwork независим от содержания изображения-контейнера. Это обеспечивает довольно высокое сопротивление большинству негеометрических модификаций изображения. Для анализа необходимо сделать некоторые предположения: сигнал каждой цветовой компоненты кодируется числом от 0 до 255, все уровни яркости одинаково вероятны, изменяемые точки изображения выбираются случайным образом. Алгоритм Patchwork выполняется следующим образом: берутся любые две точки, А и B, выбранные наугад в изображении. Пусть равняется яркости в точке А, а - яркости в точке B. Теперь пусть .

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

Хотя ожидаемое значение равно 0, это не говорит нам ничего о том, какое значение будет принимать в каждом конкретном случае. Это объясняется тем, что рассеивание весьма высоко для этой процедуры. Дисперсия — мера того, как сильно значения будут сгруппированы вокруг ожидаемого значения 0. Чтобы ее вычислить, используем предположение о независимости выбора точек а и b. Так как , и а и b приняты независимыми, может быть вычислена следующим образом (это и все другие уравнения вероятности - по Дрейку):

где для однородной S есть:

Очевидно, что , так как а и b – элементы одного и того же множества значений яркости. Таким образом:

тогда значение среднеквадратичного отклонения . Это означает, что в более чем половине случаев значение S будет больше, чем 43, или меньше, чем -43, что значительно отличается от нуля. Принимая гауссовское распределение, недопустимо использовать только одну итерацию. Поэтому данную процедуру необходимо повторить большое количество раз. Пусть процедура повторяется n раз, обозначим через и значения а и b на i-ой итерации, – разность этих значений. Теперь пусть определяется как:

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

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

а среднеквадратичное отклонение:

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

  1. Использовать специальный ключ генератора псевдослучайных чисел для выбора точек и . Это очень важно, так как декодер должен обработать те же самые точки, что и кодер.
  2. Увеличить значение яркости в точке на величину , равную 1 - 5 из 256.
  3. Уменьшить яркость точки на ту же самую величину .
  4. Повторить действия раз (обычно ).

Алгоритм извлечения ЦВЗ

Для обнаружения ЦВЗ необходимо посетить те же точки, что и при кодировании, вычислив при этом сумму разностей яркости в точках и :

Мат.ожидание величины

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

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

См. также

Литература

  1. Основы компьютерной стеганографии: Учебное пособие для вузов / А.В.Аграновский, П.Н.Девянин, Р.А.Хади, А.В.Черемушкин. – М.: Радио и связь, 2003
  2. Цифровая стеганография / В.Г.Грибунин, И.Н.Оков, И.В.Туринцев – М.: СОЛОН-Пресс, 2002
  3. Exploring Steganography: Seeing the Unseen / Neil F. Johnsin, Sushil Jajodia