python

Стеганография в акроконструкциях. Алгоритм DANTSOVA

  • суббота, 2 апреля 2016 г. в 03:14:27
https://habrahabr.ru/post/280646/
  • Ненормальное программирование
  • Машинное обучение
  • Криптография
  • Информационная безопасность
  • Python


— Потом решила избавиться. Во!
— Ей!.. так хорошо?
— А, без разницы...

Давно хотел опубликовать этот just4fun проектик по стеганографии, но что-то не было времени.
И вот и время и повод нашелся.
К тому же пятница!



Решил я как-то раз реализовать стеганографию в акроконструкциях.
Для наглядности сделать, как в акростихах, только автоматизировать процесс и строить акропредложения автоматически. Короче говоря, повторить задумку Тритемия, только программным способом ;)

Интерфейс итоговой программы прост:
  1. пользователь вводит сообщение на русском языке;
  2. программа выдает акротекст. (Это текст, по первым буквам каждого слова которого можно собрать исходное сообщение).


Например на запрос "привет хабр!" программа написала текст: "потом решила избавиться во ей так хорошо а без разницы". Знаки препинания программа пока не расставляет — это делает пользователь на свое усмотрение.

Конечно далеко до naitive русского языка, но для just4fun проекта, написанного на коленке за пару вечеров, я думаю сгодиться…

Алгоритм обучается на бесчисленных романах Дарьи Донцовой. Именно поэтому он в честь нее и назван — DANTSOVA.

Кому интересно, как все это работает, прошу под кат!



Акростихи и акроконструкции



Акростих — это стихотворение, в котором первые буквы каждой строки составляют осмысленный текст (слово, словосочетание или предложение).

Например знаменитый акмеист Николай Гумилев однажды написал своей жене (Анне Ахматовой) такое стихотворене:
Аддис-Абеба, город роз.
На берегу ручьёв прозрачных,
Небесный див тебя принес,
Алмазной, средь ущелий мрачных.

Армидин сад… Там пилигрим
Хранит обет любви неясной
(Мы все склоняемся пред ним),
А розы душны, розы красны.

Там смотрит в душу чей-то взор,
Отравы полный и обманов,
В садах высоких сикомор,
Аллеях сумрачных платанов.

Акростих — самый простой вариант акроконструкции.
Акроконструкция — это более общее понятие; если в акростихе вкрапление происходит в первых буквах каждой строки, то в акроконструкции — в любом произвольном месте.

К примеру, можете ли вы своей девушке на 8 марта написать что-нибудь типа этого?:


Чё слабо? То-то!

Поэзия оставила нам множество аналогичных примеров. Кому эта тема интересна, то советою почитать статьи Ивана Чудасова
"От акростиха к акроконструкции" и "От акростиха к акроконструкции (продолжение)". На мой взгляд это лучшие статьи по данной теме: с одной стороны доступные широкой публике, с другой стороны — не вульгарные.

Возникает вопрос, как такие тексты создавать?

По сути есть три класса способов.
  1. Создавать текст самостоятельно. Именно это и делали поэты по науськиванию Иоганна Гайденберга Тритемия.
  2. Создавать текст программным способом. Например алгоритм DANTSOVA
  3. Комбинировать программный способ и творчество оператора. На мой взгляд это самое интересное, что можно придумать. Программа создает определенное количество вариантов различных слов, затем человек выбирает наиболее семантически подходящее злово из списка, затем программа создает еще одно слово… И так далее, пока не получиться единый цельный текст


Принципы алгоритма DANTSOVA



Кому лень читать мат.часть может сразу перейти к главе «Исходники & примеры».
Для остальных рассказываю.

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

Мне было интересно, есть ли какие-нибудь крайне простые идеи, которые можно было бы воплотить в простой и незамысловатой программе. Цель алгоритма DANTSOVA показать, что задача искусственного построения акротекстов — не является невозможной задачей.

