Русская Википедия:Визуальная криптография
Визуальная криптография — один из криптографических методов, который позволяет зашифровать зрительную информацию (картинку, текст и так далее) таким образом, что дешифрование становится механической операцией, не требующей использования компьютера.
Один из самых известных методов принадлежит Мони Наору (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]
Пример
В этом примере изображение было разделено на 2 компоненты. Каждая из них имеет пару пикселей для каждого пикселя в исходном изображении. Эти пиксельные пары заштрихованы чёрным или белым согласно следующему правилу: если пиксель в оригинальном изображении чёрный, пиксельные пары должны дополнять друг друга. Случайным образом выбираются один ■□ и другой □■. Когда эти комплементарные пары перекрываются, они превращаются в тёмно-серый. С другой стороны, если пиксель в исходном изображении был белым, его пары должна быть одинаковыми. Обе ■□ или обе □■. При их наложении получится светло-серый.
Поэтому, когда две компоненты изображения накладываются, появляется оригинальное изображение. Однако рассматриваемые по отдельности компоненты не показывают никакой информации об исходном изображении; оно не отличимо от случайного набора пар вида ■□ / □■. Кроме того, если есть одна компонента изображения, можно использовать правила, приведённые выше для создания подделки второй части изображения, которая в сочетании с первой может дать вообще любое изображение.
(2, N) -случай
Это случай совместного использования секрета произвольным количеством людей N так, что по крайней мере 2 из них нужны для декодирования секрета. Данная схема была представлена публике Мони Наором и Ади Шамиром в 1994 году. В этой схеме есть секретное изображение, которое закодировано в N частях, напечатанных на прозрачной плёнке. Части произвольные и не содержат информации о расшифровке секретной информации, однако если любые 2 части наложить друг на друга, то секретное изображение становится расшифрованным для человеческого глаза.
Каждый пиксель из секретного изображения кодируется в несколько субпикселей в каждой части изображения с помощью матрицы, определяющей цвет пикселя. В (2, N)-случае белый пиксель в секретном изображении кодируется с использованием матрицы из следующего набора, в котором каждая строка даёт субпиксельный образец для одной из компонент:
все перестановки столбцов: <math>\mathbf{C_0 = } \begin{bmatrix} 1 & 0 & ... &0 \\ 1 & 0 & ... & 0 \\ ...\\ 1 & 0 & ... &0 \end{bmatrix}.</math>
В то время, как чёрный пиксель в секретном изображении кодируется с использованием следующей матрицы:
все перестановки столбцов:<math> \mathbf{C_1 =}\begin{bmatrix} 1 & 0 & ...& 0 \\ 0 & 1 & ... & 0 \\ ... \\ 0 & 0 & ...& 1 \end{bmatrix}.</math>
Например, в (2, 2)-случае (секрет разделён на 2 части и обе части необходимы для декодирования секрета) используется дополнительная матрица для чёрных пикселей и идентичная ей матрица для белых пикселей. Проделав операции со всеми пикселями, получаем все субпиксели. Связанные с чёрными пикселями ассоциируются теперь с чёрными, в то время как 50% субпикселей, связанные с белыми, – остаются белыми.
Обман в схеме (2, N) визуальной криптографии
Horng и др. предложил метод, который позволяет N-1 сговорившимся сторонам обмануть честную партию [8]. Они выигрывают, зная лежащий в основе закон распределения пикселей в частях, чтобы создать новые части, которые комбинируют с существующими для создания нового секретного сообщения по выбору обманщиков.
Мы знаем, что двух частей достаточно для того, чтобы расшифровать секретное сообщение с помощью зрения человека. Но рассматриваемые 2 части также дают информацию о третьей части. Например, сговорившиеся участники могут посмотреть свои части, чтобы определить, в каких случаях они оба имеют чёрные пиксели, и использовать эту информацию, чтобы определить, что другой участник также будет иметь чёрный пиксель в этом месте. Зная, где чёрный пиксель находится в других частях, они могут создать новую часть, которая будет создана исходя из ранее полученных предположений, и даст новое секретное сообщение. В этом случае набора частей сговорившихся людей достаточно, чтобы создать секретный код-обман других честных участников.
Простой алгоритм
Существует простой алгоритм для бинарной (чёрно-белой) визуальной криптографии, который создаёт 2 зашифрованных изображения из оригинального. Алгоритм следующий: сначала формируется изображение из случайных пикселей такого же размера и вида, как и в исходном изображении. Потом создаётся второе изображение того же размера и вида как первое, но где пиксели исходного изображения, такие же как в соответствующем первом зашифрованном, меняют цвет на противоположный, а пиксель, который в первом зашифрованном сообщении не совпадает с исходным, становится соответствующим пикселю первого зашифрованного во втором зашифрованном изображении. Два случайных изображения теперь могут быть объединены с использованием "исключающего или" (XOR), чтобы восстановить исходное изображение.
Примечания
- ↑ 1,0 1,1 1,2 Шаблон:Книга
- ↑ Шаблон:Книга
- ↑ Шаблон:Cite web
- ↑ Шаблон:Cite web
- ↑ Шаблон:Книга
- ↑ Шаблон:Книга
- ↑ Шаблон:Cite web
- ↑ Horng, G, Chen, T. and Tasi, D.S. Cheating in Visual Cryptography, Designs, Codes and Cryptography Шаблон:Wayback, 2006, pp219—236
