Кодирование JEPG. Предсказать алгоритм Хаффмана.

[Pirotexnik]

Доброго времени суток!

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

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

Суть такова:

Сообщение от копипаста с хакепа

У нас есть текст «00112233011223322113». Как видишь, символы 4,5,6,7,8,9 не используются. Можно ввести следующее обозначение:

00 - 0

11 - 1

22 - 2

33 - 3

01 - 4

12 - 5

23 - 6

32 - 7

21 - 8

13 - 9

Таким образом наш текст можно записать в виде: «0123456789». После подобного преобразования текст стал занимать в два раза меньше объема. Все допустимые символы присутствуют в тексте. Чтобы получить исходный текст, необходимо, согласно обозначению, вновь заменить символы на их комбинацию.

Собсно что я хочу - ручками заменить 0 на <, 1 на ?, 2 на e и тд.

Как? Насколько я понял, я могу править "дерево". Тоесть подобрав нужную частоту, и создав свое дерево, я смогу добится результата.

Все, вроде, просто, но сжатие JEPG имеет "немного" более сложную реализацию, которую я не смог осилить. Там сначала идет сжатие самого изображение со 100% (исходная картинка), до 90% (картинка ПЕРЕД прогоном по хаффману), а после уже уплотнение.

Так вот, любой EXIF заменяется следующим:

CREATOR: gd-jpeg v1.0 (using IJG JPEG v62), quality = 90

Вопрос к вам - что за зверь такой, как он устроен. Есть ли хоть 1% вероятность успеха?

Спасибо.

[s-andriano]

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

PS. То, что Вы описали, не является алгоритмом Хаффмана.

[Pirotexnik]

Вы не поняли.

Нужно не найти строчку. Нужно задать такие входные данные для алгоритма, которы ПОСЛЕ обработки алгоритмом будут содержать нужную мне строку.

p.s. любые JEPG изображения кодируются по Хаффману.

к примеру:
До кодирования --------- после кодирования

asm38sfd93mf93 --------- naskd831w2dj0120d
(Неизвестно) --------- My_string

[s-andriano]

Я правильно понял, что Вам нужно.
Но не понял, чем Вы располагаете.
Если алгоритм для Вас "черный ящик", то только перебор длительностью намного больше, чем можно себе позволить. Т.е. задача практически неразрешимая.
Хаффман - далеко не единственное преобразование, используемое при JPEG сжатии. И то, что Вы описали - не Хаффман.

[Pirotexnik]

Не совсем черный

CREATOR: gd-jpeg v1.0 (using IJG JPEG v62), quality = 90

Я надеялся на эту строку.

[JTG]

Наверное, можно. Длина текстовой строки будет ограничена 64 символами + понадобится подогнать коэффициенты таблицы квантования и включить их в JPEG. Стандарт такие фокусы позволяет, но любой нормальный кодировщик заменит таблицу квантования своей.


UPD: ну можно ещё "в лоб"

1. Взять картинку (лучше однотонную серую)
2. Изменить 1 байт
3. Пережать определённым кодером с указанным качеством
4. Проверить, изменился ли байт после сжатия. Если изменился - вписать значение ещё раз, и перейти к п.3. Если не изменился - сдвинуть позицию на 1, записать новый байт, перейти к п.3

В итоге удалось втиснуть сторку размером 52 байта, которая сохраняется в файле при пережатии gd-jpeg'ом с качеством 90, отключённой оптимизацией и прогрессией.

000002A0 DA 00 0C 03 01 00 02 11 03 11 00 3F 00 E2 65 92 Ú..........?.âe’
000002B0 48 45 4C 4C 4F 20 57 4F 52 4C 44 20 59 4F 55 52 HELLO WORLD YOUR
000002C0 20 54 45 58 54 20 47 4F 45 53 20 48 45 52 45 20 TEXT GOES HERE
000002D0 42 4C 41 48 20 42 4C 41 48 20 42 4C 41 48 20 41 BLAH BLAH BLAH A
000002E0 4E 44 20 52 45 E4 F7 8A 9A 8A 92 9C A4 6E 4F D2 ND REä÷ŠšŠ’œ¤nOÒ

[Pirotexnik]

Хм... Попробовал заменить лобой байт на свой, загрузил, структура сильно изменилась, повторил с той же позицеей - в результате картинка перестала загружатся(

Sorry... That photo could not be added to your profile.
Photos must be in .jpg format.

[Pirotexnik]

Получается записать не большие значения, но на некоторых символах картинка просто отказывается грузится(

[JTG]

Хз, у меня получилось при помощи XnView (там используется gd-jpeg)

[Pirotexnik]

Ну вот к примеру:
Оригинал

↕ŢǦʎŁJP…
П*Ѓ
—Рбc]A2cP
фǔ§T/0P…
ПPǦ
—Рбc]A2c

Измененная версия №1:

MY_STRINGП*Ѓ
—Рбc]A2cP
фǔ§T/0P…
ПPǦ
—Рбc]A2c

Это работает великолепно.

Дальше меняю следующий байт

MY_STRING2*Ѓ
—Рбc]A2cP
фǔ§T/0P…
ПPǦ
—Рбc]A2c

и изображение полностью искажается, и либо перестает быть картинкой, либо после прогона по алгоритму меняется ПОЛНОСТЬЮ заменяя "ME_STRING" другими байтами.

Есть идеи?