
Текстовые стеганографы 461
Регулярные функции имитации можно смоделировать с помощью схемы кодирова-
ния по Хаффману. Известно, что любой язык обладает некоторыми статистическими
свойствами. Этот факт используется многими методами сжатия данных. Если на алфа-
вите
Σ задано распределение вероятностей A, то можно воспользоваться схемой кодиро-
вания по Хаффману для создания функции сжатия с минимальной избыточностью
f
A
:Σ→{0,1}*, где символ * используется в смысле Σ*=∪
i≥0
{x
1
…x
i
|x
1
,…,x
i
∈Σ}. Такую
функцию можно построить на основе функции сжатия Хаффмана:
G(x)=f
BОшибка! Закладка
не определена.
(f
A
(x)).
Таким образом, секретный файл можно сжать по схеме Хаффмана с распределением
A, в результате чего получится файл двоичных строк, которые могут интерпретировать-
ся как результат операции сжатия некоторого файла с распределением
B. Этот файл мо-
жет быть восстановлен с применением инверсной функции сжатия
f
BОшибка! Закладка не опре-
делена.
к файлу двоичных строк и использоваться в дальнейшем как стеганограмма. Если
функции
f
A
и f
BОшибка! Закладка не определена.
являются взаимно однозначными, то и созданная
функция имитации будет также взаимно однозначна. Доказано, что построенная таким
образом функция подобия оптимальна в том смысле, что если функция сжатия Хаффма-
на
f
A
является теоретически оптимальной и файл x состоит из случайных бит, то взаим-
но однозначная функция
f
AОшибка! Закладка не определена.
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