Нордавинд
Компания
41,92
рейтинг
19 апреля 2013 в 22:28

Разработка → Схема разделения секретной визуальной информации

Доброго времени суток, Хабрапользователи!

Визуальная криптография [1] впервые была введена Мони Наором и Ади Шамиром в 1994 году [3]. Она используется для шифрования изображения или текста, представленного в виде изображения. Основная идея модели визуальной криптографии состоит в разбиении исходного изображения на несколько шифрованных («теневых» изображений, shadow images), каждое из которых не дает никакой информации об исходном изображении кроме, может быть, его размера (изображение – а-ля «белый шум»). При наложении шифрованных изображений друг на друга, можно получить исходное изображение. Таким образом, для декодирования не требуется специальных знаний, высокопроизводительных вычислений и даже компьютера (в случае, если распечатать теневые изображения на прозрачных пленках). В случае использования этого алгоритма в компьютерных системах, наложить все части изображения друг на друга можно используя логические операции AND, OR, XOR (или установив более высокую степень прозрачности в графическом редакторе). Данная технология обладает криптоустойчивостью за счет того, что при разделении исходного изображения на множество шифроизображений происходит случайным образом.


Рисунок 1. Возможные состояния пикселя при (2, 2)-визуальной схеме секретного обмена

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

Алгоритм визуальной криптографии

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

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

Рассмотрим (2, 2)-визуальную схему секретного обмена, т.е. исходное изображение разбивается на два теневых изображения, каждое из которых представляет собой изображение белого шума, но при наложении дают исходное изображении. Каждый пиксель исходного изображения будем разбивать на четыре части, таким образом, если размер исходного изображения был M×N, то размеры теневых изображений будут 2M×2N.

На рисунке 1 показано, что пиксель, разделенный на четыре части, может иметь шесть разных состояний.

Если пиксель на первом слое имеет одно положение, пиксель на втором слое в свою очередь может иметь два положения: идентичное либо инвертированное пикселю первого слоя. Если пиксель части 2 идентичен пикселю части 1, то пиксель, полученный в результате наложения обоих теневых изображений, будет наполовину белый и наполовину черный. Такой пиксель называют серым или пустым. Если пиксели части 1 и части 2 противоположны, то пиксель, полученный в результате наложения, будет полностью черным. Он будет являться информационным.

Опишем процесс получения теневых изображений для исходного изображения для схемы (2, 2): для каждого пикселя исходного изображения, для первого теневого изображения случайным образом выбирается одно из шести возможных состояний пикселя, приведенных на рисунке 1. Состояние пикселя второго теневого изображения выбирается идентичным или симметричным состоянию пикселя первой «тени» в зависимости от того, белый или черный это был пиксель в исходном изображении соответственно. Схожим образом можно построить любую (k, n) визуальную схему секретного обмена [3].

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

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

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

