整数の対称生物アルゴリズム

StackOverflow https://stackoverflow.com/questions/3131193

質問

32ビットの署名された整数の1対1のマッピング（つまり、衝突なし）を別の32ビット署名整数に実行できるアルゴリズムが必要です。

私の本当の懸念は、関数の出力がランダムに見えるように、十分なエントロピーであることです。基本的に、私はXor暗号に似た暗号を探していますが、それはより任意の外観の出力を生成することができます。あいまいさはあいまいですが、セキュリティは私の本当の関心事ではありません。

明確化のために編集：

  1. アルゴリズム しなければならない keypairなしで操作を逆転させることができるように、対称にしてください。
  2. アルゴリズム しなければならない 32ビットの入力番号ごとに、32ビットの一意の数値を生成する必要があります。
  3. 関数の出力は十分に不明瞭でなければなりません。入力に1つだけを追加すると、出力に大きな影響があります。

予想される結果の例：

F（100）= 98456
F（101）= -758
F（102）= 10875498
F（103）= 986541
F（104）= 945451245
F（105）= -488554

MD5と同じように、1つのことを変更すると、多くのことが変わる可能性があります。

私は数学的な機能を探しているので、手動で整数をマッピングすることは私にとって解決策ではありません。尋ねている人にとって、アルゴリズムの速度はそれほど重要ではありません。

役に立ちましたか？

解決

32ビットブロック暗号を使用してください！定義上、ブロック暗号は、その範囲内のあらゆる可能な入力値を一意の出力値、可逆的な方法でマッピングし、設計上、特定の値がキーなしで何をマッピングするかを判断することは困難です。キーを選ぶだけで、セキュリティや不明瞭さが重要な場合は秘密にしてください。また、変換として暗号を使用してください。

このアイデアを2つの範囲に拡張するには、私の投稿を参照してください ブロック暗号で順列を固定します.

特定の懸念に対処する：

  1. アルゴリズムは実際に対称です。 「キーペアなしで操作を逆転させる」とはどういう意味かわかりません。キーを使用したくない場合は、ハードコードをランダムに生成したものをハードコードし、アルゴリズムの一部を検討してください。
  2. YUP-定義上、ブロック暗号は生物物です。
  3. うん。そうでなければ、それは良い暗号ではないでしょう。

他のヒント

私はこれに対する私の解決策をはるかに単純な例で説明しようとします。

4ビット番号があるとします。 16個の異なる値があります。それを4次元のキューブであるかのように見てください： 4 dimensional cube
（ソース： ams.org)
.

すべての頂点はこれらの数値の1つを表し、すべてのビットは1つの次元を表します。したがって、その基本的なxyzw。各寸法には0または1のみが値を持つことができます。 別の順序 寸法の。たとえば、xzyw。頂点のそれぞれがその数を変更しました！

これを任意の数の次元で行うことができます。これらの次元を並べ替えるだけです。セキュリティがあなたの懸念でない場合、これはあなたにとって素晴らしい速い解決策かもしれません。一方、出力があなたのニーズに十分に「不明瞭」になるかどうかはわかりません。確かに大量のマッピングが行われた後、マッピングを逆にすることができます（ニーズに応じて、これは利点または不利な点です。）

次の論文では、4つまたは5つのマッピングの例を示し、マッピングされたセットを構築するのではなく機能を提供します。 www.cs.auckland.ac.nz/~john-rugis/pdf/bijectivemapping.pdf

ランダムルックアップテーブルの生成とは別に、関数の組み合わせを使用できます。

  • xor
  • 対称ビット順列（たとえば、16ビットをシフトするか、0-31から31-0をフリップするか、0-3から3-0、4-7〜7-4などをフリップします）
  • もっと？

あなたの目標が単に数の一見ランダムな順列を取得することである場合 だいたい 定義されたサイズ、次に、別の可能な方法があります。数字のセットを素数に減らします。

次に、フォームのマッピングを使用できます

f（i）=（i * a + b）％p

そして、Pが実際にプライムである場合、これはすべてのa！= 0およびすべてのbの偏りになります。より大きなaとbの場合、かなりランダムに見えます。

