Обобщённый алгоритм визуальной криптографии

Spoiler

Вступление

Рассмотрим схему визуальной криптографии, предложенную Мони Наору и Ади Шамиром [2, 3]. Основная идея схемы заключается в том, что для передачи секретного изображения генерируются две пластины, каждая по отдельности выглядящая как белый шум и не несущая никакой информации об секретном изображении. Чтобы раскодировать сообщение достаточно наложить две пластины друг на друга. Таким образом, процесс декодирования не требует никакого специального оборудования. Материал взят из статьи Generalized Visual Cryptography Scheme with Completely Random Shares. [1]

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

Термины

В процессе кодирования одна пластина называется базовой, которая генерируется независимо от секретного изображения, другая - кодировочной. Кодировочная пластина является функцией от секретного изображения и базовой пластины.

Каждый пиксель секретного изображения соответствует n x n пикселям, которые образуют плитку. Из плиток формируются базовая и кодировочная пластина. В нашем случае плитка будет размера 2 x 2. Мы будем называть плитку базовой пластины базовой плиткой, а плитку кодировочной пластины - кодировочной плиткой. Базовая пластина генерируется из плиток, выбранных случайным образом. Примеры плиток 2 x 2 со всевозможным сочетанием чёрных и белых пикселей вы можете видеть на рисунке 1.

Рисунок 1: Квадраты 2x2 со всевозможным сочетанием белых и чёрных пикселей

Классическая схема

Рассмотрим процесс генерации кодировочной пластины. Кодировочная плитка берётся равной базовой плитке, соответствующей тому же пикселю секретного изображения, если данный пиксель белый. Если пиксель чёрный, то кодировочная плитка является противоположной к соответствующей базовой плитке. Примеры наложения плиток вы можете видеть на рисунке 2.

Рисунок 2: Демонстрация наложения квадратов при декодировке

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

Мы будем демонстрировать наши исследования на примере изображения, показанного на рисунке 3.

Рисунок 3: Секретное изображения, которое будет закодировано через 2 пластины

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

Раскодированное изображение показано на рисунке 4a. Информация видна с контрастом наполовину меньше чем на оригинальной картинке.

Рисунок 4: (a) классический алгоритм (b) случайный (c) почти случайный

Никакая из пластин не содержит секретной информации, так как плитки выбираются случайным образом. Базовые пластины показаны на рисунке 5; кодировочные пластины имеют такой же вид.

Рисунок 5: (a) классический алгоритм (b) случайный (c) почти случайный

Легко проверить, что классические пластины не являются случайными в том смысле, что их пиксели не образуют случайную последовательность нулей и единиц. Это происходит, потому что соседние пиксели связаны между собой ограниченным выбором плиток. Так как плаcтины специфичны исходя из метода кодирования, то происходит утечка самого факта кодирования. Далее будет предложен способ это избежать.

Версия со случайными плитками

Наше предложение заключается в том, чтобы для генерации базовой пластины использовать любую плитку из 16 возможных (показаны на рисунке 1). Кодировочная пластина генерируется аналогично, как и в классической схеме. Базовая и кодировочная пластины теперь абсолютно случайны. Базовая пластина случайной версии кодирования показана на рисунке 5b. Также добавим, что как и в случае классического алгоритма, базовая и кодировочная пластины выглядят абсолютно одинаково.

Раскодированное изображение показано на рисунке 4b. В данном случае, появляются ошибки декодирования. Они включают в себя плитки, которые должны содердать белые пиксели, но в соответствующей базовой плитке их недостаточно. В классической схеме в плитке всегда два белых пикселя, поэтому мы возьмём классический вариант как точу отсчёта. Тогда, ошибки появляются, когда не хватает одного или два белых пикселя в базовой плитке. Самая жёсткая ошибка возникает, когда нет ни одного белого пикселя в базовой плитке, и белый пиксель секретного изображения будет раскодирован как чёрный квадрат 2 x 2, тогда как в классическом варианте это был наполовину белый квадрат 2 x 2. Будем называть это -2 ошибкой. Когда не хватает одного белого пикселя: -1. Такая ошибка не очень жёсткая. Также есть ошибки +, когда в базовой плитке три или четыре белых пикселя, то есть в раскодированнм изображении будут плитки с более чем двумя белыми плитками. Это +1 и +2 ошибки. Такие ошибки не очень важные, так как они не ухудшают видимость информации. В случае с чёрным пикселем никаких ошибок не возникает. Ошибки разного типа показаны в Секции Визуализация ошибок.

Версия с почти случайными плитками

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

1. Перечисленные плитки могут быть исключены из кодировочных пластин.

2. Перечисленные плитки будут использованы только для чёрных регионов секретного изображения.

Базовая пластина, созданная по возможности 1 показана на рисунке 5c. Она не содержит чёрных плиток, поэтому её внешний вид менее шероховатый, чем базовая пластина случайного алгоритма, показанная на рисунке 5b. Это делает раскодированное изображение, показанное на рисунке 4c, менее размытым, чем раскодированное с помощью случайного алгоритма, рисунок 4b. Будем называть этот процесс почти-случайное 1 кодирование. В самом деле, как будет показано в Секции Визуализация ошибок, количество ошибок кодирования меньше чем в случайной версии.

