Схема передачи зашифрованных изображений (n, n+1)

Схема передачи зашифрованных изображений (n, n+1) (англ.  (n, n+1) Multi secret image sharing (MSIS) Scheme) - Схема визуальной криптографии, которая позволяет отправить $n$ изображений в виде $n+1$ зашифрованных изображений, визуально представляющих шум. Для восстановления $n$ зашифрованных изображений, необходимым условием является наличие всех $n+1$ шумных изображений. Данная схема передачи имеет высокую степень защиты за счет принципа разделения секрета и стойкости к изменению шумных изображений в неполном количестве, которое не раскроет никакой частичной информации о зашифрованных изображениях.

Введение

Одной из множества техник передачи зашифрованного изображения является криптография, которая осуществляет шифрование/восстановление текстовых данных при помощи ключа, который необходимо предоставить принимающей стороне, что не есть безопасно. Другой техникой является цифровой водяной знак, который используется в стеганографии при обмене сообщениями внедренными в цифровой сигнал. Но из-за внедрения в исходный сигнал, принимающая сторона может столкнуться с невозможностью восстановления исходного сообщения в неизменном виде. Для решения вышеперечисленных проблем была создана подобласть криптографии — визуальная криптография. Своими истоками визуальная криптография обязана Ади Шамиру, который впервые предложил передавать изображение в виде нескольких искаженных (визуально шумных), что не позволяло увидеть детали исходного изображения, но при совмещении всех переданных компонент - восстановление проходит без значимых искажений. По мере развития технологий появилась потребность одновременно отправлять более чем одно секретное изображение - для достижения этой цели и были разработаны схемы $(n,n)$ и $(n,n+1)$. Подобные схемы широко применяются в областях, где обмен секретными данными происходит по незащищенным каналам, что актуально в условиях нелегальной разведки.

Алгоритм метода (n, n+1)

Уникальность нижеописанного метода заключается в том, что вместо привычной для имплементации подобных алгоритмов операции XOR - используется модульная арифметика. Ее главное преимущество - отсутствие куда более времязатратной операции XOR, которая требует выполнения побитовых операций и может раскрыть частичную информацию об исходном изображении, имея даже менее чем $n$ шумных изображений. Обозначим два числа противоположными, если $a+b=0(mod$ $n)$. Для черно-белых или цветных изображений, RGB значение пикселя примем за скалярную величину в диапазоне [0,255]. Каждое число из данного диапазона имеет противоположное, со значением модуля 256.

Алгоритм шифрования

• Входные данные: n секретных изображения ${SI_{1},SI_{2}...SI_{n}}$ размера h × w.
• Выходные данные: n+1 шумное изображение ${NI_{1},NI_{2}...NI_{n},NI_{n+1}}$.
• 1. Генерируется n временных переменных ${C_{1},C_{2}...C_{n}}$.

Данные переменные генерируются путем применения операции деления к изображениям $SI_{i},i=1,2,...n$ с делителем $n+1$ . Далее, чтобы округлить полученные значения с плавающей точкой к наиболее близким целочисленным значениям, используется функция округления $round$ (примерами функций округления могут служить ceil, floor). Операция деления необходима для того, чтобы скалярное значения каждого пикселя не могло превысить 255 при умножении на константу $a$ ∈ $N$.

  $C_{i}=round((SI_{i}/(n+1)))$, где ${i=1,2,...n}$

• 2. Генерируется случайная матрица $R$ размера h x w.

  $R=Random(h,w)$

• 3. На удаленном сервере генерируется ключ $SK$ путем применения операции сложения по модулю к временным переменным $C_{i},i=1,2,...n$.

  $SK=(C_{1})mod256$
  $SK=(C_{i}+SK)mod256$, где ${i=2,3,...n}$

• 4. Генерируется n+1 шумное изображение ${NI_{1},NI_{2},...NI_{n},NI_{n+1}}$

Первые $n$ изображений генерируются применением операции сложения по модулю к временным переменным $C_{i}$, серверному ключу $SK$ и случайной матрице $R$.

Последнее изображение $NI_{n+1}$ генерируется применением операции сложения по модулю только к серверному ключу SK и случайной матрице R, умноженными на $n+1$.

  $NI_{i}=(C_{i}+SK+R)mod256$, где ${i=1,2,...n}$
  $NI_{n+1}=((n+1)*(SK+R))mod256$

$(n+1)$-е шумное изображения необходимо для отыскания случайной матрицы $R$ на принимающей стороне.

Алгоритм восстановления зашифрованных изображений

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

• Входные данные: n+1 шумных изображений ${N_{1},N_{2}...N_{n}}$.
• Выходные данные: n восстановленных изображений ${RI_{1},RI_{2},...RI_{n}}$.
• 1. На стороне клиента генерируется ключ $CK$ как обратное к первым $n$ изображениям.

  $CK=(N_{1})mod256$
  $CK=(CK+N_{i})mod256,$ где ${i=2,3...n}$

• 2. Далее генерируются временные шумные изображения $P_{i},i=1,2,...n,$ путем перемножения входных изображений на $(n+1)$ (количество полученных зашифрованных изображений).

  $P_{i}=((n+1)*N_{i})mod256,$ где ${i=1,2,...n}$

