Шифр Цезаря с частотным анализом, что делать дальше?

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

void frequencyUpdate(std::vector< std::vector< std::string> > &file, std::vector<int> &freqArg) {
    for (int itr_1 = 0; itr_1 < file.size(); ++itr_1) {

        for (int itr_2 = 0; itr_2 < file.at(itr_1).size(); ++itr_2) {

            for (int itr_3 = 0; itr_3 < file.at(itr_1).at(itr_2).length(); ++itr_3) {
                file.at(itr_1).at(itr_2).at(itr_3) = toupper(file.at(itr_1).at(itr_2).at(itr_3));

                if (!((int)file.at(itr_1).at(itr_2).at(itr_3) < 65 || (int)file.at(itr_1).at(itr_2).at(itr_3) > 90)) {
                    int temp = (int)file.at(itr_1).at(itr_2).at(itr_3) - 65;
                    freqArg.at(temp) += 1;
                }
            }

        }

    }
}

вот как я получаю частоту данного файла, содержимое которого разбито на строки, а затем на слова, следовательно, двойной вектор строк и использование значений символов ASCII - 65 для индексов. Результирующий вектор целых чисел, которые содержат частоту, сохраняется.

Теперь я не знаю, как действовать дальше. Должен ли я жестко кодировать const std:: vector <int> для английской частоты букв, а затем как-то сравнивать? Как бы я мог эффективно сравнивать, а не просто сравнивать каждый вектор друг с другом, потому что это возможно неэффективный метод?

Это сравнение предназначено для получения подходящего значения сдвига для сдвига шифра Цезаря для расшифровки текста. Я не хочу использовать грубую силу и сдвигать по одному, пока текст не станет читаемым. Любые советы о том, как подойти к этому? Спасибо.


person Kthieu    schedule 03.03.2015    source источник
comment
У вас будет элемент грубой силы. Такова природа вашего подхода.   -  person Captain Giraffe    schedule 03.03.2015


Ответы (3)


Возьмите свой вектор частот и вектор частот для "типичного" английского текста и найдите взаимную корреляцию.

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

person Ben Voigt    schedule 03.03.2015
comment
Хороший вопрос, для более сложных алгоритмов можно было бы использовать взаимную корреляцию, но в случае Цезаря, я думаю, вычисления были бы более сложными, чем атака грубой силы с проверкой всех 26 возможностей. - person Krystian; 03.03.2015
comment
@Krystian: Возможно, нет - стоимость кросс-корреляции зависит от размера алфавита, а не от размера декодируемого текста. Вы строите частотную таблицу за один проход по зашифрованному тексту. Брут-форс требует многочисленных проходов по всему тексту (хотя, возможно, вы можете выйти раньше, если первые несколько слов выходят плохо) - person Ben Voigt; 04.03.2015
comment
Несмотря на то, что я отметил это как правильный ответ, я не знаю, как начать поиск взаимной корреляции между двумя векторами. - person Kthieu; 04.03.2015
comment
Вы читали описание в Википедии? Чтобы сделать сумму, вам понадобится цикл. - person Ben Voigt; 04.03.2015
comment
Должен ли я изменить элементы в моем векторе частот на проценты вместо целых? Я спрашиваю, потому что получение списка частот букв английского алфавита, как правило, имеет очень большие значения int. Как только я получу сумму каждого? вектор, как мне получить необходимый сдвиг? Не уверен, что векторы похожи на функции. - person Kthieu; 04.03.2015

В английском языке «е» имеет самую высокую частоту. Таким образом, какая бы буква из вашего зашифрованного текста не встречалась чаще всего, она, скорее всего, соответствует букве «е». Поскольку e --> X, то ключ должен быть разницей между 'e' и вашей наиболее часто встречающейся буквой X.

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

person Krystian    schedule 03.03.2015

Я бы предложил алгоритм обхода графа. Ваш начальный узел не имеет назначенных замен и имеет 26 связанных узлов, по одному для каждой возможной замены буквы для наиболее часто встречающейся буквы зашифрованного текста. Следующий узел имеет еще 25 связанных узлов для возможных букв для второй наиболее часто встречающейся буквы зашифрованного текста (на одну меньше, так как вы уже использовали одну возможную букву). Какой узел назначения вы выберете, должен основываться на том, какие буквы, скорее всего, имеют нормальное частотное распределение для целевого языка.

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

person Jherico    schedule 03.03.2015
comment
Шифры Цезаря гораздо более строгие, чем общий шифр замены. - person Ben Voigt; 03.03.2015
comment
Ах да... ну, обход графа технически все еще будет работать, это всего лишь один узел с 25 пунктами назначения для разной ширины сдвига. :) - person Jherico; 03.03.2015