Опять какие‑то философы из V века до н.э. зашифровали ваше сообщение? Разберемся, что с этим делать, в этой статье.

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

Шифр простой перестановки

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

const int SIZE_ABC = 33;

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

Алфавит зафиксирован. Теперь определить оператор преобразования текста. Этот шифр относится к типу блочных шифров, т. е. преобразует текст по блокам. Длина блока равна длине ключа.

Возникает вопрос. А что если длина текста не кратна длине ключа? Тут есть несколько вариантов. Можно дополнить последний блок текста и «добрать» длину до нужной. В этом есть своя уязвимость, т.к. нужно придумать, какими символами дополнять текст. В нашем случае упросим задачу. Шифрование будет осуществляться только если длина текста кратна длине ключа. Реализуем эту проверку в программе.

Теперь поясним как работает перестановка на простом блоке и как задаётся ключ.

На скриншоте показано, как работает шифрование 1 блока. Мы задали ключ — 3421. Цифры означают порядок символов исходной последовательности в выходной последовательности. В теории групп эта структура называется группой перестановок и является подгруппой симметрической группы. Такая подгруппа циклически замкнута. т. е. если применить эту перестановку много раз, рано или поздно мы получим исходную последовательность.

Тождественная перестановка выглядит как {1234}. т. е. порядок символов не меняется. Также теория групп говорит нам о существовании обратной перестановки. Её нам и нужно найти, правда искать мы её будем не математически, а при помощи криптоанализа.

Программная реализация шифра простой перестановки

Для программной реализации использован С++ с прикрученными Windows Forms.

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

string encrypt(string text, string key) {
	string result;
	string word;

	text = validate(text);

	for (int i = 0; i < text.length() / key.length(); i++) {
		word.clear();
		for (int j = 0; j < key.length(); j++) {
			string s{ key[j] };
			word += text[stoi(s) + key.length() * i - 1];
		}
		result += word;
	}

	return result;
};

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

Протестируем работу программы.

Как видим, практический результат совпадает с теоретическим. Теперь попробуем дешифровать наши данные. Однако такая маленькая последовательность для этого не подойдет. В качестве исходного текста возьмем достаточно большой текст (300+ символов).

Анализ модели алфавита

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

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

Как видно из гистограммы — частотный анализ не даёт результатов. Синим показано частотное распределение для шифртекста, с желтым — для любого осмысленного текста из нашего алфавита. Графики частотного распределения почти совпадают, в отличие от шифра Виженера и Цезаря.

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

Для криптоанализа воспользуемся другим приёмом. Построим распределение биграмм текста. Выглядит оно следующим образом:

Биграмма — это 2 символа. Распределение представляет собой матрицу для всех возможных биграмм. Размер матрицы: [длина алфавита * длина алфавита].

Каждая ячейка отражает значение, сколько раз данная биграмма встречалась в тексте. Например, биграмма «аа» встретилась 5 раз. Функция для сбора биграмм проходится по всему тексту, читая i и i+1 символ, запоминая их в матрицу.

void ABCModel::CalculateBigrams(string& text)
{
	vector<char>::iterator itrI;
	vector<char>::iterator itrJ;
	for (unsigned int i = 0; i < text.length() - 1; i++) {
		itrI = find(ABC.begin(), ABC.end(), text[i]);
		itrJ = find(ABC.begin(), ABC.end(), text[i + 1]);
		bigrams[distance(ABC.begin(), itrI)][distance(ABC.begin(), itrJ)]++;
	}
}

Криптоанализ шифра простой перестановки

Теперь у нас есть всё для взлома шифра.

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

• Перебираем по всем возможным длина ключа (В данном случае не более 10). Отбрасывает ключ, если он не кратен длине текста.

• Набираем 50 блоков из шифртекста, равных длине предполагаемого ключа

• Генерируем всевозможные перестановки для этого блока и проверяем их по биграммам.

Что значит проверяем по биграммам ?

int DecryptionSwap::CalculateBigram(string text, int* a) {
	int result = 0, chance;
	vector<char>::iterator itrI;
	vector<char>::iterator itrJ;
	for (unsigned int i = 0; i < text.length() - 1; i++) {

		char x = text[*a - 1];
		a++;
		char y = text[*a - 1];

		itrI = find(ABC.begin(), ABC.end(),x);
		itrJ = find(ABC.begin(), ABC.end(), y);
		int z1 = distance(ABC.begin(), itrI);
		int z2 = distance(ABC.begin(), itrJ);
		chance = bigrams[distance(ABC.begin(), itrI)][distance(ABC.begin(), itrJ)];

		if (chance == 0) {
			return 0;
		}

		result += chance;
	}

	return result;
}

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

Если вдруг шанс равен нулю, то это запрещенная биграмм. Например, нулю равна биграмма «ьъ». Такая точно никогда не встретится в русском языке. Таким образов, если в результате предполагаемой перестановки появилась запрещенная биграмма — то такая перестановка отбрасывается. Из остальных перестановок, которые дали положительные результаты нам нужно найти перестановку с самым большим значением.

Как достигается такой эффект от биграмм?

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

Если проанализировать матрицу биграмм, будут видны наиболее часто встречающиеся сочетания. Например, много слов заканчиваются на «а», «о», «и», «е». Задача как раз найти перестановку, которая даст наибольший шанс. Пусть, например, в перестановке не нашлась запрещенная биграмма, но нашлось много биграмм с малыми весами. Это биграммы с весами до 100. Но, если вдруг в перестановке встретиться сразу несколько биграмм «а » или «е «, то сразу даём +500 очков к этой перестановке, т.к. в результате неё получились биграммы с высокой долей вероятности. Можно считать матрицу биграмм — матрицей вероятностей.

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

Далее, для простоты восприятия, перестановка ещё раз переводится в обратную и получается исходный ключ.

Как видим, программа нашла ключ правильно.

Заключение

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

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

Другие статьи по теме:

• Шифр Виженера