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

Введение

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

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

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

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

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

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

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

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

  ${\displaystyle R=Random(h,w)}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 ${\displaystyle {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.

  Примечания

  1. ↑ Verheul, E.R. and H.C.A.van Tilborg. Constructions and properties of k out of n visual secret sharing schemes. — Design Codes and Cryptography, 1997. — С. 11(2):179–196.
  2. ↑ Daoshun Wang. Two secret sharing schemes based on Boolean operations. — 2007.

  На эту статью не ссылаются другие статьи Википедии. Пожалуйста, установите ссылки в соответствии с принятыми рекомендациями.