Какие есть алгоритмы шифрования изображений, устойчивые к трансформации?

#фурье #fft #изображения #wavelet #шифрование

Какие есть алгоритмы шифрования изображений, устойчивые к изменению размера изображения,
поворотам на углы, кратные 90 градусам?
Т.е. зашифровал исходное изображение - оно на себя не похоже, набор узоров, загрузил
на фотохостинг, где его в т.ч. уменьшили. Взял уменьшенный вариант, и тем же ключом
расшифровал в уменьшенную копию исходной картинки. Есть такие решения?
В идеале — вообще зашифровали - распечатали - сфотографировали на мобильник распечатку
- дешифровали в исходное, пусть такого же уменьшенного разрешения и плюс искажения
перспективы. Т.е. решение, не привязанное жестко к пикселам, и к точным значениям цветов/яркостей.
Upd. как шаг к анонимности интернетов в эпоху тотального контроля государств и корпораций,
имеет смысл добиваться такого вида зашифрованного изображения, что автоматическими
методами сложно провести его связь с исходником. Т.е. например, гистограмма зашифрованного
никак не должна кореллировать с гистограммой исходника. Например, если порезать картинку
на блоки и переставить их местами, гистограмма никак не изменится. Если канал инвертнуть,
гистограмма его просто отзеркалится. Поэтому, повторю, интересно услышать тех, кто
работал с FFT (быстрое преобразование Фурье) и вейвлетами.    

Ответы

Ответ 1

UPD [2013-02-07] Новый алгоритм «Chan»
Не оставляет меня в покое эта тема. Написал новый алгоритм шифрования.
Алгоритм работает очень долго, посему просьба не тестировать на больших картинках
и набраться терпения: кнопки «Encrypt» и «Decrypt» понимают с первого раза, не стреляйте
в них очередью.
Примеры:

Оригинал
Зашифрованное изображение
Расшифрованное изображение
Расшифрованное с неверным паролем

Основан на преобразовании цветов пикселей, но работает весьма неплохо, на мой взгляд. 
Недостатки:

шифрование слишком слабое; перебо́ров за 10–20 можно подобрать такой пароль, который
даст представление о содержании изображения (хотя цвета могут быть искажены)
JPEG-компрессия сказывается на расшифрованном изображении (появляется рябь), поэтому
на тестовой странице я выдаю результат в PNG
очень много коллизий ключей
очень медленно, необходимо оптимизировать

Положительные черты:

устойчивость к любым трансформациям (кроме цвета), будь то поворот/разворот или даже
посторонние данные, например:
Исходное: зашифрованная ранее картинка находится на нормальной (к примеру, фото плаката
с изображением зашифрованной фотографии)
Расшифрованное: зашифрованная картинка «распаковалась»

Есть идея добавить свойство (bool) loseless, в зависимости от которого алгоритм и,
соответственно, результат, будет меняться:

при loseless = on – будет работать как сейчас;
при loseless = off –  шифрование будет значительно надежнее, но с потерей двух цветов:
0xFFFFFF станет 0xFFFFFE, а 0x000000 – 0x000001 (то есть, и в зашифрованном и в дешифрованном
абс. белый и абс. черный будут отсутствовать).

Или можно не заморачиваться и прописать loseless = off как единственный вариант.
@sergiks, а у тебя как дела с этой задачей?
-----------------------------------------------------------------------------------------
UPD [2013-01-30] Новая версия алгоритма «мозаика»

Доделал вот прототип: http://image.lotoflot.com/mosaic_crypt.php
Выдерживает повороты кратные 90 град., но с изменением размера беда: очень сильные
искажения после дешифровки.
Удачный пример

Оригинал
Зашифрованное изображение
Расшифрованное изображение

Лавина хорошая благодаря md5. Ключ внутри функции раскладывается на составляющие,
каждый из которых хешируется. Для нормальной работы нужен массивный набор данных (а
не 2-3 символа), поэтому решил не изобретать и подключить md5.
Параметр Pieces определяет, на сколько кусков в обоих направлениях (X, Y) будет порезана
картинка. Чем больше значение, тем больше блоков. Обычно лучше устанавливать значение
в диапазоне 10—30 для картинок размера 300—2000 px.
Я как-то давно на PHP начал писать класс-прослойку для GD. Так вот эти функции шифровки/дешифровки
я запихнул в класс расширения этой прослойки, так что код будет слегка запутанным.
Но если все же заинтересует, могу поделиться.


Ответ 2

Конкретных алгоритмов не скажу, но наверняка они есть. Наверное надо копать в сторону
именно графической шифровки, к примеру поставить точки которые организуют квадрат чтобы
уйти от зависимости от ориентации картинки, и внутри этого генерировать данные которые
представляют исходную картинку. самое тупое - например точка 2x2 или 3x3 - 1, нет такой
точки - 0. Можно наверное более сложно придумать - яркая точка начала, от неё рисовать
примитивы - линия под углом - определённый набор битов (например угол задаётся исходным
куском битов, цвет каждой следующей линии - следующая пачка данных) ну и т.д. Ваша
задача - графически представить нужные вам данные - как - простор для фантазии. 
Так же можно использовать тупо набор известных вам однозначно обратимых фильтрах
(сдвиги, повороты и т.д.) которые Вы применяете в определённом порядке, а для расшифровки
- в обратном (например картинку сдвигает на 10 пикселов, поворачиваете на 15 градусов,
сдвигаете на 3 пиксела вниз, инвертируете цвета, сдвигаете цвета на 20, меняете каналы
местами и т.д.).


Ответ 3

Я бы посоветовал копать в сторону стеганографических трюков с изображениями, когда
модифицируется наименее значимый бит (LSB) пикселя или что-то подобное. Обзор некоторых
из таких методов здесь
Наиболее перспективный для вас метод на мой взгляд это redundant pattern encoding,
то есть когда шифровка размещается не по всему изображению, а дублируется в нескольких
частях (pattern), так что при обрезке изображения останутся кодированные куски из которых
можно будет восстановить сообщение.
Теперь рассмотрим способ восстановления исходного шифросообщения после изменения
размера изображения (паттерна). Здесь может помочь один из алгоритмов избыточного кодирования,
например метод Хамминга или что-то подобное. Благо таких способов довольно много, надо
просто задаться процентом сколько бит надо уметь восстанавливать из потерянных - это
чуть ли не целая отрасль математики.


Ответ 4

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