Watermarking ciphers.pdf Введение Методы шифрования данных и внедрения в них водяных знаков принадлежат различным областям науки - криптографии [1, 2] и стеганографии [3, 4] соответственно. Первые применяются для защиты конфиденциальности информации, вторые - для защиты информации от её нелегального использования. Как правило, шифрование данных является обратимым преобразованием с ключом расшифрования, неизвестным злоумышленнику, а внедрение в данные водяного знака есть операция сокрытия последнего в данных для идентификации автора нелегальной копии данных. Предполагается, что это сокрытие производится без существенного искажения защищаемых данных, как это делается, например, при внедрении водяного знака в цифровое видео. Рассматривается проблема обеспечения защиты данных от обеих указанных угроз. Есть два тривиальных способа решить эту проблему: сначала внедрить водяной знак в данные и затем зашифровать полученный открытый текст, либо, наоборот, сначала зашифровать данные и затем после расшифрования внедрить в полученный текст нужный водяной знак. Имеются, однако, серьёзные ограничения к применению этих способов на практике [4]. В частности, второй способ предполагает доверенного получателя данных, каковым не является, например, покупатель тех же видеоданных. В работе вводится понятие шифра с водяным знаком, называемого, для краткости, w-шифр, или, в англоязычной транскрипции, a watermarking cipher. В нём преобразование открытого текста x композицией алгоритмов зашифрования и расшифрования, использующих некоторые, должным образом подобранные ключи зашифрования и расшифрования, порождает текст x', содержащий заданный водяной знак w. Мы показываем, каким образом с помощью w-шифра возможно внедрение водяного знака в данные (в тайне от их получателя, естественно) как в процессе зашифрования данных отправителем, так и в процессе расшифрования данных их получателем. Функции зашифрования и расшифрования в w-шифре не обязательно связаны между собой отношением обратимости, как в криптографических шифрах. Это значит, что в действительности w-шифры не обязаны быть шифрами, но всякий шифр является частным случаем w-шифра (с вырожденным водяным знаком), и все термины, понятия и обозначения, оносящиеся к шифрам, вполне уместны и в применении к w-шифрам. Далее, прежде чем дать общее определение шифров с водяными знаками и описать некоторые конкретные примеры их, мы сформулируем некоторые допущения и предположения, необходимые для того, чтобы сделать это более или менее корректно и понятно. 1. Проблема w-шифрования Прежде всего, предположим для простоты, что защищаемые данные представлены конечной последовательностью (строкой, словом) символов, являющихся элементами аддитивной группы G с операцией сложения +. Например, G = Zn или G = Zn для некоторого n ^ 2, и т. п. В частности, данные могут быть представлены последовательностью бит (возможно, с некоторой структурой). Для любых а = aiа2 ... аг и b = bib2... br в Gr пусть а + b = (ai + bi)(a2 + b2)... (ar + br), - b = (-bi)(-b2)... (-br) и а - b = а + (-b). Предполагается, что водяной знак является некоторой парой w = (г,п), где г = = г^2 ... гт е (G\{0})m и n = М2 ... im, j е {1,...,l}, j = 1,... ,m, 1 ^ ii < «2 < ... < < im ^ l для некоторого / ^ 1. В случае необходимости он обозначается (г, п)ь Водяной знак w' = (г', n), в котором г' = -г, называется инверсией знака w и обозначается -w. Очевидно, -(-w) = w. В случае |G| = 2 считаем, что G = Z2. В этом случае в любом водяном знаке w = (г, n) слово г есть вектор 11. . . 1, так что w однозначно определяется набором n, и мы пишем w = n. Встраивание водяного знака w в строку данных x = xix2 ... x^ е G1 выполняется с помощью операции сложения, определённой на G. Результатом встраивания является строка данных x' = x^ ... x{, в которой xj = xj + г4, если j = it е J = {ii,..., im}, и xj = xj, если j е {1,...,/} \ J. Говорим, что строка x' есть строка x с внедрённым знаком w, и обозначаем её x + w. Мы пишем также x - w вместо x + (-w). Строка г и набор n называются соответственно значением и местоположением знака w в x'. Фактически, числа ii, i2,... , im в n указывают позиции в x для встраивания vi, г2,... , гт соответственно из значения г знака w. Набор n называется подходящим местоположением для w в x, если x' получается из x без заметной потери информации. В этом случае мы называем x' производной (или копией) от x с корректно (или приемлемо) встроенным (внедрённым) водяным знаком w. Например, если x является битовой строкой цифрового видео и г = 11... 1 е Zm, то встраивание знака w в x состоит в инвертировании бит xix, xi2,... , xim. В этом случае если позиции бит ii, i2,... , im выбраны так, что инверсия этих бит в x заметно не разрушает видео, то полученная битовая строка x' является копией строки x c приемлемо внедрённым водяным знаком w, обе x' и x могут равнозначно использоваться как цифровое видео, но x', кроме того, содержит водяной знак для идентификации потенциального злоумышленника. Мы говорим, что водяной знак и строка данных взаимно подходящие, т.е. w подходит для x и наоборот, если x имеет экспоненциальное количество подходящих местоположений для w в x. Здесь под экпоненциальным количеством подразумевается экспоненциальная функция от длины m знака w. Такое число походящих местоположений предотвращает злоумышленника от атаки грубой силы перечислением всех возможных подходящих местоположений в x'. Так, цифровые аудио- и видеоданные являются двумя примерами битовой строки данных, для которой встраивание водяного знака путём инверсии битов в некоторых позициях является подходящим. Кроме того, мы предполагаем, что существуют производитель (DP) строки данных x и её покупатели, или клиенты (DC). Производитель DP хочет передать строку x некоторому DC U так, что никто другой не может перехватить x или секретно получить её в своё собственное владение от U. С этой целью DP должен выбрать уникальный и подходящий водяной знак w и некоторый ключ шифрования ke для некоторого w-шифра C, зашифровать x, применив C и ke, и послать клиенту U полученный так шифртекст у и нужный ключ расшифрования kd, построенный таким образом, что расшифрование y на этом ключе даёт в качестве результата некоторую строку данных x', которая является производной от x, с корректно внедрённым знаком w. При этом неважно, на какой стадии, во время шифрования или расшифрования, w встроен в x. Расшифровывая y на ключе kd, клиент U получает уникальную и приемлемую копию x' данных x. Если U передаст её другому клиенту, то DP сможет однозначно идентифицировать U по значению v из w и его местоположению п в x'. Поскольку U сам может быть мошенником, ключ расшифрования kd должен быть связан с водяным знаком w так, что определить w по kd и шифртексту y вычислительно невозможно за реальное время, т. е. не существует алгоритма вообще или с полиномиальной сложностью (как функции от m), вычисляющего w из kd и у. 2. Определение w-шифра Итак, мы приходим к следующему понятию w-шифра: для любых взаимно подходящих водяного знака w и открытого текста x преобразование последнего композицией операций зашифрования и расшифрования на соответствующих ключах, связанных некоторым образом друг с другом и с w, создаёт текст x' = x + w, представляющий собой результат внедрения w в x: На этом пути мы вводим два типа w-шифров: 1) w-шифр с w-расшифрованием - открытый текст x зашифровывается в зависимости только от ключа k w-шифра, а полученный шифртекст у расшифровывается в зависимости от k и подходящего водяного знака w. Таким образом, значение ke ключа зашифрования может быть произвольным, ключ расшифрования kd должен быть предопределён выбранными ke и w, т. е. быть функцией от k и w; 2) w-шифр с w-зашифрованием - открытый текст x зашифровывается в зависимости от ключа k w-шифра и подходящего водяного знака w, а полученный шифртекст y расшифровывается в зависимости только от k. Таким образом, ключ зашифрования ke должен быть функцией от k и w, ключ расшифрования kd должен быть функцией только от k. Формально w-шифр определяется набором из шести объектов C = (X, K, W, h, E, D), где X есть множество строк данных, включая открытые тексты, шифртексты и тексты с встроенными водяными знаками, X = G*; K и W суть множества ключей и водяных знаков соответственно; h есть ключевая функция, h : K х W ^ K, и E и D суть алгоритмы зашифрования и расшифрования соответственно, являющиеся некоторыми отображениями E : X х K ^ X и D : X х K ^ X, такими, что для любых взаимно подходящих x Е X и w Е W и для любого k Е K удовлетворяются следующие условия: 1) в w-шифре с w-расшифрованием - если E(x, k) = у, то D(y, h(k, w)) = x' = x + w; 2) в w-шифре с w-зашифрованием - если E(x, h(k, w)) = y, то D(y, k) = x' = x + w. В случае h(k,w) = k для любых k Е K, w Е W мы допускаем вместо k писать h(k, w) в последних выражениях и Л вместо h в C. 3. Примеры w-шифров Тривиальный пример w-шифра (X, K, W, Л, E, D) над G можно построить из симметричного шифра (X, Y, K, E', D') с X = Y = G* и множества W водяных знаков, положив E(x, k) = E'(x + w, k) и D(y,k) = D'(y, k) или E(x, k) = E'(x, k) и D(y, k) = D'(y, k) + w. Простейшим нетривиальным примером w-шифра является одноразовый блокнот с водяным знаком C1 = (X, K, W, h, E, D), где X = K = G*. В этом w-шифре с w-рас-шифрованием для данного водяного знака w = (v,n) шифртекст y = y1y2 .. .y^ Е X получается сложением открытого текста x = x1x2 ... xi Е X и ключа k = z1z2 ... z Е Е K, т. е. y = x+k, и расшифрование y в открытый текст x' = x1x'2 ... xl Е X с водяным знаком w производится вычитанием другого ключа k' = k - w = z1 z2 ... z' Е K из y, т. е. x' = y - k'. Этот же w-шифр с w-зашифрованием описывается соотношениями k' = k + w, y = x + k', x' = y - k. Непосредственно проверяется, что в обоих случаях x' = x + w. В первом случае ke = k, kd = h(k, w) = k' и знак w автоматически встраивается в x в процессе расшифрования. Во втором случае это делается в процессе зашифрования и ke = k' = h(k,w), kd = k. Другими словами, для любых l ^ 1, x,k Е Gl и w Е W 1) в C1 с w-расшифрованием - E(x, k) = x + k = y, h(k, w) = k - w, D(y, h(k, w)) = y - h(k, w) = y - k + w = x'; 2) в C1 с w-зашифрованием - h(k, w) = k + w, E(x, h(k, w)) = x + h(k, w)= x + k + w = y, D(y, k) = y - k = x'. Ещё одним примером w-шифра является поточный шифр с водяным знаком Ca = = (X, K, W, h, E, D) над конечным полем F с X = F* и с генератором ключевого потока, являющимся некоторым конечным автономным автоматом A с нелинейной функцией выходов. Автомат A представляется четвёркой объектов A = (Q, Z, g, f), где Q, Z суть множества состояний и выходных символов соответственно, Q = Fn, n ^ 1, Z = F и g,f суть функции переходов и выходов автомата A, g : Q ^ Q,f : Q ^ Z. Предполагается, что функция выходов f является непременно частью ключа k w-шифра. Иногда начальное состояние q(1) автомата A и его функция переходов g могут быть другими частями этого ключа. Далее, для общности, произвольный ключ в K обозначается знаком k[q(1), g, f ], подразумевающим f обязательной и q(1) и g опциональными составляющими ключа. Предполагается также, что в A для любого начального состояния q(1) е Q и целого / ^ 1 состояния q(t) = gt-i(q(1)), t = 1, 2,..., /, все различные. В этом случае для любого w = (г, n) е W с г = г^2 ... гт и n = iii2 ... im можно определить функцию : Q ^ Z таким образом, что для любого s е Q, ^w,q(i),z(s) = Wj, если s = q(ij), j е {1, 2,... , m}, и ^w,q(i),1 (s) = 0 в противном случае, т. е. если s = q(t), t е {1, 2,...,/} \ {ii, i2,... , im}. Ключевая функция h, алгоритмы шифрования и расшифрования E,D и ключи ke,kd в CA определяются в каждом из двух возможных случаев следующим образом: 1) случай w-расшифрования - Е(x,k) = Е (xix2 .. .xi,k[q(1),g,f ]) = yig2 ...yi = У, где y = x + z, z = ZiZ2 ... zj, zt = f (gt-i(q(1))), t =1, 2,... ,/; h(k,w) = h(k[q(1),g,f], (w,n)i) = k[q(1),g,fiL где fi = f - ^w,q(i),i; D(y,k[q(1),g,fi]) = D(yiy2 . ..yi,k[q(1),g,fi]) = xix2 .. .x1 = x', где x' = y - z', z' = zi z2 ...zl, zt = fi(gt-i(q(1))), t = 1, 2,...,/; 2) случай w-зашифрования - h(k,w) = ^fc^^gj^ (w,n)i) = k[q(1),g,f2], где f2 = f + £w,q(i),i; E(x, h(k, w)) = E(xix2 ... xj, k[q(1), g, f2]) = yiy2 ... y = y, где y = x + z', z' = zi z2 ...z', zt = f2(gt-i(q(1))), t = 1, 2,...,/; D(y,k) = D(yiy2 . . .y,k[q(1),g,f]) = xix2 . . .xJ = ^ где x' = y - z, z = ziz2 ... zj, zt = f (gt-i(q(1))), t =1, 2,..., /. В обоих случаях непосредственно проверяется, что x' = x+w. Кроме того, в первом случае ke = k[q(1),g,f] и = k[q(1), g, fi], во втором случае ke = k[q(1),g,f2] и = = k[q(1), g, f]. Наконец, опишем шифр с водяными знаками CR = (X, K, W, h, Е, D), являющийся конкретизацией w-шифра CA, в которой автомат A = (Q,Z, g, f) представляет собой нелинейный фильтрующий генератор ключевого потока [2], построенный из регистра сдвига с линейной обратной связью (LFSR) R некоторой длины n с примитивным характеристическим полиномом c0 + ci u + ... + cn-iun-i - un в Z2 [u] и нелинейной булевой фильтрующей функцией f от n переменных. Таким образом, F = Z2, X = Z2, в любом w = (г,^ е W строка г есть вектор 11... 1, так что w = n = ii i2 ...im, Q = Zn, Z = Z2 и для любого s = s0si... sn-i е Q имеет место g(s) = si... sn-isn, где sn = C0s0 + Cisi + ... + Cn-isn-i. Поскольку в Z2 операции сложения и вычитания совпадают со сложением по mod 2 и сложение с 1 означает инверсию, следующие соотношения верны в CR: 1) если q(1) = m = 00... 0 и / ^ 2n - 1, то 5w,q(i),i(s) = Е sq(ij), где для a = a0ai... an-i е Zn спраj=i ведливо: sCT = sq° Л s^1 Л ... Л sn-i1, s^4 = -st, если at = 0, и s^4 = st, если at = 1, t = 0,1,... , n - 1; 2) fi = f2; 3) алгоритмы зашифрования и расшифрования в случае w-зашифрования являются алгоритмами соответственно расшифрования и зашифрования в случае w-расшифрования. w-Шифр CR со встраиванием водяного знака в процессе расшифрования реализован и протестирован на MPEG-видеоданных. Информацию об этом см. в [5, 6].

Скачать электронную версию публикации