たとえば、私がこの質問に出くわした私の場合、私は1073741789を1 << 30を超える数字の範囲のプライムとして使用しました。

私のエンコードはそうです

((n + 173741789) * 507371178) % 1073741789

そして、デコードはです

(n * 233233408 + 1073741789 - 173741789) % 1073741789

507371178 * 233233408％1073741789 == 1であるため、これらの2つの数値は数値モジュロ1073741789の逆であることに注意してください（そのようなフィールドでは、拡張ユークリッドアルゴリズムと逆数を把握できます）。

私はAとBをかなりarbitrarily意的に選びましたが、Pの約半分のサイズがあることを確認しました。

ランダムに生成されたルックアップテーブルを使用できますか？テーブル内の乱数が一意である限り、生物多数のマッピングを取得します。しかし、それは対称ではありません。

32ビット値すべての16 GBルックアップテーブルはおそらく実用的ではありませんが、ハイワードと低い単語に2つの個別の16ビットルックアップテーブルを使用できます。

PS：それが重要であれば、対称的な生物のルックアップテーブルを生成できると思います。アルゴリズムは、空のlutで始まります。

+----+        +----+
|  1 |   ->   |    |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |    |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

最初の要素を選択し、ランダムマッピングを割り当てます。マッピングを対称にするには、逆も割り当てます。

+----+        +----+
|  1 |   ->   |  3 |
+----+        +----+
|  2 |   ->   |    |
+----+        +----+
|  3 |   ->   |  1 |
+----+        +----+
|  4 |   ->   |    |
+----+        +----+

次の番号を選択して、もう一度ランダムマッピングを割り当てますが、まだ割り当てられていない番号を選択します。 （つまり、この場合、1または3を選択しないでください）。 LUTが完了するまで繰り返します。これにより、ランダムな生物の対称マッピングが生成されるはずです。

数字を取得し、9を掛け、逆数桁を、9で除算します。

123  <> 1107 <> 7011 <> 779
256  <> 2304 <> 4032 <> 448
1028 <> 9252 <> 2529 <> 281

十分に不明瞭でなければなりません!!

編集：それは0の終了整数のbijectionではありません

900 <> 8100 <> 18 <> 2
2   <> 18   <> 81 <> 9

次のような特定のルールをいつでも追加できます。数字を取得し、10 x時間を割って、9、逆数桁、9、倍数を10^xで除算します。

など 

900 <> 9 <> 81 <> 18 <> 2 <> 200
200 <> 2 <> 18 <> 81 <> 9 <> 900

w00tそれは動作します！

編集2：あいまいさを増やすために、任意の数字を追加して、最後にサブトレストすることができます。

900 < +256 > 1156 < *9 > 10404 < invert > 40401 < /9 > 4489 < -256 > 4233
123 < +256 > 379 < *9 > 3411 < invert > 1143 < /9 > 127 < -256 > -129

私の簡単なアイデアは次のとおりです。Peterkが提案したように、数のビットを動き回ることができますが、各数値のビットの異なる順列を持つことができ、それでも解読することができます。

暗号は次のようになります：入力番号をビットの配列として扱う I[0..31], 、および出力として O[0..31]。配列を準備します K[0..63] 64のランダムに生成された数値の。これがあなたの鍵になります。最初の乱数によって決定された位置から入力数のビットを取得します（I[K[0] mod 32]）そして、結果の先頭にそれを置きます（O[0]）。現在、どのビットを配置するかを決定します O[1], 、以前に使用したビットを使用します。 0の場合は、k [1]を使用してで位置を生成します I そこから、それは1、k [2]を使用します（これは単に1つの乱数をスキップすることを意味します）。

同じビットを2回取ることができるので、これはうまく機能しません。それを避けるために、反復ごとにビットを変更し、使用済みビットを省略します。取るべき位置を生成する O[1] 使用する I[K[p] mod 31], 、ビットに応じて、pは1または2です O[0], 、残り31ビットがあり、0から30の数字です。

これを説明するために、例を挙げてください。

4ビット数と8つの乱数があります：25、5、28、19、14、20、0、18。

I: 0111    O: ____
    _

