Thoughts before bed: fractal mixing algorithm
Recently, for the first time this season, I spent the night in the country and could not fall asleep due to the unusual situation. And then my brain rushed to think about XOR-encryption. It's quite simple, but I was thinking how to improve it. Unfortunately, instead of falling asleep sweetly, I thought of shaking the source data in some way. And then the idea of ​​fractal mixing came to my mind (because of which I fell asleep after four nights).
The essence of the algorithm is as follows: the source data vector is taken and divided into N equal parts (if the vector is not divided into N, then the tail is left on the right, although it can be left). These N parts are shuffled according to some vector of shuffle m [N] (which is then transmitted as a key to the recipient, if you use this algorithm for encryption). After mixing, each part of the original vector is divided in the same way into N equal parts, and similar mixing is performed inside each part. Then it happens again and again until it is possible.
What is remarkable is that this algorithm is easy to implement using recursion, but you can also implement it iteratively. In addition, the mixing algorithm is symmetric, that is, to obtain the original data vector, it is necessary to apply it again with the same vector m [N].
When I came up with it, I immediately called it fractal, since the mixing takes place inside the mixing (and the word “fractal” is cool). And I immediately got to look for it in Google (fortunately, the mobile Internet in the country works). But did not find! Then, in my eyes, the flame of excitement caught fire - did I come up with something new and simple? After such thoughts, I could not fall asleep for a long time - but I was not thinking so much about the mixing algorithm, but about how I would write an article on Habr.
A week later, while I was already at home, I overcame my laziness and wrote C ++ code that mixes the given string with my algorithm using the given number N. For simplicity, I used a vector that rearranges the data backwards. But, of course, the algorithm is designed for an arbitrary mixing vector.
')
Note: The main method calls shuffleString , I advise you to start watching the code from it.
Here is how this code works:
“Hello_world!” For N = 2: dl! Owrol_eHl
“Hello_world!” For N = 3: dlr! W_ooleHl
“Hello_world!” For N = 4: ld! Worlo_Hel
“Hello_world!” For N = 8: ow_olleHrld!
Of course, some could confuse the "tail" on the right. It is not difficult to transfer it to the left, but, for example, it is better not to do this for encryption - in fact, then almost always the first bytes of the original message will remain in place, and this is not at all good.
You can get rid of the “tail” in different ways - you can mix the vector twice (first with the left, and then with the right “tail”), or you can add “fake” data to the tail so that the vector is divided by N without a residue. There are many ways, but personally the “tail” does not bother me (all the more so because some methods violate the symmetry of the mixing function).
Also, the algorithm can be improved if we make it iterative — it is possible to perform mixing not in each mixed piece, but to mix the whole vector again, but by dividing it into smaller parts (increasing N). But then the mixing function will definitely not be symmetrical - you will have to make a detour, starting with small parts and ending with large ones.
Surely it was not me who first came up with such an algorithm in a crazy dream. But I liked it because of its simplicity. I would be happy to receive links to it in the comments!
I want to finish the article with a question: what do you think about before going to bed?
The essence of the algorithm is as follows: the source data vector is taken and divided into N equal parts (if the vector is not divided into N, then the tail is left on the right, although it can be left). These N parts are shuffled according to some vector of shuffle m [N] (which is then transmitted as a key to the recipient, if you use this algorithm for encryption). After mixing, each part of the original vector is divided in the same way into N equal parts, and similar mixing is performed inside each part. Then it happens again and again until it is possible.
What is remarkable is that this algorithm is easy to implement using recursion, but you can also implement it iteratively. In addition, the mixing algorithm is symmetric, that is, to obtain the original data vector, it is necessary to apply it again with the same vector m [N].
When I came up with it, I immediately called it fractal, since the mixing takes place inside the mixing (and the word “fractal” is cool). And I immediately got to look for it in Google (fortunately, the mobile Internet in the country works). But did not find! Then, in my eyes, the flame of excitement caught fire - did I come up with something new and simple? After such thoughts, I could not fall asleep for a long time - but I was not thinking so much about the mixing algorithm, but about how I would write an article on Habr.
A week later, while I was already at home, I overcame my laziness and wrote C ++ code that mixes the given string with my algorithm using the given number N. For simplicity, I used a vector that rearranges the data backwards. But, of course, the algorithm is designed for an arbitrary mixing vector.
')
C ++ Code
Note: The main method calls shuffleString , I advise you to start watching the code from it.
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; // } }; Here is how this code works:
“Hello_world!” For N = 2: dl! Owrol_eHl
“Hello_world!” For N = 3: dlr! W_ooleHl
“Hello_world!” For N = 4: ld! Worlo_Hel
“Hello_world!” For N = 8: ow_olleHrld!
Nuances
Of course, some could confuse the "tail" on the right. It is not difficult to transfer it to the left, but, for example, it is better not to do this for encryption - in fact, then almost always the first bytes of the original message will remain in place, and this is not at all good.
You can get rid of the “tail” in different ways - you can mix the vector twice (first with the left, and then with the right “tail”), or you can add “fake” data to the tail so that the vector is divided by N without a residue. There are many ways, but personally the “tail” does not bother me (all the more so because some methods violate the symmetry of the mixing function).
Also, the algorithm can be improved if we make it iterative — it is possible to perform mixing not in each mixed piece, but to mix the whole vector again, but by dividing it into smaller parts (increasing N). But then the mixing function will definitely not be symmetrical - you will have to make a detour, starting with small parts and ending with large ones.
Conclusion
Surely it was not me who first came up with such an algorithm in a crazy dream. But I liked it because of its simplicity. I would be happy to receive links to it in the comments!
I want to finish the article with a question: what do you think about before going to bed?
Source: https://habr.com/ru/post/146583/
All Articles