Matlab-функция, выполняющая разделения исходного двоичного изображения на два теневых «в лоб», использующая 4 (из 6 возможных, см. рис. 6) состояния пикселя будет иметь следующий вид:
function [S1,S2] =getShdwImg(Img)
% получение теневых изображений S1 и S2 из исходного бинарного изображения (Img)
% 
% получаем размер исходного изображения
[m,n] = size(Img);
% запасаемся памятью для каждого теневого изображения :)
S1= zeros(2*m,2*n);
S2= zeros(2*m,2*n);
% для каждого пикселя исходного изображения - действуем согласно Рис. 1
% Примечание:
for i=1:m-1
    for j=1:n-1
        r = randi(4);
        if(Img(i,j)==1)
            switch r
            case 1,
                S1(2*i,2*j)=1;
                S1(2*i+1,2*j)=1;
                S1(2*i,2*j+1)=0;
                S1(2*i+1,2*j+1)=0;
                
                S2(2*i,2*j)=1;
                S2(2*i+1,2*j)=1;
                S2(2*i,2*j+1)=0;
                S2(2*i+1,2*j+1)=0;
            case 2,
                S1(2*i,2*j)=0;
                S1(2*i+1,2*j)=0;
                S1(2*i,2*j+1)=1;
                S1(2*i+1,2*j+1)=1;
                
                S2(2*i,2*j)=0;
                S2(2*i+1,2*j)=0;
                S2(2*i,2*j+1)=1;
                S2(2*i+1,2*j+1)=1;
            case 3,
                S1(2*i,2*j)=0;
                S1(2*i+1,2*j)=1;
                S1(2*i,2*j+1)=1;
                S1(2*i+1,2*j+1)=0;
                
                S2(2*i,2*j)=0;
                S2(2*i+1,2*j)=1;
                S2(2*i,2*j+1)=1;
                S2(2*i+1,2*j+1)=0;
            case 4,
                S1(2*i,2*j)=1;
                S1(2*i+1,2*j)=0;
                S1(2*i,2*j+1)=0;
                S1(2*i+1,2*j+1)=1;
                
                S2(2*i,2*j)=1;
                S2(2*i+1,2*j)=0;
                S2(2*i,2*j+1)=0;
                S2(2*i+1,2*j+1)=1;
            end
            
        else
            switch r
            case 1,
                S1(2*i,2*j)=1;
                S1(2*i+1,2*j)=1;
                S1(2*i,2*j+1)=0;
                S1(2*i+1,2*j+1)=0;
 
                S2(2*i,2*j)=0;
                S2(2*i+1,2*j)=0;
                S2(2*i,2*j+1)=1;
                S2(2*i+1,2*j+1)=1;
            case 2,
                S1(2*i,2*j)=0;
                S1(2*i+1,2*j)=0;
                S1(2*i,2*j+1)=1;
                S1(2*i+1,2*j+1)=1;
 
                S2(2*i,2*j)=1;
                S2(2*i+1,2*j)=1;
                S2(2*i,2*j+1)=0;
                S2(2*i+1,2*j+1)=0;
            case 3,
                S1(2*i,2*j)=0;
                S1(2*i+1,2*j)=1;
                S1(2*i,2*j+1)=1;
                S1(2*i+1,2*j+1)=0;
 
                S2(2*i,2*j)=1;
                S2(2*i+1,2*j)=0;
                S2(2*i,2*j+1)=0;
                S2(2*i+1,2*j+1)=1;
            case 4,
                S1(2*i,2*j)=1;
                S1(2*i+1,2*j)=0;
                S1(2*i,2*j+1)=0;
                S1(2*i+1,2*j+1)=1;
 
                S2(2*i,2*j)=0;
                S2(2*i+1,2*j)=1;
                S2(2*i,2*j+1)=1;
                S2(2*i+1,2*j+1)=0;
            end
        end
    end
end

Функция getShdwImg разбивает исходное изображение так, как показано на Рис. 1, с единственной разницей только в том, что в двоичных изображениях Matlab — черные пиксели изображения равну нулю, а белые, соответственно, равны единице.
Ниже приведен код Matlab-скрипта, демонстрирующий работу алгоритма разделения секретной визуальной информации.

close all
% считываем исходное RGB-изображение и преобразуем его в бинарное
biImg = imread('nordavind_logo.jpg'); 
biImg = rgb2gray(biImg);
level = graythresh(biImg);      % пороговая фильтрация по Отсу (Otsu)
biImg = im2bw(biImg,level);
% выводим результат на экран
figure(1)
imshow(biImg);
title(['Original binary image']);
% получаем два теневых изображения
[S1,S2] =getShdwImg(biImg);
% выводим их на экран
figure(2)
imshow(S1);
title(['Shadow image S1']);
% 
figure(3)
imshow(S2);
title(['Shadow image S2']);
% выводим на экран результат их наложения друг на друга 
% различными способами
figure(4)
% imshow(or(S1, S2));
% imshow(and(S1,S2));
imshow(~xor(S1, S2));      % операция “~”(NOT) используется, чтобы получить черный текст на белом фоне, а не наоборот
title(['Superimposed image']);

