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

'''Схема передачи зашифрованных изображений (n, n+1)''' ({{lang-en| (n, n+1) Multi secret image sharing (MSIS) Scheme}}) - Схема [[Визуальная криптография|визуальной криптографии]], которая позволяет отправить <math>n</math> изображений в виде <math>n+1</math> зашифрованных изображений, визуально представляющих шум. Для восстановления <math>n</math> зашифрованных изображений, необходимым условием является наличие всех <math>n+1</math> шумных изображений. Данная схема передачи имеет высокую степень защиты за счет принципа [[Разделение секрета|разделения секрета]] и стойкости к изменению шумных изображений в неполном количестве, которое не раскроет никакой частичной информации о зашифрованных изображениях.

== Введение ==
Одной из множества техник передачи зашифрованного изображения является [[криптография]], которая осуществляет шифрование/восстановление текстовых данных при помощи ключа, который необходимо предоставить принимающей стороне, что не есть безопасно. Другой техникой является [[цифровой водяной знак]], который используется в [[Стеганография|стеганографии]] при обмене сообщениями внедренными в цифровой сигнал. Но из-за внедрения в исходный сигнал, принимающая сторона может столкнуться с невозможностью восстановления исходного сообщения в неизменном виде.   
Для решения вышеперечисленных проблем была создана подобласть [[Криптография|криптографии]] — [[визуальная криптография]]. Своими истоками [[визуальная криптография]] обязана [[Шамир, Ади|Ади Шамиру]], который впервые предложил передавать изображение в виде нескольких искаженных<ref name=":0">{{Книга|автор = 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|страниц = |isbn = }}</ref> (визуально шумных), что не позволяло увидеть детали исходного изображения, но при совмещении всех переданных компонент - восстановление проходит без значимых искажений. По мере развития технологий появилась потребность одновременно отправлять более чем одно секретное изображение - для достижения этой цели и были разработаны схемы <math>(n, n)</math> и <math>(n, n+1)</math>. Подобные схемы широко применяются в областях, где обмен секретными данными происходит по незащищенным каналам, что актуально в условиях [[Нелегальная разведка|нелегальной разведки]].

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

==== Алгоритм шифрования ====
* Входные данные: '''n''' секретных изображения <math>{SI_{1}, SI_{2}...SI_{n}}</math> размера h × w.
* Выходные данные: '''n+1''' шумное изображение <math>{NI_{1},NI_{2}...NI_{n},NI_{n+1}}</math>.
* 1. Генерируется '''n''' временных переменных <math>{C_{1},C_{2}...C_{n}}</math>. 
Данные переменные генерируются путем применения операции деления к изображениям <math>SI_{i} ,i = 1,2,...n</math> с делителем <math>n + 1</math> . Далее, чтобы округлить полученные значения с плавающей точкой к наиболее близким целочисленным значениям, используется функция округления <math>round</math>    (примерами функций округления могут служить [[Floor and ceiling functions|ceil, floor]]). Операция деления необходима для того, чтобы скалярное значения каждого пикселя не могло превысить 255 при умножении на константу <math>a</math> ∈ <math>N</math>.

   <math>C_{i}=round((SI_{i}/(n+1)))</math>, где <math>{i=1,2,...n}</math>
* 2. Генерируется случайная матрица <math>R</math> размера h x w. 
   <math>R = Random(h, w)</math>
* 3. На удаленном сервере генерируется ключ <math>SK</math> путем применения операции сложения по модулю к временным переменным <math>C_{i}, i = 1,2,...n</math>.
   <math>SK = (C_{1})mod 256</math>
   <math>SK = (C_{i} + SK)mod 256</math>, где <math>{i = 2, 3,...n}</math>
* 4. Генерируется '''n+1''' шумное изображение <math>{NI_{1},NI_{2},...NI_{n},NI_{n+1}}</math>

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

Последнее изображение <math>NI_{n+1}</math> генерируется применением операции сложения по модулю только к серверному ключу SK и случайной матрице R, умноженными на <math>n + 1</math>.
   <math>NI_{i} =(C_{i}+SK+R)mod256</math>, где <math>{i=1,2,...n}</math>
   <math>NI_{n+1}=((n+1)*(SK+R))mod256</math>
<math>(n+1)</math>-е шумное изображения необходимо для отыскания случайной матрицы <math>R</math> на принимающей стороне.

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