Однако оба предложенных принципа имеют серьёзные недостатки. Возможность 1 подразумевает утечку информации о факте кодирования (смотрите Секцию Случайность пластин). Легко проверить, что некоторые типы плиток не используются в пластинах (смотрите рисунок 7).

Возможность 2 должна быть немедленно исключена так как она подразумевает утечку информации в тёмных регионах секретного изображения, что недопустимо. Происходит визуальная утечка информации в кодировочной пластине, показанной на рисунке 6, где тень секретной информации может быть легко замечена. Это вызвано использованием чёрных плиток только в местах, где в секретом изображении чёрный пиксель и базовые плитки белые. Этот эффект может быть исключён, если мы не будем также использовать полностью белую плитку, что мы назовём почти-случайное 2 кодирование. В самом деле, при этом кодировании, кодировочная пластина не открывает секрет, и её внешний вид такой же как и у базовой пластины, показанной на рисунке 5d. Однако, как мы увидим в Секции Случайность пластин, в этом случае пластины также не обладают абсолютно случайными свойствами.

Рисунок 6: тень секретной информации видна

Случайность пластин

В классическом алгоритме плитки в базовой пластине выбираются случайно из плиток с ровно двумя белыми пикселями. Очевидно, что в результате этого отдельные пиксели не выбираются случайно, что можно чётко видеть, сравнив пластину классического алгоритма на рисунке 5a, и пластину случайного алгоритма на рисунке 5b, чьи пиксели выбираются случайно. Это наблюдение может быть подтверждено тестами на случайность, например, тест, основанный на числе нулей или единиц в непрерывной последовательности.

Результаты для кодировочной и базовой пластин в классическом, случайном и обоих случаях почти случайных алгоритмах шифрования показаны в таблице 1. Для проведения тестирования, ряды пикселей были составлены из последовательных рядов или столбцов. P-критерий немного разный для этих двух способов. Что наиболее хорошо видно в этой таблице, это то, что пластины только случайного алгоритма могут считаться по настоящему случайными. Только в этом случае факт кодирования скрыт, так же как и сама секретная информация. Это сделано ценой некоторой потери качества декодирования секретного изображения. Это может быть видно на декодированных изображениях на рисунке 4 и на визуализации ошибок на рисунке 8 в Секции Визуализация ошибок. Здесь видно, что эта потеря в допустимом диапазоне, при условии умеренной детализации секретного изображения.

Таблица 1: Результаты тестов на случайность для кодировочных и базовых пластин.

Также простой метрикой случайности является доля плиток в разных типах пластин. Доли плиток пластин для изображения на рисунке 7, сгенерированных при разных алгоритмах, показаны соответственно: классический на рисунке 7a, случайный на 7b, почти-случайный 1 на 7c, почти-случайный 2 на 7d.

Рисунок 7: распределение плиток в кодировании

По ним видно, например, что в почти-случайном 1 алгоритме, рисунок 7c, в базовой пластине доли плиток примерно равны 1/15 (не абсолютно точно, так как выборка плиток происходит случайно), кроме отсутствующей плитки номер 1. В кодировочной пластине плитка номер 1 (абсолютно чёрная) присутствует, так как в процессе кодирования некоторые плитки номер 16 (абсолютно белая) в базовой пластине заменяются на противоположные исходя из алгоритма кодирования.

Вариативность выборки плиток может быть выражена дисперсией долей плиток для каждой пластины для каждого кодирования. Это показано в таблице 2. Дисперсия самая низкая в случайном кодировании, что говорит о том, что в эта выборка наиболее случайна. В случайном и классическом кодировании значения дисперсии в двух пластинах близки друг другу. В почти-случайном 1 алгоритме дисперсии относительно малы, но различие значений дисперсий для базовой и кодировочной пластины больше чем в два раза.

Таблица 2: Дисперсия частоты появления плиток

Выборка плиток в базовой пластине может быть произвольной, в то время как кодировочная пластина является функцией от базовой пластины и секретного изображения. Уменьшение числа плиток может быть виден как постепенный, но поэтапный переход от 16 плиток в случайном кодировании до 6 плиток в классическом кодировании. Мы сделали первый шаг, убрав плитку номер 1 в базовой пластине. Этот шаг повлёк негативные результаты, как говорилось ранее. Он привёл к потере симметрии в долях плиток и, что хуже, к утечке информации о секретном изображении.

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

Визуализация ошибок

В модифицированной версии кодировочных алгоритмов ошибки декодирования возникают только в белых регионах секретного изображения. Ошибки изображены в таким образом, что те белые пиксели секретного изображения, которые были декодированы отлично от классического декодирования обозначены цветами. -2, -1 ошибки декодирования отображены красным и тёмно-жёлтым , а +1, +2 ошибки декодирования отображены бирюзовым и зелёным соответственно. Визуализация ошибок показана на рисунке 8. (a) - случайный алгоритм, (b) - почти случайный 1, (c) - почти случайный 2.