Результаты

Ниже приведены результаты выполнение операции кодирования и декодирования исходного «секретного» изображения. Рассматриваются различные операции совмещения полученных из исходного теневых изображений: с помощью XOR (Рис. 6), AND (Рис. 7) и OR (Рис. 8).


Рисунок 2. Исходное изображение


Рисунок 3. После преобразования изображения в ч/б


Рисунок 4. Теневое изображение 1


Рисунок 5. Теневое изображение 2


Рисунок 6. Результат для NOT(XOR(S1, S2))


Рисунок 7. Результат для AND(S1, S2)


Рисунок 8. Результат для OR(S1, S2)

Заключение

(k, n)-визуальная схема разделения секретной информации является криптостойкой до тех пор, пока k частей изображения не попадут в руки злоумышленника. Если же перехвачено менее k частей, то расшифровка исходного изображения – невозможна.
Если в процессе использования данной системы полностью соблюдается случайный подход к разбитию пикселей на блоки, то визуальная криптография предлагает абсолютную надежность и секретность.
Здесь был рассмотрен классический алгоритм визуальной криптографии. На сегодняшний день существует множество улучшенных моделей этого алгоритма, например, для кодирования цветных изображений [4, 6], или схемы, где, вместо теневых изображений в виде белого шума, используются семантически значимые изображения [5], а также схемы визуальной криптографии на основе техник стеганографии [2, 7].

Ссылки

1. en.wikipedia.org/wiki/Visual_cryptography
2. ru.wikipedia.org/wiki/%D0%A1%D1%82%D0%B5%D0%B3%D0%B0%D0%BD%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F
3. M. Naor and A. Shamir. Visual cryptography. In EUROCRYPT’94. — Springer-Verlag Berlin, 1995.
4. D. Jin, W.Q. Yan, and M.S. Kankanhalli. Progressive color visual cryptography. In Journal Of Electronic Imaging, 2005.— Vol. 14, Issue 3.
5. Feng Liu and ChuanKun Wu. Embedded extended visual cryptography schemes. — China, 2006.
6. Y.C. Hou. Visual cryptography for color images. In Pattern Recognition, 2003.
7. Ritesh Murherjee, Nabin Ghoshal. Steganography based visual cryptography. – Berlin: Springer-Verlag, 2013.
Автор: @Nordavind
Нордавинд
рейтинг 41,92
Компания прекратила активность на сайте

