Сказал как-то один французский дипломат...

Что же он такого мог сказать в 16 веке? Разберемся в этой статье.

Строго говоря, шифр Виженера был придумал не им. Виженер лишь изучил труды других ученых того времени и скомпоновал всё в 1 книге, которая называется «Трактат о шифрах». Всё это происходило примерно в 16 веке, однако современное название шифр получил не так давно.

Шифр использует простой метод многоалфавитной замены. Долгое время шифры этого семейства считались абсолютно стойкими, но примерно в 19 веке с этим решил поспорить Фридрих Касиски, при чём успешно. Правда он не опубликовал свои труды, поэтому увидели их только ближе к нашему времени и метод, описанный автором, назвали в его честь. Мы к нему ещё вернемся.

На этом закончим с краткой исторической справкой и перейдем к алгоритму шифра.

Шифрование по методу Виженера

Для начала зафиксируем алфавит, в котором мы будем работать. В нашем случае это будет русский алфавит, включающий только маленькие буквы и символ пробела, исключая букву ё. Будем считать, что вместо ё пишут е.

Получается 33 символа (Русский алфавит - ё + пробел).

const int SIZE_ABC = 33;

const char ABC[SIZE_ABC] = {
  'а', 'б', 'в', 'г', 'д', 'е', 'ж', 'з', 'и', 'й', 'к', 'л', 'м', 'н',
  'о', 'п', 'р', 'с', 'т', 'у', 'ф', 'х', 'ц', 'ч', 'ш', 'щ', 'ъ', 'ы',
  'ь', 'э', 'ю', 'я', ' '};

Каждый символ этого алфавита имеет свой индекс. От 0 до 32. Распределение индексов показано на картинке ниже. Пробельный символ обозначен знаком «_». Далее везде в статье будем обозначать пробел таким образом. Делается это для удобства восприятия. В программной реализации пробел — это действительно пробел.

Зафиксируем еще несколько понятий, которые нам пригодятся:

• Исходный текст - то, что мы вводим (входные данные);

• Зашифрованный текст или шифртекст - применение к исходному тексту функции зашифрования;

• Расшифрованный текст - применение к шифртексту функции расшифрования;

• Дешифрованный текст - применение к шифртексту функции криптоанализа (взлома).

Шифр Виженера состоит из последовательности нескольких шифров Цезаря с различными значениями сдвига. Шифр Цезаря предполагает замену каждой буквы исходного текста на другую, путем сдвига индекса буквы на определенное число. Разберем конкретный пример. Возьмём слово «Хабр» как исходный текст и применим к нему сдвиг на +1 по индексам, зафиксированным нами выше. Результат получился такой:

Индексы показаны над буквами. Вычисление индексов ведется по модулю размера зафиксированного алфавита. Т.е. Если к пробельному символу прибавить 1, то он перейдет в букву А.

В данном примере функция шифрования сдвигает индексы на 1. Это и есть простой шифр Цезаря. Однако, метод Виженера работает чуть хитрее.

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

Возьмем в качестве исходного текста слово «Публикация», а в качестве ключа — слово «Лайк». Разложим оба слова по индексам и сложим индексы по модулю 33 (длина нашего алфавита). Запишем ключ как бы 'под' исходным текстом. Т.к. ключ меньше, запишем его столько раз, сколько нужно, пока весь исходный текст не будет покрыт ключом. Если ключ целиком не поместится, то так и оставим. Получается следующая картина:

Теперь ключ покрывает весь исходный текст. Дело за малым. Преобразуем текст и ключ в индексы и сложим по модулю 33. Индексы записаны строго с 2 знаками для удобства восприятия и выравнивания формулы.

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

Программная реализация шифра Виженера

Для реализации программного обеспечения используется язык C++ с прикрученными Windows Forms. Тут не будет объяснений по программированию интерфейса. Разберем лишь основные функции по изучаемому шифру. Внизу будет ссылка на гит с полным кодом проекта.

string Vizhiner::encrypt(string text, string key) {
	string result;

	text = validate(text);
	key = validate(key);

	vector<int> shift = GetPositions(key);

	for (unsigned int i = 0; i < text.length(); i++) {
		vector<char>::iterator itr = find(ABC.begin(), ABC.end(), text[i]);

		result += ABC[(distance(ABC.begin(), itr) + shift[i % key.length()]) % ABC.size()];
	}

	return result;
};

vector<int> Vizhiner::GetPositions(string& text) {
	vector<int> result;

	for (unsigned int i = 0; i < text.length(); i++) {
		vector<char>::iterator itr = find(ABC.begin(), ABC.end(), text[i]);
		result.push_back(distance(ABC.begin(), itr));
	}

	return result;
}

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

На картинке показано вычисление дистанции от начала алфавита до итератора. Итератор указывает на один из символов алфавита. Фактически дистанция и представляет из себя индекс символа. К индексу начального символа прибавляется индекс ключа по модулю длины ключа. Модуль нужен для создания той самой цикличности, т. е. когда ключ закончится, мы возвращаемся в его начало. В конце берем модуль по длине алфавита, чтобы избежать «выкатывания» за пределы алфавита (Пр.2).

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

