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

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

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

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

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

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

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

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

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

(k, N) — визуальная схема

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

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

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

Пример

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

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

(2, N) -случай

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

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

все перестановки столбцов: C 0 = [ 1 0 . . . 0 1 0 . . . 0 . . . 1 0 . . . 0 ] . {displaystyle mathbf {C_{0}=} {egin{bmatrix}1&0&…&0\1&0&…&0\…\1&0&…&0end{bmatrix}}.}

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

все перестановки столбцов: C 1 = [ 1 0 . . . 0 0 1 . . . 0 . . . 0 0 . . . 1 ] . {displaystyle mathbf {C_{1}=} {egin{bmatrix}1&0&…&0\0&1&…&0\…\0&0&…&1end{bmatrix}}.}

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

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

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

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

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

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

Реализация алгоритма

Ниже приведён код программы на языке Python, реализующий алгоритм, который создаёт два «теневых» изображения, которые накладываются с использованием «исключающего или» (XOR).

Initial image

In[1]:

import random import numpy as np from PIL import Image, ImageDraw import matplotlib.pyplot as plt import matplotlib import matplotlib.cm as cm %matplotlib inline dpi = 150 matplotlib.rc(«savefig», dpi=dpi)

In[2]:

def show_image(img, plot=True): plt.imshow(img, cmap=cm.Greys_r) if plot: plt.show()

In[3]:

image = Image.open(«image.jpg») img = np.asarray(image) show_image(img) image.save(«1.jpg», «JPEG»)

Binary

In[4]:

def rgb2gray(rgb): r, g, b = rgb[:,:,0], rgb[:,:,1], rgb[:,:,2] gray = 0.2989 * r + 0.5870 * g + 0.1140 * b return gray

In[5]:

img_grey = rgb2gray(img) print(img_grey.shape) show_image(img_grey)

(448, 640)

In[6]:

t = 64 # 0 <= t <= 256 img_b = np.copy(img_grey) img_b[img_grey > t] = 255 img_b[img_grey <= t] = 0 show_image(img_b)

2 shadow images

In[7]:

patterns = np.array([ [[1, 0], [1, 0]], [[0, 0], [1, 1]], [[1, 0], [0, 1]], [[0, 1], [1, 0]], [[1, 1], [0, 0]], [[0, 1], [0, 1]]]).astype(np.bool) #patterns

In[8]:

def concat(img): return np.vstack([np.hstack(line) for line in img])

In[9]:

rand_mask = np.random.randint(0, 6, size=img_b.shape) images = [] images.append(patterns[rand_mask]) images.append(patterns[rand_mask]) image_mask = img_b.astype(np.bool) images[1][image_mask] = patterns[5 — rand_mask][image_mask]

In[10]:

images = list(map(concat, images))

In[11]:

show_image(images[0])

In[12]:

show_image(images[1])

Sum 2 shadow images

In[13]:

show_image((images[0] ^ images[1])[::2, ::2])