Недавно я впервые в этом сезоне ночевал на даче и никак не мог уснуть из-за непривычной обстановки. И тогда мой понесся думать про 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). Но тогда функция перемешивания уже точно не будет симметричной – придётся делать обход, начиная с маленьких частей и заканчивая большими.
Заключение
Наверняка не я первый в бредовом полусне придумал такой алгоритм. Но он мне понравился из-за своей простоты. Буду рад получить ссылки на него в комментариях!
Хочется закончить статью вопросом: а о чем Вы думаете перед сном?
Автор: Odd_Wanderer