25 mod 4 = 1なので、ポジションが1（0からカウント）のビットを取ります

I: 0_11    O: 1___
     _

ちょっとした値1を取ったばかりなので、1つの乱数をスキップして28を使用します。残り3ビットがあります。位置をカウントするには、28 mod 3 = 1を取得します。残りのビット：

I: 0__1    O: 11__
   _

繰り返しますが、1つの数字をスキップして、14を取得します。14mod 2 = 0では、0番目のビットを取得します。

I: ___1    O: 110_
      _

今では問題ではありませんが、前のビットは0だったので、20を取得します。20mod1 = 0：

I: ____    O: 1101

そして、これです。

そのような数字を解読するのは簡単です。同じことをする必要があります。コードの最初のビットをキーから配置する位置は、キーから知られています。次の位置は、以前に挿入されたビットによって決定されます。

これには明らかに、ビットを移動するだけのすべての欠点があります（たとえば、0は0になり、maxintはmaxintになります）が、秘密でなければならないキーを知らずに誰かが数字を暗号化した方法を見つけるのは難しいようです。

適切な暗号化アルゴリズムを使用したくない場合（おそらくパフォーマンスと複雑さの理由で）、代わりに、よりシンプルな暗号を使用できます。 Vigenère暗号. 。この暗号は実際にとして説明されていました Le ChiffreIndéchifFrable （「壊れない暗号」のフランス語）。

対応するキー値に基づいて値をシフトする単純なC＃実装は次のとおりです。

void Main()
{
  var clearText = Enumerable.Range(0, 10);
  var key = new[] { 10, 20, Int32.MaxValue };
  var cipherText = Encode(clearText, key);
  var clearText2 = Decode(cipherText, key);
}

IEnumerable<Int32> Encode(IEnumerable<Int32> clearText, IList<Int32> key) {
  return clearText.Select((i, n) => unchecked(i + key[n%key.Count]));
}

IEnumerable<Int32> Decode(IEnumerable<Int32> cipherText, IList<Int32> key) {
  return cipherText.Select((i, n) => unchecked(i - key[n%key.Count]));
}

このアルゴリズムは、入力がわずかに変更されたときに出力に大きなシフトを作成しません。ただし、それを達成するために追加する代わりに別の生物操作を使用できます。

大きな紙の上に大きな円を描きます。すべての整数を0からmaxintから時計回りに、円の上部から書き込み、等間隔です。すべての整数を0からミニント反時計回りに書き込み、再び間隔を空けます。 Minintが円の下部にあるMaxintの隣にあることを観察してください。ここで、硬いカードの両側にこの図を複製します。硬いカードを両方の中心を介して円にピン留めします。回転角、好きな角度を選択します。これで、要件の一部を満たす1-1マッピングがありますが、おそらく十分に不明瞭ではありません。カードを取り外して、直径、任意の直径の周りにひっくり返します。あなたが満足しているbijectionができるまで（任意の順序で）これらの手順を繰り返します。

あなたが密接にフォローしている場合、これをあなたの好みの言語でプログラムすることは難しいことではありません。

明確にするために コメントに従ってください：ペーパーに対してカードを回転させるだけの場合、この方法は不平を言うのと同じくらい簡単です。ただし、マッピングの上にカードをひっくり返すと、 (x+m) mod MAXINT どちらのために m. 。たとえば、カードを無口で残し、0（クロック面の上部にある）から直径の周りにひっくり返すと、1は-1、2から-2などにマッピングされます。 (x+m) mod MAXINT カードの回転のみに対応します。

数を2つ（16の最も重要なビットと16個の最低ビット）で分割し、2つの16ビット結果のビットを2つのデッキのカードとして考慮します。一方を強制するデッキをもう一方に混ぜます。

したがって、初期番号がそうである場合 b31,b30,...,b1,b0 あなたは終わります b15,b31,b14,b30,...,b1,b17,b0,b16. 。逆のように、それは速くて迅速です。

結果の10進表現を見ると、シリーズはかなりあいまいに見えます。

0-> maxValueとmaxValue-> 0を手動でマッピングして、それらをマッピングしないようにすることができます。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top