就寝時の思考：フラクタル混合アルゴリズム

最近、この季節に初めて、私は田舎で夜を過ごし、異常な状況のために全く眠ることができませんでした。 そして、私の脳は急いでXOR暗号化について考えました。 結局のところ、それは非常に単純ですが、私はそれを改善する方法を考えました。 残念ながら、甘く眠りに落ちる代わりに、何らかの方法で元のデータをシャッフルすることを考えました。 そして、フラクタルミキシングのアイデアが思い浮かびました（そのため、4晩後に眠りに落ちました）。



アルゴリズムの本質は次のとおりです。ソースデータのベクトルを取得し、N個の等しい部分に分割します（ベクトルをNで除算しない場合、「テール」は単に左に残されますが、左にもできます）。 これらのN個の部分は、何らかの種類のシャッフルベクトルm [N]に従って混合されます（このアルゴリズムが暗号化に使用される場合、受信者にキーとして送信されます）。 混合後、元のベクトルの各部分はN個の等しい部分に均等に分割され、各部分の内部で同様の混合が実行されます。 それが可能になるまで何度も何度も起こります。



注目すべきこと-このアルゴリズムは再帰を使用して簡単に実装できますが、繰り返し実装することができます。 さらに、ミキシングアルゴリズムは対称です。つまり、元のデータベクトルを取得するには、同じベクトルm [N]で再度適用する必要があります。



ミキシングはミキシングの内部で行われるため、「フラクタル」という言葉はクールだからです。 そして、すぐにGoogleで検索しました（残念ながら、この国のモバイルインターネットは機能します）。 しかし、見つかりませんでした！ それから興奮の炎が私の目に輝いた。本当に新しくてシンプルなものを思いついたのか？ そのような考えの後、私は長い間眠ることができませんでした-しかし、私はミキシングアルゴリズムについてはあまり考えていませんでした。Habrに関する記事を書く方法について。

1週間後、すでに家にいたとき、怠を克服し、C ++コードを記述しました。これは、指定された文字列を指定された数値Nを使用してアルゴリズムと混合します。簡単にするために、データを後方に再配置するベクトルを使用しました。 しかし、もちろん、アルゴリズムは任意の混合ベクトル用に設計されています。

C ++コード

注： shuffleStringメソッドはmainで呼び出されます。そのコードを確認することをお勧めします。

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！

ニュアンス

もちろん、右側の「尻尾」に混乱する人もいます。 左に移動することは難しくありませんが、たとえば、暗号化のためにこれを行わないほうがよいでしょう。なぜなら、ほとんどの場合、元のメッセージの最初のバイトがその場所に残り、これは完全に悪いからです。

さまざまな方法で「テール」を取り除くことができます-ベクターを2回混合する（最初は左、次に右の「テール」）か、「偽」データをテールに追加して、ベクターがNで余りなく分割されるようにします。 多くの方法がありますが、「テール」は個人的には気にしません（特に、一部の方法はミキシング関数の対称性に違反するため）。

また、アルゴリズムを反復することで改善できます。各混合部分を混合することはできませんが、ベクトル全体を再度混合することはできますが、より小さい部分に分割します（Nを増やします）。 しかし、その後、ミキシング機能は間違いなく対称ではなくなります-小さな部分から始まり、大きな部分で終わる迂回をする必要があります。

おわりに

確かに、私はこのようなアルゴリズムを思いついた妄想的な半眠りの最初の人ではありませんでした。 しかし、私はそのシンプルさのためにそれが好きだった。 コメントでリンクを受け取ってうれしいです！

私は質問で記事を終了したいと思います：寝る前にあなたはどう思いますか？