Определение 20.4

Функцией имитации n-го порядкабудем называть такую функциюf, которая в-окрестности выполняет статистически эквивалентное преобразование файлаАв файлВ.

Таким образом, если p(t, A)— вероятность появления некоторой строкиtв файлеА, то функцияfпреобразует файлАв файлВтак, что для всех строкtдлиной меньшеnвыполняется соотношение|p(t, f(A)) –p(t, B)| < .

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

Регулярные функции имитации можно смоделировать с помощью схемы кодирования по Хаффману. Известно, что любой язык обладает некоторыми статистическими свойствами. Этот факт используется многими методами сжатия данных. Если на алфавите задано распределение вероятностейA, то можно воспользоваться схемой кодирования по Хаффману для создания функции сжатия с минимальной избыточностьюf_A:{0,1}*, где символ*используется в смысле*=_i0{x₁…x_i|x₁,…,x_i}. Такую функцию можно построить на основе функции сжатия Хаффмана:G(x)=f_B(f_A(x)).

Таким образом, секретный файл можно сжать по схеме Хаффмана с распределением A, в результате чего получится файл двоичных строк, которые могут интерпретироваться как результат операции сжатия некоторого файла с распределениемB. Этот файл может быть восстановлен с применением инверсной функции сжатияf_Bк файлу двоичных строк и использоваться в дальнейшем как стеганограмма. Если функцииf_Aиf_Bявляются взаимно однозначными, то и созданная функция имитации будет также взаимно однозначна. Доказано, что построенная таким образом функция подобия оптимальна в том смысле, что если функция сжатия Хаффманаf_Aявляется теоретически оптимальной и файлxсостоит из случайных бит, то взаимно однозначная функцияf_A(X)имеет наилучшую статистическую эквивалентность кА.

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

Контекстно-свободная грамматика определяется упорядоченной четверткой <V, V, П, SV\>, гдеVи— соответственно множества переменных и терминальных символов,П— набор продукций (правил вывода), аS— начальный символ. Продукции подобны правилам подстановки, они преобразуют переменную в строку, состоящую из терминальных или переменных символов. Если с помощью правил вывода из стартового символа можно получить последовательность терминальных символов, то говорят, что последовательность получена грамматикой. Такие грамматики называются контекстно-свободными, т.к. любой символ можно заменить последовательностью символов, не обращая внимания на контекст, в котором он встретился. Если для каждой строкиsсуществует только один путь, по которомуsможет быть порождена из начального символа, то такая грамматика называется однозначной.

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

<{S,A,B,C},{A,…,Z, a,…,z},П,S>,

где каждой возможной продукции приписана некоторая вероятность: П={S_0.5 Alice B, S_0.3 Bob B, S_0.1 Eve B, S_0.1 I A; A_0.3 am working, A_0.4 am lazy, A_0.4 am tired; B_0.5 is С, B_0.5 can cook; C_0.5 reading, C_0.1 sleeping, C_0.4 working}.

Пусть П_Vi={_i,1,…,_i,n}— набор всех продукций, которые связаны с переменнойV_i. Тогда для каждого набораП_iможно создать функцию сжатия Хаффманаf_Пi. На рис. 20.7 показаны возможные деревья дляП_SиП_А, из которых может быть легко получена функция сжатия Хаффмана. Например, продукцияEve Bбудет кодироваться как110,I am tired— как11и т.д.

Для стеганографических задач используется инверсная функция Хаффмана. На этапе сокрытия данных отправитель получает с помощью КСГ некоторую строку, которая считается стеганограммой. Стартуя с начального символа S, самая левая переменнаяV_iзаменяется по соответствующей продукции. Эта продукция определяется в соответствии с секретным сообщением и функцией сжатия Хаффмана дляП_Viследующим образом. В соответствии с очередным битом секретного сообщения происходит просмотр дерева Хаффмана до тех пор, пока не будет достигнут лист в дереве, после чего начальный символ заменяется на значение, которое приписано данному листу. Этот процесс повторяется для всех битов сообщения. Результирующая строка состоит только из терминальных символов.

Рис. 20.7.Функция сжатия Хаффмана дляП_SиП_А

Рассмотрим пример. Пусть секретное сообщение будет 11110. Тогда для указанной выше грамматикиПна первом шаге просмотр дереваП_Sс помощью трех первых битов сообщения достигнет листаI. Таким образом, начальный символSбудет заменен наI A. Затем, просматривая еще раз дерево, с помощью следующий двух секретных битов сообщения произойдет замена очередных символов наam working. В результате, конечная строка будет состоять только из терминальных символов. В итоге стеганограмме11110соответствует сообщениеI am working.

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

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