Расшифрование делается в обратном порядке, как было описано выше. Есть только 1 нюанс. Для расшифрования достаточно было бы поменять знак с + на -, а далее всё работало бы за счёт операции модуля, как это описано в линейной алгебре.

Но в C++ модуль работает не совсем так, поэтому если индекс получился отрицательный, нужно вручную привести его к положительному таким образом:

if (x < 0) { x += ABC.size(); }

Реализацию алгоритма зашифрования и расшифрования мы сделали. Теперь можно подумать о криптоанализе данной системы. Однако, прежде необходимо построить модель исходного языка и проанализировать её.

Построение модели языка

Модель языка имеет множество характеристик. Например, биграммы. Это частота встреч сочетаний из 2-х символов. Также есть слова из 1,2,3-х букв. В программе реализован поиск таких слов, однако для криптоанализа данного шифра они не пригодятся, так что разбирать мы это не будем.

Параметр модели, который нужен для взлома — это частотное распределение. Построить его очень просто. Загоняем в программу какой‑то достаточно большой текст (> ~ 300 символов) и считаем количество каждого из символов. Далее по оси Y пересчитываем значение частоты символа в относительную величину(частота символа/общее кол-во символов). Таким образом мы получаем, фактически, вероятность встречи символа в тексте. В результате получится график частотного анализа. Для зафиксированного нами алфавита этот график выглядит так:

Для построения анализа, в программе нужно вставить текст в поле «Пример текста из исходного алфавита». Для удобства есть выбор из текстового файла. На GitHub уже есть этот файл по пути input/model.txt, но можно вставить и любой другой текст. Считается, что в задачах криптографии алфавит известен, поэтому проблем с поиском длинных текстов для построения модели алфавита быть не должно и это не является ограничением.

Криптоанализ шифра Цезаря

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

Рассмотрим шифртекст Цезаря, состоящий из достаточно большого числа символов. Опять же, > ~ 300. В данной ситуации это является ограничением и для дешифрования криптоаналитик должен набрать некоторое кол-во шифртекстов.

Рассмотрим конкретный пример. Пусть есть шифртекст Цезаря с величиной сдвига равной 5. Построим график частотного распределения для этого текста. Получается следующая картина:

Заметим, что этот график «Сдвинут», относительного графика нашего алфавита, вправо на 5 позиций, что как раз равно величине сдвига при зашифровании. Действительно, так и получается, т.к. при таком методе шифрования, каждый символ X всегда переходит в другой символ Y. X и Y сохраняются на протяжении всего шифра. Например, символ «И» всегда переходит в «Н».

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

Сведение шифра Виженера к шифрам Цезаря

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

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

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

Остаётся только одна загвоздка... Для выделения одинаковых блоков нужно знать длину ключа. На рисунке выше видно, что длина ключа равна 4, значит из ширтекста Виженера мы выделяем 4 шифртекста Цезаря. Первый включает каждую 4 буквы, начиная с первой. Второй блок включает каждую 4 букву, но начиная со второй... и т.д. Остаётся решить задачу по нахождению длины ключа.

Индекс совпадений

Эта часть статьи будет чуть сложнее, но я постараюсь объяснять её также просто.

В нахождении длины ключа нам поможет Касиски. Тот самый, который в 19 веке придумал этот метод и забыл всем рассказать. Суть способа заключается в введении ещё 1 характеристики, которая называется индекс совпадений.

Вычисляется он по следующей формуле, представленной ниже. Тут ci - это индекс совпадений. m - некий текст. l - длина текста. l c индексом - это кол-во букв с таким же индексом. т.е. l1 - это кол-во букв а.

Как видно, слагаемые представляют из себя вероятность появления буквы в тексте (l1 / l это кол‑во символов а / общее кол‑во символов или вероятность встретить символ а). Возведение вероятностей в квадрат и их сложение даёт нам индекс совпадений.

Поясним, что из себя представляет эта величина. Для этого представим, в каком случае она будет принимать минимальное значение. Алфавит у нас зафиксирован. Предположим, что длинна текста не меняется (хотя это и не так важно). Тогда индекс совпадения будет минимальным, если l i‑тое будут минимальными, т.к. при возведении в квадрат, слагаемое даст ещё более маленькую величину. Каждое l‑i‑тое будет минимальным, если распределение вероятность появления символа будет минимальным, а значит — одинаковым для всех символов. Равновероятностное распределение символов даёт минимальный индекс совпадений. Как вы убедились из модели алфавита, его частотное распределение совсем не равновероятностное и индекс его совпадений будет значительно выше. Максимальное значение индекса совпадений будет иметь текст, состоящий из 1 буквы. Например: «ААААА».

Такие тексты нас не интересуют, нам важен лишь факт, что при НЕ равновероятностном распределении частоты символов — индекс совпадения будет выше. Считаем, что если индекс совпадения текста низкий — значит перед нами что‑то похожее на бред, а вот если он становится выше, значит какие‑то символы в тексте начинают преобладать, а значит такой текст гораздо более похож на реальный.

Криптоанализ шифра Виженера

