Визуальная криптография — один из криптографических методов, который позволяет зашифровать зрительную информацию (картинку, текст и так далее) таким образом, что дешифрование становится механической операцией, не требующей использования компьютера.
Один из самых известных методов принадлежит Мони Наору (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)-случае белый пиксель в секретном изображении кодируется с использованием матрицы из следующего набора, в котором каждая строка даёт субпиксельный образец для одной из компонент:
все перестановки столбцов:
В то время, как чёрный пиксель в секретном изображении кодируется с использованием следующей матрицы:
все перестановки столбцов:
Например, в (2, 2)-случае (секрет разделён на 2 части и обе части необходимы для декодирования секрета) используется дополнительная матрица для чёрных пикселей и идентичная ей матрица для белых пикселей. Проделав операции со всеми пикселями, получаем все субпиксели. Связанные с чёрными пикселями ассоциируются теперь с чёрными, в то время как 50% субпикселей, связанные с белыми, – остаются белыми.
Обман в схеме (2, N) визуальной криптографии
правитьHorng и др. предложил метод, который позволяет N-1 сговорившимся сторонам обмануть честную партию [8]. Они выигрывают, зная лежащий в основе закон распределения пикселей в частях, чтобы создать новые части, которые комбинируют с существующими для создания нового секретного сообщения по выбору обманщиков.
Мы знаем, что двух частей достаточно для того, чтобы расшифровать секретное сообщение с помощью зрения человека. Но рассматриваемые 2 части также дают информацию о третьей части. Например, сговорившиеся участники могут посмотреть свои части, чтобы определить, в каких случаях они оба имеют чёрные пиксели, и использовать эту информацию, чтобы определить, что другой участник также будет иметь чёрный пиксель в этом месте. Зная, где чёрный пиксель находится в других частях, они могут создать новую часть, которая будет создана исходя из ранее полученных предположений, и даст новое секретное сообщение. В этом случае набора частей сговорившихся людей достаточно, чтобы создать секретный код-обман других честных участников.
Простой алгоритм
правитьСуществует простой алгоритм для бинарной (чёрно-белой) визуальной криптографии, который создаёт 2 зашифрованных изображения из оригинального. Алгоритм следующий: сначала формируется изображение из случайных пикселей такого же размера и вида, как и в исходном изображении. Потом создаётся второе изображение того же размера и вида как первое, но где пиксели исходного изображения, такие же как в соответствующем первом зашифрованном, меняют цвет на противоположный, а пиксель, который в первом зашифрованном сообщении не совпадает с исходным, становится соответствующим пикселю первого зашифрованного во втором зашифрованном изображении. Два случайных изображения теперь могут быть объединены с использованием "исключающего или" (XOR), чтобы восстановить исходное изображение.
Примечания
править- ↑ 1 2 3 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