Мысли перед сном: алгоритм фрактального перемешивания

Недавно я впервые в этом сезоне ночевал на даче и никак не мог уснуть из-за непривычной обстановки. И тогда мой мозг понесся думать про XOR-шифрование. Оно ведь довольно простое, а я думал, как можно его улучшить. К сожалению, вместо того, чтобы сладко уснуть, я додумался до того, что надо перетасовать исходные данные каким-нибудь образом. И тогда мне в голову пришла идея фрактального перемешивания (из-за которой я уснул после четырех ночи).

Суть алгоритма такова: берется вектор исходных данных и делится на N равных частей (если на N вектор не делится, то просто оставляется справа «хвостик», хотя можно и слева). Эти N частей перемешиваются согласно какому-то вектору перетасовки m[N] (который потом передается в качестве ключа получателю, если использовать этот алгоритм для шифрования). После перемешивания каждая часть исходного вектора делится точно так же на N равных частей, и внутри каждой части выполняется аналогичное перемешивание. Потом это происходит снова и снова, пока это будет возможно.

Что примечательно – этот алгоритм легко реализовать с помощью рекурсии, но можно реализовать его и итерационно. Кроме того, алгоритм перемешивания симметричный, то есть для получения исходного вектора данных надо применить его опять с тем же вектором m[N].

Когда я его придумал, я сразу же назвал его фрактальным, так как перемешивание происходит внутри перемешивания (да и слово «фрактал» классное). А ещё я сразу же полез искать его в Гугл (к счастью, мобильный интернет на даче работает). Но не нашел! Тогда в моих глазах загорелось пламя азарта – неужели я придумал что-то новое и простое? После таких мыслей я еще долго не мог уснуть – но я уже думал не столько об алгоритме перемешивания, сколько о том, как буду писать статью на Хабр.
Через неделю я, будучи уже дома, переборол свою лень и написал код на С++, который перемешивает заданную строку моим алгоритмом, используя заданное число N. Для простоты я использовал вектор, который переставляет данные задом наперед. Но, конечно же, алгоритм рассчитан на произвольный вектор перемешивания.

Код на C++

Примечание: В main вызывается метод shuffleString, советую начинать смотреть код с него.

class FractalShuffle {
private:
	unsigned int* positions;
	unsigned int power;
	string data;

	/*
	* Метод переставляет позиции в исходном векторе в обратном порядке:
	* 0, 1, 2, 3 -> 3, 2, 1, 0
	*/
	void setReversePositions(unsigned int sizeOfVector) {

		unsigned int swap;

		for (unsigned int i = 0; i < sizeOfVector / 2; i++){
			swap = positions[i];
			positions[i] = positions[sizeOfVector - i - 1];
			positions[sizeOfVector - i - 1] = swap;
		}
	}

	void recursiveShuffling(unsigned int startIndex, unsigned int atomSize) {

		string shuffledData;	//это будет перемешанная строка
		unsigned int size = atomSize - (atomSize % power);	//размер нашего кусочка 
						//("хвостик" справа останется неперемешанным)
		
		if (atomSize >= power){	//проверяем, можно ли выполнить перемешивание

			//atomSize - размер неделимой части строки, которая будем перемешиваться
			atomSize = size / power;	//не забываем его уменьшить

			for (unsigned int i = 0; i < power; i++){ 
				shuffledData.append(data,
 				startIndex + positions[i] * atomSize,
				atomSize);
				//по очереди добавляем куски строк в уже перемешанном порядке
				//(при помощи вектора positions), размер куска - atomSize
			}

			for (unsigned int i = 0; i < size; i++){
				data[startIndex + i] = shuffledData[i];
				//переносим перемешанную часть строки в исходную строку
			}

			shuffledData.clear();	//метод рекурсивный, 
				//потому не забываем следить за памятью

			//перемешаем кусочки поменьше
			for (unsigned int numberOfPart = 0; numberOfPart < power; numberOfPart++){
				//делим нашу часть строки на power кусочков
				//и вызываем для каждого из них рекурсивное перемешивание
				recursiveShuffling(startIndex + numberOfPart * atomSize, atomSize);
			}
		}
		
	}
public:
	FractalShuffle(){};

	~FractalShuffle(){};

	string shuffleString(string initialData, unsigned int _power) {

		if (_power <= 1){
			return initialData;
		}
		if (initialData.length() < _power){
			return initialData;
		}

		data = initialData; //на первый взгляд может показаться, что
		//исходная строка испортится. Но это не так.
		//Копируется вся строка, а не только ссылка.
		power = _power;

		positions = new unsigned int[power]; //вектор нового расположения

		for (unsigned int i = 0; i < power; i++){
			positions[i] = i; //исходный вектор имеет вид "0, 1, 2, 3..."
		}

		setReversePositions(power); //для примера перемешаем вектор в обратном порядке

		recursiveShuffling(0, data.length()); //перемешиваем, оставляя "хвостик" справа

		delete[] positions; //не забываем про отсутствие сборщика мусора в C++

		return data; //возвращаем перемешанную строку
	}
};

Вот как этот код работает:

«Hello_world!» для N = 2: dl!owrol_eHl
«Hello_world!» для N = 3: dlr!W_ooleHl
«Hello_world!» для N = 4: ld!worlo_Hel
«Hello_world!» для N = 8: ow_olleHrld!

Нюансы

Конечно же, некоторых мог смутить «хвостик» справа. Совсем несложно его перенести влево, но, например, для шифрования лучше этого не делать – ведь тогда почти всегда первые байты исходного сообщения останутся на своем месте, а это совсем нехорошо.
От «хвостика» можно избавиться разными способами – можно перемешивать вектор дважды (сначала с левым, а потом с правым «хвостиком»), либо же добавлять к хвостику «липовые» данные, чтобы вектор делился на N без остатка. Способов много, но лично мне «хвостик» не мешает (тем более что некоторые способы нарушают симметричность функции перемешивания).
Так же, алгоритм можно улучшить, если сделать его итерационным – можно выполнять перемешивание не в каждом перемешанном кусочке, а перемешивать весь вектор опять, но разделив уже на более мелкие части (увеличив N). Но тогда функция перемешивания уже точно не будет симметричной – придётся делать обход, начиная с маленьких частей и заканчивая большими.

Заключение

Наверняка не я первый в бредовом полусне придумал такой алгоритм. Но он мне понравился из-за своей простоты. Буду рад получить ссылки на него в комментариях!
Хочется закончить статью вопросом: а о чем Вы думаете перед сном?