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

Визуальная криптография — один из криптографических методов, который позволяет зашифровать зрительную информацию (картинку, текст и так далее) таким образом, что дешифрование становится механической операцией, не требующей использования компьютера.

Один из самых известных методов принадлежит Мони Наору (Moni Naor) и Ади Шамиру, разработавшим его в 1994 году.^[1] Они продемонстрировали графическую схему с разделением секрета, согласно которой изображение было разделено на n частей так, что только человек, имеющий все n частей мог расшифровать изображение, в то время как остальные n-1 части не показали никакой информации об оригинальном изображении. Каждая часть была напечатана на отдельном диапозитиве, и расшифровка была выполнена путём наложения этих частей. То есть при наложении всех n частей появляется исходное изображение. Таким образом, для декодирования не требуется высокопроизводительных вычислений, специальных знаний и даже компьютера.

Используя этот алгоритм в компьютерных системах, все части изображения накладываются друг на друга с помощью логических операций AND (конъюнкция), OR (дизъюнкция), XOR (исключающее или) или путём увеличения степени прозрачности в графическом редакторе.

Есть несколько обобщений основной схемы, включая k-из-n визуальную криптографию.^[1]

Используя подобную идею, диапозитивы могут быть использованы для реализации криптосистемы одноразового блокнота (шифр Вернама), при котором один из них является открытым, а другой выступает в роли криптотекста (зашифрованного текста). Если одна из двух частей построена рекурсивно, то эффективность визуальной криптографии может быть увеличена до 100%.^[2]

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

Некоторые предпосылки визуальной криптографии можно найти в патентах 1960-х годов.^[3]^[4] Другие встречаются в работе по восприятию и безопасной коммуникации.^[5]^[6]

Визуальная криптография может быть использована для защиты биометрических данных, в которых расшифровка не требует каких-либо сложных вычислений, для защиты от копирования и проверки подлинности (авторских прав), отслеживания электронных бланков при удалённом голосовании и тому подобном.

(k, N) - визуальная схемаПравить

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

Наор и Шамир продемонстрировали (k, n)-визуальную схему секретного обмена, где изображение было разбито на n частей, таким образом, что кто-либо, обладавший любыми k частями мог расшифровать его, в то время как любые k-1 частей не давали никакой информации о содержании исходного изображения. Когда все k частей будут наложены друг на друга, мы увидим исходное изображение ^[1].

Для того, чтобы разбить исходное чёрно-белое изображение на n частей, необходимо каждый пиксель изображения представить в виде некоторого количества меньших частей. Количество белых и чёрных частей всегда одинаково. Если пиксель делится на 4 части, то получается 2 белых и 2 чёрных блока. Если на 2, то один белый и один чёрный.^[7]

ПримерПравить

Visual crypto animation demo

В этом примере изображение было разделено на 2 компоненты. Каждая из них имеет пару пикселей для каждого пикселя в исходном изображении. Эти пиксельные пары заштрихованы чёрным или белым согласно следующему правилу: если пиксель в оригинальном изображении чёрный, пиксельные пары должны дополнять друг друга. Случайным образом выбираются один ■□ и другой □■. Когда эти комплементарные пары перекрываются, они превращаются в тёмно-серый. С другой стороны, если пиксель в исходном изображении был белым, его пары должна быть одинаковыми. Обе ■□ или обе □■. При их наложении получится светло-серый.

Поэтому, когда две компоненты изображения накладываются, появляется оригинальное изображение. Однако рассматриваемые по отдельности компоненты не показывают никакой информации об исходном изображении; оно не отличимо от случайного набора пар вида ■□ / □■. Кроме того, если есть одна компонента изображения, можно использовать правила, приведённые выше для создания подделки второй части изображения, которая в сочетании с первой может дать вообще любое изображение.

(2, N) -случайПравить

Это случай совместного использования секрета произвольным количеством людей N так, что по крайней мере 2 из них нужны для декодирования секрета. Данная схема была представлена публике Мони Наором и Ади Шамиром в 1994 году. В этой схеме есть секретное изображение, которое закодировано в N частях, напечатанных на прозрачной плёнке. Части произвольные и не содержат информации о расшифровке секретной информации, однако если любые 2 части наложить друг на друга, то секретное изображение становится расшифрованным для человеческого глаза.

Каждый пиксель из секретного изображения кодируется в несколько субпикселей в каждой части изображения с помощью матрицы, определяющей цвет пикселя. В (2, N)-случае белый пиксель в секретном изображении кодируется с использованием матрицы из следующего набора, в котором каждая строка даёт субпиксельный образец для одной из компонент:

все перестановки столбцов: $\text{[math]}$ $\text{[math]}$ $\mathbf {C_{0}=} {\begin{bmatrix}1&0&...&0\\1&0&...&0\\...\\1&0&...&0\end{bmatrix}}.$

В то время, как чёрный пиксель в секретном изображении кодируется с использованием следующей матрицы:

все перестановки столбцов: $\text{[math]}$ $\text{[math]}$ $\mathbf {C_{1}=} {\begin{bmatrix}1&0&...&0\\0&1&...&0\\...\\0&0&...&1\end{bmatrix}}.$

Например, в (2, 2)-случае (секрет разделён на 2 части и обе части необходимы для декодирования секрета) используется дополнительная матрица для чёрных пикселей и идентичная ей матрица для белых пикселей. Проделав операции со всеми пикселями, получаем все субпиксели. Связанные с чёрными пикселями ассоциируются теперь с чёрными, в то время как 50% субпикселей, связанные с белыми, – остаются белыми.

Обман в схеме (2, N) визуальной криптографииПравить

Horng и др. предложил метод, который позволяет N-1 сговорившимся сторонам обмануть честную партию ^[8]. Они выигрывают, зная лежащий в основе закон распределения пикселей в частях, чтобы создать новые части, которые комбинируют с существующими для создания нового секретного сообщения по выбору обманщиков.

Мы знаем, что двух частей достаточно для того, чтобы расшифровать секретное сообщение с помощью зрения человека. Но рассматриваемые 2 части также дают информацию о третьей части. Например, сговорившиеся участники могут посмотреть свои части, чтобы определить, в каких случаях они оба имеют чёрные пиксели, и использовать эту информацию, чтобы определить, что другой участник также будет иметь чёрный пиксель в этом месте. Зная, где чёрный пиксель находится в других частях, они могут создать новую часть, которая будет создана исходя из ранее полученных предположений, и даст новое секретное сообщение. В этом случае набора частей сговорившихся людей достаточно, чтобы создать секретный код-обман других честных участников.

Простой алгоритмПравить

Существует простой алгоритм для бинарной (чёрно-белой) визуальной криптографии, который создаёт 2 зашифрованных изображения из оригинального. Алгоритм следующий: сначала формируется изображение из случайных пикселей такого же размера и вида, как и в исходном изображении. Потом создаётся второе изображение того же размера и вида как первое, но где пиксели исходного изображения, такие же как в соответствующем первом зашифрованном, меняют цвет на противоположный, а пиксель, который в первом зашифрованном сообщении не совпадает с исходным, становится соответствующим пикселю первого зашифрованного во втором зашифрованном изображении. Два случайных изображения теперь могут быть объединены с использованием "исключающего или" (XOR), чтобы восстановить исходное изображение.

ПримечанияПравить

↑ ¹ ² ³ 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.
↑ Gnanaguruparan, M. and Kak, S. Recursive hiding of secrets in visual cryptography. — vol. 26. — Cryptologia, 2002. — С. 68-76.
↑ Cryptographic process and enciphered product (неопр.). Дата обращения: 11 декабря 2015. Архивировано 23 декабря 2015 года.
↑ Information encoding and decoding method (неопр.). Дата обращения: 11 декабря 2015. Архивировано 23 декабря 2015 года.
↑ Kafri, O. and E. Keren. Encryption of pictures and shapes by random grids. — Vol. 12, Issue 6. — Optics Letters, 1987. — С. 377–379.
↑ Arazi, B., I. Dinstein, O. Kafri. Intuition, perception, and secure communication. — Vol. 19, Issue 5. — IEEE Transactions on Systems, Man and Cybernetics, 1989. — С. 1016–1020.
↑ Схема разделения секретной визуальной информации (неопр.). Дата обращения: 11 декабря 2015. Архивировано 22 декабря 2015 года.
↑ Horng, G, Chen, T. and Tasi, D.S. Cheating in Visual Cryptography, Designs, Codes and Cryptography Архивная копия от 17 февраля 2020 на Wayback Machine, 2006, pp219—236

[:0-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] Gnanaguruparan, M. and Kak, S. Recursive hiding of secrets in visual cryptography. — vol. 26. — Cryptologia, 2002. — С. 68-76.

[3] Cryptographic process and enciphered product (неопр.). Дата обращения: 11 декабря 2015. Архивировано 23 декабря 2015 года.

[4] Information encoding and decoding method (неопр.). Дата обращения: 11 декабря 2015. Архивировано 23 декабря 2015 года.

[5] Kafri, O. and E. Keren. Encryption of pictures and shapes by random grids. — Vol. 12, Issue 6. — Optics Letters, 1987. — С. 377–379.

[6] Arazi, B., I. Dinstein, O. Kafri. Intuition, perception, and secure communication. — Vol. 19, Issue 5. — IEEE Transactions on Systems, Man and Cybernetics, 1989. — С. 1016–1020.

[7] Схема разделения секретной визуальной информации (неопр.). Дата обращения: 11 декабря 2015. Архивировано 22 декабря 2015 года.

[8] Horng, G, Chen, T. and Tasi, D.S. Cheating in Visual Cryptography, Designs, Codes and Cryptography Архивная копия от 17 февраля 2020 на Wayback Machine, 2006, pp219—236

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]