33

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

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

明確にするために編集します。

  1. キーペアなしで操作を元に戻すことができるように、アルゴリズムは対称である必要があります。
  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つのものを変更すると、多くのことが変更される可能性があります。

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

4

11 に答える 11

34

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

このアイデアの2乗以外の範囲への拡張については、ブロック暗号を使用した安全な順列に関する私の投稿を参照してください。

特定の懸念に対処する：

  1. アルゴリズムは確かに対称的です。「キーペアなしで操作を逆にする」とはどういう意味かわかりません。キーを使用したくない場合は、ランダムに生成されたキーをハードコーディングし、それをアルゴリズムの一部と見なします。
  2. うん-定義上、ブロック暗号は全単射です。
  3. うん。そうでなければ、それは良い暗号ではないでしょう。
于 2010-07-01T08:45:36.760 に答える
6

これに対する私の解決策をもっと簡単な例で説明しようと思います。これは、大きな例に簡単に拡張できます。

私は4ビットの数字を持っているとしましょう。16の異なる値があります。それが4次元の立方体であるかのように見てください:(出典：ams.org） 。4次元キューブ

すべての頂点はそれらの数値の1つを表し、すべてのビットは1つの次元を表します。つまり、基本的にXYZWであり、各ディメンションの値は0または1のみです。ここで、異なる順序のディメンションを使用するとします。たとえば、XZYW。各頂点の数が変更されました。

これは、任意の数のディメンションに対して実行できます。それらのディメンションを並べ替えるだけです。セキュリティがあなたの関心事でないなら、これはあなたにとって素晴らしい速い解決策かもしれません。一方、出力がニーズに対して十分に「あいまい」であるかどうかはわかりません。また、大量のマッピングを行った後、マッピングを逆にすることができます（ニーズによっては長所と短所があります）。

于 2010-07-01T07:31:20.957 に答える
5

次のペーパーでは、4つまたは5つのマッピング例を示し、マップされたセットを作成するのではなく、関数を提供します。www.cs.auckland.ac.nz/~john-rugis/pdf/ BijectiveMapping.pdf

于 2010-07-01T08:14:43.450 に答える
5

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

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

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

そして、pが実際に素数である場合、これはすべてのa！=0とすべてのbの全単射になります。aとbが大きい場合は、かなりランダムに見えます。

たとえば、この質問に出くわした私の場合、1 << 30より小さい数の範囲の素数として、1073741789を使用しました。これにより、35の数しか失われません。これは、私の場合は問題ありません。

私のエンコーディングは

((n + 173741789) * 507371178) % 1073741789

デコードは

(n * 233233408 + 1073741789 - 173741789) % 1073741789

507371178 * 233233408％1073741789 == 1であるため、これら2つの数値は1073741789を法とする数値のフィールドの逆数になります（拡張ユークリッドアルゴリズムを使用すると、このようなフィールドの逆数を計算できます）。

私はaとbをかなり恣意的に選択しましたが、それらがpの約半分のサイズであることを確認しただけです。

于 2014-08-03T17:36:39.920 に答える
4

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

  • XOR
  • 対称ビット順列（たとえば、16ビットをシフトするか、0-31から31-0にフリップするか、0-3から3-0に、4-7から7-4にフリップするなど）
  • もっと？
于 2010-07-01T09:39:09.500 に答える
1

適切な暗号化アルゴリズムを使用したくない場合（おそらくパフォーマンスと複雑さの理由で）、代わりに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]));
}

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

于 2010-07-07T12:15:43.870 に答える
1

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

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

PS：それが重要な場合は、対称全単射ルックアップテーブルを生成できると思います。アルゴリズムは空のLUTから始まります。

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

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

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

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

于 2010-07-01T07:02:37.873 に答える
1

数を取り、9で乗算し、逆数の桁で、9で除算します。

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

十分に曖昧なはずです!!

編集：0で終わる整数の全単射ではありません

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
于 2010-07-01T08:07:03.833 に答える
1

これが私の簡単なアイデアです。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]0から30までの番号が付けられた31ビットが残っているためです。

これを説明するために、例を示します。

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を取ります。最初の（0から数えて）を取ります。残りのビット：

I: 0__1    O: 11__
   _

ここでも1つの数値をスキップし、14を取ります。14mod 2 = 0なので、0番目のビットを取ります。

I: ___1    O: 110_
      _

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

I: ____    O: 1101

そして、これはそれです。

そのような数を解読するのは簡単です、人はただ同じことをしなければなりません。コードの最初のビットを配置する位置はキーからわかり、次の位置は前に挿入されたビットによって決定されます。

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

于 2010-07-01T10:11:34.560 に答える
0

大きな紙に大きな円を描きます。0からMAXINTまでのすべての整数を、円の上部から時計回りに等間隔で書き込みます。0からMININTまでのすべての整数を反時計回りに、再び等間隔で書き込みます。MININTが円の下部にあるMAXINTの隣にあることを確認します。次に、硬いカードの両面にこの図の複製を作成します。硬いカードを両方の中心を通る円に固定します。回転角を好きな角度で選んでください。これで、いくつかの要件を満たす1-1マッピングができましたが、おそらく十分に曖昧ではありません。カードのピンを外し、直径、任意の直径の周りに裏返します。満足のいく全単射が得られるまで、これらの手順を（任意の順序で）繰り返します。

あなたが綿密にフォローしているなら、あなたの好みの言語でこれをプログラムすることは難しいことではないはずです。

コメントに続く明確化のために：あなたが紙に対してカードを回転させるだけなら、方法はあなたが不平を言うのと同じくらい簡単です。ただし、カードを裏返すと、マッピングは(x+m) mod MAXINTどのに相当するものではありませんm。たとえば、カードを回転させずに、直径を0（文字盤の上部にある）で裏返すと、1は-1、2、-2などにマップされます。 (x+m) mod MAXINTカードの回転のみに対応します。

于 2010-06-28T09:51:46.503 に答える
0

数値を2つに分割し（最上位16ビットと最下位16ビット）、2つの16ビット結果のビットを2つのデッキのカードと見なします。デッキを混ぜ合わせて、一方を他方に押し込みます。

したがって、最初の番号がであるb31,b30,...,b1,b0場合は、で終わりますb15,b31,b14,b30,...,b1,b17,b0,b16。逆の場合と同様に、実装は迅速かつ迅速です。

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

0->maxvalueおよびmaxvalue->0を手動でマップして、それらが自分自身にマップされないようにすることができます。

于 2010-07-06T22:36:25.877 に答える