Комментарии (26)

  • +5
    Сказать по правде, с криптографией сталкивался давно и мало что помню, но всё же возникли вопросы. В частности, при чём тут изображения? В чём отличие от XOR шифруемой последовательности бит со случайной последовательностью? Зачем увеличивать разрешение в 2 раза?
    • +2
      Насколько я понял, в данном случае мы имеем несколько частей секрета. И чтобы востановить данные, нам необходимо получить либо все части секрета, либо часть из них. В то время, как в обычных схемах шифрования используется один единственный ключ и его знание приводит к полному раскрытию шифра.
      Можно использовать, например, в случае когда имеется группа из 5 человек, посвященных в некую секретную информацию, запечатленную на изображении. И для разглашения этой секретной информации необходимо получить большинство, т.е. 3 голоса. Создается (3,5)-визуальная схема и каждая из пяти частей раздается участникам. Теперь можно с большой вероятностью быть уверенным, что если секрет будет раскрыт, это означает что трое из пяти договорились о раскрытии.
      • 0
        Но ведь можно зашифровать зашифрованные данные другим ключом, чтобы расшифровка происходила в несколько этапов с разными ключами.
        • +1
          Так в том то и дело, что если мы зашифруем сообщение пятью ключами, то для восстановления сообщения понадобится пять ключей. А данная схема разделения секрета гораздо более гибкая. Можно разделить секрет на пять человек, но восстановить его смогут скажем только трое из пяти. Или при небольшом изменении алгоритма четверо. И так далее.
        • 0
          в этом случае расшифровка будет происходить последовательно и схема 3 из 5 принципиально не возможна.
      • 0
        Прям эпизод из фильма Джонни Мнемоник :)
      • +2
        Вообще есть алгоритм Шамира, который не требует создания картинок и позволяет разделять секрет на любые доли для любого числа участников.

        • +2
          Ссылка почему-то битая (с лишней закрывающей кавычкой).
          Вот верная.

          Спасибо.
        • 0
          Вообще есть много алгоритмов разделения секрета раз уж пошла такая пьянка. И описывается всего лишь один из них, очень интересный как по мне.
    • 0
      Как я понял, специальные алгоритмы требуются в виду того, что если при попытке взлома мы случайную последовательность подобрали лишь частично, то все равно сможем визуально идентифицировать информацию, небольшие искажения этому не помешают. Ну и с некоторыми модификациями становится возможным скрыть сам факт передачи конфиденциальных изображений. Скажем, присылаю вам две фотки и вы их в фотошопе друг на друга накладываете и «магически» из двух безобидных получается одна «обидная».
  • 0
    При ресэмплинге изображений, уменьшении размера, повороте — полное фиаско, как я понимаю?
    • +2
      Звучит, как «фи» алгоритму, но я бы назвал это просто естественным ограничением на область его применения. Те же самые ограничения на применение стеганографии. Понимание этих ограничений позволяет бороться с применением этих алгоритмов, имхо.
      • +1
        Спасибо, просто уточнял. Разрабатываю аналогичную тему, устойчивую к трансформациям.
        • +1
          Ждем пост по результатам Ваших исследований.
    • 0
      Кстати, не факт, по-моему. Волне может быть, что картинка размоется, исказится, может инвертируется, но останется узнаваемой.
  • 0
    А если добавить ещё пару «мусорных» изображений, не участвующих в дешифровке — вообще замечательно должно получиться.
    • 0
      Если не секрет, куда предлагается их добавить?
      • +1
        Я к этому отношения не имею, но что-то мне подсказывает, что если на флешке (как частный пример) из хранимых 30 файлов только 5 будут участвовать в декодировании — доступ к информации будет существенно затруднён для человека, не имеющего представления о том, какие именно и в каком количестве изображения требуются.
        • 0
          Согласен, как вариант! Но нужно понимать, что к этим 5-ти еще желательно, чтобы у получателя флешки был хотя бы еще один, участвующий в декодировании:)
          • 0
            … присланный отличным от флешки способом. Можно ещё много всего добавить, всё зависит от высотв чувств, вызываемых праноей.
            • 0
              Почему сразу паранойей?:) Я бы сказал: зависит от ценности информации и модели угроз.
              • 0
                Я, в свою очередь, не говорил что параноя — это плохо. Профессиональная деформация скорее.
          • 0
            Зависит от постановки задачи. Даже если алгоритм (5,5), то 5 единственных из 30 дает порядка 10³⁰ вариантов, если я совсем комбинаторику не забыл. Главное, чтобы принцип выбора нужных был не очевидным.
  • +3
    По сути тот же одноразовый блокнот.
    • +1
      Зато звучит-то как: визуальная криптография.
  • +2
    Все верно, просто в несколько более красивом и завуалированном исполнении.
    На самом деле, большинство книжек по криптографии начинаются описания криптографического алгоритма со 100% стойкостью: есть буфер размером N и ключ размером N. Накладываем ключ на блок каким-нибудь XOR-ом и получаем «зашифрованный» блок, который принципиально не может быть подвергнут криптоанализу. Здесь ровно тот же случай:)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.

Самое читаемое Разработка