* Входные данные: '''n+1''' шумных изображений <math>{N_{1}, N_{2}...N_{n}}</math>.
* Выходные данные: '''n''' восстановленных изображений <math>{RI_{1}, RI_{2},...RI_{n}}</math>.
* 1. На стороне клиента генерируется ключ <math>CK</math> как обратное к первым <math>n</math> изображениям.
   <math>CK = (N_{1})mod 256</math>
   <math>CK = (CK + N_{i})mod 256,</math> где <math>{i = 2,3...n}</math>
* 2. Далее генерируются временные шумные изображения <math>P_{i}, i = 1,2,...n,</math> путем перемножения входных изображений на <math>(n+1)</math> (количество полученных зашифрованных изображений).  
   <math>P_{i} =((n+1)*N_{i})mod256,</math> где <math>{i=1,2,...n}</math>
* 3. Генерируется матрица <math>R</math>, которая была сгенерирована на сервере при шифровании для обеспечения случайности в шаблоне изображений с шумом.
Для этого используется клиентский ключ <math>CK</math> и последнее изображение <math>NI_{n+1}</math>.
   <math>R=(N_{n+1}-CK)mod256</math>
* 4. Наконец, генерируются восстановленные изображения <math>{ RI_{i}, i = 1, 2,...n}</math>, используя модуль разности временного изображения <math>P_{i}, i = 1,2,...n</math> и суммы <math>CK + R</math>.  
   <math>RI_{i} = (P_{i}-(CK + R))mod 256</math>

== Пример использования алгоритма ==
[[File:Demo of msis algorithm.png|thumb|150px|справа|Рисунок 1. Пример результата работы алгоритма]]
На рисунке 1 можно наблюдать экспериментальную выборку из <math>5</math> исходных изображений <math>SI_{1}, SI_{2}, SI_{3}, SI_{4}, SI_{5}</math> размера <math>512</math>х<math>512</math> пикселей, которые при помощи описанного алгоритма были преобразованы в 6 шумных изображений <math>NI_{1},NI_{2},NI_{3},NI_{4},NI_{5},NI_{6}</math>. Результатом восстановления исходных изображений являются изображения <math>RI_{1} , RI_{2} , RI_{3} , RI_{4} , RI_{5}</math> соответственно. Можно убедиться, что для человеческого глаза отсутствует визуальная разница между исходными данными и результатом.