Алгоритм DANTSOVA основан на нескольких весьма понятных идеях.
Разумеется добавляя большее количество правил в генерации текста можно получить более хороший результат,
однако в DANTSOVA мы ограничемся только четырьмя положениями — «мыслями».

Мысль 1. Слово зависит от прошлого слова.



После слова "вкусное" увидеть слово "молоко" вполне ожидаемо.
А вот после слова "вкусное" вы вряд ли увидете слово "синхофазатрон".
Во первых, синхофазатроны не кушают; во-вторых слова не согласованы: «синхофазатрон» мужского рода, а слово "вкусное" — среднего.

Разумеется слово зависит не только от предыдущего, но и от предпредыдущего и т.д.
Однако учитывать это я не стал по причине проклятия размерности.

Таким образом нужно взять много-много текста и посмотреть пары: «слово — следующее слово».
После необходимо создать конструкцию вида:
слово следующее слово вес
слово следующее слово вес
... ... ...


вес задается просто — сколько раз после "слова" было "следующее слово"?
Например Дарья Донцова (см. файл dantsova.d0.plf в исходниках)
за свою богатую карьеру после слова "вооруженный" употребила слово "букетом" целых три раза!
А после слова "прельстить" слово "секстеррориста" встречается только один раз.

Данную табличку будем называть платформой.

Очевидно, что на разных корпусах текста строяться различные платформы.

Мысль 2. Платформу нужно строить на корпусе текстов одного автора



Суть этой мысли в том, что текст должен быть «однотипным».
Нам не подходит корпус, состоящий из статьей о Валерие Харламове, о Фолклендской войне и о творчестве Ричарда Баха…
Это совершенно разнотипные тексты.

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

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

Мысль 3. Чем больше корпус, тем лучше



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

Например Пётр Ершов не подходит, так как он написал только одну сказку: Конёк Горбунок.
Сказ про Федота Стрельца Леонида Филатова — тоже не вариант.

Мысль 4. Чем примитивнее качество текста — тем лучше



Чем автор богаче и интереснее — тем разнообразнее его речь.
Нам такие авторы не нужны.
Например Иосиф Александрович Бродский написал больше стихотворений, чем Пушкин.
Но платформа на корпусе стихов Бродского получается не очень…

Итог.



Итак, нам нужен автор с примитивненькой речью, написавший много-много осмысленного текста одной тематики.
Что самое примитивное по речи? Правильно: детективные романы для девушек от пятидесяти и передача «Пусть орут» с Андреем Малаховым. Так как субтитры «Пусть орут» я не нашел, то ограничился детективными романами.

Так что методом исключения этим плодовитым автором оказалась Дарья Донцова (кстати, её настоящее имя — Агрипина Аркадьевна)!

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

Занудный нюанс
В алгоритме есть параметр с.
Это настраиваемый параметр системы.
Он показывает желаемое количество слов в предложении.

Алгоритм ставит точку после слова A и следующую букву X записывает в независимости от A в двух случаях:
  1. когда нет слова B, начинающегося на X c большим весом.
  2. когда длина предложения больше c



Занудный нюанс №2
Бывает случай, когда после слов A1 и A2 нельзя подобрать слова A3… Его просто нет.
В этом случае, мы либо обрываем предложение (параметр c), либо возращаемся на шаг назад,
заменяем A2 на некое A2*, вес которого на втором месте, и после A2* ищем A3.


Исходники & примеры