• 3. Генерируется матрица $R$, которая была сгенерирована на сервере при шифровании для обеспечения случайности в шаблоне изображений с шумом.

Для этого используется клиентский ключ $CK$ и последнее изображение $NI_{n+1}$.

  $R=(N_{n+1}-CK)mod256$

• 4. Наконец, генерируются восстановленные изображения ${RI_{i},i=1,2,...n}$, используя модуль разности временного изображения $P_{i},i=1,2,...n$ и суммы $CK+R$.

  $RI_{i}=(P_{i}-(CK+R))mod256$

Пример использования алгоритма

Рисунок 1. Пример результата работы алгоритма

На рисунке 1 можно наблюдать экспериментальную выборку из $5$ исходных изображений $SI_{1},SI_{2},SI_{3},SI_{4},SI_{5}$ размера $512$х$512$ пикселей, которые при помощи описанного алгоритма были преобразованы в 6 шумных изображений $NI_{1},NI_{2},NI_{3},NI_{4},NI_{5},NI_{6}$. Результатом восстановления исходных изображений являются изображения $RI_{1},RI_{2},RI_{3},RI_{4},RI_{5}$ соответственно. Можно убедиться, что для человеческого глаза отсутствует визуальная разница между исходными данными и результатом.

Оценка соответствия восстановленных изображений

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

Коэффициент корреляции

Коэффициент корреляции $r$ принимает значения от $-1$ до $+1$. Значение $+1$ означает, что два сравниваемых изображение идентичны, значение $-1$ - изображения противоположны, а $r=0$ означает, что изображения не коррелируют. В конкретном случае коэффициент корреляции задается формулой:

  $r=(n*\sum {pq}-\sum {p}\sum {q})/({\sqrt {(n*\sum {p^{2}}-(\sum {p})^{2})*(n*\sum (q^{2})-(\sum (q))^{2}}})$

$n$ - количество парных значений пикселя исходного $p$ и пикселя восстановленного $q$ изображения.

Среднеквадратичная ошибка

Среднеквадратичная ошибка $\sigma$ дает тем большие значения, чем меньше сходство сравниваемых изображений.В конкретном случае задается формулой:

   $\sigma ={\sqrt {(1/(M*N))\sum _{\mathop {x} =1}^{M}\sum _{\mathop {y} =1}^{N}(SI_{x,y}-RI_{x,y})^{2}}}$

где $M$ и $N$ - размеры изображения. $SI_{x,y}$ - пиксельное значение секретного изображения в точке ${(x,y)}$. $RI_{x,y}$ - пиксельное значение восстановленного изображения в точке ${(x,y)}$

Пиковое отношение сигнала к шуму

Пиковое отношение сигнала к шуму $PSNR$ тем выше, чем лучше совпадают исходное и восстановленное изображение. В конкретном случае задается формулой:

$PSNR(db)=20*log_{10}255/\sigma$

Данная схема позволяет расшифровать полученные изображения с ошибкой $\sigma$≈3, что не уступает схемам на основе булевых операций AND (конъюнкция), OR (дизъюнкция), XOR (исключающее или). Пример точной оценки соответствия тестовых изображений можно наблюдать в таблице 1.

Изображения	Корреляция	Среднеквадратичная ошибка	Пиковое отношение сигнала к шуму
$SI_{1},RI_{1}$	0.9992	3.0288	38.54dB
$SI_{2},RI_{2}$	0.9994	3.1793	38.12dB
$SI_{3},RI_{3}$	0.9995	3.0270	38.54dB
$SI_{4},RI_{4}$	0.9993	3.0306	38.53dB
$SI_{5},RI_{5}$	0.9997	3.0293	38.54dB
$SI_{6},RI_{6}$	0.9997	3.0293	38.54dB

Безопасность схемы (n, n+1)

Криптостойкость

Ключевая проблема многих схем визуальной криптографии передачи зашифрованных изображений в том, что они раскрывают частичную информацию из менее чем $n+1$ шумных изображений из-за несовершенства методов шифрования на основе операции XOR, что ставит под угрозу безопасность. Примером схемы, допускающей подобную утечку может служить []. Вышеописанный алгоритм с использованием модульной арифметики лишен подобной уязвимости из-за использования случайно-сгенерированной матрицы $R$, вносящей случайный характер в зашифрованные изображения, хотя оставляет возможность взлома при наличии у злоумышленника полного набора зашифрованных изображений.

Метод подбора грубой силой

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

 ${n+1 \choose 2}=C_{n+1}^{2}={\frac {(n+1)!}{2!\left(n-1\right)!}}.$

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

См. также

• Визуальная криптография
• Стеганография

Научные статьи

• Daoshun Wang, Lei Zhang. Two secret sharing schemes based on Boolean operations. — 2007.

• Ming-Hong Tsai, Chaur-Chin Chen. A STUDY ON SECRET IMAGE SHARING. — 2013.

• Mohit Rajput, Maroti Deshmukh. A Technique to Share Multiple Secret Images. — 2016.

• Tzung-Her Chen, Chang-Sian Wu. Efficient multi-secret image sharing based on Boolean operations. — 2011.

• Maroti Deshmukh, Neeta Nain, Mushtaq Ahmed. An (n, n)-Multi Secret Image Sharing Scheme Using Boolean XOR and Modular Arithmetic. — 2016.