== Оценка соответствия восстановленных изображений ==
Для оценки соответствия восстановленных и исходных изображений удобно пользоваться: [[Корреляция|коэффициентом корреляции]], [[Среднеквадратическое отклонение|среднеквадратичной ошибкой]] и [[Пиковое отношение сигнала к шуму|пиковым отношением сигнала к шуму]].
==== Коэффициент корреляции ====
Коэффициент корреляции <math>r</math> принимает значения от <math>-1</math> до <math>+1</math>. Значение <math>+1</math> означает, что два сравниваемых изображение идентичны, значение <math>-1</math> - изображения противоположны, а <math>r=0</math> означает, что изображения не коррелируют. В конкретном случае коэффициент корреляции задается формулой: 
   <math>r=(n*\sum{pq}-\sum{p}\sum{q}) / (\sqrt{  (n*\sum{p^2}-(\sum{p})^2)*(n*\sum(q^2)-(\sum(q))^2 })</math>
<math>n</math> - количество парных значений пикселя исходного <math>p</math> и пикселя восстановленного <math>q</math> изображения.

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

    <math>\sigma = \sqrt{(1/(M*N))\sum_{\mathop x=1}^{M}\sum_{\mathop y=1}^{N}(SI_{x,y}-RI_{x,y})^2} </math>
где <math>M</math> и <math>N</math> - размеры изображения. <math>SI_{x, y}</math> - пиксельное значение секретного изображения в точке <math>{(x, y)}</math>. <math>RI_{x, y}</math> - пиксельное значение восстановленного изображения в точке <math>{(x, y)}</math>

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

 <math>PSNR(db) = 20*log_{10}255/\sigma</math>

Данная схема позволяет расшифровать полученные изображения с ошибкой <math>\sigma</math>≈3, что не уступает схемам на основе [[Булева алгебра|булевых операций]] AND ([[конъюнкция]]), OR ([[дизъюнкция]]), XOR ([[исключающее или]]). Пример точной оценки соответствия тестовых изображений можно наблюдать в таблице 1.
{| class="wikitable"
|-
! Изображения !! Корреляция !! Среднеквадратичная ошибка !! Пиковое отношение сигнала к шуму
|-
| <math>SI_{1},RI_{1}</math> || 0.9992 || 3.0288 || 38.54&nbsp;dB
|-
| <math>SI_{2},RI_{2}</math> || 0.9994 || 3.1793 || 38.12&nbsp;dB
|-
| <math>SI_{3},RI_{3}</math> || 0.9995 || 3.0270 || 38.54&nbsp;dB
|-
| <math>SI_{4},RI_{4}</math> || 0.9993 || 3.0306 || 38.53&nbsp;dB
|-
| <math>SI_{5},RI_{5}</math> || 0.9997 || 3.0293 || 38.54&nbsp;dB
|-
| <math>SI_{6},RI_{6}</math> || 0.9997 || 3.0293 || 38.54&nbsp;dB
|}

== Безопасность схемы (n, n+1) ==
==== Криптостойкость ====
Ключевая проблема многих схем [[Визуальная криптография|визуальной криптографии]] передачи зашифрованных изображений в том, что они раскрывают частичную информацию из менее чем <math>n+1</math> шумных изображений из-за несовершенства методов шифрования на основе операции [[Сложение по модулю 2|XOR]], что ставит под угрозу безопасность. Примером схемы, допускающей подобную утечку может служить [<ref name=":2">{{Книга|автор = Daoshun Wang|заглавие = Two secret sharing schemes based on Boolean operations|ответственный = |издание = |место = |год = 2007|страницы = |страниц = |isbn = }}</ref>]. Вышеописанный алгоритм с использованием модульной арифметики лишен подобной уязвимости из-за использования случайно-сгенерированной матрицы <math>R</math>, вносящей случайный характер в зашифрованные изображения, хотя оставляет возможность взлома при наличии у злоумышленника полного набора зашифрованных изображений.

==== Метод подбора грубой силой ====
При условии наличия у злоумышленника алгоритма шифрования и всех переданных изображений - последним этапом защиты является порядок переданных изображений.
Корректный порядок необходим для восстановления клиентского ключа <math>CK</math> и матрицы <math>R</math>. Количество вариантов подбора оценивается следующим [[Сочетание|числом сочетаний]]:
  <math>{n+1\choose 2} = C_{n+1}^2 = \frac{(n+1)!}{2!\left(n-1\right)!}.</math>
что вносит дополнительные вычислительные расходы в [[Атака «грубой силой»|атаку грубой силой]] при отправке большого числа изображений.

== См. также ==
* [[:Визуальная криптография|Визуальная криптография]]
* [[:Стеганография|Стеганография]]

=== Научные статьи ===
* {{статья
  |автор          = {{nobr|Daoshun Wang}}, {{nobr|Lei Zhang}}
  |заглавие       = Two secret sharing schemes based on Boolean operations
  |ссылка         = https://www.sciencedirect.com/science/article/abs/pii/S003132030600481X
  |год            = 2007
}}

* {{статья
  |автор          = {{nobr|Ming-Hong Tsai}}, {{nobr|Chaur-Chin Chen}}
  |заглавие       = A STUDY ON SECRET IMAGE SHARING
  |ссылка         = http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.390.4165&rep=rep1&type=pdf
  |год            = 2013
}}

* {{статья
  |автор          = {{nobr|Mohit Rajput}}, {{nobr|Maroti Deshmukh}}
  |заглавие       = A Technique to Share Multiple Secret Images
  |ссылка         = https://arxiv.org/abs/1611.09261
  |год            = 2016
}}

* {{статья
  |автор          = {{nobr|Tzung-Her Chen}}, {{nobr|Chang-Sian Wu}}
  |заглавие       = Efficient multi-secret image sharing based on Boolean operations
  |ссылка         = https://www.sciencedirect.com/science/article/pii/S0165168410002598
  |год            = 2011
}}

* {{статья
  |автор          = {{nobr|Maroti Deshmukh}}, {{nobr|Neeta Nain}},  {{nobr|Mushtaq Ahmed}}
  |заглавие       = An (n, n)-Multi Secret Image Sharing Scheme Using Boolean XOR and Modular Arithmetic
  |ссылка         = https://www.researchgate.net/publication/303513480_An_n_n-Multi_Secret_Image_Sharing_Scheme_Using_Boolean_XOR_and_Modular_Arithmetic
  |год            = 2016
}}

== Примечания ==
{{примечания}}

{{изолированная статья|дата=2018-12-12}}

[[Категория:Криптография]]