Рисунок 8: Визуализация ошибок декодирования

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

Развитие идеи

Идеи из данной статьи были развиты в следующих исследованиях.

• "Случайность пластин в сравнении с качеством декодирования в чёрно-белой визуальной криптографии." [4]
  
  Резюме: стандартная схема визуальной криптографии Наора-Шамира модифицирована таким образом, что позволяет производить выборку из всех возможных 16 плиток два на два для генерации пластин. Такая процедура делает пластины не только случайными на вид, но и случайными в статистическом смысле. Конечно, есть цена, которую придется заплатить в виде несколько ухудшившегося качества реконструированного секрета. В этой статье мы пытаемся найти разумный компромисс между случайностью пластин и качеством процесса декодирования.

• "Цветная визуальная криптография с полностью случайными кодировочными цветами." [5]
  
  Резюме: К цветным изображениям применяется концепция визуальной криптографии с двумя полностью случайными пластинами. В классическом кодировании пластины не коррелируют с секретным изображением, но не являются полностью случайными. Мы применяем полностью случайное кодирование, предложенное ранее для случая черно-белых изображений, к цветным изображениям. Это повышает безопасность процесса. Предлагаемый метод имеет свойства, аналогичные свойствам большинства чисто визуальных криптографических методов, включая снижение контрастности и потерю мелких деталей. В процессе декодирования никаких вычислений не требуется, поэтому декодирование может выполняться невооруженным человеческим глазом. Использование полностью случайного кодирования цветов вносит некоторый шум в результаты, но его уровень умеренный. Используется цветовая модель RGB и рассматривается схема криптографии (2, 2).

Практическое применение

• Визуальная криптография может быть использована для защиты биометрических данных, в которых расшифровка не требует каких-либо сложных вычислений. На эту тему существует исследование "Визуальная криптография для биометрической безопасности". [6]
  
  Резюме: Сохранение конфиденциальности цифровых биометрических данных (например, изображений лиц), хранящихся в центральной базе данных, приобрело первостепенное значение. В этой работе исследуется возможность использования визуальной криптографии для придания конфиденциальности биометрическим данным, таким как изображения отпечатков пальцев, коды радужной оболочки глаза и изображения лиц. В случае лиц частное изображение лица разделяется на два основных изображения лица (известные как листы), которые хранятся на двух отдельных серверах баз данных, так что частное изображение может быть раскрыто только тогда, когда оба листа доступны одновременно; в то же время отдельные изображения листов не раскрывают идентичность частного изображения.

• Также интересным является применение визуальной криптографии для детектирования фишинг-аттак (получение доступа к конфиденциальной информации пользователей - логинам и паролям). На это тему есть исследование "Детектирование фишинг-аттак используя визуальную криптографию в ad-hoc сети". [7]
  
  Резюме: Мобильные специализированные сети (MANET) обеспечивают широкий спектр приложений, таких как помощь при бедствиях, военные приложения, беспроводные сенсорные сети (WSN), образование, увлечение, здравоохранение, коммерческая и гражданская среда. Одно из его важных приложений - это коммерческая и гражданская среда, охватывающая электронную торговлю, автомобильные услуги и сети посетителей в аэропортах. В настоящее время количество фишинговых атак на веб-сайты электронной коммерции растет. В этой статье представлен новый подход к борьбе с фишингом, основанный на визуальной криптографии. Согласно этому подходу пользователь генерирует две доли изображения, используя схему визуальной криптографии (2, 2). Клиент сохраняет первую долю этого изображения, а вторая доля загружается на веб-сайт во время регистрации пользователя. После этого веб-сайт запрашивает другую информацию, например, вторую часть изображения, имя пользователя и пароль. Эти учетные данные конкретного пользователя могут изменяться один раз за один вход. На каждом этапе входа в систему пользователь проверяет легитимность веб-сайта, получая секретную информацию с помощью объединения обоих общих ресурсов. Существует множество подходов, основанных на криптографической технике, но все они страдают от ложного срабатывания уведомления. Однако предлагаемый подход не страдает от ложных срабатываний (FP) уведомления и превосходит все существующие подходы.

Выводы

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

Ссылки

1. Оригинальная статья: Orowski A., and Chmielewski L. J. "Generalized Visual Cryptography Scheme with Completely Random Shares"

2. M. Naor and A. Shamir. 1995. Visual Cryptography

3. M. Naor and A. Shamir. 1997. Visual Cryptography II

4. Orowski A., and Chmielewski L. J. Randomness of Shares Versus Quality of Secret Reconstruction in Black-and-White Visual Cryptography

5. Orowski A., and Chmielewski L. J. Color Visual Cryptography with Completely Randomly Coded Colors

6. Arun Ross, Asem A Othman Visual Cryptography for Biometric Privacy

7. Vimal Kumar, Rakesh Kumar Detection of phishing attack using visual cryptography in ad hoc network