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

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

Этот шифр является усовершенствованной версией шифрования а-ля Цезарь, только вместо латинского алфавита, используется целая таблица (которая, кстати, называется tabula recta), состоящая из последовательности «ABCDEFGHIJKLMNOPQRSTUVWXYZ», которая в каждой строке таблицы сдвигается на 1 шаг вправо.

Эта таблица выглядит так:

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

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

Как видите, это очень просто.

Для реализации шифра Виженера нам потребуется сгенерировать tabula recta, для чего нужна вспомогательная функция, сдвигающая строку на n символов вправо, назовем эту функцию strshift (string shift).

Для генерации таблицы потребуется структура данных, которая будет хранить сдвинутую алфавитную строку: на мой взгляд, здесь можно использовать одну очень крутую возможность языка D, а именно, ассоциативные массивы (не удивляйтесь, поддержка ассоциативных массивов в D — нативная). Чтобы построить tabula recta, воспользуемся вот таким массивом char[char][char] — т.е. этот массив будет хранить в себе один символ, соответствующий определенному символу исходного сообщения и ключа (в роли индексов такого массива — символы).

После инициализации ассоциативного массива, происходит сдвиг алфавитной строки на некоторое количество символов (исходя из таблицы, легко увидеть, что сдвиг происходит на число, которое изменяется на единицу, при движении по строкам таблицы сверху вниз, т.е. позиция сдвига меняется от 0 до 25) и конкатенация переменной-накопителя с полученным результатом. Далее начинается размещение полученной строки в ассоциативном массиве, для чего используется вложенный цикл foreach, пробегающий по алфавитной строке и вычленяющий из переменной-аккумулятора символ, соответствующий символу исходного сообщения и символу ключа (Описание сложное, но код не такой уж и пугающий, поверьте !).

На выходе, после всех этих процедур имеем полностью заполненную tabula recta  :)

Дальше процедура шифрования, которая реализована в виде функции encode и которая существенно проще. Однако, для старта шифрования необходимо, чтобы длина ключа была равна (или чуть больше) длине сообщения, т.е нужно произвести выравнивание ключа по сообщению. Осуществить выравнивание очень просто: нужно повторить пароль, накапливая его в некоторую переменную, до тех пор, пока его длина не сравняется или не превысит длину исходного текста для шифровки, что достигается простым использованием конкатенации строк и цикла while. После этой процедуры действия вполне элементарные: нужно пройтись по всему исходному тексту для шифрования в цикле и используя индекс цикла, как порядковый номер символа в исходном тексте и в ключе, сопоставить эти два параметра с tabula recta. И все :)

Расшифровка производиться почти также.

Собственно, код этой затеи:

import std.stdio;

void main() {
   writeln(encode("ATTACKATDAWN","LEMON"));
   writeln(decode("LXFOPVEFRNHR","LEMON"));
}

string strshift(string s,size_t pos) {
	string tmp = "";
	for (size_t i = 0; i <= pos; i++) {
		tmp ~= s;
	}
	return tmp[pos..(pos+s.length)];
}

char[char][char] tabula_recta() {
	char[char][char] v;
	string tmp = "";
	string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

	for (size_t i = 0; i < alpha.length; i++) {
		tmp ~= strshift(alpha,i);
	}

    int pchar = 0;
	foreach (i;alpha) {
		foreach (j; alpha) {
           v[i][j] = tmp[pchar];
           pchar++;
		}
	}
    return v;
}

string encode(string phraze,string pass) {
	char[char][char] tr = tabula_recta();
	string passw = pass; 
	string res = "";

    while (passw.length < phraze.length) {
    	passw ~= pass;
    }

    passw = passw[0..phraze.length];

    for(int i = 0; i < phraze.length; i++) {
    	res ~= tr[phraze[i]][passw[i]];
    }

    return res;
}


string decode(string phraze,string pass) {
	char[char][char] tr = tabula_recta();
	string res = "";
	string passw = pass; 
	string alpha = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

	while (passw.length < phraze.length) {
    	passw ~= pass;
    }

    passw = passw[0..phraze.length];

	for (size_t i = 0; i < passw.length; i++) {
		foreach (j; alpha) {
			if (tr[passw[i]][j] == phraze[i]) res ~= j;
		}
	}

	return res;
}

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

P.S: Почти сразу после написания этого кода, я понял, что есть способ гораздо проще (!) и я бы воспользовался им, если бы дочитал то, что предложено в источнике по вышеупомянутой ссылке.

        Мораль: читайте источник до конца!

Добавить комментарий