Шифр Вижинера и его разгадка

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

    Блезом Вижинером в 17 веке был предложен довольно интересный метод шифрования. Ключом шифра служит специальная фраза. Эта фраза, многократно повторяясь, пишется над шифруемым текстом. Каждая буква секретного сообщения получается сдвигом каждой буквы исходного текста на определённое число, задаваемое буквой ключевой фразы (Буква А не даёт сдвига, буква Б — сдвиг на одну позицию, В — на две и т.д.).
    Например попробуем зашифровать слово «СЕКРЕТ», пользуясь ключевой фразой «АБВ». Буква С не сдвигается, первая буква Е сдвигается на одну позицию, превращаясь в Ж, буква К сдвигается на две позиции, превращаясь в М. Продолжая шифровать сообщение, мы в итоге получим «СЖМРЖФ».

    На протяжении трёх веков этот шифр считался практически не взламываемым. Первые попытки взлома этого шифра были предприняты в 19 веке. Все эти попытки были основаны на определении длины ключевой фразы. Если нам известна её длина, то весь зашифрованый текст мы можем разбить на фрагменты, каждый из которых кодируется одним и тем же сдвигом. В нашем примере буквы С, Р кодируются с нулевым сдвигом, Е, Е кодируются со сдвигом в единицу, К, Т кодируются со сдвигом 2. Если текст достаточно длинный, мы можем применить частотный анализ и тем самым, раскрыть исходное сообщение. Получается, что разгадка этого шифра сводится к поиску длины ключевой фразы.

    Сейчас мы рассмотрим два метода нахождения этой длины. Первый метод был предложен Фридрихом Касицким. Основа метода Касицкого — поиск биграмм. В случае, когда в шифруемом сообщении одна и та же биграмма повторяется на расстоянии, кратном длине ключевой фразы, она встретитс на тех же позициях и в зашифрованном тексте. Найдя это расстояния и, получив все его делители, мы получим набор чисел-кандидатов на длину ключевой фразы.

    Попробуем расшифровать методом Касицкого следующий текст: «ОАИТАБНПХЮПМЪАЭМАЗЧАФРЮЯЦМАТВУШКГЮНШИЪДООЯВТЫХЧЪТЫЖПЫТЕЭНХЕАПНХДРСЕЗЬУНЯЗ». Зашифрованный текст содержит три повторяющихся биграммы МА (позиции 16 и 26), ТЫ (позиции 44 и 49) и НХ (позиции 57 и 62). Биграмма МА повторяется на расстоянии в 10 позиций, биграммы ТЫ и НХ на расстоянии в 5 позиций. Скорее всего позиции длина ключевой последовательности равна 5. Рассматриваемый метод требует некоторого везения, т.к. в тексте могут возникать «случайные» биграммы. Их вероятность много ниже, чем у «регулярных», но в небольших текстах они могут значительно усложнить расшифровку.

    Прежде чем окончательно расшифровать текст, мы рассмотрим ещё один метод определения длины ключа, предложенный Фридманом. Суть метода в циклическом сдвиге сообщения. Полученные таким образом сообщения записываются под оригинальным шифротекстом и подсчитывается число совпавших букв в верхней и нижней строке. На основе этих чисел вычисляется т.н. индекс совпадений, равный отношению количества совпадений к полной длине сообщения. Для русских текстов индекс совпадений равен примерно 6%, но для случайных текстов этот индекс равен 1/32, т.е. приблизительно 3%. На этом факте и основан метод Фридмана. Текст записывается со сдвигом в 1,2,3 и т.д. позиций и для каждого сдвига вычисляется индекс совпадений. Циклический сдвигая наше сообщение получаем:
    Сдвиг Совпадений Индекс
    2 0 0.000
    3 5 0.068
    4 2 0.027
    5 8 0.110 (!)
    6 1 0.014
    7 1 0.014
    8 2 0.027
    При сдвиге 5 индекс резко возрастает, следовательно длина ключевого слова скорее всего равна 5. Понять почему индекс резко возрастает довольно просто. В случае, когда все символы сдвигаются на одну и ту же позицию, индекс совпадения такой же, как и у исходного текста. В случае, когда мы вычисляем индекс для шифра Вижинера мы во всех случаях (кроме того, где длина сдвига равна длине ключа) сравниваем фактически случайный текст.

    Определив длину ключа мы можем, воспользовавшись таблицей частоты букв, выяснить, что зашифровано было известное детское стихотворение:
    Наша Таня громко плачет:
    Уронила в речку мячик.
    Таня, Танечка, не плачь,
    Не утонет в речке мяч!
    В качестве пароля была взята фамилия автора «Барто».

    Надеюсь, в этой заметке вы нашли для себя что-то новое. И, надеюсь, полученные знания вы используете исключительно во благо.
    Share post

    Comments 30

    • UFO just landed and posted this here
        0
        Чем меньше отношение (длина ключа) / (длина сообщения), тем проще расшифровать текст вышеописанными методами.
        +1
        Полезно с точки зрения истории скорей
          +4
          Можно кодировку восстанавливать подобными средствами.
            0
            Хотя, врятли… но попробовать можно.
              +9
              Я когда-то пробовал. Попался файл с испорченной кодировкой. Интернета в те далекие времена у меня не было, то есть всяких «штирлицев» скачать было проблемой там и тогда не решаемой. Написал программу, скормил ей большой объем текста — получил частотное распределение символов в русском языке. Скормил тот файл — получил таблицу подстановки. Дальше — обработка-расшифровка файла по этой таблице. Результат был слегка читаем. Одно дело теоритическое распределение букв в русском языке, совершенно другое — в отдельно взятом тексте. Дальше пошла игра с корректировкой таблицы подстановки, через десяток шагов я получил текст, с которым справился спелчекер.
              Короче, как разминка для ума — задача неплохая, но и только.
          +2
          > Суть метода в циклическом сдвиге сообщения.
          Ищется максимум автокорреляционной функции, короче =) Подобным образом и другие сигналы анализируют :-)

          А вообще познавательно, спасибо.
            –6
            Вот уж, наверное, нечего больше на хабр постить, кроме как кастрированные версии лекций с первых курсов.
              0
              хех, на питоне ргр делал по шифрованию/дешифрованию/взлому в то время как все руками мучались =)
                0
                помнится писал курсач, где реализовал в числе многих и этот метод шифрования. в принципе для защиты данных просто от посторонних лиц на время — очень даже удобно. скажем так, зашифровать и оставить на компе у себя, чтобы посторонние не смогли прочесть — сестра, брат, родители или просто друг.
                  +2
                  Смысла нет. Вручную всё равно неудобно, а если программа то есть куча реализаций куда более серьёзных алгоритмов.
                    0
                    я согласен. но я в свое время написал такую программку, иногда использую чтобы скрыть от посторонних глаз информацию. для мох целей ее хватает вполне.

                    суть не в том, что есть что-то лучше, а что-то хуже. суть в том, что есть такой инструмент и его можно или применять или нет, в зависимости от потребностей. В свое время ведь данный алгоритм был востребован.
                • UFO just landed and posted this here
                    +1
                    Если нам известна её длина, то весь зашифрованый текст мы можем разбить на фрагменты, каждый из которых кодируется одним и тем же сдвигом.

                    Помоему не каждый фрагмент будет кодироваться с одним и тем же сдвигом, а внутри любого фрагмента каждый i-ый элемент будет кодироваться с одним и тем же сдвигом.
                      0
                      В детстве смотрел советский фильм, где автора шифра называли «Вегинер»-ом.
                      Так какая транскрибация правильная?
                        0
                        В Википедии: «Vigenère (French pronunciation: [viʒnɛːʁ])»
                        Так что Виженер.
                        0
                        «Суть метода в циклическом сдвиге сообщения» — можно поподробнее, что куда сдвигать предлагается?
                          +4
                          Очень рекомендую прочитать «Криптономикон» всем, кто хотя бы чуть-чуть интересуется криптографией (а так же всем, кому просто хочется прочитать хорошую книгу :)
                            +2
                            Хорошая книжка, присоединяюсь.
                              +2
                              Ага, приключенческий роман с листингами :)
                                0
                                А еще, можно почитать «Книгу шифров», тоже интересно.
                                0
                                По поводу написания фамилии: неожиданная у гугла выдача по слову Viginer
                                  0
                                  Попробуйте свои силы в Виженере и не только на
                                  cryptolib.com/challenges.php
                                  Замечательный набор, для одного самого короткого примера пришлось анализировать частоты 4-грамм.
                                    0
                                    Было бы интересно узнать, как много лет назад для шифрования использовались обычные книги. Вроди того, как Штирлиц расшифровывал радиограммы Центра.
                                      0
                                      Стало самому интересно и вот нашел описание этого метода в «Досье ОДЕССЫ» Форсайта
                                      … Йозеф бодрствовал на кровати в номере заштатной гостиницы на окраине Мюнхена, как вдруг из фойе позвонили и сказали, что ему пришла телеграмма. Йозеф спустился и забрал ее. Вернувшись к себе, он вскрыл желто-коричневый конверт и пробежал взглядом внушительное содержимое. Телеграмма начиналась так:

                                      Сельдерей: 481 марка 53 пфеннига
                                      Дыни: 362 марки 17 пфеннигов
                                      Апельсины: 627 марок 24 пфеннига
                                      Грейпфруты: 313 марок 88 пфеннигов…

                                      Список был длинный, однако все входившие в него фрукты и овощи обычно экспортировал в Европу Израиль, так что телеграмма читалась как ответ какого-нибудь представителя торговой фирмы о ценах на продукты. Пользоваться международным телеграфом для передачи шифровок – дело рискованное, однако в ФРГ из-за границы приходит ежедневно столько деловых телеграмм, что для проверки их всех потребовалась бы целая армия криптографов.

                                      Не обращая внимания на слова, Йозеф выписал все цифры впритык друг к дружке. Таким образом, трех– и двухзначные числа, обозначавшие цены в марках и пфеннигах, исчезли, из них образовалось одно число, столь многозначное, что оно занимало несколько строк. Йозеф разбил его на группы по шесть цифр, вычел из каждой тогдашнюю дату – 20 февраля 1964 года. Получились новые шестизначные числа.

                                      Для шифровки использовался простейший книжный код, основанный на Уэбстеровском толковом словаре английского языка, изданном в Нью-Йорке в серии «Популярная библиотека». Первые три цифры шестизначного числа указывали номер его страницы, в четвертой учитывалась лишь четность. Если цифра была нечетной, это означало, что искать нужно в левом столбце на странице словаря, если четной – в правом. Последние две соответствовали номеру слова в столбце, если считать сверху. Йозеф трудился не покладая рук полчаса, наконец раскодировал телеграмму, прочел ее… и горестно схватился за голову...
                                      0
                                      Баловался с этим шифром — его взломом то есть. Как всегда попал на простую истину. Надо знать примерную тему сообщения, потому что в противном случае частоты повторения букв будут не те. Нельзя использовать частоты букв из «Войны и Мира», для расшифровывания текста газеты 60х годов. Ну и знание тематики расшифровываемого текста — судя по всему самый главный ключ в любом шифре.
                                        0
                                        > на специализированных олимпиадах

                                        Какое двусмысленное замечание.
                                        0
                                        дайте ссылочку на таблицу частот букв!

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