Несколько примеров.
Понятно, что это далеко до практического применения, но уже совсем не рандом!..
Определенная семантика проскальзывает…
Алгоритм DANTSOVA в действии
сообщение акроконструкция
славься отечество наше свободное братских народов союз вековой сейчас лучше а в сторону я очень трудно ее через его с тобой в общем не ахти.
шофер елены сергеевны в общем без особых денег на одном ее было рот а ты с кем из холодильника не.
абсолютно разные органы дело обстояло в сторону от юры записан в ее к окну взяла одну.
йогурт
научный руководитель не ахти.
уже через неделю.
ыыы.
йогурт российского уголовного кодекса.
она в общем да и тут еще лучше.
эйяфьядлайоукюдль это.
йогурт я фразу я даже лучше а йод опомнилась.
уже к юле домой лягу
миллионы вас нас тьмы и тьмы и тьмы меня и лишь легкое изделие одной ноге в америке стоят на аборт сделать так много интересного ты меня и тут.
меня
за родину за сталина за апрель.
раз она даже и не успела за апрель сентябрь.
только адрес лиды и не ахти
хабрахабр хорошо а без разницы а хозяйка а без разницы
как некогда в разросшихся хвощах ревела от сознания бессилья как александр клянется.
не ела капусту овощи грибы добавить апельсиновый.
все равно а затем раздался оглушительный свист шум и хорошо сейчас я хочу в общем.
ща алина хмыкнула роза елена вадимовна.
ее лицо а она так сказать о здоровье не ахти невкусно.
из ящика бумагу ее с собой и лишь.
ьгори.
явно
глокая куздра штеко будланула бокра и кудрячит бокрёнка где лежал один класс а я кивнула ушла за дверь распахнулась автоматически.
шофер только если кто он был у двери лифта а на улице лизы а без особых комплексов рассекает.
абсолютно искренне.
как у двери распахнулись я чуть инфаркт то бы он как раз на кухню а
надеюсь мне засчитают эту глупость за сданный курс питона в шаде не ахти.
для ее юбка с мужем не ела за апрель сентябрь.
что и тут а юра тихо.
это ты уже говорила лишь удивляться почему он с тобой знаем адрес сказала девушка а на него.
йогурт кефир.
уже рассказывала сколько помню их тут она не ахти.
все шло а для ее
наши западные партнеры не ахти.
шофер и за апрель.
потом аккуратно добавить немного.
ыыы.
ее по адресу расположен тот не ела рагу.
ыыы


Если хотите больше — можете сами нагенерить.
Исходники лежат тут: https://github.com/PavelMSTU/DANTSOVA

Стеганография



Теперь зададимся вопросом: как на всем этом сделать стеганографию?

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

Короче — есть множество различных идей для воплощения самых извращенных и коварных стеганографических фантазий!

И это будет секьюрно, но не наглядно, как алгоритм DANTSOVA.

ЧаВо


Предчувствуя три вопроса, упреждающе на них отвечаю.

Почему алгоритм назвается dAntsova, а не dOntsova?
Есть несколько точек зрения на столь душераздирающий вопрос.
Одни говорят, что это было сделано специально, мол если Агрипина Аркадьевна (сокращенно просто Дарья) попытается подать в суд, что она уже сделала с rutracker'ом, то автор заявет, что это не в её честь названо, ибо фамилия другая.
Но есть другая точка зрения, согласно которой изменение буквы O на A является особой стеганографической передачей тайного послания.
Однако скептики говорят, что PavelMSTU просто должен больше спать и меньше работать, тогда с орфографией проблем не будет.

Почему мы вкрапляем в первую букву, ведь это же не секьюрно?
Цель топика и самого алгоритма — не в секьюрности, а в наглядности.
Автор хотел показать, что написав на коленках три *.py файла и съаккамулировав большое количество текста одного автора можно добиться определенного результата.
И без всякого deep learning и десятков человеколет какого-нибудь НИИ…
Разумеется для практического использования следует придумать промежуточное кодирование, о чем в статье написано.

PavelMSTU, почему вы не учитывали падежи, род, число? И вообще, где ней<s>т</s>ронные сети и дип лёрнинг?
Пока цель стояла сделать самую простую конструкцию. Это следующий этап.


Вашего вопроса нет в ЧаВо? — задавайте его в комментариях!
Есть ли у акростеганографии будущее?

Проголосовало 69 человек. Воздержалось 28 человек.

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