Недавно я впервые в этом сезоне ночевал на даче и никак не мог уснуть из-за непривычной обстановки. И тогда мой мозг понесся думать про XOR-шифрование. Оно ведь довольно простое, а я думал, как можно его улучшить. К сожалению, вместо того, чтобы сладко уснуть, я додумался до того, что надо перетасовать исходные данные каким-нибудь образом. И тогда мне в голову пришла идея фрактального перемешивания (из-за которой я уснул после четырех ночи).
Суть алгоритма такова: берется вектор исходных данных и делится на N равных частей (если на N вектор не делится, то просто оставляется справа «хвостик», хотя можно и слева). Эти N частей перемешиваются согласно какому-то вектору перетасовки m[N] (который потом передается в качестве ключа получателю, если использовать этот алгоритм для шифрования). После перемешивания каждая часть исходного вектора делится точно так же на N равных частей, и внутри каждой части выполняется аналогичное перемешивание. Потом это происходит снова и снова, пока это будет возможно.
Что примечательно – этот алгоритм легко реализовать с помощью рекурсии, но можно реализовать его и итерационно. Кроме того, алгоритм перемешивания симметричный, то есть для получения исходного вектора данных надо применить его опять с тем же вектором m[N].
Когда я его придумал, я сразу же назвал его фрактальным, так как перемешивание происходит внутри перемешивания (да и слово «фрактал» классное). А ещё я сразу же полез искать его в Гугл (к счастью, мобильный интернет на даче работает). Но не нашел! Тогда в моих глазах загорелось пламя азарта – неужели я придумал что-то новое и простое? После таких мыслей я еще долго не мог уснуть – но я уже думал не столько об алгоритме перемешивания, сколько о том, как буду писать статью на Хабр.
Через неделю я, будучи уже дома, переборол свою лень и написал код на С++, который перемешивает заданную строку моим алгоритмом, используя заданное число N. Для простоты я использовал вектор, который переставляет данные задом наперед. Но, конечно же, алгоритм рассчитан на произвольный вектор перемешивания.
Примечание: В main вызывается метод shuffleString, советую начинать смотреть код с него.
Вот как этот код работает:
«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). Но тогда функция перемешивания уже точно не будет симметричной – придётся делать обход, начиная с маленьких частей и заканчивая большими.
Наверняка не я первый в бредовом полусне придумал такой алгоритм. Но он мне понравился из-за своей простоты. Буду рад получить ссылки на него в комментариях!
Хочется закончить статью вопросом: а о чем Вы думаете перед сном?
Суть алгоритма такова: берется вектор исходных данных и делится на 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). Но тогда функция перемешивания уже точно не будет симметричной – придётся делать обход, начиная с маленьких частей и заканчивая большими.
Заключение
Наверняка не я первый в бредовом полусне придумал такой алгоритм. Но он мне понравился из-за своей простоты. Буду рад получить ссылки на него в комментариях!
Хочется закончить статью вопросом: а о чем Вы думаете перед сном?
