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

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

    Давно хотел опубликовать этот 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>ронные сети и дип лёрнинг?
    Пока цель стояла сделать самую простую конструкцию. Это следующий этап.


    Вашего вопроса нет в ЧаВо? — задавайте его в комментариях!

    Only registered users can participate in poll. Log in, please.

    Есть ли у акростеганографии будущее?

    • 51%Да, если сделать все секьюрно: шифрование + кодирование «последовательность бит --> куски текста»48
    • 48.9%Нет, генерировать текст можно только для спама; LSB — наше всё!46
    Share post

    Comments 26

      0
      Получается что акростих это частный случай вашего алгоритма?
        0
        Вернее акроТЕКСТ.
        Поэзию генерить на корпусе текстов Донцовой — этого моя прога не умеет. :)
        +3
        за
        за апрель
        за апрель…
        за апрель…
        за апрель…
        за апрель…
        Recursive should be more smart.
          0
          Точно! Нужно внести определенную рандомизацию.

          Например при количестве потенциальных кандидатов равных n
          брать i-е слово с вероятностью pi=wi/(w1+w2+...+wn),
          где wi — вес i-го слова.
            +1
            Ещё бросается в глаза обилие «не ахти». Рандомизация определённо нужна.
          +1
          Слова менее 3 букв желательно подбирать тройками и да, рандомизировать не помешает выбор по весам.
            0
            Автор в орфографии не силен, но читать интересно.
              +2
              Ой… не говорите… Писал ночью. Надеюсь не сильно мешает. Пишите в личку — обязательно буду править!
              +1
              Google: "цепи Маркова генерация текста"
                +7
                При достаточно длинной входной последовательности получится новое произведение Д.Донцовой
                  +2
                  То есть, в терабайтах донцовых текстов, выложенных на рутрекере и ставших одной из причин его блокировки, содержалась такая потенциальная польза?!
                    +6
                    "йогурт российского уголовного кодекса" — оно что-то знает.
                      +1
                      Что за таинственные «ьгори»?
                        0
                        Посмотрел — это видимо описка в *.fb2 файлах.
                        Так как на мягкий знак ничего не начинается, вот это "слово" и оказалось единственным.

                        Уберите в коде мягкий знак из CORRECT_ALPHABET.
                        Задайте :
                        CORRECT_ALPHABET = u'йцукенгшщзхъфывапролджэячсмитбю'
                        +3
                        "Хорошо учился, и тут — армия..."
                        Какая полезная программа! Установил, буду пользоваться.
                          0
                          Хм… а у меня получилось "хорошо училась и тут а".
                          Вы видимо по методике №3 работали ;))
                          3. Комбинировать программный способ и творчество оператора. На мой взгляд это самое интересное, что можно придумать. Программа создает определенное количество вариантов различных слов, затем человек выбирает наиболее семантически подходящее злово из списка, затем программа создает еще одно слово… И так далее, пока не получиться единый цельный текст
                          0
                          Вот еще добавить бы программке интеллекта от Яндекс.Весны и цены бы ей не было :)
                            +4
                            Донцова — автор плодовитый,
                            Она штамповку очень любит.
                            Напишет сотни детективов,
                            Ценить её за это будут.
                            О, далеко не все такие,
                            Всего лишь малый круг людей:
                            Агент, издательство, родные,
                            Другие может, из зверей.
                            Ах да, ещё поклонники её
                            Редчайшего писательского дара
                            (Я пошутил над этим, если что).
                            А остальные спросят: "Что за Дарья?"
                            Решившим прочитать хоть книгу:
                            Клянитесь больше так не поступать!
                            А лучше даже в топку кинуть —
                            Дрова не так легко уж добывать.
                            Ещё под холодильник пару книг
                            Впихнуть, чтоб не шатался больше.
                            Ну или утащить к себе в нужник,
                            А там читать уже попроще.
                              0
                              Это гениально! Хабраюзеры, у кого залежалось — дайте инвайт этому человеку!
                                +4
                                Благодарю за столь высокую оценку (выше, чем оценка творчества Донцовой), но это вряд ли достойно инвайта. Лучше уж я через песочницу, тем более, статья на стадии "да когда я её уже закончу".
                              0
                              "За апрель". Но "не ахти". По-моему, у Донцовой это используется уж очень часто. Наверняка, какие-то выражения еще чаще.
                                +1
                                Мысль любопытная, но генерировать ещё большее количество бессмысленного словесного мусора считаю не просто излишним, но даже сомнительным с морально-этической точки зрения. И без того уже страдаем.
                                  +3
                                  Ааааа! А вдруг Донцова для своего творчества УЖЕ использует подобную программу? :)
                                    0
                                    Увы. Если бы это было истиной, то такая программа могла бы совершенствоваться с ростом технологий, повышая качество продуцируемого контента.
                                –1
                                DANTSOVA засудит же.

                                Only users with full accounts can post comments. Log in, please.