Теперь то у нас есть все инструменты для вскрытия шифра Виженера. Эту задачу можно разбить на несколько пунктов:

1. Поиск длины ключа

2. Выделение L блоков шифров Цезаря (L - длина ключа)

3. Криптоанализ L шифртекстов Цезаря. Нахождение сдвига для каждого шифртекста.

4. Дешифрование

Возьмем Y как шифр текст (достаточной длины). Для поиска длины ключа воспользуемся индексом совпадений. Предположим, что длина ключа равна 1. Тогда весь шифртекст это 1 шифр Цезаря. Т.е. каждый символ "сдвинут" на одинаковую величину. Посчитаем индекс совпадений для всего шифртекста и запомним его. Предположим, что длина ключа равна 2-м. Тогда каждый 2-й символ, начиная с первого образует шифртекст Цезаря. И каждый 2-й символ, начиная со 2 тоже будет шифртекстом Цезаря, но с другим сдвигом. Возьмем 1-й шифртекст Цезаря и посчитаем для него индекс совпадений. И т.д.. для длины ключа 3 получится 3 шифртекста Цезаря. Посчитаем индекс для первого из них. Так сделаем до 20 (Тут опционально. В данном примере посчитаем, что длина ключа меньше 20).

Построим график индексов совпадений для наших 20-ти предположений длины ключа. А также усредним все индексы совпадений и построим среднюю линию. Получается следующая картина:

Из графиков видим, что когда мы сделали предположение о длине ключа, равной 4 — произошел всплеск индекса совпадений. Это означает, что если мы выбираем из текста каждый 4-тый символ, начиная с 1 и считаем для этого текста индекс совпадений, он оказывается довольно высоким, а значит его распределение вероятностей является более «осмысленным» и это и будет наш первый шифртекст Цезаря.

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

А дальше все тривиально. Отбираем из текста k текстов (k — длина ключа) и решаем каждый их них как шифр Цезаря. Найдя сдвиг для каждого k‑того текста, восстанавливаем ключ. Индекс сдвига — это фактически индекс символа ключа. Полученный ключ мы можем применить для расшифрования данных. Шифр взломан.

Программная реализация

Пояснение к некоторым важным функциям.

void ABCModel::CalculateDistribution(string& text) {
	vector<int> countChar(33, 0);

	for (unsigned int i = 0; i < text.length(); i++) {
		vector<char>::iterator itr = find(ABC.begin(), ABC.end(), text[i]);
		countChar[distance(ABC.begin(), itr)]++;
	}

	for (unsigned int i = 0; i < this->ABC.size(); i++)
	{
		distribution[ABC[i]] = (double)countChar[i] / (double)text.length();
	}
}

void ABCModel::CalculateIndexOfMatches()
{
	double summ = 0;

	map<char, double>::iterator itr;
	for (itr = distribution.begin(); itr != distribution.end(); itr++) {
		summ += (itr->second * itr->second);
	}

	this->indexOfMatches = summ;
}

//Считаем индексы совпадений. В даном случае decriptor считает их для 20-ти текстов
vector<double> indexes = decriptor->GetIndexesOfMatches();

//Считаем среднее
int i = 1;
double average = 0, MAX = 0;
vector<double>::iterator itr;
for (itr = indexes.begin(); itr != indexes.end(); itr++) {
	average += *itr;
	if (*itr > MAX) { MAX = *itr; }
	i++;
}

average /= i;

average = ((MAX + average) / 2);

//Ищем длину ключа как первый всплекс индекса совпадений выше среднего
unsigned int keyLength;
for (unsigned int i = 0; i < indexes.size(); i++) {
	if ((MAX - average) < 0.005) { keyLength = 1; break; }
	if (indexes[i] > average) { keyLength = i + 1; break; }
}

//Набираем k шифр текстов Цезаря и делаем для них частотный анализ
for (unsigned int i = 0; i < keyLength; i++) {

	string text;
	separationEncrypt.push_back(new ABCModel(ABC));
	for (unsigned int j = i; j < encryptionText.length(); j += keyLength) {
		text += encryptionText[j];
	}

	separationEncrypt[i]->CalculateDistribution(text);

}

/*Проходимся по всем текстам и считаем, 
насколько их частотное распределение сдвинуто,
относительно исходного распределения для исходного алфавита */
for (unsigned int i = 0; i < separationEncrypt.size(); i++) {
	unsigned int shift = originalModel->CalculateShift(separationEncrypt[i]->GetDistribution());
	key += originalModel->GetCharABC(shift);
}

Полную программную реализацию можно скачать на GitHub. В репозитории есть директория input с примерами текстов, но вы можете использовать свои. Также есть уже скомпилированный exe файл, чтобы не собирать проект. Собрать вручную можно через Visual Studio (легко) или совсем самостоятельно через компилятор и командную строку (посложнее). Требуется Net Framework.

В статье не уделяется много внимания программной реализации, т.к. хотелось сделать фокус на сам криптоанализ.

P. S. Ключ в итоге оказался «хабр». Говорят, что именно на этом слове Виженер и зашифровал свой текст на картинке в самом начале (текст вводить без пробелов. Роль пробела играет «_»).