Способ встраивания сжатого сообщения в цифровое изображение

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

 

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

Известны способы стеганографической защиты информации, основанные на внедрении дополнительной информации в растровые изображения путем замены младших значащих битов в байтах цветового представления исходного изображения битами добавляемой информации (См. Bender W., Gruhl D., Morimoto N., Lu A., Techniques for data hiding, IBM system journal, VOL 35 (3&4): pp. 313-336, 1996. Патент РФ №2002135272, опубл.10.07.2004).

Другим вариантом организации стегоканала является способ внедрения дополнительной информации в цифровые изображения, в котором для противодействия статистическим методам анализа, используется только часть младших значащих битов в байтах цветового представления исходного изображения, а оставшиеся биты используются для последующей коррекции наиболее важных статистических параметров (См. Provos N. Defending Against Statistical Steganalysis, Proceeding of the 10 USENIX Security Symposium, 2001, pp. 323-335).

Для организации скрытого хранения и передачи конфиденциальной информации по открытым каналам был предложен способ внедрения дополнительной информации в цифровые изображения (См. Патент РФ №2288544, опубл. 27.11.2006 г., Бюл. №33), заключающийся в том, что исходное цифровое изображение раскладывают на битовые слои, для записи дополнительной информации выбирают один из полученных битовых слоев, который представляют в виде битовой последовательности, запись дополнительной информации осуществляют с помощью кода, при этом в полученной битовой последовательности биты, расположенные на границах всех переходов одинаковых последовательностей нулей и единиц, заменяют в соответствии с битами записываемой дополнительной информации, оставшиеся биты нижележащих битовых слоев при необходимости используют для коррекции исходного изображения или для записи другой дополнительной информации.

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

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

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

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

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

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

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

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

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

фиг.1 - структура памяти компрессора;

фиг.2 - блок-схема работы компрессора в процессе сжатия;

фиг.3 - структура ссылки в памяти словаря, содержащей фрагмент встраиваемого сообщения;

фиг.4 - структура ссылки после переупорядочивания;

фиг.5 - блок-схема работы декомпрессора в процессе извлечения сообщения.

На фиг.1 представлена структура памяти 101 компрессии, используемая компрессором, которая включает встраиваемое сообщение 103, кольцевой буфер 105 и словарь 107. 103 буферизирует встраиваемое сообщение. Кольцевой буфер используется для хранения данных части цифрового изображения, соответствующей размеру встраиваемого сообщения, и поиска совпадений последовательностей битов, хранящихся в встраиваемом сообщении 103. Словарь 107 используется как «окно истории» компрессии, в котором хранятся данные, на которые может ссылаться декомпрессор для восстановления исходного сообщения. Словарь 107 состоит из частей 109, 111, 113, 115. Первая часть 109 словаря содержит номер бита совпадения, который определяет положение сжимаемого фрагмента встраиваемого сообщения 103. Размер части 109 зависит от размера встраиваемого сообщения в битах. Часть 109 используется только в алгоритме переупорядочивания ссылок в памяти словаря (фиг.2, 213) и не используется при извлечении сообщения. Вторая часть 111 словаря содержит флаговый бит, значение которого определяет значения третьей и четвертой частей словаря. При значении флагового бита, равном нулю, третья часть 113 словаря содержит номер бита, который определяет положение найденного совпадения сжимаемого фрагмента встраиваемого сообщения в кольцевом буфере 105, поскольку размер цифрового изображения в среднем составляет 3 мегабайта, то размер третьей части определен в 25 битов. Четвертая часть 115 словаря в этом случае содержит размер в битах найденного совпадения в части встраиваемого сообщения и части кольцевого буфера. Экспериментально установлено, что размер в битах совпадения части встраиваемого сообщения и части кольцевого буфера не превышает 256. Исходя из этого, размер четвертой части 115 словаря определен в 8 битов. Таким образом, размер частей 111, 113 и 115 словаря, которые используются при встраивании и извлечении сообщения, составляет 34 бита (1+25+8).

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

На фиг.2 показана блок-схема работы компрессора, используемого для осуществления настоящего изобретения.

На первом шаге 201 осуществляется запись в память встраиваемого сообщения, подлежащего сжатию.

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

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

На шаге 207 для каждого совпадения формируется ссылка следующего вида: номер бита совпадения встраиваемого сообщения, флаговый бит, номер бита совпадения в цифровом изображении, размер совпадения (фиг.1, 109, 111, 113, 115). Этот выходной сигнал используется для формирования части сообщения сжатых данных, которые затем встраиваются в цифровое изображение.

На шаге 209 осуществляется сдвиг последовательности битов части цифрового изображения в кольцевом буфере.

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

На шаге 213 осуществляется переупорядочивание ссылок в памяти словаря по следующему алгоритму:

Шаг 1. Ссылки записываются в порядке возрастания значений номеров битов совпадений встраиваемого сообщения.

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

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

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

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

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

д) Если значение номера бита совпадения встраиваемого сообщения одной ссылки больше аналогичного значения второй ссылки и при этом значение суммы (номер бита совпадения встраиваемого сообщения + размер совпадения) второй ссылки меньше значения номера бита совпадения встраиваемого сообщения первой ссылки, то между первой и второй ссылками вставляется новая ссылка, в первой части которой (фиг.3, 301) записывается номер первого несовпавшего бита встраиваемого сообщения, вторая часть ссылки - флаговый бит 303 устанавливается в «единицу», при этом третья часть ссылки 305 размером 5 битов определяет размер несовпавшего фрагмента встраиваемого сообщения с цифровым изображением, а четвертая часть ссылки 307, длина которой 28 битов, заполняется несовпавшими фрагментами встраиваемого сообщения. При этом, если размер несовпавшего фрагмента встраиваемого сообщения больше 28 битов, используются несколько ссылок с флаговым битом, установленным в единицу. При размере несовпавшего фрагмента встраиваемого сообщения менее 28 битов, оставшаяся часть заполняется нулями. Таким образом, суммарный размер частей 303, 305 и 307 ссылки в данном случае также составляет 34 бита (1+5+28).

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

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

На фиг.5 показана блок-схема работы декомпрессора в процессе декомпрессии.

На первом шаге 501 осуществляется прием цифрового изображения и извлечение из него встроенной таблицы совпадений по способу, описанному в патенте РФ №2407216 опубл. 20.12.2010 г.

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

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

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

На шаге 509 производится проверка обработки всех ссылок таблицы совпадений. Если все ссылки обработаны, работа останавливается. В противном случае этапы обработки данных повторяются с шага 505, пока не будут обработаны все ссылки словаря.

На шаге 511 осуществляется формирование сообщения данных после декомпрессии.

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

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

Для оценки эффективности предлагаемого способа встраивания сжатого сообщения в цифровое изображение были проведены испытания, суть которых сводилась к следующему. Сначала была сформирована выборка, состоящая из 100 фотореалистичных цифровых изображений, размер которых находился в пределах от одного до трех мегабайт. Затем осуществлялось встраивание сообщения размером 300 килобайт в цифровые изображения по описанному выше способу. Относительный объем внедренных данных варьировался от 10 до 30% от объема исходного цифрового изображения при полном сохранении визуального качества последнего.

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